Lokam, Satyanarayana V. Complexity lower bounds using linear algebra. (English) Zbl 1176.68084 Found. Trends Theor. Comput. Sci. 4, No. 1-2, 1-163 (2008). Summary: 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. Cited in 27 Documents MSC: 68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) 68-02 Research exposition (monographs, survey articles) pertaining to computer science PDFBibTeX XMLCite \textit{S. V. Lokam}, Found. Trends Theor. Comput. Sci. 4, No. 1--2, 1--163 (2009; Zbl 1176.68084) Full Text: DOI