Páidí CreedSchool of Mathematical Sciences
Queen Mary, University of London
Mile End, London,
I am currently post-doctoral research assistant in the School of Mathematical Sciences at Queen Mary, University of London, where I am investigating complexity of computational counting with Mark Jerrum.
I graduated from University College Cork, Ireland with a degree in Computer Science in 2004. Following that I spent a year at the University of St. Andrews in Scotland studying mathematics before coming to Edinburgh to study for a PhD under the supervision of Mary Cryan. Following my PhD I spent two years working as a research assistant for Dave Cohen in the Computer Science department of Royal Holloway, University of London. During this time I was a member of the Oxford/Royal Holloway Constraints Research Group, and I continue to work closely with some members of the group.
During my time at Cork I worked with James Little, Ken Brown, and Gene Freuder of the Cork Constraint Computation Centre, and with Michel Schellekens and Marc van Dongen of the Centre for Efficiency Oriented Languages.
I am a member of the European Association for Theoretical Computer Science and an active member of the Computing at Schools working group, an association promoting the teaching of Computer Science in UK schools. I occasionally post to twitter as @paidicreed.
ResearchMy research interests lie broadly in the area of Algorithms and Complexity. I am currently interested in the the computational complexity of counting problems and valued constraint languages, linear and semi-definite relaxations of VCSPs, structural complexity of constraint satisfaction problems, fixed-parameter algorithms, approximation algorithms (optimisation and counting), randomized algorithms for sampling and counting, combinatorial enumeration, and random graphs.
TeachingQueen Mary: Algebraic Structures (Tutor, Spring 2012)
University of Notre Dame: Data Structures (Lecturer, Autumn 2011)
University of Edinburgh: Data Structures and Algorithms (Teaching Assistant, Spring 2006,2007)
The number of Eulerian orientations of a random regular graph.
Páidí Creed and Mary Cryan.
The number of Euler tours of a random directed graph.
Páidí Creed and Mary Cryan.
The tractability of Hybrid CSP classes defined by binary forbidden
David A. Cohen, Martin C. Cooper, Páidí Creed, Daniel Márx, and Andras Sálamon.
Earlier version on [arXiv].
Sampling Eulerian orientations of the triangular lattice graphs
Journal of Discrete Algorithms, 7(2), pages 168-180, 2009.
[pdf] [doi] [arXiv]
A preliminary version of this work appeared as an extended abstract in Proceedings of ACiD 2006: the 2nd Algorithms and Complexity in Durham workshop Texts in Algorithmics, College Publications, 2006.
On minimal weighted clones.
Páidí Creed and Stanislav Živný
Proceedings of the 17th International Conference on Principles and Practice of Constraint Programming (CP'11), LNCS, 2011.
Algebraic Theory of Complexity for Valued Constraints: Establishing a Galois
David A. Cohen, Páidí Creed, Peter G. Jeavons, and Stanislav Živný.
Proceedings of the 36th International Symposium on Mathematical Foundations of Computer Science (MFCS'11), LNCS, 2011.
Also available as Oxford University Computing Laboratory RR-10-16.
The number of Euler tours of a random d-in/d-out graph
Páidí Creed and Mary Cryan.
Proceedings of 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms, Vienna, Austria, 2010.
Thermal Test Scheduling Using Constraint Programming
Little J., Goyal S., Creed P., Berry S., Cokely D.
Proceedings of INCOM 2006, Saint-Etienne, France, 2006.
Received award for being one of the best industrial papers presented at the conference.
Adversarial Constraint Satisfaction by Game-tree Search
Kenneth N. Brown, James Little, Páidí J. Creed and Eugene. C. Freuder
Proceedings ECAI 2004, Valencia, Spain, pages 151-155, 2004.
Named as one of the 11 best papers accepted to the conference.
An earlier version of this paper appeared with the title Game based CSPs, in Proc. 2nd Intl Workshop on Multiparadigm Constraint Programming Languages at CP 2003, Kinsale, Ireland.
Counting and Sampling Problems on Eulerian Graphs
Doctoral thesis, School of Informatics, University of Edinburgh, 2010.
Supervisor: Dr. Mary Cryan
[ pdf ]
Generating Functions and their application to the Average-Case Time
Complexity Analysis of Algorithms
Undergraduate thesis, Department of Computer Science, University College Cork, 2004.
Supervisors: Prof. Michel Schellekens, Dr. Marc van Dongen
Available as a CEOL technical report.
Events I have attended or will be attending
- CP 2011, Perugia, Italy. (12-16 September, 2011)
- Workshop on Algebra and CSPs, Fields Institute, Toronto, Canada. (August 2-6, 2011)
- BCC 23, University of Exeter, UK. (4-8 July, 2011)
- CP 2010, St Andrews
- International Workshop on Tractability, Microsoft Research, Cambridge, UK
- Analysis of Algorithms 2010, Vienna
- EIDMA mini-course on Algebraic Optimization and Semidefinite Programming, Amsterdam
- BCTCS 2010, Edinburgh
- CP 2009, Lisbon
- BCTCS 2009, Warwick
- Bristol Summer School on Probabilistic Techniques in Theoretical Computer Science, Bristol
- New Algorithmic Paradigms in Optimization, Summer School in Ascona, Switzerland
- Markov-Chain Monte Carlo Methods, Cambridge
- ICMS Workshop on Geometry and Algorithms in Heriot-Watt University, Edinburgh.
- ACiD'06 in Durham.
- LMS/EPSRC Short Course on Stochastic Stability, Large Deviations, and Coupling methods in Heriot-Watt University, Edinburgh.
- BCTCS 2006 in Swansea.
Blogs, news, and opinions from Maths and TCS
- All you need to know from the world of Computational Complexity, courtesy of Lance Fortnow.
- The irreverent opinions of Doron Zeilberger.
- Scott Aaronson is Shtetl-Optimized.
- Luca Trevisan, In Theory.
- Richard Lipton has many detailed posts on a variety of math/TCS topics.
- Theorem of the Day.
- Algorithms Reading Group
- Lists of conferences and events are maintained by CDAM, Tom Friedetzky, and Mohammad Farshi.
- Seminars: QMUL Combinatorics, QMUL Pure Mathematics, LSE.
- TCS cheat sheet
- Some useful concentration of measure inequalities
- Computational complexity texts available online by Oded Goldreich and Sanjeev Arora & Boaz Barak.
- Ian Parberry's useful guides.