000			01319 a2200229 4500
999			_c2551 _d2551
005			20240530150528.0
008			240529b ||||| |||| 00| 0 eng d
020			_a9781601982421
041			_aeng
082			_a004.6 LOK/C
100			_aLokam, Satyanarayana V. _98676
245			_aComplexity lower bounds using linear algebra
260			_bNow Publishers -- _c2009 _aUnited States of America --
300			_axi, 163p.
500			_a1. 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
520			_aSurveys 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.
650			_aComputer science _91296
650			_aMathematics _98721
650			_aComputer algorithms _9828
650			_aMathematical logic _95049
942			_cBK