Grant: Canada Research Chairs
University of Toronto
$8,333.00
Observational Astrophysics
EF 2014-15
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
Canada Research Chairs
Bénéficiaire
Emplacement
Ontario, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data
Tel que publié
Application id
1000228106-2011
Name nom
Jayawardhana, Ray
Department département
Astronomy & Astrophysics
Organization id
31
Institution établissement
University of Toronto
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2014
Competition year année de concours
2011
Award amount
8333
Program id
CRC
Program name en
Canada Research Chairs
Program name fr
Chaires de recherche du Canada
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
9998
Committee name en
Canada Research Chair Selection Committee
Committee name fr
Comité de sélection des Chaires de recherche du Canada
Area of application code
9999
Area of application group en
Not available
Area of application group fr
Non disponible
Area of application en
Not available
Area of application fr
Non disponible
Research subject code
3200
Research subject group en
Astronomy and astrophysics
Research subject group fr
Astronomie et astrophysique
Research subject en
Astronomy and astrophysics
Research subject fr
Astronomie et astrophysique
Partie
0
Application title
Observational Astrophysics
Keyword
CRC
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.