EUVIMEDEUVIMED entdecken
Crossref

Complexity Lower Bounds using Linear Algebra

Satyanarayana V. Lokam

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →