Summer School on Lower Bounds 2015

The program of the school will consist of three tutorial series related to lower bounds. The late Monday afternoon is devoted to presentations of own research by some of the junior participants of the workshop. We expect the talks to include a fair amount of technical details. The workshop will also include plenty of time for discussions.

Tutorial speakers

Special feature:

Date and location

Date: June 28 - July 1, 2015, lectures start on Sunday morning and end by Wednesday morning session
Location: Horoměřice, Modrá stodola (near Prague, Czech Republic)

Organizers (contact person): Michal Koucký (Charles University).

Tentative programme

Sunday 28.6.2015

  10:00 - 11:10   Ryan Williams: Algorithms as Lower Bounds
  11:20 - 12:30   Arkadev Chattopadhyay: Multiparty Communication Complexity

  14:30 - 16:00   Kristoffer Arnsfelt Hansen: Boolean circuits and polynomials
  17:00 - 18:00   Virginia V. Williams: Hardness for easy problems

Monday 29.6.2015

   9:00 - 10:30   Arkadev Chattopadhyay: ...
  11:00 - 12:30   Ryan Williams: ...

  14:30 - 16:00   Kristoffer Arnsfelt Hansen: ...
  16:30 - 17:00   Florian Speelman: Catalytic computation
  17:00 - 17:30   Pavel Dvorak: On the complexity of online Ramsey game
  17:30 - 18:00   Cody Murray: On the (non) NP-hardness of computing circuit complexity

  20:00           Social program - bowling

Tuesday 30.6.2015

   9:00 - 10:30   Ryan Williams: ...
  11:00 - 12:30   Arkadev Chattopadhyay: ...

  14:30 - 16:00   Kristoffer Arnsfelt Hansen: ...
  16:30 - 17:00   Mayank Goswami: Tight lower bounds for approximate range emptiness
  17:00 - 17:30   Jevgēnijs Vihrovs: On sensitivity versus block sensitivity of boolean functions
  17:30 - 18:00   Elazar Goldenberg: Low distortion embedding from edit to hamming distance using coupling

Wednesday 1.7.2015

    9:00 - 10:30   Arkadev Chattopadhyay: ...
   11:00 - 12:30   Ryan Williams: ...

   12:30 final lunch

List of participants

Martin Babka (CU), Lucas Boczkowski (U.Paris 7, LIAFA), Martin Böhm (CU), Arkadev Chattopadhyay (TIFR, Mumbai), Ondřej Čepek (CU), Vladimír Čunát (CU), Debarati Das (CU), Pavel Dvořák (CU), Noah Fleming (Memorial U./U. of Toronto), Lukáš Folwarczný (CU), Anna Gal (U. of Texas, Austin), Tomáš Gavenčiak (CU), Elazar Goldenberg (CU), Mayank Goswami (MPI Saarbrucken), Nathan Grosshans (ENS Cachan & U. de Montreal), Kristoffer Arnsfelt Hansen (Aarhus U.), Šimon Hrabec (CTU), Pavel Hrubeš (Math Inst., Prague), Emil Jeřábek (Math Inst., Prague), Vojtěch Kaluža (CU), Raheleh Jalali Keshavarz (Math Inst., Prague), Dušan Knop (CU), Michal Koucký (CU), Karel Král (CU), Petr Kučera (CU), Mrinal Kumar (Rutgers U.), Bruno Loff (CU), Nikhil Mande (TIFR, Mumbai), Anton Marchenko (Kazan Federal U.), Morteza Monemizadeh (CU), Sagnik Mukhopadhyay (TIFR, Mumbai), Cody Murray (Stanford U.), Mateus de Oliveira Oliveira (Math Inst., Prague), Krisjanis Prusis (U. of Latvia), Shadab Romani (Memorial U.), Jiří Sgall (CU), Florian Speelman (CWI, Amsterdam), Ondřej Suchý (CTU), Amirhossein Akbar Tabatabai (Math Inst., Prague), Neil Thapen (Math Inst., Prague), Meng-Tsung Tsai (Rutgers U.), Virginia Vassilevska Williams (Stanford U.) Pavel Veselý (CU), Jevgēnijs Vihrovs (U. of Latvia), Vojta Vorel (CU), Ryan Williams (Stanford U.), Nikola Yolov (Oxford U.), Mansur Ziatdinov (Kazan Federal U.),

Funding info

ERC logo This workshop has received funding from the European Research Council under the European Union's Seventh Framework Programme (FP7/2007-2013)/ERC grant agreement no. 616787. FP7 logo