Complexity theory seeks to describe the computational resources which are both necessary and sufficient to resolve a given problem or class of problems in theoretical computer science. The complexity can be measured both in terms of the run-time necessary to resolve the problem (as in algorithmic complexity) or in terms of the proof length for certifying a desired statement, as in proof complexity.
The proposed research follows a two-pronged approach to resolving tight bounds for problems in proof and algorithmic complexity. In the first research theme, the project applies structural graph techniques to give exact characterizations of the classes of input which are algorithmically feasible under a given model of computation for a selection of graph problems. In the second research theme, the project applies algebraic techniques to give new super-polynomial bounds to the necessary proof length for tautologies in various proof systems. The approach to each theme is designed so that progress on one will give new tools and techniques which can be applied to the other.
We briefly describe the potential impact of the proposed research.
1. Perhaps the most significant question in complexity theory is how to prove given complexity classes of problems are distinct (the question of whether P is not equal NP is perhaps the most famous example of a question of this kind, but the relationship between other complexity classes based on randomized algorithms or quantum algorithms remain important open questions). The proposed work under each theme makes progress on these questions.
The exact characterizations of the hard instances of given algorithmic problem under Theme 1 will provide a further refinement to the broader complexity theoretic picture and offer insight as to the relationships between the general classes of problems. Furthermore, exactly characterizing the hard instances of a problem identifies a given complexity class by a class of graphs. It may be possible to prove relationships between the corresponding complexity classes by proving relationships between the graph classes. This would represent a wholly new approach to proving relationships between complexity classes.
The proposed work under Theme 2 provides a more direct approach on proving the inequality of given complexity classes; successfully resolving the proposed research in the theme would strengthen the known techniques which have already proven successful in [BIKPPW92].
2. A number of important open conjectures remain in graph theory about classes defined by excluding a fixed graph under a given containment relationship. One example is a conjecture of Lescure and Meynial which related the chromatic number of a graph and excluded clique immersions [LM1989]. In 2016, Wollan along with two visiting students to Sapienza University, Le from University of Lyon and Gauthier from Princeton University, proved the best-known bounds on the relationship [LGW2017]. Further progress on the conjecture hinges upon the kind of exact characterizations of graph classes which are the proposed topic of study in Theme 1, and so progress under this theme should yield further results in discrete mathematics and graph theory.
3. Under the proposed work of Theme 2, the approach shaped by [GP14, LIV15] is innovative and gives some hope that proving lower bounds for H-systems may not to be completely out of the reach of the known lower bound techniques. In any case, no significant lower bound is showed in either of [GP14, LIV15]. Hence any lower bound for any non-trivial subsystem of H which would employ this approach and use the partial derivative method applied to non-commutative formulas or simpler circuits would be already an important result that would strengthen the importance of such approach as a method to prove lower bounds for proof systems.
[BIKPPW92] P.Beame, R. Impagliazzo, J. Krajícek, T. Pitassi, P. Pudlák, A. Woods. STOC 1992: 200-220
[GP14] J. A. Grochow, T. Pitassi. FOCS 2014: 110-119
[LGW2017] N. Le, G. Gauthier, P. Wollan, "Forcing clique immersions through chromatic number" submitted manuscript.
[LIW15] F. Li, I. Tzameret, Z. Wang. Conf. Comp. Complexity 2015: 412-432
[LM1989] F. Lescure, H. Ann. Disc. Math. 41:325-331 (1989)