A fundamental goal of research in theory of computing is to understand the inherent computational complexity of specific problems. Progress in computational complexity is essential to establish limits to efficiency of algorithms, to understand the role of randomness in computation, and to build rigorous foundations for important areas such as cryptography and machine learning. This research program will study complexity questions in several combinatorial and algebraic models of computation. In particular, this research will develop lower bound techniques for these models based on linear algebra, communication complexity, and graph theory. Specific directions of research proposed are
1. Robustness Functions of Matrix Rank and their Applications: broad classes of functions that describe the robustness of the rank of a matrix have wide-ranging applications in computational complexity. In particular, several such functions can be used to attack lower bound problems on Boolean and algebraic circuits, decision trees, branching programs, and communication complexity. Known results by the PI and other researchers also indicate that spectral methods provide a unified approach to understanding rank robustness. This project proposes to extend these techniques and apply them to study combinatorial and algebraic complexity. Some alternative approaches that may overcome certain technical barriers faced by existing methods are also studied.
2. Multiparty Communication Complexity: This fundamental model has applications to the complexity theory of circuits, branching programs, and time-space trade-offs. Some weaker models of multiparty communication complexity have recently been investigated due to their continued relevance to circuit complexity and the apparent hope for stronger lower bounds. This project will study the relative strengths of the various multiparty models and their connections to complexity theory. General techniques such as discrepancy bounds and tensor rigidity will be explored to attack lower bound questions in these models. Recent discoveries of unexpected upper bounds in this area with critical consequences to some lower bound approaches motivate several new questions.
3. Graph Theoretic Approaches to Boolean Function Complexity: A combinatorial model that generalizes the models of both Boolean circuits and two-party communication complexity is obtained by considering computations on graphs. The research will explore the effectiveness of some graph-theoretic techniques to Boolean complexity using the framework of this model. In particular, various linear algebraic representations of graphs, with potential applications to other areas, will be studied to derive lower bounds on graph complexity that may have consequences to circuits. A unifying theme among these three topics is the use of communication complexity techniques to attack lower bound questions in computational complexity. Furthermore, each of these topics provides potential approaches to attack some long-standing open questions in computational complexity such as superlinear size lower bounds on log-depth circuits and ACC circuits. More generally, the research will advance the technology for lower bounds by targeting less restricted and/or more abstract models than those for which strong lower bounds are currently known. Techniques developed in these topics give rise to mathematical problems that have wider interest to other branches of theoretical computer science such as algorithms and cryptography as well as to subjects like linear algebra, combinatorics, and graph theory.
