Activities in the Foundations of Computer Science Group

DIMAP

The Foundations of Computer Science (FoCS) Research Group is one of the research groups in the Department of Computer Science at the University of Warwick, one of the leading Computer Science departments in the United Kingdom. It is also one of the core groups affiliated with the interdisciplinary Centre for Discrete Mathematics and its Applications (DIMAP) at the University of Warwick.

Recent Prizes and Awards

Harry Räcke is a co-winner of the Best Paper STOC'2008 award for his paper "Optimal hierarchical decompositions for congestion minimization in networks" (see the abstract for more details about this excellent paper).
The 40th STOC'2008 conference, held in May 17-20, 2008 in Victoria, Canada, is one of the two most prestigious conferences in Theoretical Computer Science. The main criterion for selection is the same as for being a top-rated paper in STOC: introduction of a strong new technique, solution of a long-standing open problem, or introduction and solution of an interesting and important new problem.

This is Harry's second best paper award on STOC/FOCS; in FOCS'2002, he was a sole winner of the best paper award and the winner of the best student paper award for his breakthrough paper "Minimizing congestion in general networks."
Amin Coja-Oghlan was awarded the EATCS Award for the Best Paper in Track A at the 36th International Colloquium on Automata, Languages and Programming (ICALP 2009) for his paper »A better algorithm for random k-SAT«.
EATCS Distinguished Award 2006: In recognition of his outstanding scientific contributions to Theoretical Computer Science, Mike Paterson received the EATCS Distinguished Award 2006. The award was presented to Mike by the European Association for Theoretical Computer Science during the ICALP 2006 conference in Venice, July 2006, to acknowledged his »extensive and widely recognised contributions to theoretical computer science over a life long scientific career«.
Mike Paterson was awarded the EATCS Award for the Best Paper in Track A at the 33rd International Colloquium on Automata, Languages and Programming (ICALP 2006) for his paper (co-authored by Martin Dyer (University of Leeds) and Leslie Ann Goldberg (University of Liverpool)) »On counting homomorphisms to directed acyclic graphs«.
The Mathematical Association of America has awarded Mike Paterson and his collaborator Uri Zwick the Lester R. Ford Award for their article Overhang in the American Mathematical Monthly. The problem of how far off the edge of a table one can reach by stacking n identical blocks first appeared in the American Mathematical Monthly in 1923. A classical solution achieving an overhang logarithmic in n was widely believed to be optimal. The article clarifies the problem and shows that the overhang can be made exponentially larger than this.
The Mathematical Association of America has awarded its 2011 David Robbins Prize for the two papers: “Overhang” by Mike Paterson and Uri Zwick (Tel Aviv University) and “Maximum Overhang” by Mike Paterson, Yuval Peres (Microsoft Research), Mikkel Thorup (AT&T), Peter Winkler (Dartmouth), and Uri Zwick.
The prize, presented on 7 January 2011 at the AMS-MAA Joint Mathematics Meetings in New Orleans, is given every three years for papers reporting on novel research in algebra, combinatorics, or discrete mathematics. Both papers appeared in 2009 in the American Mathematical Monthly.
In October 2009, the Royal Society awarded a prestigious Leverhulme Trust Senior Research Fellowship to Dr. Alexander Tiskin, for his research on the communication and synchronisation efficiency of parallel algorithms, and advanced methods of approximate comparison and matching in strings.
DIMAP: Artur Czumaj is the Principal Investigator of the recently awarded EPSRC grant to support the DIMAP, the Centre for Discrete Mathematics and its Applications that has been established in June 2006 by the University of Warwick. He is also the Director of the DIMAP Centre. All members of the Algorithms and Computational Complexity Research Group are involved in the activities of the DIMAP. DIMAP builds on a collaboration between the Algorithms and Computational Complexity Research Group within the Department of Computer Science, the Warwick Mathematics Institute, and the Operational Research and Information Systems group in the Warwick Business School.
Amin Coja-Oghlan has EPSRC grant »Random Structures, Spin Glasses and Efficient Algorithms«.
Artur Czumaj received an EPSRC grant »Efficient Decentralised Approaches in Algorithmic Game Theory«.
Artur Czumaj received an EPSRC grant »Advances in Sublinear Algorithms«.
Marcin Jurdziński received an EPSRC grant »Games for Quantitative Analysis of Real Time Systems«.
Amin Coja-Oghlan, Artur Czumaj, and Harry Räcke (jointly with Uri Feige and Robert Krauthgamer) received a Weizmann-UK Making Connections Grant »The Interplay between Algorithms and Randomness«.
Rahul Savani spent three years in FoCS as the recipient of the prestigious EPSRC Postdoctoral Research Fellowship in Theoretical Computer Science. The fellowship has been awarded to enable talented young researchers to establish an independent research career directly or shortly after completing their PhD. The title of the grant: »Algorithms for Computing Equilibria in Games«.
Matthias Englert is the recipient of the prestigious EPSRC Postdoctoral Research Fellowship in Theoretical Computer Science. The fellowships, which last three years, are awarded to enable talented young researchers to establish an independent research career directly or shortly after completing their PhD. The title of the grant: »Randomisation in Online Algorithms, Load Balancing and other Dynamic Problems«.
Benjamin Sach is the recipient of the prestigious EPSRC Postdoctoral Research Fellowship in Theoretical Computer Science. The fellowships, which last three years, are awarded to enable talented young researchers to establish an independent research career directly or shortly after completing their PhD. The title of the grant: »Pattern Matching Algorithms for Streaming Data«.

Seminars

The main seminar of the FoCS Group is the DIMAP Seminar Series.
Sometimes (not always very regularly) we organize also the Algorithms Seminar, though it's often a part of the DIMAP Seminar Series.

Workshops and Conferences

The Algorithms and Computational Complexity Research Group together with Centre for Discrete Mathematics and its Applications (DIMAP) is organizing the 39th International Colloquium on Automata, Languages and Programming (ICALP 2012), University of Warwick, July 9 - 13, 2012.
Amin Coja-Oghlan, Artur Czumaj, and Matthias Englert are co-organizers (together with Uri Feige and Robert Krauthgamer) of the Weizmann-Warwick Workshop 2011, University of Warwick, September 12 - 16, 2011.
Artur Czumaj was a co-organizer (together with Piotr Indyk, Robert Krauthgamer, and Ronitt Rubinfeld) of the Bertinoro Workshop on Sublinear Algorithms, Bertinoro, Italy, May 22 - 27, 2011.
Amin Coja-Oghlan, Artur Czumaj, and Harry Räcke co-organized (together with Uri Feige and Robert Krauthgamer) the Weizmann-Warwick Workshop 2010, Weizmann Institute of Science, Israel, December 5 - 9, 2010.
Artur Czumaj, Jan Hladký, and Diana Piguet were organizing the Workshop on Extremal and Probabilistic Combinatorics, July 18 - 25, 2010, Wetherdown Hostel, Petersfield, Hampshire, England.
Artur Czumaj, Matthias Englert, and Harry Räcke were organizing the DIMAP Summer School on Approximation and Randomized Algorithms, DIMAP, University of Warwick, July 12 - 16, 2010.
Artur Czumaj and Harry Räcke were co-organizers of Mike's Mini-workshop on Algorithms, a workshop to honor Mike Paterson's numerous contributions to theoretical computer science, the University of Warwick, and DIMAP. The workshop was organized jointly by the Centre for Discrete Mathematics and its Applications (DIMAP) and the Algorithms and Computational Complexity Research Group at the Department of Computer Science, University of Warwick, December 14, 2009.
Artur Czumaj was a co-organizer (together with Sara Kalvala and Steve Matthews) of the 25th British Colloquium for Theoretical Computer Science (BCTCS 2009), University of Warwick, April 6 - 9, 2009.
The Algorithms and Computational Complexity Research Group together with Centre for Discrete Mathematics and its Applications (DIMAP) organized the DIMAP Algorithms Day, University of Warwick, October 24, 2008.
Artur Czumaj was a co-organizer (together with Leslie Ann Goldberg (University of Liverpool) and Uri Zwick (Tel Aviv University)) Mike66, a workshop in honour of Professor Mike Paterson's 66th birthday, DIMAP, University of Warwick, September 18 - 19, 2008.
Artur Czumaj was a co-organizer (together with S. Muthu Muthukrishnan (google Research), Ronitt Rubinfeld (MIT), and Christian Sohler (University of Bonn)) of Dagstuhl Seminar 08341 Sublinear Algorithms, that will be held in the International Conference and Research Center for Computer Science, Schloss Dagstuhl, Germany, August 17 - 22, 2008.
Haris Aziz was the main organizer of the 19th Postgraduate Combinatorial Conference (PCC 2008), DIMAP, University of Warwick, July 21 - 23, 2008.
Artur Czumaj and Harry Räcke were co-organizers (together with Anupam Gupta (CMU), Stefano Leonardi (Universita' di Roma "La Sapienza"), and R. Ravi (CMU)) of the 3rd Research Workshop on Flexible Network Design, DIMAP, University of Warwick, July 13 - 16, 2008.
Marcin Jurdziński was a co-organizer (together with Jean-Jacques Herings (Maastricht University), Peter Bro Miltersen (University of Aarhus), Éva Tardos (Cornell), and Bernhard von Stengel (London School of Economics)) of Dagstuhl Seminar 07471 Equilibrium Computation, that will be held in the International Conference and Research Center for Computer Science, Schloss Dagstuhl, Germany, November 18 - 23, 2007.
Together with the Centre for Discrete Mathematics and its Applications (DIMAP), the Algorithms and Computational Complexity Research Group organized the Workshop on Algorithmic Game Theory, University of Warwick, March 25 - 28, 2007.
Artur Czumaj was a co-organizer (together with Friedhelm Meyer auf der Heide (University of Paderborn), Klaus Jansen (University of Kiel), and Ingo Schiermeyer (University of Freiberg)) of Oberwolfach Workshop on Algorithmic Graph Theory, that was held in the Mathematisches Forschungsinstitut Oberwolfach, Germany, February 12 - 18, 2006.
Artur Czumaj was a co-organizer (together with S. Muthu Muthukrishnan (google Research), Ronitt Rubinfeld (MIT), and Christian Sohler (University of Paderborn)) of Dagstuhl Seminar 05291 Sublinear Algorithms, that was held in the International Conference and Research Center for Computer Science, Schloss Dagstuhl, Germany, July 17 - 22, 2005.

Recent Activities/News

In July 2011, Andrew Handley joined the Foundations of Computer Science (FoCS) Research Group as a Postdoctoral Research Fellow.
In early 2011, Dr Benjamin Sach joined for 3 years the Foundations of Computer Science (FoCS) Research Group as a Postdoctoral Research Fellow. Matthias' fellowship is supported by an EPSRC grant »Pattern Matching Algorithms for Streaming Data«
In spring 2011, John Fearnley successfully passed his viva and graduated.
In autumn 2010, Peter Krusche successfully passed his viva and graduated.
In October 2010, Chintan Shah joined the Foundations of Computer Science (FoCS) Research Group as a DIMAP PhD student.
In early 2010, Dr A.Y. Pachón Pinzón joined the Foundations of Computer Science (FoCS) Research Group as a Postdoctoral Researcher.
In January 2010, Dr Amin Coja-Oghlan joined the Foundations of Computer Science (FoCS) Research Group as an Associate Professor (Reader).
In January 2010, Dr Troels Bjerre Sørensen joined the Foundations of Computer Science (FoCS) Research Group as a DIMAP Postdoctoral Researcher.
In January 2010, Dr Charilaos Efthymiou joined the Foundations of Computer Science (FoCS) Research Group as a Postdoctoral Researcher.
In October 2009, Dr Rajiv Raman joined the Foundations of Computer Science (FoCS) Research Group as a DIMAP Postdoctoral Researcher.
In October 2009, Dr Diana Piguet joineded the Foundations of Computer Science (FoCS) Research Group as a DIMAP Postdoctoral Researcher.
In October 2009, Matthew Felice Pace joined the Foundations of Computer Science (FoCS) Research Group as a DIMAP PhD student.
In October 2009, Ebrahim Ardeshir joined the Foundations of Computer Science (FoCS) Research Group as a DIMAP PhD student.
In October 2009, Jan Hladky joined the Foundations of Computer Science (FoCS) Research Group as a DIMAP PhD student.
In September 2008, Anna Adamaszek joined the Foundations of Computer Science (FoCS) Research Group as a DIMAP PhD student.
In September 2008, Dr Matthias Englert joined the Foundations of Computer Science (FoCS) Research Group as a Postdoctoral Research Fellow. Matthias' fellowship is supported by an EPSRC grant »Randomisation in Online Algorithms, Load Balancing and other Dynamic Problems«.
In August 2007, Dr Oded Lachish joined the Foundations of Computer Science (FoCS) Research Group as a DIMAP Postdoctoral Researcher.
In May 2007, Dr Harry Räcke joined for 3 years the Foundations of Computer Science (FoCS) Research Group as a DIMAP Assistant Professor.
In October 2006, Dr Rahul Savani joined for 3 years the Foundations of Computer Science (FoCS) Research Group as a Postdoctoral Research Fellow. Rahul's fellowship was supported by an EPSRC grant »Algorithms for Computing Equilibria in Games«.

Harry Räcke was in the Program Committee of the MFCS 2011 conference, Warsaw, Poland, August 2011.
Harry Räcke was in the Program Committee of the PODC 2011 conference, San Jose, California, USA, June 2011.
Harry Räcke was in the Program Committee of the SODA 2011 conference, San Francisco, California, USA, January 2011.
Artur Czumaj was in the Program Committee of the SODA 2011 conference, San Francisco, California, USA, January 2011.
Amin Coja-Oghlan was in the Program Committee of ICALP 2010 track A, Bordeaux, France, July 2010.
Artur Czumaj was in the Program Committee of IPDPS 2010 conference, Atlanta, Georgia, USA, April 2010.
Mike Paterson was in the Program Committee of the LATIN 2010 conference, Oaxaca, Mexico, April 2010.
Artur Czumaj was in the Program Committee of WINE 2009 conference, Rome, Italy, December 2009.
Artur Czumaj was in the Program Committee of SAGA 2009 conference, Sapporo, Japan, October 2009.
Artur Czumaj was in the Program Committee of APPROX 2009 conference, Berkeley, USA, August 2009.
Harry Räcke was in the Program Committee of the 36th International Colloquium on Automata, Languages and Programming (ICALP 2009), Track C, Rhodos, Greece, July 5 - 12, 2009.
Harry Räcke was in the Program Committee of the 26th International Symposium on Theoretical Aspects of Computer Science (STACS 2009), Freiburg, Germany, February 26 - 28, 2009.
Artur Czumaj was in the Program Committee of the Game Theoretic Aspects of E-commerce Track at the 35th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2009), Spindleruv mlyn, Czech Republic, January 24 - 30, 2009.
Artur Czumaj was in the Program Committee of the 49th Annual Symposium on Foundations of Computer Science (FOCS 2008), Philadelphia, PA, USA, October 26 - 28, 2008.
Harry Räcke was in the Program Committee of the 49th Annual Symposium on Foundations of Computer Science (FOCS 2008), Philadelphia, PA, USA, October 26 - 28, 2008.
Mike Paterson was in the Program Committee of the 16th Annual European Symposium on Algorithms (ESA 2008), Karlsruhe, Germany, September 15 - 17, 2008.
Artur Czumaj was in the Program Committee of the 35th International Colloquium on Automata, Languages and Programming (ICALP 2008), Reykjavik, Iceland, July 6 - 13, 2008.
Artur Czumaj was in the Program Committee of the 34th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2008), Durham University, UK, June 30 - July 2, 2008.
Artur Czumaj was in the Program Committee of the International Symposium on Combinatorial Optimization 2008 (CO 2008), University of Warwick, UK, March 16 - 19, 2008.
Artur Czumaj was in the Program Committee of the 15th Annual European Symposium on Algorithms (ESA 2007), Eilat, Israel, October 8 - 10, 2007.
Artur Czumaj was in the Program Committee of the 39th ACM Symposium on Theory of Computing (STOC 2007), San Diego, CA, USA, June 11 - 13, 2007, part of the 2007 Federated Computing Research Conference (FCRC).
Mike Paterson was in the Program Committee of the 1st International Symposium on Combinatorics, Algorithms, Probabilistic and Experimental Methodologies (ESCAPE 2007), Zhejiang University, Hangzhou, China, April 7 - 9, 2007.

Matthias Englert gave an invited presentation at the DIMACS Workshop on Competitive Algorithms for Packet Scheduling, Buffering and Routing in the Internet, July 6 - 8, 2011, DIMACS Center, CoRE Building, Rutgers University.
Amin Coja-Oghlan gave an invited presentation at the Dagstuhl seminar No. 11241 »Design and Analysis of Randomized and Approximation Algorithms«, the International Conference and Research Center for Computer Science, Dagstuhl, Germany, June 14 - 17, 2011.
Harry Räcke is an invited speaker at the Workshop on Approximation Algorithms: The Last Decade and the Next, the Center for Computational Intractability, Princeton, NJ, USA, June 13 - 17, 2011.
Artur Czumaj was an invited speaker at the 18th Annual European Symposium on Algorithms (ESA 2010), Liverpool, UK, September 6 - 8, 2010.
Artur Czumaj and Alexander Tiskin gave invited presentations at the Bristol Algorithms Days 2010, Feasibility Workshop, February 15 - 16, 2010, University of Bristol, Bristol, UK.
Artur Czumaj was an invited speaker at the ITCS mini-workshop on Property Testing, ITCS, Tsinghua University, Beijing, China, January 8 - 10, 2010 (see also here).
Artur Czumaj was a keynote speaker at the 3rd Workshop on Theory of Randomized Search Heuristics, Birmingham, UK, October 19 - 20, 2009.
Artur Czumaj gave an invited presentation at the Workshop I: Probabilistic Techniques and Applications, in the Special Program on Combinatorics: Methods and Applications in Mathematics and Computer Science, Institute for Pure and Applied Mathematics (IPAM), Los Angeles, October 5 - 9, 2009.
Artur Czumaj and Harry Räcke gave invited presentations at the Bristol Algorithms Days, May 11 - 12, 2009, University of Bristol, Bristol, UK.
Marcin Jurdziński gave an invited presentation at the 35th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2009), Spindleruv mlyn, Czech Republic, January 24 - 30, 2009.
Artur Czumaj gave an invited presentation/tutorial at the 2nd Polish Combinatorial Conference, Bedlewo, October 17 - 23, 2008.
Harry Räcke gave an invited presentation at the 11th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2008), MIT, Boston, USA, August 25 - 27, 2008.
Artur Czumaj gave an invited presentation at the Liverpool Algorithms Day, University of Liverpool, UK, May 23, 2008.
Artur Czumaj gave an invited presentation at the 24th British Colloquium for Theoretical Computer Science (BCTCS 2008) conference, Durham, UK, April 7 - 10, 2008.
Artur Czumaj and Mike Paterson gave invited presentations at the Bristol Algorithms Days, March 2 - 4, 2008, University of Bristol, Bristol, UK.
Mike Paterson gave an invited presentation at the 3rd Workshop on Algorithms and Complexity in Durham, UK, September 17 - 19, 2007.
Artur Czumaj gave an invited presentation at the Pervasive Adaptive (PERAD 2007), joint FET - EATCS Workshop, Brussels, Belgium, January 26, 2007.
Artur Czumaj was an invited speaker at the Optimization in Complex Networks, Satellite Workshop at European Conference on Complex Systems 2006 (ECCS '06), Said Business School, University of Oxford, UK, September 28 - 29, 2006.

DIMAP

Recent Prizes and Awards

Seminars

Workshops and Conferences

Recent Activities/News

Activities and News in ACRG