Grant: Discovery Grants Program - Individual
Université de Montréal
$82,000.00
Lower bounds and derandomizations for branching programs
FY 2023-24
Summary
GENERAL:The long-term goal of my research program is to help elucidating the structure of the complexity class P of efficiently solvable problems. In particular, can every problem in P be solved using a logarithmic amount of memory? This question predates the P versus NP question and hints at the main shortcoming of complexity theory: despite intensive efforts by a generation of researchers, no truly satisfactory lower bounds on the complexity of problems within the complexity class NP, let alone the class P, are known.SPECIFICS:In the next 5 years I will return to the study of branching programs, a computation model known to capture the memory resource. I first propose to concentrate on trying to explain why no branching program size lower bound better than quadratic is known for problems in NP. Obstacles to obtaining lower bounds on computational resources for solving a problem have been identified before. One influential notion of such an obstacle was developed by Razborov and Rudich in 1997: strong lower bounds obtained by means of what these authors named "natural proofs" were shown to rule out the existence of objects called efficient pseudorandom number generators, widely believed to exist. The empirical fact that many of our best current complexity lower bounds were obtained by natural proofs is thus an obstacle in the above sense.The last 25 years have seen much research on pseudo-randomness in the context of memory-bounded computation. I am hoping to draw from this work in order to define the equivalent of natural proofs against (say) cubic size lower bounds for branching programs and to derive unlikely derandomization consequences. I will explore possible variants of natural proofs involving the recently introduced notion of pseudo-deterministic computation. I will investigate derandomization of bounded-width branching programs under the guidance of algebraic automata theory. I will consider probabilistic variants of restricted branching programs (such as monotone or incremental) and analyse their expressivity and their derandomizations. SIGNIFICANCE:Rigorously proving computational complexity lower bounds can be very useful. A famous example arises in cryptography, where the current lack of computational hardness proofs prevents ruling out that a clever individual or organization might break into communication channels thought to be secure. Other examples follow from a 30-year-old discovery by now exploited extensively: if certain computational problems could be proved hard, then tools to construct pseudorandom number generators would follow; such tools in turn could serve to transform known efficient probabilistic algorithms into equally efficient deterministic (hence freed from the uncertainty that accompanies the reliance on random bits) algorithms. Searching for obstacles to proving lower bounds could as well suggest new ways to improve existing algorithms.
Program
Discovery Grants Program - Individual
Recipient
Location
Quebec, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
RGPIN-2018-04500
Name nom
McKenzie, Pierre
Department département
DIRO
Organization id
63
Institution établissement
Université de Montréal
Province en
Québec
Province fr
Québec
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2023
Competition year année de concours
2018
Award amount
82000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR LA DÉCOUVERTE
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
802
Area of application group en
Information and communication services
Area of application group fr
Services d'information et de télécommunications
Area of application en
Information systems and technology
Area of application fr
Systèmes d'information et technologie de l'information
Research subject code
9999
Research subject group en
Not available
Research subject group fr
Not available
Research subject en
Non disponible
Research subject fr
Non disponible
Application title
Lower bounds and derandomizations for branching programs
Keyword
boolean circuits; branching programs; completeness; complexity classes; computational complexity; resource lower bounds; space resource; Turing machine
Application summary
GENERAL:The long-term goal of my research program is to help elucidating the structure of the complexity class P of efficiently solvable problems. In particular, can every problem in P be solved using a logarithmic amount of memory? This question predates the P versus NP question and hints at the main shortcoming of complexity theory: despite intensive efforts by a generation of researchers, no truly satisfactory lower bounds on the complexity of problems within the complexity class NP, let alone the class P, are known.SPECIFICS:In the next 5 years I will return to the study of branching programs, a computation model known to capture the memory resource. I first propose to concentrate on trying to explain why no branching program size lower bound better than quadratic is known for problems in NP. Obstacles to obtaining lower bounds on computational resources for solving a problem have been identified before. One influential notion of such an obstacle was developed by Razborov and Rudich in 1997: strong lower bounds obtained by means of what these authors named "natural proofs" were shown to rule out the existence of objects called efficient pseudorandom number generators, widely believed to exist. The empirical fact that many of our best current complexity lower bounds were obtained by natural proofs is thus an obstacle in the above sense.The last 25 years have seen much research on pseudo-randomness in the context of memory-bounded computation. I am hoping to draw from this work in order to define the equivalent of natural proofs against (say) cubic size lower bounds for branching programs and to derive unlikely derandomization consequences. I will explore possible variants of natural proofs involving the recently introduced notion of pseudo-deterministic computation. I will investigate derandomization of bounded-width branching programs under the guidance of algebraic automata theory. I will consider probabilistic variants of restricted branching programs (such as monotone or incremental) and analyse their expressivity and their derandomizations. SIGNIFICANCE:Rigorously proving computational complexity lower bounds can be very useful. A famous example arises in cryptography, where the current lack of computational hardness proofs prevents ruling out that a clever individual or organization might break into communication channels thought to be secure. Other examples follow from a 30-year-old discovery by now exploited extensively: if certain computational problems could be proved hard, then tools to construct pseudorandom number generators would follow; such tools in turn could serve to transform known efficient probabilistic algorithms into equally efficient deterministic (hence freed from the uncertainty that accompanies the reliance on random bits) algorithms. Searching for obstacles to proving lower bounds could as well suggest new ways to improve existing algorithms.