Complexity Lower Bounds using Linear Algebra
Satyanarayana V. Lokam
Broschiertes Buch

Complexity Lower Bounds using Linear Algebra

Versandkostenfrei!
Versandfertig in 1-2 Wochen
99,99 €
inkl. MwSt.
PAYBACK Punkte
50 °P sammeln!
While rapid progress has been made on upper bounds (algorithms), progress on lower bounds on the complexity of explicit problems has remained slow despite intense efforts over several decades. As is natural with typical impossibility results, lower bound questions are hard mathematical problems and hence are unlikely to be resolved by ad hoc attacks. Instead, techniques based on mathematical notions that capture computational complexity are necessary. Complexity Lower Bounds using Linear Algebra surveys several techniques for proving lower bounds in Boolean, algebraic, and communication comple...