权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

AF: Small: Symmetry and regularity in the theory of computing

AF：小：计算理论中的对称性和规律性

基本信息

批准号：
1718902
负责人：
Laszlo Babai
金额：
$ 45万
依托单位：
University of Chicago
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2017
资助国家：
美国
起止时间：
2017-09-01 至 2021-08-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1718902&HistoricalAwards=false
关键词：
AF Small Symmetry regularity theory

项目摘要

The acronym "NP" describes the class of mathematical puzzles that may or may not have a solution but if they do, the solution is easy to verify. (Think of Sudoku.) Such puzzles are at the heart of much of the progress behind the algorithms that power computation and communication, the twin pillars of societal activity in the information age, including science, commerce, banking, security, etc. While verifying a solution to such puzzles is easy, just how difficult it is to find a solution (or decide that none exists) is an open question, one of the great open problems of mathematics today, known as the "P vs. NP problem. Many puzzles in the class NP are known to be as hard as they can get; these problems are called "NP-complete." At the other end of the spectrum is the class "P" of "tractable" problems, i.e., problems solvable in "polynomial time" -- a theoretical benchmark of efficiency. NP-problems that do not belong to either extreme (neither in P nor NP-complete) are called "NP-intermediate." In contrast to the vast collection of important problems known to be NP-complete and the rich set of problems in P, there are very few natural candidates for NP-intermediateness. One of the most prominent among these is the Graph Isomorphism (GI) problem that asks the simple question, given two networks of nodes and links, are they in effect the same (after relabeling the nodes)?The PI has recently achieved a result on the complexity of GI that has been hailed as a breakthrough. For three decades, the best bound was "moderately exponential" (Luks, 1983), still far out in the intractable domain, but not as bad as "exponential," the suspected complexity of NP-complete problems. Recently the PI dramatically reduced the complexity estimate, down to "quasipolynomial," a complexity status "in the suburbs" of the tractable domain, borrowing Scott Aaronson's phrase. The result required a deeper understanding of the interplay between the notions of symmetry and regularity of mathematical objects. The gap between these two related notions is the essence of the GI problem. "Group theory" is the name of the algebraic theory of symmetry; this classical branch of mathematics has provided the key tools for the PI's work.The PI's result generated a measure of interest across the globe, unprecedented in the PI's career and seldom seen in connection with any single result; it extended beyond the core research communities and has fascinated scientists, engineers, educators, and amateurs. The PI's first seminar lecture about the result drew an overflow audience to the largest lecture theater at the University of Chicago and was live tweeted to a global audience. Subsequently the PI gave marathon seminars and lecture series at eminent research institutions coast to coast and overseas and lectured at conferences in CS, combinatorics, group theory, quantum computing. The result was widely reported in the popular science press. This interest attests to the foundational nature of the problem, the unexpected strength of the result, and the connection of the work to multiple areas of mathematics and computation theory. While its immediate impact outside CS is in mathematics, notably in algebraic combinatorics and asymptotic group theory, it also addresses as well as raises questions pertinent to the underlying philosophy of computational complexity theory. Invitation by the Mathematical Association of America (MAA) to deliver an address at the Joint Mathematics Meetings (January 2018) underlines the interest of mathematics educators in the work.Groups of undergraduates have shown interest. The PI gave presentations at a Research Experiences for Undergraduates (REU) Site at the University of Chicago, at Budapest Semesters in Mathematics (BSM) (a highly-rated study-abroad program for American undergraduates the PI helped found decades ago), and a student seminar in St. Andrews, U.K., arranged by a student who previously attended the PI's lecture at Chicago. This year, a student from the Univ. of Michigan who was among the PI's BSM audience will study under the PI's mentorship in Chicago over the summer. (Note: both students mentioned in this paragraph are female, a reflection of the fact that both BSM and the Chicago REU Site make a special effort to recruit qualified female applicants.) Building on the popularity of his work, the PI continues his outreach with the larger goal of popularizing mathematics, the theory of computing, and the close interaction of these fields. A professor at St. Andrews reported increased interest in group theory since the PI's presentation there.Researchers in the field of quantum computing have also shown interest in the PI's work. The central problem of the theory of quantum computation is to identify computational tasks that can be solved more efficiently in the quantum model than in the classical model. Following Shor's celebrated paper that demonstrated that two of the most important candidate NP-intermediate problems, factoring integers and discrete logarithm, can be solved efficiently in the quantum model using "quantum Fourier transform" (QFT), attention turned to GI as a problem to be attacked by a nonabelian version of QFT. While these attempts have as yet not been successful, the PI's work now provides a more fine-grained approach, some components of which may motivate a search for a quantum approach. The PI has been invited to address quantum computing audiences, even though the PI's work is limited to the classical model.Building on the momentum of the GI accomplishment, the PI will explore new frontiers in the area of NP-intermediate problems, as well as broaden his agenda to include models of computation where structural symmetry is either part of the problem definition or is expected to give a new direction to the investigations. Problems of the first type include canonical forms, hypergraph isomorphism, and the group isomorphism problem, as well as the equivalence problem for certain classes of non-explicit structures such as linear codes and permutation groups. Problems of the second type include the sensitivity problem for Boolean functions and problems in the "property testing" model, including local list-decoding of homomorphism codes, an area initiated by the classic paper of Goldreich and Levin on Hadamard codes and more recently championed by Madhu Sudan and his collaborators.Problems at the interface of algorithms and group theory are expected to play a key role in the entire project. Beyond the combinatorial problems that have arisen from the study of GI, the project leads to analogous questions of the symmetry vs. regularity gap in linear algebra.An important extension of the GI problem is the question, can one find canonical forms as efficiently as testing isomorphism under the new result. The PI expects that isomorphism of hypergraphs can be tested in time quasipolynomial in the number of vertices and polynomial in the number of edges, providing an interpolation between the GI result and a 1999 result of Luks on hypergraph isomorphism. The PI's results on canonical structures ("Split-or-Johnson routine") invite a study of connections to mathematical logic, suggested by audience members at a recent workshop at the Simons Institute for the Theory of Computing in Berkeley.The isomorphism problem for explicitly given groups represents a barrier to further progress on GI; its quasipolynomial complexity has not been significantly reduced over the past several decades, in spite of the availability of powerful algebraic machinery. The PI aims to gain a better understanding of this barrier in the critical case of nilpotent groups of class 2. The related equivalence problem for linear codes may also have connections to cryptography through the ElGamal cryptosystem.