Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with decision-tree complexity:
TR10-075 | 22nd April 2010
Ben Reichardt

Least span program witness size equals the general adversary lower bound on quantum query complexity

Span programs form a linear-algebraic model of computation, with span program "size" used in proving classical lower bounds. Quantum query complexity is a coherent generalization, for quantum algorithms, of classical decision-tree complexity. It is bounded below by a semi-definite program (SDP) known as the general adversary bound. We connect these ... more >>>

TR17-149 | 7th October 2017
Or Meir, Avi Wigderson

Prediction from Partial Information and Hindsight, with Application to Circuit Lower Bounds

Revisions: 5

Consider a random sequence of $n$ bits that has entropy at least $n-k$, where $k\ll n$. A commonly used observation is that an average coordinate of this random sequence is close to being uniformly distributed, that is, the coordinate “looks random”. In this work, we prove a stronger result that ... more >>>

ISSN 1433-8092 | Imprint