Program

The conference will be held in a hybrid format. The online part will use Webex video conference software. If you want to obtain the link, please send a request with your name and affiliation to smc@sochisirius.ru. The topic should be "007w conference link"

The abstracts for the invited talks are listed here

The proceedings are available at https://link.springer.com/book/10.1007/978-3-030-79416-3 (LNCS 12730) in free access till July 21st.

All times are given in Moscow time zone (UTC+3).

Monday, June 28
Session 1: Opening and best paper. Chair: Daniil Musatov
14:00–14:50 50 min Registration and hardware testing
14:50–15:00 10 min Welcome remarks
15:00–16:00 1 hour OPENING LECTURE: Tim Roughgarden (Columbia University, USA), "How Computer Science Informs Modern Auction Design"
16:00–16:30 30 min BEST PAPER and BEST STUDENT PAPER: Pranjal Dutta, Real tau-Conjecture for sum-of-squares: A unified approach to lower bound and derandomization
16:30–17:00 30 min Coffee break
Session 2: Algebraic complexity and combinatorics of words. Chair: Alexander Razborov
17:00–17:30 30 min Prasad Chaugule, Variants of the Determinant Polynomial and the VP-completeness (joint work with Nutan Limaye and Shourya Pandey)
17:30–18:00 30 min Purnata Ghosal, Limitations of Sums of Bounded Read Formulas and ABPs (joint work with Raghavendra Rao B V)
18:00–18:30 30 min Klaus Meer, A PCP of proximity for Real Algebraic Polynomials
18:30–19:00 30 min Augusto Modanese, Lower Bounds and Hardness Magnification for Sublinear-Time Shrinking Cellular Automata
19:00–19:30 30 min Olga Parshina, On closed-rich words (joint work with Svetlana Puzynina)
Tuesday, June 29
Session 3: Games and boolean functions. Chair: Alexey Milovanov
14:00–15:00 1 hour INVITED TALK: Edith Elkind (University of Oxford, UK), "United for Change: Deliberative Coalition Formation to Change the Status Quo"
15:00–15:30 30 min Vaibhav Krishan, Upper Bound for Torus Polynomials
15:30–16:00 30 min Nikolay Proskurin, On Separation between the Degree of a Boolean Function and the Block Sensitivity
16:00–16:30 30 min Coffee break
Session 4: Combinatorics. Chair: Alexei Savvateev
16:30–17:30 1 hour INVITED TALK: Joel Spencer (New York University, USA), Balancing Problems: A Fourfold Approach
17:30–18:00 30 min Yekun Xu, A Generalization of a Theorem of Rothschild and van Lint (joint works with Ning Xie and Shuai Xu)
18:00–18:30 30 min Zuguang Gao, Approximation Schemes for Multiperiod Binary Knapsack Problems (joint work with John R. Birge and Varun Gupta)
18:30–19:30 1 hour Business meeting
Wednesday, June 30
Session 5: Approximation. Chair: Alexander Smal
14:00–14:30 30 min Vladimir Shenmaier, Approximation and Complexity of the Capacitated Geometric Median Problem
14:30–15:00 30 min Zeev Nutov, Approximation algorithms for connectivity augmentation problems
15:00–15:30 30 min Zeev Nutov, On rooted k-connectivity problems in quasi-bipartite digraphs
15:30–16:30 1 hour INVITED TALK: Jens Vygen (University of Bonn, Germany), "Traveling Salesman Problems: Approximation Algorithms and Black-Box Reductions"
16:30–17:00 30 min Coffee break
Session 6: Logic and formal languages. Chair: Daniil Musatov
17:00–18:00 1 hour INVITED TALK: Ugo dal Lago (University of Bologna, Italy), "On Differential Program Semantics"
18:00–18:30 30 min Alexander Okhotin, Input-driven pushdown automata on well-nested infinite strings (joint work with Victor Selivanov)
18:30–19:00 30 min Pablo Rotondo, Analysis of an efficient reduction algorithm for random regular expressions based on universality detection (joint work with Florent Koechlin)
19:00–19:30 30 min Paweł Parys, Shelah-Stupp's and Muchnik's Iterations Revisited
Thursday, July 1
Session 7: Games and interactions. Chair: Daniil Musatov
14:00–14:30 30 min Daiki Miyahara, A Secure Three-input AND Protocol with a Standard Deck of Minimal Cards (joint work with Hiroto Koyama, Takaaki Mizuki and Hideaki Sone)
14:30–15:30 1 hour INVITED TALK: Hugo Gimbert (LaBRI, Bordeaux, France), Two-Sided Random Matching Markets
15:30–16:00 30 min Kristoffer Arnsfelt Hansen, Computational Complexity of Multi-Player Evolutionarily Stable Strategies (joint work with Manon Blanc)
16:00–16:30 30 min Markus Holzer, On the Computational Complexity of Reaction Systems, Revisited (joint work with Christian Rauch)
16:30–17:00 30 min Coffee break
Session 8: Various topics in complexity I. Chair: Nikolay Vereshchagin
17:00–18:00 1 hour INVITED TALK: Merav Parter (Weizmann Institute of Science, Rehovot, Israel), Resilient Distributed Computation
18:00–18:30 30 min Svetlana Selivanova, Bit-Complexity of Systems of Linear Evolutionary Partial Differential Equations (joint work with Ivan Adrian Koswara, Gleb Pogudin and Martin Ziegler)
18:30–19:00 30 min Xuangui Huang, Average-case rigidity lower bounds (joint work with Emanuele Viola)
19:00–19:30 30 min Ridwan Syed, Upper Bounds on Communication in terms of Approximate Rank (joint work with Anna Gal)
Friday, July 2
Session 9: Graphs and Randomness. Chair: Dmitry Sokolov
14:00–15:00 1 hour INVITED TALK: Amin Coja-Oghlan (Goethe University, Frankfurt, Germany), "Belief Propagation"
15:00–15:30 30 min Johan M. M. van Rooij, A Generic Convolution Algorithm for Join Operations on Tree Decompositions
15:30–16:00 30 min Anuj Tawari, Dynamic Complexity of Expansion (joint work with Samir Datta and Yadu Vasudev)
16:00–16:30 30 min Siani Smith, Injective Colouring for H-Free Graphs (joint work with Jan Bok, Nikola Jedličková, Barnaby Martinand Daniel Paulusma)
16:30–17:00 30 min Coffee break
Session 10: Various topics in complexity II. Chair: Edward Hirsch
17:00–18:00 1 hour INVITED TALK: Toniann Pitassi (University of Toronto, Canada), How Hard is it to Refute a Random Unsatisfiable Formula?
18:00–18:30 30 min Austen Z. Fan, Dichotomy Result on 3-Regular Bipartite Non-negative Functions (joint work with Jin-Yi Cai)
18:30–19:00 30 min Shuo Pang, Large clique is hard on average for resolution
19:00–19:30 30 min Alexey Milovanov, Predictions and algorithmic statistics for infinite sequences