Search
 New @ Now
Products
 FnTs in Business  FnTs in Technology
For Authors
 Review Updates
 Authors Advantages
 Download Style Files
 Submit an article
 

Complexity Lower Bounds using Linear Algebra



Author(s): Satyanarayana V. Lokam

Source:
    Journal:Foundations and Trends® in Theoretical Computer Science
    ISSN Print:1551-305X,  ISSN Online:1551-3068
    Publisher:Now Publishers
    Volume 4 Number 1–2,

Document Type: Article
Pages: 155(1-155)
DOI: 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.