Complexity lower bounds using linear algebra / by Satyanarayana V. Lokam.
| Author/creator | Lokam, Satyanarayana V. |
| Format | Book |
| Publication Info | Hanover, Mass. : Now Publishers, ©2009. |
| Description | ix, 163 pages : illustrations ; 24 cm. |
| Subjects |
| Series | Foundations and trends in theoretical computer science, 1551-3068 ; v. 4, issue 1-2, p. 1-155 Foundations and trends in theoretical computer science ; v. 4, issue 1-2, p. 1-155. UNAUTHORIZED |
| Contents | Abstract -- 1. Introduction -- 2. Matrix rigidity -- 3. Spectral methods to study rank robustness -- 4. Sign-rank and other complexity measures of sign matrices -- 5. Rank robustness and two-party communication complexity -- 6. Graph complexity and projective and affine dimensions of graphs -- 7. Span programs : a linear algebraic model of computation -- 8. Conclusions and open problems -- Acknowledgments -- References. |
| 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. |
| Bibliography note | Includes bibliographical references (p. 157-163). |
| ISBN | 9781601982421 |
| ISBN | 1601982429 |