On Non-Approximability for Quadratic Programs Preliminary Version (2008)
Sanjeev Arora, Eli Berger, Elad Hazan, Guy Kindler, Muli Safra
This paper studies the computational complexity of the following type of quadratic programs: given an arbitrary matrix whose diagonal elements are zero, find x ∈ {−1, +1} n that maximizes xT Ax....
Ranged hash functions and the price of churn (2008)
James Aspnes, Muli Safra, Yitong Yin
Ranged hash functions generalize hash tables to the setting where hash buckets may come and go over time, a typical case in distributed settings where hash buckets may correspond to unreliable...
Michael Ben-Or, Greg Kuperberg, and Boris Tsirelson for helpful discussions, and to (2008)
Gil Kalai, Daniel Gottesman, Pierfrancesco La Mura, Nati Linial, Simon Litsyn, Yuval Peres, ...
We will try to explore, primarily from the complexity-theoretic point of view, limitations of error-correction and fault-tolerant quan-tum computation. We consider stochastic models of quantum...
Hardness Amplification for Errorless Heuristics (2007)
An errorless heuristic is an algorithm that on all inputs returns either the correct answer or the special symbol ⊥, which means “I don’t know. ” A central question in average-case complexity...
Thoughts on noise and quantum computing (2005)
Gil Kalai, Gil Kalai, Daniel Gottesman, Pierfrancesco La Mura, Nati Linial, Simon Litsyn, ...
We will try to explore, primarily from the complexity-theoretic point of view, limitations of error-correction and fault-tolerant quan-tum computation. We consider stochastic models of quantum...
Michael Ben-Or, Greg Kuperberg, and Boris Tsirelson for helpful discussions, and to (2005)
Gil Kalai, Daniel Gottesman, Pierfrancesco La Mura, Nati Linial, Simon Litsyn, Yuval Peres, ...
We will try to explore, primarily from the complexity-theoretic point of view, limitations of error-correction and fault-tolerant quan-tum computation. We consider stochastic models of quantum...
SAFRA: On non-approximability for quadratic programs (2005)
Sanjeev Arora, Eli Berger, Elad Hazan, Guy Kindler, Muli Safra
This paper studies the computational complexity of the following type of quadratic programs: given an arbitrary matrix whose diagonal elements are zero, find x ∈ {−1, 1} n that maximizes x T Mx....