EUVIMEDObjevte EUVIMED
Crossref

Complexity Lower Bounds using Linear Algebra

Satyanarayana V. Lokam

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.

AbstraktBibliografické údajeCiteRelated studies

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}
}
Start for free →