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

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

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.