St. Petersburg Special Complexity Semester and Workshops

University Of California-San Diego, La Jolla CA

Investigators

Abstract

This project funds travel expenses for US graduate student participation in a Workshop on Algorithms in Communication Complexity, Property Testing, and Combinatorics in Moscow, Russia, April 9-13, 2016; a Workshop on Proof Complexity in St. Petersburg, Russia, May 15-20, 2016; and a Workshop on Low-Depth Complexity in St. Petersburg, Russia, May 21-25, 2016, as part of a special program in complexity theory at St. Petersburg during April-June 2016. The special semester and its tutorials and workshops will promote research in theoretical computer science and logic, areas with important applications for computer science. All three workshops include introductory tutorial lectures. The US graduate students will benefit from participation in the tutorial courses and workshops, and have a valuable opportunity to interact with and learn from an international community of researchers in complexity, and to promote their research and education training. Proof complexity has important connections to computational complexity, and to the highly successful computer-based theorem proving systems. Proof complexity has made substantial advances in the understanding the complexity of resolution theorem proving, and better understanding of algebraic proof systems. Low-depth complexity studies the complexity of functions that can be computed with low-depth Boolean and arithmetic circuits. Low-depth complexity is intimately connected with research into communication complexity, proof complexity, algorithms for NP-hard problems, learning and cryptography. Property testing and communication complexity deal with understanding what can be feasibly computed or approximated when given only part of the input, or when the input is shared among multiple parties. All these areas are of fundamental importance for a better understanding of algorithms and proof search. Main web page: http://en.chebyshev.spb.ru/complexity2016/ Workshop web pages: http://math.ucsd.edu/~sbuss/SPB_Workshops/AlgCPTC_1.html http://math.ucsd.edu/~sbuss/SPB_Workshops/ProofComp_1.html http://math.ucsd.edu/~sbuss/SPB_Workshops/LowDepth_1.html