СПбГУ, мат-мех





Специальный семестр по теории сложности
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 deadlines for the participation in the special semester program on Computational and Proof Complexity, which will be held in St.Petersburg in 2016, are:

  • Visiting graduate students. To attend a workshop or apply for a visit of up to three months, please complete simple application form before November 30, 2015.
  • Visiting researchers and postdocs. If you would like to make a research visit to St.Petersburg, please complete the simple application form before October 31, 2015.

While we will still accept applications after the deadlines, if you need financial or organizational support, it is strongly recommended to meet the deadlines.

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. Title TBA.
  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.
  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.
  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:

We also welcome suggestions on the format of the program.

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").

Санкт-Петербург 199178, 14 линия В.О., дом 29Б

Тел.: (812) 363-68-71