St. Petersburg Special Complexity Semester and Workshops

该项目资助美国研究生参加2016年4月9日至13日在俄罗斯莫斯科举行的通信复杂性、性质测试和组合学中的算法研讨会；2016年5月15日至20日在俄罗斯圣彼得堡举行的证明复杂性研讨会；以及2016年5月21日至25日在圣彼得堡举行的低深度复杂性研讨会，作为2016年4月至6月在圣彼得堡举行的复杂性理论特别项目的一部分。特别学期及其教程和研讨会将促进理论计算机科学和逻辑的研究，这两个领域对计算机科学具有重要的应用。所有三个研讨会都包括入门教程课程。美国研究生将从参加辅导课程和研讨会中受益，并有一个宝贵的机会与国际复杂性研究人员交流和学习，并促进他们的研究和教育培训。Proof Complex与计算复杂性和非常成功的基于计算机的定理证明系统有重要联系。证明复杂性在理解归结定理证明的复杂性和更好地理解代数证明系统方面取得了实质性的进展。低深度复杂性研究可以用低深度布尔和算术电路计算的函数的复杂性。低深度复杂性与通信复杂性、证明复杂性、NP-Hard问题的算法、学习和密码学的研究密切相关。属性测试和通信复杂性涉及理解当只给出部分输入时，或者当输入在多方之间共享时，什么可以被可行地计算或近似。所有这些领域对于更好地理解算法和证据搜索都是至关重要的。主要网页：http://en.chebyshev.spb.ru/complexity2016/Workshop Web pages:http://math.ucsd.edu/~sbuss/SPB_Workshops/AlgCPTC_1.htmlhttp://math.ucsd.edu/~sbuss/SPB_Workshops/ProofComp_1.htmlhttp://math.ucsd.edu/~sbuss/SPB_Workshops/LowDepth_1.html

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.htmlhttp://math.ucsd.edu/~sbuss/SPB_Workshops/ProofComp_1.htmlhttp://math.ucsd.edu/~sbuss/SPB_Workshops/LowDepth_1.html