Robert Crowston

Hello! I recently completed my PhD at Royal Holloway, supervised by Professor Gutin.

Before this I obtained a BA and CASM in Mathematics at Peterhouse, University of Cambridge

This is my academic website. For my personal website, see here.

I can be found on: Google Scholar | DBLP | arXiv | Royal Holloway Website

Journal Publications

Note on Max Lin-2 above Average
Robert Crowston, Gregory Gutin, Mark Jones
Information Processing Letters, Volume 110, Issue 11, 16 May 2010, Pages 451-454.
arXiv preprint | Google Scholar
A New Lower Bound on the Maximum Number of Satisfied Clauses in Max-SAT and Its Algorithmic Applications
Robert Crowston, Gregory Gutin, Mark Jones, Anders Yeo
Algorithmica September 2012, Volume 64, Issue 1, pp 56-68
arXiv preprint | Google Scholar
A preliminary version of this paper appeared in the Proceedings of IPEC 2010
IPEC 2010 Proceedings: Lecture Notes in Computer Science Volume 6478, 2010, pp 84-94
Parameterized Eulerian Strong Component Arc Deletion Problem on Tournaments
Robert Crowston, Gregory Gutin, Mark Jones, Anders Yeo
Information Processing Letters, Volume 112, Issue 6, 15 March 2012, Pages 249-251
arXiv preprint | Google Scholar
Parameterized Complexity of Satisfying Almost All Linear Equations over F_2
Robert Crowston, Gregory Gutin, Mark Jones, Anders Yeo
Theory of Computing Systems, June 2012
arXiv preprint | Google Scholar
Fixed-parameter tractability of satisfying beyond the number of variables
Robert Crowston, Gregory Gutin, Mark Jones, Venkatesh Raman, Saket Saurabh, Anders Yeo
Algorithmica, October 2012
Google Scholar
A preliminary version of this paper appeared in the Proceedings of SAT 2012
SAT 2012 Proceedings: Lecture Notes in Computer Science Volume 7317, 2012, pp 355-368
Parameterized Complexity of MaxSat Above Average
Robert Crowston, Gregory Gutin, Mark Jones, Venkatesh Raman, Saket Saurabh
Theoretical Computer Science, January 2013
arXiv preprint | Google Scholar
A preliminary version of this paper appeared in the Proceedings of LATIN 2012
LATIN 2012 Proceedings: Lecture Notes in Computer Science Volume 7256, 2012, pp 184-194
Satisfying more than half of a system of linear equations over GF(2): A multivariate approach
R. Crowston, M. Fellows, G. Gutin, M. Jones, E.J. Kim, F. Rosamond, I.Z. Ruzsa, S. Thomassé, A. Yeo.
Journal of Computer and System Sciences, October 2013.
Google Scholar
Maximum Balanced Subgraph Problem Parameterized Above Lower Bound
R. Crowston, G. Gutin, M. Jones, G. Muciaccia.
Theoretical Computer Science, November 2013.
arXiv preprint | Google Scholar
A preliminary version of this paper appeared in the Proceedings of COCOON 2013
COCOON 2013 Proceedings: Lecture Notes in Computer Science Volume 7936, 2013, pp 434-445

Conference Publications

Systems of Linear Equations over F_2 and Problems Parameterized Above Average
Robert Crowston, Gregory Gutin, Mark Jones, Eun Jung Kim, Imre Z. Ruzsa
SWAT 2010 Proceedings: Lecture Notes in Computer Science Volume 6139, 2010, pp 164-175
arXiv preprint | Google Scholar
Simultaneously Satisfying Linear Equations Over F_2: MaxLin2 and Max-r-Lin2 Parameterized Above Average
Robert Crowston, Michael Fellows, Gregory Gutin, Mark Jones, Frances Rosamond, Stéphan Thomassé, Anders Yeo
FSTTCS 2011 Proceedings: Leibniz International Proceedings in Informatics Volume 13, 2011, pp 229-240
arXiv preprint | Google Scholar
Max-Cut Parameterized Above the Edwards-Erdös Bound
Robert Crowston, Mark Jones, Matthias Mnich
ICALP 2012 Proceedings: Lecture Notes in Computer Science Volume 7391, 2012, pp 242-253
arXiv preprint | Google Scholar
Parameterized Study of the Test Cover Problem
Robert Crowston, Gregory Gutin, Mark Jones, Saket Saurabh, Anders Yeo
MFCS 2012 Proceedings: Lecture Notes in Computer Science Volume 7464, 2012, pp 283-295
Google Scholar
Directed Acyclic Subgraph Problem Parameterized above the Poljak-Turzík Bound
Robert Crowston, Gregory Gutin, Mark Jones
FSTTCS 2012 Proceedings: Leibniz International Proceedings in Informatics Volume 18, 2012, pp 400-411
arXiv preprint | Google Scholar
Fixed-Parameter Tractability of Workflow Satisfiability in the Presence of Seniority Constraints
J. Crampton, R. Crowston, G. Gutin, M. Jones, M. S. Ramanujan
FAW-AAIM 2013 Proceedings: Lecture Notes in Computer Science Volume 7924, 2013, pp 198-209
arXiv preprint | Google Scholar

ArXiV Preprints

Parameterizations of Test Cover with Bounded Test Sizes
Robert Crowston, Gregory Gutin, Mark Jones, Gabriele Muciaccia, Anders Yeo
Submitted
Google Scholar

Conference/Workshop Attendance

  1. 2 June 2010, Royal Holloway, University of London: Computer Science Postgraduate Colloquium 2010 (contributed talk)
  2. 26-28 July 2010, King's College London: 21st International Workshop on Combinatorial Algorithms (IWOCA 2010) (participant)
  3. 20-22 September 2010, Durham: Algorithms and Complexity in Durham 2010 (ACiD 2010) (participant)
  4. 8-12 November 2010, Lorentz Center, Leiden: WorKer 2010: Workshop on Kernelization (participant)
  5. 1 June 2011, Royal Holloway, University of London: Computer Science Postgraduate Colloquium 2011 (contributed talk)
  6. 7-9 July 2011, Saarbrucken, Germany: 6th International Symposium on Parameterized and Exact Computation (IPEC 2011) (participant)
  7. 2-4 September 2011, Vienna University of Technology: WorKer 2011: The Third Workshop on Kernelization (contributed talk)
  8. 12-14 December 2011, Mumbai, India: Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011) (talk: presenting paper)
  9. 17-20 December 2011, Chennai, India: Recent Advances in Data Structures Workshop (participant)
  10. 28-29 February 2012, Paris, France: International Workshop on Approximation, Parameterized and EXact algorithms (APEX 2012) (participant)
  11. 16-17 May 2012, QMUL and LSE, London: Two One-Day Colloquia in Combinatorics 2012 (participant)
  12. 30 May 2012, Royal Holloway, University of London: Computer Science Postgraduate Colloquium 2012 (contributed talk)
  13. 8 July 2012, Warwick: Workshop on Applications of Parameterized Algorithms and Complexity (APAC 2012) (participant)
  14. 15-17 August 2012, Warwick: 22nd Postgraduate Combinatorial Conference (contributed talk)
  15. 27-31 August 2012, Bratislava, Slovakia: Mathematical Foundations of Computer Science (MFCS 2012) (talk: presenting paper)
  16. 10-21 December 2012, Chennai, India: Visit IMSc

Talks

On 2nd June 2010, I gave a talk at the Department Postgraduate Colloquium: "Unit-Conflict-Free Max-Sat Paramaterized Above Expectation". You can view the slides, or look at the paper which contains the results above.