|
|
|
|
Complexity Lower Bounds using
Linear Algebra
Foundations and Trends® in
Theoretical Computer Science
Volume 4 Issue 1–2
DOI: 10.1561/0400000011
Complexity Lower Bounds using
Linear Algebra
Satyanarayana V. Lokam
Microsoft Research India, Bangalore 560080, 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
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.
|
|
|
|
|
|
|
|
|