St. Petersburg Special Complexity Semester and Workshops

圣彼得堡特殊复杂性学期和研讨会

• 批准号: 1565931
• 负责人: Samuel Buss
• 金额: $ 1.5万
• 依托单位: University of California-San Diego
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-02-01 至 2017-01-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1565931&HistoricalAwards=false
• 关键词: St.; Petersburg; Special; Complexity; Semester

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

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