ru en

Special Semester Program on Complexity Theory

A Special Semester on Computational and Proof Complexity
Chebyshev Laboratory, St.Petersburg State University
Organized jointly with Skolkovo Institute of Science and Technology
and Steklov Institute of Mathematics at St.Petersburg
April–June 2016
St.Petersburg, Russia

News: Programs have been posted at the pages of St.Petersburg workshops.

News: a list of some recommended hotels (St.Petersburg) is available.

The semester program will include visiting researchers, visiting PhD students, and two workshops. Dates are tentative.

  1. Tutorials and Workshop on Algorithms in Communication Complexity, Property Testing and Combinatorics.
    Moscow (SkolTech), April 9-13, 2016.
    Workshop organizers: Ilan Newman and Nikolay Vereshchagin.
    Keynote speaker: Madhu Sudan.
    Confirmed speakers include Eli Ben-Sasson, Artur Czumaj, Sofia Raskhodnikova, Amir Shpilka, Amir Yehudayoff, Sergey Yekhanin,see workshop webpage.
  2. Tutorials on Proof Complexity.
    St. Petersburg, May 15-16, 2016.
    Sam Buss. Proof complexity, NP search problems and bounded arithmetic.
    Toniann Pitassi. Proof complexity.
  3. Workshop on Proof Complexity.
    St. Petersburg, May 17-20, 2016.
    Workshop organizers: Sam Buss and Pavel Pudlák.
    Keynote speaker: Jan Krajicek.
    More speakers and other details are on workshop webpage.Some photos from the tutorial and workshop, taken by A.Smal.
  4. Tutorials on Low-Depth Complexity.
    St. Petersburg, May 21-22, 2016.
    Ben Rossman, A Switching Lemma Tutorial.
    Neeraj Kayal, Low-Depth Arithmetic Complexity.
    Ryan O’Donnell, Analysis of Boolean Functions.
    Srikanth Srinivasan, The Polynomial Method.
  5. Workshop on Low-Depth Complexity.
    St. Petersburg, May 23-25, 2016.
    Workshop organizers: Ben Rossman and Rahul Santhanam.
    Keynote speaker: Ryan Williams.
    More speakers and other details are on workshop webpage.Some photos from the tutorial and workshop, taken by A.Smal.
  6. Visiting graduate students. There will be lecture courses aimed at PhD students and other researchers attending the workshops. Those will be held before or after the workshops. There will be opportunites for student grants for travel and local expenses. There is also a possibility of extended stays by graduate students for up to three months.
  7. Visiting researchers and postdocs. There will be opportunities for grants for research visits to St.Petersburg. These are intended to support joint research in St. Petersburg with organizers or other participants of the workshops, or simply with colleagues from elsewhere. Please apply for a grant!
  8. There are two other events in St.Petersburg which will be held during the semester:
    • CSR-2016, June 9-13, (11th Intl. Computer Science Symposium in Russia)
    • SEA-2016, June 5-8. (15th Intl. Symposium on Experimental Algorithms)

If you have questions about the program and how to participate, or wish to be on the mailing list for further announcements, please contact the Special Semester organizers:

Organizational email: complexityspb-at-gmail-dot-com

The program organizers acknowledge the US National Science Foundation support for additional support for student travel. Scientific projects of the Chebyshev Laboratory are supported by JSC «Gazprom Neft» (under the social investment program «Native Towns»).