New Directions in Complexity Theory

复杂性理论的新方向

• 批准号: RGPIN-2017-06399
• 负责人: Pitassi, Toniann
• 金额: $ 4.37万
• 依托单位: University of Toronto
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2019
• 资助国家: 加拿大
• 起止时间: 2019-01-01 至 2020-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=690962
• 关键词: 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)通信的一个难度递增定理，该定理应该导致新的电路下界。其次，我想证明分支程序和比较电路的超二次下界，打破了自1960年S以来的长期存在的障碍。第三，在证明复杂性方面，我想证明割平面证明系统(以及相关的矩阵切割系统)的尺寸下界，并进一步发展我在Grochow开始的代数电路复杂性和证明复杂性之间的一个新的联系。使用这种方法，我希望证明AC0[p]-Frege系统的下界，这是证明复杂性方面的一个长期悬而未决的问题。*我的第二个研究领域旨在理解和开发由大数据产生的几个相互关联的问题的数学解决方案：隐私、公平性和自适应数据分析中的控制错误发现。第一个主题是数据隐私--如何在保护隐私的同时利用敏感但*重要的数据(如人口普查数据或医疗记录)造福社会？差异隐私是一种很有前途的方法，它已经产生了一个用于数据私有化的算法工具箱。我建议继续在这一领域工作，使这些方法在实践中更有用，并发现与稳定性重要的相关领域(如机器学习和自适应数据分析)的联系。一个相关的问题是公平：随着越来越多地依赖学习算法来做出决定，我们如何确保这些决定是公平的，而不是潜在偏见的结果？我们在其中一些问题(分类的公平性和自适应数据分析的泛化)上取得了部分进展，但才刚刚开始触及皮毛。