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.

首字母缩略词“NP”描述了一类数学难题，它们可能有解决方案，也可能没有解决方案，但如果有解决方案，解决方案很容易验证（想想数独）。此类难题是数学背后许多进展的核心。为计算和通信提供动力的算法是信息时代社会活动的两大支柱，包括科学、商业、银行、安全等。虽然验证此类难题的解决方案很容易，但找到解决方案（或决定没有存在）是一个开放性问题，是当今数学中最伟大的开放性问题之一，被称为“P vs. NP 问题”。NP 类中的许多难题都被认为是非常困难的；这些问题被称为“NP”频谱的另一端是“可处理”问题的“P”类，即可以在“多项式时间内”解决的问题——效率的理论基准。不属于任一极端的 NP 问题（既不是 P 中的问题，也不是 NP 完全问题）被称为“NP 中间问题”。与已知的 NP 完全问题的大量重要问题和 P 中丰富的问题​​集相比，NP 问题的自然候选者很少。其中最突出的问题之一是图同构（GI）问题，它提出一个简单的问题，给定两个节点和链接网络，它们实际上是否相同（在重新标记节点之后）？PI 最近实现了结果关于 GI 的复杂性，三十年来一直被誉为突破性的，最好的界限是“适度指数”（Luks，1983），仍然处于棘手的领域，但并不像怀疑的“指数”那么糟糕。最近，PI 极大地降低了复杂性估计，降至“拟多项式”，这是可处理域“郊区”的复杂状态，借用斯科特的话。阿伦森的说法需要更深入地理解数学对象的对称性和正则性概念之间的相互作用，这两个相关概念之间的差距是“群论”的代数理论的名称。对称性；这个经典的数学分支为 PI 的工作提供了关键工具。PI 的结果在全球范围内引起了一定程度的兴趣，这在 PI 的职业生涯中是前所未有的，而且很少见任何单一结果都超出了核心研究群体的范围，并吸引了科学家、工程师、教育工作者和业余爱好者。 PI 关于该结果的第一次研讨会讲座吸引了大批观众来到芝加哥大学最大的演讲厅，并在推特上进行了现场直播。随后，PI 在国内外著名研究机构举办了马拉松研讨会和系列讲座，并在计算机科学、组合学、群论、量子计算等领域的会议上发表了演讲，其成果在《计算机科学》杂志上得到了广泛报道。这种兴趣证明了该问题的基础性质、结果的意想不到的强度以及该工作与数学和计算理论的多个领域的联系，而它在计算机科学之外的直接影响是在数学领域。代数组合学和渐近群论，它还解决并提出了与计算复杂性理论的基本哲学相关的问题。美国数学协会 (MAA) 邀请在联合数学会议（2018 年 1 月）强调了数学教育工作者对这项工作的兴趣，PI 在芝加哥大学数学学期的本科生研究体验 (REU) 网站上发表了演讲。 BSM）（PI 几十年前帮助建立的针对美国本科生的高评价海外留学项目），以及在圣路易斯举行的学生研讨会。英国圣安德鲁斯，由一位曾在芝加哥参加过 PI 讲座的学生安排，今年夏天，一名来自密歇根大学的学生将在 PI 的指导下在芝加哥学习。本段中提到的两名学生都是女性，这反映出 BSM 和芝加哥 REU 站点都特别努力招募合格的女性申请人。）基于他的作品的受欢迎程度，圣安德鲁斯大学的一位教授报告说，自从 PI 在圣安德鲁斯发表演讲以来，人们对群论的兴趣日益浓厚。 量子计算领域的研究人员继续致力于普及数学、计算理论和这些领域的密切互动。量子计算理论的核心问题是确定在量子模型中比在经典模型中可以更有效地解决的计算任务。这最重要的候选 NP 中间问题，整数因式分解和离散对数，可以使用“量子傅里叶变换”（QFT）在量子模型中有效解决，注意力转向 GI 作为一个受非阿贝尔版本 QFT 攻击的问题。虽然这些尝试尚未成功，但 PI 的工作现在提供了一种更细粒度的方法，其中的一些组件可能会激发对量子方法的搜索。量子计算观众，尽管 PI 的工作仅限于经典模型，但以 GI 成就的势头为基础，PI 将探索 NP 中间问题领域的新领域，并扩大他的议程以包括在内。结构对称是问题定义的一部分或有望为研究提供新方向的计算模型。第一类问题还包括规范形式、超图同构和群同构问题。作为某些类别的非显式结构（例如线性代码和置换群）的等价问题，第二类问题包括布尔函数的敏感性问题和“属性测试”模型中的问题，包括同态代码的本地列表解码。 ，这一领域由 Goldreich 和 Levin 关于 Hadamard 码的经典论文发起，最近由 MadhuSudan 和 hiss 倡导。算法和协作者群理论的接口问题预计将发挥关键作用除了 GI 研究中出现的组合问题之外，该项目还引发了线性代数中对称性与正则性差距的类似问题。GI 问题的一个重要扩展是这样的问题：人们能否找到规范形式与在新结果下测试同构一样有效 PI 期望超图的同构可以在顶点数和多项式的时间准多项式中进行测试。在边的数量上，提供了 GI 结果和 Luks 1999 年关于超图同构的结果之间的插值。 ​PI 在规范结构（“Split-or-Johnson 例程”）上的结果引发了对与数理逻辑联系的研究，建议。伯克利西蒙斯计算理论研究所最近举行的一次研讨会上，观众提出了这一观点。明确给定群的同构问题是 GI 拟多项式复杂性进一步发展的障碍；尽管有强大的代数机制，但在过去的几十年里并没有显着减少。​PI 的目的是在 2 类幂零群的关键情况下更好地理解这一障碍。​相关的等价问题。线性代码还可以通过 ElGamal 密码系统与密码学建立联系。

项目成果

List-Decoding Homomorphism Codes with Arbitrary Codomains

具有任意共域的列表解码同态码

• 发表时间: 2018-08
• 期刊: Leibniz international proceedings in informatics
• 作者: Babai, Laszlo;Black, Timothy;Wuu, Angela
• 通讯作者: Wuu, Angela

GROUP, GRAPHS, ALGORITHMS: THE GRAPH ISOMORPHISM PROBLEM

群、图、算法：图同构问题

• DOI: 10.1142/9789813272880_0183
• 发表时间: 2019-05
• 期刊: ICM 2018
• 作者: BABAI; LÁSZLÓ
• 通讯作者: LÁSZLÓ

Canonical form for graphs in quasipolynomial time: preliminary report

拟多项式时间图的规范形式：初步报告

• DOI: 10.1145/3313276.3316356
• 发表时间: 2019-06
• 期刊: STOC 2019: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing
• 作者: Babai; László
• 通讯作者: László