Reference number : GC-2017-Q1-03234, amendment number : , agreement type : G, recipient legal name : Pitassi, Toniann (University of Toronto), recipient country : CA, recipient province : nan, recipient city : Ontario, recipient postal code : nan, program name english : Discovery Grants Program - Individual, program name french : Programme de subventions à la découverte - individuelles, program purpose english : 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., program purpose french : 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., agreement title english : New Directions in Complexity Theory, agreement title french : New Directions in Complexity Theory, agreement number : RGPIN, agreement value : 300000.0, agreement start date : 2017-05-10, agreement end date : nan, description english : nan, description french : nan, expected results english : nan, expected results french : nan, additional information english : Grant or Award spanning more than one fiscal year. (2017-2018 to 2022-2023), additional information french : Subvention ou bourse octroyée s'appliquant à plus d'un exercice financier. (2017-2018 à 2022-2023), owner organization : nserc-crsng, owner organization title : Natural Sciences and Engineering Research Council of Canada | Conseil de recherches en sciences naturelles et en génie du Canada