New Directions in Complexity Theory

复杂性理论的新方向

• 批准号: RGPIN-2017-06399
• 负责人: Pitassi, Toniann
• 金额: $ 4.37万
• 依托单位: University of Toronto
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2020
• 资助国家: 加拿大
• 起止时间: 2020-01-01 至 2021-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=712221
• 关键词: 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开创的代数电路复杂性与证明复杂性之间的新联系。使用这种方法，我希望证明AC0[p]-Frege系统的下界，这是证明复杂性中一个长期存在的开放问题。