Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

University of Toronto

$43,000.00

Average-Case Lower Bounds in Boolean Circuit Complexity

EF 2016-17

Résumé
Complexity Theory studies the nature and limits of efficient computation. The ultimate goals are lower bounds showing that fundamental problems, such as CLIQUE and STCONN, cannot be solved with limited computational resources, such as polynomial time or logarithmic memory. The subfield of Circuit Complexity seeks to prove lower bounds in combinatorial models of computation. Among these models, Boolean circuits (composed of AND, OR and NOT gates) are the most elemental and important, as they offer a concrete path to resolving the P versus NP question: one need only prove a super-polynomial circuit-size lower bound for the CLIQUE problem (or any other problem in NP). However, after over 60 years of effort, the strongest known lower bounds are only linear. With the aim of developing sharper insights and techniques, the majority of the research in Circuit Complexity has focused on restricted classes of Boolean circuits (such as formulas, bounded-depth circuits, and monotone circuits). Following a burst of seminal lower bounds in the 80's and 90's, progress slowed as the existing techniques appeared to reach their limits. The ""Natural Proofs barrier"" of Razborov and Rudich (1997) identifies a formal roadblock to further progress by showing that lower bounds against more powerful classes of Boolean circuits can only proceed from techniques that are honed to specific hard-to-compute functions, while avoiding the generic properties shared by almost all functions. This research proposal aims for a major advance in Circuit Complexity through a set of new techniques tailored to fundamental problems including CLIQUE and STCONN. One promising approach, introduced in previous work of the author, provides a combinatorial explanation of why small Boolean formulas fail to detect long paths in Erdos-Rényi random graphs. This approach has already produced groundbreaking lower bounds. The proposed research will pursue a sequence of next steps, with the ambitious goal of proving a super-polynomial lower bound against Boolean formulas. This would resolve a significant open problem in Complexity Theory (separating NC1 from P). Alongside this ambitious goal, this proposal explores other promising directions of research in Boolean circuit complexity and connections to areas such as proof complexity and communication complexity.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Ontario, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
RGPIN-2016-06467
Name nom
Rossman, Benjamin
Department département
Computer Science (St. George Campus) - Computer Science (St. George Campus)
Organization id
31
Institution établissement
University of Toronto
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2016
Competition year année de concours
2016
Award amount
43000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
1200
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Advancement of knowledge
Area of application fr
Avancement des connaissances
Research subject code
2703
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Complexity
Research subject fr
Complexité
Partie
1
Nb partie
5
Application title
Average-Case Lower Bounds in Boolean Circuit Complexity
Keyword
NSERC
Application summary
Complexity Theory studies the nature and limits of efficient computation. The ultimate goals are lower bounds showing that fundamental problems, such as CLIQUE and STCONN, cannot be solved with limited computational resources, such as polynomial time or logarithmic memory. The subfield of Circuit Complexity seeks to prove lower bounds in combinatorial models of computation. Among these models, Boolean circuits (composed of AND, OR and NOT gates) are the most elemental and important, as they offer a concrete path to resolving the P versus NP question: one need only prove a super-polynomial circuit-size lower bound for the CLIQUE problem (or any other problem in NP). However, after over 60 years of effort, the strongest known lower bounds are only linear. With the aim of developing sharper insights and techniques, the majority of the research in Circuit Complexity has focused on restricted classes of Boolean circuits (such as formulas, bounded-depth circuits, and monotone circuits). Following a burst of seminal lower bounds in the 80's and 90's, progress slowed as the existing techniques appeared to reach their limits. The ""Natural Proofs barrier"" of Razborov and Rudich (1997) identifies a formal roadblock to further progress by showing that lower bounds against more powerful classes of Boolean circuits can only proceed from techniques that are honed to specific hard-to-compute functions, while avoiding the generic properties shared by almost all functions. This research proposal aims for a major advance in Circuit Complexity through a set of new techniques tailored to fundamental problems including CLIQUE and STCONN. One promising approach, introduced in previous work of the author, provides a combinatorial explanation of why small Boolean formulas fail to detect long paths in Erdos-Rényi random graphs. This approach has already produced groundbreaking lower bounds. The proposed research will pursue a sequence of next steps, with the ambitious goal of proving a super-polynomial lower bound against Boolean formulas. This would resolve a significant open problem in Complexity Theory (separating NC1 from P). Alongside this ambitious goal, this proposal explores other promising directions of research in Boolean circuit complexity and connections to areas such as proof complexity and communication complexity.