Lokam, Satyanarayana V.
Complexity lower bounds using linear algebra - United States of America -- Now Publishers -- 2009 - xi, 163p.
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
Surveys 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.
9781601982421
Computer science
Mathematics
Computer algorithms
Mathematical logic
004.6 LOK/C
Complexity lower bounds using linear algebra - United States of America -- Now Publishers -- 2009 - xi, 163p.
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
Surveys 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.
9781601982421
Computer science
Mathematics
Computer algorithms
Mathematical logic
004.6 LOK/C