Monotone computations, bracket formulas, and liftings theorems

Par

Dmitry Sokolov

École Polytechnique Fédérale de Lausanne

Mercredi 9 avril 2025, 10:30-11:30 EST, Salle 6214

Pavillon André-Aisenstadt, Université de Montréal, 2920 Chemin de la Tour

Abstract: Suppose some function can be computed in time T on one computer. Can we parallelize the computational process? Namely, can we compute our function in time T/K if we have access to K computers? In this talk, we consider ideas behind one of my recent results that informally can be stated in the following way: "monotone computations cannot be efficiently parallelized". We discuss the result itself and the machinery behind it, which involves several areas: proof, circuit, and communication complexity.

Bio: In 2015 Dmitry completed his Ph.D. at Steklov Institute of Mathematics at St. Petersburg in Russia under the supervision of Edward Hirsch and Dmitry Itsykson. In 2017 he was a postdoc at KTH University in Stockholm hosted by Jakob Nordstrom, a postdoc at Lund University and a visitor at University of Copenhagen. In 2020 he got an Associate Professor position at St. Petersburg State University in Russia. In 2022 he moved to EPFL as a researcher. His research interests are concentrated in complexity theory, discrete mathematics, and math logic. It mainly focuses on proof, communication, and circuit complexity.