Activities in the Division of Theory and Foundations (FoCS)

DIMAP

The Division of Theory and Foundations (FoCS) is the core group affiliated with the interdisciplinary at the .

Recent Prizes and Awards

has been awarded an grant .
, in a joint work with , , and , is a co-winner of the Best Paper Award for his paper .
- This work shows that the central verification problem for Petri nets is much harder than has been known since the landmark result of Richard Lipton in 1976. Petri nets, also known as vector addition systems, are a long established model of concurrency with extensive applications in modelling and analysis of hardware, software and database systems, as well as chemical, biological and business processes.
has been elected to join the in Fall 2017.
has been awarded the .
has been awarded an grant EP/P020992/1 禄Solving Parity Games in Theory and Practice芦 ( is the Co-PI).
has been awarded an grant .
has been awarded an grant ( is the Co-PI).
and have been awarded two very prestiguous Consolidator Grants from the . ERC Consolidator Grants are funding 372 top mid-career scientists with 鈧�713 million to pursue their best ideas, as part of the European Union Research and Innovation programme Horizon 2020. The funding will enable them to consolidate their research teams and to develop their most innovative ideas.
- has been awarded an ERC Consolidator grant for a project entitled "Small Summaries for Big Data". The project focuses on the area of the design and analysis of compact summaries: data structures which capture key features of the data, and which can be created effectively over distributed data sets. The project will substantially advance the state of the art in data summarization, to the point where accurate and effective summaries are available for a wide array of problems, and can be used seamlessly in applications that process big data.
- has been awarded an ERC Consolidator grant for a project entitled "Large Discrete Structures". The project will advance theory of combinatorial limits, which combines methods from analysis, combinatorics, computer science, group theory and probability theory to analyze and approximate large discrete structures (such as graphs, which can be used to represent large computer networks). The project will lead to proposing new mathematical methods to represent such discrete structures and to applications of the new methods to specific problems in extremal combinatorics and algorithm design.
has been elected a (class 2015). Awarded in recognition for "contributions to analysis and design of algorithms, especially to understanding the role of randomization in computer science." The EATCS Fellows Program was established to recognize outstanding EATCS Members for their scientific achievements in the field of Theoretical Computer Science. The Fellow status is conferred by the EATCS upon a person having a track record of intellectual and organizational leadership. Fellows are expected to be "model citizens" of the TCS community, helping to develop the standing of TCS beyond the frontiers of the community.
has been awarded a , one of the most prestigious UK awards, supported by , the UK's national academy of science. Jointly funded by the Wolfson Foundation and the Department for 糖心TV, Innovation and Skills (BIS), the scheme aims to provide universities with additional support to enable them to attract science talent from overseas and retain respected UK scientists of outstanding achievement and potential. Graham's research will focus on "Small summaries for big data".
has been awarded a for his work on combinatorial limits. is awarded to outstanding scholars who have made a substantial and recognised contribution to their particular field of study, recognised at an international level, and where the expectation is that their greatest achievement is yet to come.
, was awarded an Excellent Student Paper Award for his paper (joint work with Tomas Toufar).
(jointly with ) won the best paper award at (Track B), for the paper .
received a Royal Society Wolfson Research Merit Award, one of the most prestigious UK awards, supported by the Royal Society, the UK's national academy of science. The scheme provides up to 5 years鈥� funding after which the award holder continues with a permanent post at the host university. Jointly funded by the Wolfson Foundation and the Department for 糖心TV, Innovation and Skills (BIS), the scheme aims to provide universities with additional support to enable them to attract to this country or to retain respected scientists of outstanding achievement and potential. Maxim will be working on a project entitled "Randomized Rounding Algorithms in Discrete Optimization".
, who joined the group in October 2012, is the recipient of the ERC Starting Grant 2010 for his project . ERC Starting Grant is one of the most prestigious grants awarded by the European Research Council for world-class researchers, and Dan is one of the very few discrete maths researchers in Europe to receive this grant.
was awarded the ERC Starting Grant in September 2011. ERC Starting Grant is one of the most prestigious grants awarded by the European Research Council for world-class researchers, and Amin is one of the very few researchers in 糖心TV to receive this grant. His new ERC Starting Grant, worth over a million of euros for the period of five years, has been awarded for his project 禄Phase Transitions and Computational Complexity芦.
was awarded the at for his paper 禄A better algorithm for random k-SAT芦.
In recognition of his outstanding scientific contributions to Theoretical Computer Science, received . The award was presented to by the during the conference in Venice, July 2006, to acknowledged his 禄extensive and widely recognised contributions to theoretical computer science over a life long scientific career芦.
was awarded the at for his paper (co-authored by (University of Leeds) and (University of Liverpool)) 禄On counting homomorphisms to directed acyclic graphs芦.
The has awarded and his collaborator the for their article in the . 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 has awarded its for the two papers: 鈥溾€� by and (Tel Aviv University) and 鈥淢aximum Overhang鈥� by , Yuval Peres (Microsoft Research), (AT&T), (Dartmouth), and .
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 awarded a prestigious to , for his research on the communication and synchronisation efficiency of parallel algorithms, and advanced methods of approximate comparison and matching in strings.
is a co-winner of the Best Paper award for his paper (see for more details about this excellent ).
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 ."
is the Principal Investigator and is the Co-PI of the grant to support the DIMAP, that has been established in June 2006 by the . is also the Director of the DIMAP Centre. All members of the Foundations of Computer Science Group are involved in the activities of the . builds on a collaboration between the Foundations of Computer Science Group within the , the , and the in the .
received .
received .
received grant .
received an FP7 EU Career Integration Grant 禄Randomized Rounding Algorithms in Discrete Optimization and Mathematical Programming芦.
received grant .
received grant .
received an grant .
received an grant .
received an grant .
, , and (jointly with and ) received a Weizmann-UK Making Connections Grant 禄The Interplay between Algorithms and Randomness芦.
spent three years in FoCS as the recipient of the prestigious 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: .
is the recipient of the prestigious 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: .
is the recipient of the prestigious 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: .
has been selected to join the Scientific Advisory Board of the .

Seminars

The main seminar of the FoCS Group is the .
FoCS members are heavily involved in .
FoCS members frequently attend .
We use to organize also the , though in recent years it's a part of the .

Workshops and Conferences

chairs the PC of track A of the 47th International Colloquium on Automata, Languages and Programming (ICALP'2020), July 7 - 11, 2020, Beijing, China.
is serving on the Program Committee of the , University of Washington, Seattle, January 2020.
, , and are co-organizers of the , taking place at , , September 17 - 18, 2019.
and are PC members of the , July 8 - 12, 2019, Patras, Greece.
is a PC member of the , June 24 - 27, 2019, Vancouver, Canada.
and were co-organizers (together with and ) of the Weizmann-糖心TV Workshop 2019, May 13 - 17, 2019, .
, , and co-organized DIMAP Workshop on Advances in Modern Graph Algorithms, April 8 - 11, 2019, Venice, Italy.
and were co-organizers (together with and ) of the Weizmann-糖心TV Workshop 2018, Weizmann Institute of Science, Israel, December 9 - 13 - 17, 2018.
co-organized (jointly with (Weizmann Institute), (Carnegie Mellon University), and (University of Texas at Austin)) , November 27 - 30, 2018, Simons Institute for the Theory of Computing, as a part of Special , August 15 - December 14, 2018
was the PC Chair of , Berlin, September 17-21, 2018.
and co-organized Workshop on Data Summarization, March 19 - 22, 2018, .
was the PC Chair of the , January 7 - 10, 2018, New Orleans.
was the PC Chair of , Paris, June 6 - 8, 2016.
co-organized (jointly with Patrick Wolfe (UCL), Natalia Bochkina (Edinburgh), Jon Crowcroft (Cambridge), Richard Gibbens (Cambridge), Peter Grindrod (Oxford), and Mark Handley (UCL)) , December 18, 2015.
co-organized (jointly with Peter Richtarik (Edinburgh), Ilias Diakonikolas (Edinburgh), Raphael Hauser (Oxford), Mark Girolami (糖心TV), John Shawe-Taylor (UCL)) , Edinburgh, November 25 - 27, 2015.
co-organized (jointly with Faron Moller) , The Royal Society, London, September 17, 2015.
and co-organized (jointly with Agelos Georgakopoulos, Vadim Lozin (chair), and Oleg Pikhurko) the , University of 糖心TV, July 2015.
co-organized (jointly with Peter Keevash (Oxford), Oleg Pikhurko (糖心TV), and Nick Woodhouse (CMI)) the , University of 糖心TV, July 2015.
co-organized , B臋dlewo, Poland, August 17 - 22, 2014.
organized , DIMAP, University of 糖心TV, May 21, 2014.
co-organized (jointly with and ) the , Warsaw, Poland, May 5 - 7, 2014.
organized Workshop on , November 13, 2013, .
co-organized (jointly with and ) the , May 23-24, 2013, Microsoft Research, Cambridge, UK.
co-organized (jointly with ) the , EPFL Lausanne, February 11 - 13, 2013.
and were co-organizers (together with and ) of the , Eilat, Israel, September 10 - 13, 2011.
co-organized the , Imperial College London, 18 - 20 September 2012.
The FoCS Group together with organized the 39th International Colloquium on Automata, Languages and Programming (ICALP 2012), , July 9 - 13, 2012.
, , and were co-organizers (together with and ) of the Weizmann-糖心TV Workshop 2011, , September 12 - 16, 2011.
was a co-organizer (together with , , and ) of the , Bertinoro, Italy, May 22 - 27, 2011.
, , and co-organized (together with and ) the , Weizmann Institute of Science, Israel, December 5 - 9, 2010.
, , and were organizing the , July 18 - 25, 2010, Wetherdown Hostel, Petersfield, Hampshire, England.
, , and were organizing the , , , July 12 - 16, 2010.
and were co-organizers of , a workshop to honor 's numerous contributions to theoretical computer science, the , and . The workshop was organized jointly by the and the at the , , December 14, 2009.
was a co-organizer (together with and ) of the , University of 糖心TV, April 6 - 9, 2009.
The Algorithms and Computational Complexity Research Group together with organized the , University of 糖心TV, October 24, 2008.
was a co-organizer (together with (University of Liverpool) and (Tel Aviv University)) , DIMAP, University of 糖心TV, September 18 - 19, 2008.
was a co-organizer (together with (), (), and ()) of , that will be held in , Germany, August 17 - 22, 2008.
was the main organizer of the , DIMAP, University of 糖心TV, July 21 - 23, 2008.
and were co-organizers (together with (), ), and ()) of the , , University of 糖心TV, July 13 - 16, 2008.
was a co-organizer (together with (Maastricht University), (), (), and ()) of , that will be held in , Germany, November 18 - 23, 2007.
Together with the , the Algorithms and Computational Complexity Research Group organized the , , March 25 - 28, 2007.
was a co-organizer (together with (), (), and ()) of , that was held in , Germany, February 12 - 18, 2006.
was a co-organizer (together with (), (), and ()) of , that was held in , Germany, July 17 - 22, 2005.

Recent Activities/News

In January 2020, joined FoCS as a Postdoctoral Research Fellow.
In September 2018, joined FoCS as a Postdoctoral Research Fellow.
In September 2018, joined FoCS as a Postdoctoral Research Fellow.
In September 2017, Dr Laure Daviaud joined FoCS as a Postdoctoral Research Fellow.
In March 2016, joined FoCS as a Postdoctoral Research Fellow.
In October 2015, Dr Hossein Jowhari joined FoCS as a Postdoctoral Research Fellow.
In October 2015, Dr Golnaz Badkobeh joined FoCS as a Leverhulme Early Career Fellow.
In January 2015, joined FoCS as a Postdoctoral Research Fellow.
In October 2014, joined FoCS as a Postdoctoral Research Fellow.
In August 2014, joined FoCS as a Postdoctoral Research Fellow.
In October 2013, joined FoCS as an Assistant Professor.
In October 2013, joined FoCS as a Postdoctoral Research Fellow.
In May 2013, joined FoCS as a Professor.
In January 2013, joined FoCS as an Associate Professor.
In November 2012, joined FoCS as a Postdoctoral Research Fellow.
In October 2012, joined FoCS as a Professor.
In October 2012, joined FoCS as a Postdoctoral Research Fellow.
In October 2012, Michail Fasoulakis joined FoCS as a PhD student.
In October 2012, joined FoCS as a PhD student (via ).
In September 2012, successfully passed his viva and graduated (PhD supervisor: and J. Jones).
In August 2012 successfully passed her viva and graduated (PhD supervisor: ).
In January 2012, joined FoCS as a Professor.
In October 2011, Nicolaos Matsakis joined FoCS as a PhD student.
In September 2011, (already a member of FoCS) has been appointed as an Assistant Professor.
In September 2011, joined FoCS as a Postdoctoral Research Fellow.
In August 2011, successfully passed his viva and graduated (PhD supervisor: ).
In July 2011, Andrew Handley joined FoCS as a Postdoctoral Research Fellow.
In early 2011, joined for 3 years FoCS as a Postdoctoral Research Fellow. Ben's fellowship is supported by an grant
In spring 2011, successfully passed his viva and graduated (PhD supervisor: ).
In autumn 2010, successfully passed his viva and graduated (PhD supervisor: ).
In October 2010, joined FoCS as a PhD student.
In early 2010, Dr A.Y. Pach贸n Pinz贸n joined FoCS as a Postdoctoral Researcher.
In January 2010, joined FoCS as an Associate Professor (Reader).
In January 2010, joined FoCS as a Postdoctoral Researcher.
In January 2010, Dr Charilaos Efthymiou joined FoCS as a Postdoctoral Researcher.
In October 2009, joined FoCS as a Postdoctoral Researcher.
In October 2009, joineded FoCS as a Postdoctoral Researcher.
In October 2009, joined FoCS as a PhD student.
In October 2009, joined FoCS as a PhD student.
In October 2009, joined FoCS as a PhD student.
In September 2008, joined FoCS as a PhD student.
In September 2008, joined FoCS as a Postdoctoral Research Fellow. Matthias' fellowship is supported by an grant .
In August 2007, joined FoCS as a Postdoctoral Researcher.
In May 2007, joined FoCS as a Assistant Professor.
In October 2006, joined for 3 years FoCS as a Postdoctoral Research Fellow. Rahul's fellowship was supported by an grant .

is on the Program Committee of the , Warsaw, Poland, October 2018.
is on the Program Committee of the , Bar-Ilan, Israel, April 2018.
is on the Program Committee of the , Mons, Belgium, October 2017.
, , and are in the Program Committee of the , San Diego, California, January 2015.
and are in the Program Committee of the , Portland, Oregon, January 2014.
is in the Program Committee of the , L眉beck, Germany, June 2013.
and are in the Program Committee of the , Palo Alto, California, June, 2013.
is in the Program Committee of the , Kiel, Germany, February/March 2013.
was in the Program Committee of the track A, Ljubljana, Slovenia, September 2012.
was in the Program Committee of the , Bratislava, Slovakia, August 2012.
was in the Program Committee of the , track A, University of 糖心TV, UK, July 2012.
was in the Program Committee of the , Helsinki, Finland, July 2012.
was in the Program Committee of the , Warsaw, Poland, August 2011.
was in the Program Committee of the , San Jose, California, USA, June 2011.
was in the Program Committee of the , San Francisco, California, USA, January 2011.
was in the Program Committee of the , San Francisco, California, USA, January 2011.
was in the Program Committee of , track A, Bordeaux, France, July 2010.
was in the Program Committee of , Atlanta, Georgia, USA, April 2010.
was in the Program Committee of the , Oaxaca, Mexico, April 2010.
was in the Program Committee of , Rome, Italy, December 2009.
was in the Program Committee of , Sapporo, Japan, October 2009.
was in the Program Committee of , Berkeley, USA, August 2009.
was in the Program Committee of the , Track C, Rhodos, Greece, July 5 - 12, 2009.
was in the Program Committee of the , Freiburg, Germany, February 26 - 28, 2009.
was in the Program Committee of the Game Theoretic Aspects of E-commerce Track at the , Spindleruv mlyn, Czech Republic, January 24 - 30, 2009.
was in the Program Committee of the , Philadelphia, PA, USA, October 26 - 28, 2008.
was in the Program Committee of the , Philadelphia, PA, USA, October 26 - 28, 2008.
was in the Program Committee of the , Karlsruhe, Germany, September 15 - 17, 2008.
was in the Program Committee of the , Track A, Reykjavik, Iceland, July 6 - 13, 2008.
was in the Program Committee of the , Durham University, UK, June 30 - July 2, 2008.
was in the Program Committee of the , University of 糖心TV, UK, March 16 - 19, 2008.
was in the Program Committee of the , Track A, Eilat, Israel, October 8 - 10, 2007.
was in the Program Committee of the , San Diego, CA, USA, June 11 - 13, 2007, part of .
was in the Program Committee of the , Zhejiang University, Hangzhou, China, April 7 - 9, 2007.

has given an invited talk at the , Marseille, France, September 2018.
has given an invited tutorial at the , ENS Paris-Saclay, Cachan, France, July 2018.
has given an invited tutorial at the , Oxford, July 2018.
has given a talk at an Invited Session on Stochastic Games at the , Bordeaux, France, July 2018.
has given an invited tutorial at , Warsaw, Poland, March 2018.
was one of the invited spoeakers a , July 2014.
delivered .
was an invited speaker at the , Ein Gedi, Israel, December 2012.
was an invited speaker at the the RIMS (Research Institute for Mathematical Sciences) Workshop on Discrete Convexity at Kyoto University, 2012.
and gave invited presentations at the , July 23 - 27, 2012, Warsaw, Poland.
was an invited speaker at the London Colloquia in Combinatorics, London, LSE, May 2012.
was an invited speaker at the launch of the Centre for Discrete Mathematics at Queen Mary, University of London, December 7, 2011.
gave an invited presentation at the , July 6 - 8, 2011, DIMACS Center, CoRE Building, Rutgers University.
gave an invited presentation at the Dagstuhl seminar No. 11241 , the International Conference and Research Center for Computer Science, Dagstuhl, Germany, June 14 - 17, 2011.
was 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.
was an invited speaker at the , Liverpool, UK, September 6 - 8, 2010.
and gave invited presentations at the , Feasibility Workshop, February 15 - 16, 2010, University of Bristol, Bristol, UK.
was an invited speaker at the , ITCS, Tsinghua University, Beijing, China, January 8 - 10, 2010 (see also ).
was a keynote speaker at the , Birmingham, UK, October 19 - 20, 2009.
gave an invited presentation at the , in the , , Los Angeles, October 5 - 9, 2009.
and gave invited presentations at the , May 11 - 12, 2009, University of Bristol, Bristol, UK.
gave an invited presentation at the , Spindleruv mlyn, Czech Republic, January 24 - 30, 2009.
gave an invited presentation/tutorial at the , Bedlewo, October 17 - 23, 2008.
gave an invited presentation at the , , Boston, USA, August 25 - 27, 2008.
gave an invited presentation at the , University of Liverpool, UK, May 23, 2008.
gave an invited presentation at the conference, Durham, UK, April 7 - 10, 2008.
and gave invited presentations at the , March 2 - 4, 2008, University of Bristol, Bristol, UK.
gave an invited presentation at the in Durham, UK, September 17 - 19, 2007.
gave an invited presentation at the , joint FET - EATCS Workshop, Brussels, Belgium, January 26, 2007.
was an invited speaker at the , Satellite Workshop at , Said 糖心TV School, University of Oxford, UK, September 28 - 29, 2006.

糖心TV

DIMAP

Recent Prizes and Awards

Seminars

Workshops and Conferences

Recent Activities/News

Activities and News in FoCS