New Directions in Complexity Theory

复杂性理论的新方向

• 批准号: RGPIN-2017-06399
• 负责人: Pitassi, Toniann
• 金额: $ 4.37万
• 依托单位: University of Toronto
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2018
• 资助国家: 加拿大
• 起止时间: 2018-01-01 至 2019-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=662262
• 关键词: New; Directions; Complexity; Theory

Computational complexity studies the inherent limits of computation, in terms of resources such as time, space, randomness, and nondeterminism, and how these resources are related. Proof complexity (the study of propositional proofs) is tightly connected to complexity theory: methods from communication complexity and circuit complexity have been heavily used to obtain proof complexity lower bounds, and conversely lower bounds in proof complexity can be used to rule out large classes of natural algorithms for solving optimization problems. I propose to attack several new directions in complexity theory and proof complexity. In recent work we have developed the hardness escalation method in communication complexity, and used this method to prove a variety of new circuit lower bounds (i.e., the best known monotone depth lower bounds, as well as the first exponential-size lower bounds for monotone span programs and secret sharing schemes.) This has been quite successful so far, and many problems remain to be studied. For example, we would like to prove a hardness escalation theorem for randomized (BPP) communication, which should lead to new circuit lower bounds. Secondly, I want to prove super-quadratic lower bounds for branching programs and comparator circuits, breaking the longstanding barrier from the 1960's. Thirdly, in proof complexity, I want to prove size lower bounds for Cutting Planes proof systems (and related matrix cut systems), and I want to further develop a new connection between algebraic circuit complexity and proof complexity that I initiated with Grochow. Using this approach, I hope to prove lower bounds for AC0[p]-Frege systems, a long-standing open problem in proof complexity.******My second research area aims to understand and to develop mathematical solutions for several inter-related issues that arise from large data: privacy, fairness, and controlling false discovery in adaptive data analysis. The first topic is data privacy -- how can sensitive but***important data (such as census data or medical records) be used for the good of society, while simultaneously protecting privacy? Differential privacy is a promising approach and has resulted in a toolbox of algorithms for privatizing data. I propose to continue to work in this area, to make the methods more usable in practice as well as to discover links to related areas where stability is important (such as machine learning, and adaptive data analysis). A related issue is fairness: with increasing reliance on learning algorithms to make decisions, how can we be sure that these decisions are fair and not a result of an underlying bias? We have made partial progress on some of these questions (fairness in classification, and generalization in adaptive data analysis) but have only begun to scratch the surface.*****

计算复杂性研究计算的内在限制，包括时间、空间、随机性和非确定性等资源，以及这些资源之间的关系。证明复杂性（对命题证明的研究）与复杂性理论紧密相连：通信复杂性和电路复杂性的方法被大量用于获得证明复杂性的下限，相反，证明复杂性的下限可以用来排除解决优化问题的大量自然算法。我建议攻击复杂性理论和证明复杂性的几个新方向。在最近的工作中，我们开发了通信复杂性的硬度升级方法，并使用该方法证明了各种新的电路下界（即，最著名的单调深度下界，以及单调跨度程序和秘密共享方案的第一指数大小下界。这一做法迄今已取得了相当的成功，但仍有许多问题有待研究。例如，我们想证明随机（BPP）通信的硬度升级定理，这应该会导致新的电路下界。其次，我想证明分支程序和比较器电路的超二次下界，打破了20世纪60年代的长期障碍。第三，在证明复杂性方面，我想证明切割平面证明系统（以及相关的矩阵切割系统）的大小下限，我想进一步发展代数电路复杂性和证明复杂性之间的新联系，这是我与Grochow一起发起的。使用这种方法，我希望证明AC 0 [p]-Frege系统的下界，这是一个长期存在的证明复杂性的公开问题。我的第二个研究领域旨在理解和开发数学解决方案，解决大数据中出现的几个相互关联的问题：隐私，公平性和自适应数据分析中的控制错误发现。第一个主题是数据隐私--如何在保护隐私的同时，将敏感但重要的数据（如人口普查数据或医疗记录）用于社会利益？差分隐私是一种很有前途的方法，并导致了私有化数据的算法工具箱。我建议继续在这一领域工作，使这些方法在实践中更有用，并发现与稳定性很重要的相关领域（如机器学习和自适应数据分析）的联系。一个相关的问题是公平性：随着越来越多地依赖学习算法来做出决策，我们如何确保这些决策是公平的，而不是潜在偏见的结果？我们已经在其中一些问题上取得了部分进展（分类的公平性和自适应数据分析的泛化），但只是开始触及表面。