Approximate Degree in Classical and Quantum Computing
Mark BunJustin Thaler
Broschiertes Buch

Approximate Degree in Classical and Quantum Computing

Versandkostenfrei!
Versandfertig in 1-2 Wochen
101,99 €
inkl. MwSt.
PAYBACK Punkte
51 °P sammeln!
The ability (or inability) to represent or approximate Boolean functions by polynomials is a central concept in complexity theory, underlying interactive and probabilistically checkable proof systems, circuit lower bounds, quantum complexity theory, and more. In this book, the authors survey what is known about a particularly natural notion of approximation by polynomials, capturing pointwise approximation over the real numbers. This book covers recent progress on proving approximate degree lower and upper bounds and describes some applications of the new bounds to oracle separations, quantum ...