Foundations and Trends® in Theoretical Computer Science > Vol 4 > Issue 1–2

Complexity Lower Bounds using Linear Algebra

By Satyanarayana V. Lokam, Microsoft Research India, India, satya@microsoft.com

 
Suggested Citation
Satyanarayana V. Lokam (2009), "Complexity Lower Bounds using Linear Algebra", Foundations and Trends® in Theoretical Computer Science: Vol. 4: No. 1–2, pp 1-155. http://dx.doi.org/10.1561/0400000011

Publication Date: 20 Jul 2009
© 2009 S. V. Lokam
 
Subjects
Computational aspects of communication,  Computational algebra
 

Free Preview:

Download extract

Share

Download article
In this article:
1 Introduction 
2 Matrix Rigidity 
3 Spectral Methods to Study Rank Robustness 
4 Sign-Rank and Other Complexity Measures of Sign Matrices 
5 Rank Robustness and Two-Party Communication Complexity 
6 Graph Complexity and Projective and Affine Dimensions of Graphs 
7 Span Programs: A Linear Algebraic Model of Computation 
8 Conclusions and Open Problems 
Acknowledgments 
References 

Abstract

We survey several techniques for proving lower bounds in Boolean, algebraic, and communication complexity based on certain linear algebraic approaches. The common theme among these approaches is to study robustness measures of matrix rank that capture the complexity in a given model. Suitably strong lower bounds on such robustness functions of explicit matrices lead to important consequences in the corresponding circuit or communication models. Many of the linear algebraic problems arising from these approaches are independently interesting mathematical challenges.

DOI:10.1561/0400000011
ISBN: 978-1-60198-242-1
168 pp. $99.00
Buy book (pb)
 
ISBN: 978-1-60198-243-8
168 pp. $150.00
Buy E-book (.pdf)
Table of contents:
1: Introduction
2: Matrix Rigidity
3: Spectral Methods to study Rank Robustness
4: Sign-Rank and other Complexity Measures of Sign Matrices
5: Rank Robustness and Two-Party Communication Complexity
6: Graph Complexity and Projective and Affine Dimensions of Graphs
7: Span Programs: A Linear Algebraic Model of Computation
8: Conclusions and Open Problems
Acknowledgements
References

Complexity Lower Bounds using Linear Algebra

While rapid progress has been made on upper bounds (algorithms), progress on lower bounds on the complexity of explicit problems has remained slow despite intense efforts over several decades. As is natural with typical impossibility results, lower bound questions are hard mathematical problems and hence are unlikely to be resolved by ad hoc attacks. Instead, techniques based on mathematical notions that capture computational complexity are necessary. Complexity Lower Bounds using Linear Algebra surveys several techniques for proving lower bounds in Boolean, algebraic, and communication complexity based on certain linear algebraic approaches. The common theme among these approaches is to study robustness measures of matrix rank that capture the complexity in a given model. Suitably strong lower bounds on such robustness functions of explicit matrices lead to important consequences in the corresponding circuit or communication models. Understanding the inherent computational complexity of problems is of fundamental importance in mathematics and theoretical computer science. Complexity Lower Bounds using Linear Algebra is an invaluable reference for anyone working in the field.

 
TCS-011