Monday, October 12, 2015

[DMANET] Complexity Semester in St.Petersburg

Dear Colleague,

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 soon approaching. While we will still accept applications after the deadlines, if you need financial or organizational support, it is strongly recommended to meet the deadlines.

While we are apologizing for possible cross-postings, we will appreciate if you share the announcement with your colleagues and students.

Looking forward for your participation,
Sam Buss and Edward Hirsch (organizers)


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

The semester program will include visiting researchers, visiting PhD students, and two or three workshops. Workshops will be preceded by two-day tutorial programs aimed at giving attendees the background of the workshop topics. Visiting researchers and students will be able to attend any time during the three months period.

1. Workshop on Proof Complexity.
St. Petersburg, May 17-20, 2016.
Workshop organizers: Sam Buss and Pavel Pudlák.
Keynote speaker: Jan Krajicek.
Confirmed speakers: Albert Atserias, Paul Beame, Arnold Beckmann,
Eli Ben-Sasson, Olaf Beyersdorff, Pavel Hrubeš, Rosalie Iemhoff,
Dmitry Itsykson, Emil Jeřábek, Leszek Kołodziejczyk, Massimo Lauria,
Jakob Nordström, Toniann Pitassi, Iddo Tzameret.
Tutorials: May 15-16
Sam Buss. Proof complexity, NP search problems and bounded arithmetic.
Toniann Pitassi. Title TBA.

2. Workshop on Low-Depth Complexity.
St.Petersburg, May 23-25, 2016.
Workshop organizers: Ben Rossman and Rahul Santhanam.
Keynote speaker: Ryan Williams.
Confirmed speakers: Johan HÃ¥stad, Yuan Li, Neeraj Kayal,
Igor Oliveira, Ryan O'Donnell, Rafael Oliveira, Toniann Pitassi,
Rocco Servedio, Sasha Sherstov, Srikanth Srinivasan,
Avishay Tal, Li-Yang Tan.
Tutorials: May 21-22
Ben Rossman, A Switching Lemma Tutorial.
Neeraj Kayal, Low-Depth Arithmetic Complexity.
Ryan O'Donnell, Analysis of Boolean Functions.
Srikanth Srinivasan, The Polynomial Method.

3. Workshop on Algorithms in Communication, Property Testing and Combinatorics.
Workshop organizers: Ilan Newman and Nikolay Vereshchagin.
This workshop is expected to be held in Moscow. More details TBA.

4. Visiting graduate students. To attend a workshop or apply for a visit of up to three months, please complete the application form
before November 30, 2015.

5. Visiting researchers and postdocs. If you would like to make a research visit to St.Petersburg, please complete the application form
before October 31, 2015.

6. 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:
Edward A. Hirsch (Steklov Institute/St.Petersburg;
Sam Buss (Univ. of California, San Diego;
We also welcome suggestions on the format of the program.

Web page:

APPLICATION PROCEDURE: if you wish to participate in the semester, please complete the (short) online application form (found on the web page).

Organizational email:

UNSUBSCRIPTION: If you do not wish to receive any news
regarding our Complexity Semester, please reply to this mail
and we will remove you from the mailing list.
* Contributions to be spread via DMANET are submitted to
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.