Supplemental Funding for a Conference on: Combinatorics, groups, algorithms, and complexity; March 2010; Columbus, OH

会议的补充资金：组合学、群、算法和复杂性；

• 批准号: 0946649
• 负责人: Akos Seress
• 金额: $ 2万
• 依托单位: Ohio State University Research Foundation -DO NOT USE
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2009
• 资助国家: 美国
• 起止时间: 2009-12-01 至 2010-11-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0946649&HistoricalAwards=false
• 关键词: Supplemental; Funding; Conference; Combinatorics; groups

ABSTRACTPrincipal Investigator: Seress, Akos Proposal Number: DMS - 0946649Institution: Ohio State University Research Foundation Title: Supplemental Funding for a Conference on: Combinatorics, groups, algorithms, and complexityA conference on ``Combinatorics, groups, algorithms, and complexity'' will be held on March 21-24, 2010, at The Ohio State University. The objective of the conference is to provide a forum to explore the manifold interactions between the branches of mathematics and computer science named in the title. Ever since the inception of the polynomial-time paradigm in the late 1960s, theoretical computer science has been a major consumer of concepts and techniques developed in combinatorics, and, conversely, the conceptual frameworks developed in algorithms and complexity theory have transformed much of combinatorics. As the relatively young areas of combinatorics and complexity theory have matured in the past decades, algebraic methods have become increasingly relevant to each. Group theory has played an important role both as a source of techniques and as a subject of rigorous algorithmic study, with the subarea of asymptotic group theory leading the way in the interaction.The subareas to be covered include but are not limited to arithmetic combinatorics, asymptotic group theory, automorphism groups of combinatorial structures, vertex-transitive graphs, expanders, combinatorial models of computation (circuits, decision trees, communication complexity, etc.), probabilistically checkable proofs and approximation algorithms, derandomization, algebraic graph theory, abelian sandpiles, algorithmic problems in combinatorics and algebra, mathematical problems motivated by problems in algorithms and complexity theory. This interdisciplinary conference will focus on the crossfertilization between the areas of combinatorics, group theory, algorithms, and complexity theory, the first two being areas of mathematics and the last two - areas of theoretical computer science. Each of these areas has significantly contributed to the development of the others over the past decades. It is expected that the conference will increase our understanding of the deeper mathematical issues that underlie the connections between these areas, with implications to each of the areas concerned. A particular occasion for this meeting will be the 60th birthday of Laszlo Babai whose work has been influential in developing connections between these fields.

主要调查者：Seress，Akos提案编号：DMS-0946649机构：俄亥俄州立大学研究基金会标题：为一次会议的补充资金：组合学、群、算法和复杂性将于2010年3月21-24日在俄亥俄州立大学举行`组合学、群、算法和复杂性‘’会议。会议的目的是提供一个论坛，探讨标题中提到的数学和计算机科学分支之间的多种相互作用。自从20世纪60年代末多项式时间范式问世以来，理论计算机科学一直是组合学中发展的概念和技术的主要消费者，相反，算法和复杂性理论中发展起来的概念框架已经改变了许多组合学。随着组合数学和复杂性理论相对较年轻的领域在过去几十年中成熟起来，代数方法变得越来越与两者相关。群论既是技术的来源，也是严格算法研究的主题，其中渐近群论的子领域在相互作用中处于领先地位。所涵盖的子领域包括但不限于算术组合学、渐近群论、组合结构的自同构群、顶点传递图、扩展器、计算的组合模型(电路、决策树、通信复杂性等)、概率可查证明和近似算法、去随机化、代数图论、交换沙堆、组合学和代数中的算法问题、由算法和复杂性理论中的问题引发的数学问题。这次跨学科会议将聚焦于组合学、群论、算法和复杂性理论领域之间的交叉融合，前两个领域是数学领域，最后两个领域是理论计算机科学领域。在过去几十年中，这些领域中的每一个都对其他领域的发展作出了重大贡献。预计这次会议将增进我们对这些领域之间联系的更深层次的数学问题的理解，并对每一个有关领域产生影响。这次会议的一个特别场合将是Laszlo Babai的60岁生日，他的工作在发展这些领域之间的联系方面产生了影响。