Export Citations
Save this search
Please login to be able to save your searches and receive alerts for new content matching your search criteria.
- research-articleMay 2008
Algebrization: a new barrier in complexity theory
STOC '08: Proceedings of the fortieth annual ACM symposium on Theory of computingPages 731–740https://doi.org/10.1145/1374376.1374481Any proof of P!=NP will have to overcome two barriers: relativization and natural proofs. Yet over the last decade, we have seen circuit lower bounds (for example, that PP does not have linear-size circuits) that overcome both barriers simultaneously. ...
- research-articleMay 2008
Towards an optimal separation of space and length in resolution
STOC '08: Proceedings of the fortieth annual ACM symposium on Theory of computingPages 701–710https://doi.org/10.1145/1374376.1374478Most state-of-the-art satisfiability algorithms today are variants of the DPLL procedure augmented with clause learning. The main bottleneck for such algorithms, other than the obvious one of time, is the amount of memory used. In the field of proof ...
- research-articleMay 2008
Hardness amplification proofs require majority
STOC '08: Proceedings of the fortieth annual ACM symposium on Theory of computingPages 589–598https://doi.org/10.1145/1374376.1374461Hardness amplification is the fundamental task of converting a δ-hard function f : (0, 1)n -> (0, 1) into a (1/2-ε)-hard function Amp(f), where f is γ-hard if small circuits fail to compute f on at least a γ fraction of the inputs. Typically, ε,δ are ...
- research-articleMay 2008
Infeasibility of instance compression and succinct PCPs for NP
STOC '08: Proceedings of the fortieth annual ACM symposium on Theory of computingPages 133–142https://doi.org/10.1145/1374376.1374398The OR-SAT problem asks, given Boolean formulae Φ1,...,Φm each of size at most n, whether at least one of the Φi's is satisfiable. We show that there is no reduction from OR-SAT to any set A where the length of the output is bounded by a polynomial in n,...
- research-articleMay 2008
Classical interaction cannot replace a quantum message
STOC '08: Proceedings of the fortieth annual ACM symposium on Theory of computingPages 95–102https://doi.org/10.1145/1374376.1374393We demonstrate a two-player communication problem that can be solved in the one-way quantum model by a 0-error protocol of cost O(log n) but requires exponentially more communication in the classical interactive (bounded error) model.
- research-articleMay 2008
The pattern matrix method for lower bounds on quantum communication
STOC '08: Proceedings of the fortieth annual ACM symposium on Theory of computingPages 85–94https://doi.org/10.1145/1374376.1374392In a breakthrough result, Razborov (2003) gave optimal lower bounds on the communication complexity of every function f of the form f(x,y)=D(|x AND y|) for some D:{0,1,...,n}->{0,1}, in the bounded-error quantum model with and without prior ...