Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

University of Toronto

$78,000.00

New Directions in Proof Complexity and Communication Complexity

EF 2016-17

Résumé
The central problem in computational complexity is to understand which computational problems can be solved efficiently, and to develop the most efficient algorithms for such problems. The question of whether the NP-complete problems have efficient solutions, known as the P versus NP question, is the driving force behind my research. It is a beautiful and deep question, and its solution would have profound consequences. One promising direction aimed at ultimately resolving the P versus NP question is propositional proof complexity. The central problem in propositional proof complexity is to understand which tautologies have efficient proofs in standard proof systems. Cook and Reckhow observed in 1974 that the question of whether there is a proof system giving rise to short proofs of all tautologies is equivalent to whether NP equals coNP, and therefore is closely connected to the P versus NP question. Proof complexity also gives a methodology for understanding natural classes of algorithms for solving NP-hard problems. I propose to develop methods for proving lower bounds for various proof systems and classes of algorithms, and to use these methods to obtain new insight and new lower bounds and inapproximability results for realistic models of computation. A fundamental tool in this endeavor is communication complexity; thus new communication models and techniques are a key aspect of this proposal.
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
228106-2012
Name nom
Pitassi, Toniann
Department département
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
2012
Award amount
78000
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
1207
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Information, computer and communication technologies
Area of application fr
Technologie de l'information, des ordinateurs et des réseaux de communications
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
5
Nb partie
5
Application title
New Directions in Proof Complexity and Communication Complexity
Keyword
NSERC
Application summary
The central problem in computational complexity is to understand which computational problems can be solved efficiently, and to develop the most efficient algorithms for such problems. The question of whether the NP-complete problems have efficient solutions, known as the P versus NP question, is the driving force behind my research. It is a beautiful and deep question, and its solution would have profound consequences. One promising direction aimed at ultimately resolving the P versus NP question is propositional proof complexity. The central problem in propositional proof complexity is to understand which tautologies have efficient proofs in standard proof systems. Cook and Reckhow observed in 1974 that the question of whether there is a proof system giving rise to short proofs of all tautologies is equivalent to whether NP equals coNP, and therefore is closely connected to the P versus NP question. Proof complexity also gives a methodology for understanding natural classes of algorithms for solving NP-hard problems. I propose to develop methods for proving lower bounds for various proof systems and classes of algorithms, and to use these methods to obtain new insight and new lower bounds and inapproximability results for realistic models of computation. A fundamental tool in this endeavor is communication complexity; thus new communication models and techniques are a key aspect of this proposal.