- Email: firstname.lastname@example.org
- Thesis title: TBC
Proof Complexity looks at the complexity of theorem proving in various logical systems. In particular, for various proof systems, we are interested in the size of proofs relative to the size of the theorems they are proving. Interesting questions include proving new lower bounds on proof sizes in specific proof systems, and developing new techniques for proving such lower bounds. Proof complexity has connections to computational complexity theory, and strong enough answers to these questions would lead to new results in complexity theory.
Quantified Boolean Formulas (QBFs) consist of propositional formulas in which all the variables are quantified existentially or universally. There has been substantial progress in the proof complexity of QBFs recently, and I would like to build on this, as well as better understand the relationship between proof complexity of propositional formulas and that of QBFs.
Algebraic Proof Systems seek to prove propositional theorems, and QBFs, by translating the propositional statement into a set of polynomials. I am particularly interested in algebraic QBF proof systems, and extensions of these to more general polynomials, as well as the application of known algebraic results and techniques to proof complexity.
Research groups and institutes
- Algorithms and Complexity