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

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

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.