Complexity Lower Bounds using Linear Algebra
Foundations and Trends® in Theoretical Computer Science · 20.10.2009 · 4 (1-2) · 1-155
DOI: 10.1561/0400000011 ↗Kurz gefasst
Fachartikel in der Zeitschrift Foundations and Trends® in Theoretical Computer Science, online erschienen am 20.10.2009. Verfasst von Satyanarayana V. Lokam. Die Arbeit wurde bisher 56-mal zitiert (Crossref) und nennt 104 Literaturangaben.
Abstract (Originalsprache)
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.
Zitieren
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