Special Year Workshops on Combinatorics and Complexity

组合学和复杂性特别年研讨会

• 批准号: 1742283
• 负责人: Madhu Sudan
• 金额: $ 9.6万
• 依托单位: Harvard University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2017
• 资助国家: 美国
• 起止时间: 2017-09-01 至 2018-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1742283&HistoricalAwards=false
• 关键词: Special; Year; Workshops; Combinatorics; Complexity

The Special Year Workshops on Combinatorics and Complexity award supports four workshops at the interface of the two fields during the periods of 2-6 October 2017, 13-17 November 2017, 5-9 February 2018, and 9-13 April 2018 at the Harvard Center of Mathematical Sciences and Applications (CMSA) in Cambridge, Massachusetts. Combinatorics and Computational Complexity have enjoyed a rich history of interaction leading to many significant developments in the two fields, such as the theories of NP-completeness, expander graphs, pseudorandomness, and property testing. Lately these fields have seen many new points of intersection such as in the development of the polynomial method (used, for example, in recent advances on the cap-set problem as well as in development of optimal list-decodable codes), the method of interlacing families of polynomials (yielding Ramanujan graphs and the resolution of the Kadison-Singer problem), and the theory of randomness extractors (yielding explicit constructions of Ramsey graphs. The base funding for the workshops will be provided by the Harvard CMSA and will enable the participation of senior visitors and a core group of leaders in the fields. Additional funding provided by this award will support the travel and local arrangements of graduate students, postdocs, junior researchers, members of underrepresented groups, and those without other forms of support. Topics to be covered by the workshops include: (1) Additive Combinatorics (organized by Ben Green, Swastik Kopparty, Ryan O'Donnell and Tamar Zeigler). (2) Algebraic Methods in Combinatorics (organized by Zeev Dvir, Larry Guth and Shubhangi Saraf). (3) Probabilistic and Extremal Combinatorics (organized by David Conlon and Benjamin Sudakov) and (4) Coding and Information Theory (organized by Alexander Barg, Venkatesan Guruswami, and Mary Wootters). Further information on the workshops and other special year activities may be found at http://cmsa.fas.harvard.edu/combinatorics/.

组合学和复杂性特别年度研讨会奖励于2017年10月2日至6日、2017年11月13日至17日、2018年2月5日至9日和2018年4月9日至13日在哈佛大学举办的四个研讨会，涵盖两个领域的交叉点位于马萨诸塞州剑桥的数学科学与应用中心 (CMSA)。 组合学和计算复杂性有着丰富的相互作用历史，导致这两个领域取得了许多重大发展，例如 NP 完备性、扩展图、伪随机性和属性测试的理论。 最近，这些领域出现了许多新的交叉点，例如多项式方法的开发（例如，在上限集问题的最新进展以及最优列表可解码代码的开发中使用）、交错多项式族（产生 Ramanujan 图和 Kadison-Singer 问题的解决），以及随机性提取器理论（产生 Ramsey 图的显式构造）。研讨会的基础资金该奖项将由哈佛 CMSA 提供，并使高级访问者和该领域的核心领导者能够参与其中。该奖项提供的额外资金将支持研究生、博士后、初级研究人员、代表性不足的成员的旅行和当地安排。研讨会涵盖的主题包括： (1) 加法组合学（由 Ben Green、Swastik Kopparty、Ryan O'Donnell 和 Tamar Zeigler 组织）。组合学中的代数方法（由 Zeev Dvir、Larry Guth 和 Shubhangi Saraf 组织）。 (3) 概率和极值组合学（由 David Conlon 和 Benjamin Sudakov 组织）和 (4) 编码和信息理论（由 Alexander Barg、Venkatesan Guruswami 和 Mary Wootters 组织）。有关研讨会和其他特别年度活动的更多信息，请访问 http://cmsa.fas.harvard.edu/combinatorics/。