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

点击翻译按钮获取中文摘要

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.