ERC Consolidator grant

LBCAD: Lower bounds for combinatorial algorithms and dynamic problems

"LBCAD: Lower bounds for combinatorial algorithms and dynamic problems" is a five year project funded by European Research Council (ERC) as a consolidator grant. Its principal investigator is Michal Koucký. The project is hosted by the Computer Science Institute of Charles University in Prague. The project started in February 2014.

Scientific goals of the project

The aim of this project is to further our understanding of which algorithmic problems can be solved efficiently and what are the best algorithms for these problems. Our goal is to provide lower bounds on the complexity of problems in two main areas: problems related to matrix multiplication over various semi-rings and dynamic data structure problems.

In the area of problems related to matrix multiplication we are interested in the limits of combinatorial algorithms. Examples of problems in this area are the All-Pairs Shortest Paths Problem and Boolean Matrix Multiplication. There has been only limited success in constructing non-trivial combinatorial algorithms for these problems. It might be that there are no fast combinatorial algorithms for these problems. We aim to explore this possibility by formulating a robust notion of combinatorial algorithms for these problems and proving that such algorithms cannot be fast.

In the area of dynamic data structures our goal is to prove strong lower bounds on the complexity of query and update operations for problems like dynamic graph reachability. We aim to understand the current lower bound techniques (e.g. based on communication complexity) and their limitations, develop new techniques and prove strong lower bounds.

List of papers

People

Researchers

  • Michal Koucký
  • Zdeněk Dvořák

Postdocs

  • Sagnik Mukhopadhyay (Sep 2018-Dec 2018)
  • Xiaolan Hu (Aug 2017-Sep 2018)
  • Diptarka Chakraborty (Sep 2016-Aug 2018)
  • Nitin Saurabh (Sep 2016-Nov 2017)
  • Elazar Goldenberg (Oct 2014-Sep 2016)
  • Bruno Loff (Jan 2015-Dec 2016)

Students

  • Karel Král (Oct 2017-)
  • Pavel Dvořák (Oct 2015-)
  • Debarati Das (Jan 2015-)
  • Karel Král, Master's. (Dec 2015-2017)
  • Filip Hlásek, Master's. (Oct 2015-Aug 2016)
  • Vojtěch Tůma (Feb-May, 2014)

Visitors

  • Bruno Loff (Jan 23-31, 2016)
  • Michael Saks (July 14-22, 2018)
  • Ryan Williams (July 9-16, 2018)
  • Harry Buhrman (May 23-24, 2018)
  • Eric Allender (April 22-28, 2018)
  • Michael Saks (July 16-23, 2017)
  • Ariel Gabizon (Oct/Nov, 2016)
  • Sagnik Mukhopadhyay (Sep/Oct, 2016)
  • Michael Saks (August 22-28, 2016)
  • Zvi Lotker (July 17-23, 2016)
  • Nitin Saurabh (March 20-27, 2016)
  • Diptarka Chakraborty (March 9-19, 2016)
  • Peter Bro Miltersen (Deceber 17-20, 2015)
  • Liana Yepremyan (November 1-12, 2015)
  • Pavel Hubáček (September 6-26, 2015)
  • Kristoffer Arnsfelt Hansen (June 27-July 3, 2015)
  • Arkadev Chattopadhyay (June 23-July 2, 2015)
  • Sagnik Mukhopadhyay (June 21-July 3, 2015)
  • Rasmus Jensen-Ibsen (April 6-10, 2015)
  • Sagnik Mukhopadhyay (March 7-12, 2015)
  • Chakraborty Diptarka (Sep. 29-Oct. 20, 2014)
  • Gerth Stølting Brodal (Sep. 17-19, 2014)
  • Debarati Das (Sep. 7-13, 2014)
  • Michael Saks (Aug. 10-20, 2014)
  • Elazar Goldenberg (May 20-22, 2014)
  • Igor Shinkar (May 11-13, 2014)
  • Bruno Bauwens (April 6-10, 2014)
  • Ariel Gabizon (March 12-15, 2014)

Summer School on Algorithms and Lower bounds 2018

Date: July 6 - July 9, 2018
Location: Hostivice-Břve, Sporthotel Břve Hostivice (near Prague, Czech Republic) Web-page

Previous Summer School on Lower bounds 2015.

Open positions

Postdocs

Two one‐year post‐doc positions are available within the framework of this project, with a possibility of one-year extension. Applications are invited from candidates who have strong background in computational complexity, algorithms or data structures, and who have completed their Ph.D. degree in theoretical computer science or mathematics within the last 4 years (or will complete their Ph.D. degree by Fall 2016).

Starting date: Fall 2016 or beginning of 2017.

The application should contain:

  • Short letter of motivation,
  • Professional CV (including the list of publications),
  • Two letters of recommendation.

Application deadline: January 21, 2016.

The application and the recommendation letters should be sent electronically to: koucky@iuuk.mff.cuni.cz.

PhD students

Positions for PhD students are available within the framework of this project with funding for three years and possible additional funding afterwards. Applications are invited from candidates who have strong background in theoretical computer science or discrete mathematics, and who have completed their undergraduate studies or will complete it by Fall 2015.

Starting date: Fall 2015.

The application should contain:

  • Professional CV with a statement of research interests,
  • One letter of recommendation.

Application deadline: February 22, 2015. (The deadline has passed, but feel free to inquiry about other possibilities.)

The application and the recommendation letter should be sent electronically to: koucky@iuuk.mff.cuni.cz.

Funding info

ERC logo This project is funded by the European Research Council under the European Union's Seventh Framework Programme (FP7/2007-2013)/ERC grant agreement no. 616787. FP7 logo