Complexity Lower Bounds using Linear Algebra
Foundations and Trends® in Theoretical Computer Science · 2009-10-20 · 4 (1-2) · 1-155
DOI: 10.1561/0400000011 ↗At a glance
Journal article in Foundations and Trends® in Theoretical Computer Science, published online on 2009-10-20. Written by Satyanarayana V. Lokam. Cited 56 times so far (Crossref); 104 references.
Abstract (original language)
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.
Cite
APA
Lokam, S. V. (2009). Complexity Lower Bounds using Linear Algebra. Foundations and Trends® in Theoretical Computer Science, 4(1-2), 1-155. https://doi.org/10.1561/0400000011
Vancouver
Lokam SV. Complexity Lower Bounds using Linear Algebra. Foundations and Trends® in Theoretical Computer Science. 2009;4(1-2):1-155. doi:10.1561/0400000011
BibTeX
@article{Lokam2009,
author = {Lokam, Satyanarayana V.},
title = {Complexity Lower Bounds using Linear Algebra},
journal = {Foundations and Trends® in Theoretical Computer Science},
year = {2009},
volume = {4},
number = {1-2},
pages = {1--155},
doi = {10.1561/0400000011}
}
EUVIMED