New Directions in 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.*****