Computational Complexity (cs.CC)

  • May 23 2018 quant-ph cs.CC arXiv:1805.08577v1
    We show that combining two different hypothetical enhancements to quantum computation---namely, quantum advice and non-collapsing measurements---would let a quantum computer solve any decision problem whatsoever in polynomial time, even though neither enhancement yields extravagant power by itself. This complements a related result due to Raz. The proof uses locally decodable codes.
  • PDF
    The Strong Exponential Time Hypothesis and the OV-conjecture are two popular hardness assumptions used to prove a plethora of lower bounds, especially in the realm of polynomial-time algorithms. The OV-conjecture in moderate dimension states there is no $\epsilon>0$ for which an $O(N^{2-\epsilon})\mathrm{poly}(D)$ time algorithm can decide whether there is a pair of orthogonal vectors in a given set of size $N$ that contains $D$-dimensional binary vectors. We strengthen the evidence for these hardness assumptions. In particular, we show that if the OV-conjecture fails, then two problems for which we are far from obtaining even tiny improvements over exhaustive search would have surprisingly fast algorithms. If the OV conjecture is false, then there is a fixed $\epsilon>0$ such that: (1) For all $d$ and all large enough $k$, there is a randomized algorithm that takes $O(n^{(1-\epsilon)k})$ time to solve the Zero-Weight-$k$-Clique and Min-Weight-$k$-Clique problems on $d$-hypergraphs with $n$ vertices. As a consequence, the OV-conjecture is implied by the Weighted Clique conjecture. (2) For all $c$, the satisfiability of sparse TC1 circuits on $n$ inputs (that is, circuits with $cn$ wires, depth $c\log n$, and negation, AND, OR, and threshold gates) can be computed in time ${O((2-\epsilon)^n)}$.
  • PDF
    We show that it is possible to obtain an $O(\epsilon^{-4/3})$ runtime --- including computational cost --- for finding $\epsilon$-stationary points of nonconvex functions using cutting plane methods. This improves on the best known epsilon dependence achieved by cubic regularized Newton of $O(\epsilon^{-3/2})$ as proved by Nesterov and Polyak (2006)\nocitenesterov2006cubic. Our techniques utilize the convex until proven guilty principle proposed by Carmon, Duchi, Hinder, and Sidford (2017)\nocitecarmon2017convex.
  • PDF
    Efficient computability is an important property of solution concepts in matching markets. We consider the computational complexity of finding and verifying various solution concepts in trading networks---multi-sided matching markets with bilateral contracts---under the assumption of full substitutability of agents' preferences. First, we show that outcomes that satisfy an economically intuitive solution concept---trail stability---always exist and can be found in linear time. Second, we consider a slightly stronger solution concept in which agents can simultaneously offer an upstream and a downstream contract. We show that deciding the existence of outcomes satisfying this solution concept is an NP-complete problem even in a special (flow network) case of our model. It follows that the existence of stable outcomes---immune to deviations by arbitrary sets of agents---is also an NP-complete problem in trading networks (and in flow networks). Finally, we show that even verifying whether a given outcome is stable is NP-complete in trading networks.

Recent comments

Robin Blume-Kohout Apr 07 2017 20:30 UTC

Zak, David: thanks! So (I think) this is a relation problem, not a decision problem (or even a partial function). Which is fine -- I'm happier with relation problems than with sampling problems, and the quantum part of Shor's algorithm is solving a relation problem, which is a pretty good pedigre

David Gosset Apr 06 2017 20:11 UTC

Thanks Zak, that's exactly right-- for each instance there is a set of possible solutions. Like in the Bernstein-Vazirani problem, a solution is a bit string. It can't just be a single bit since then we would have the problem you describe, Robin.

Zak Webb Apr 06 2017 17:15 UTC

You are completely correct that in order to check whether a give output is "correct" for the input, we would require an additional log-depth classical circuit, but this is not how the problem is defined. In particular, for each input there is a set of "accepting" outputs, and we only need to guaran

Robin Blume-Kohout Apr 06 2017 15:05 UTC

Is it okay to be a quantum supremacist? I thought I was, but maybe if it's "tainted" I should reconsider.

On a more serious note... a question for somebody who has read (or written) the paper. If the computation is performed on Poly(n) qubits, and all of them are relevant, and you are only allo

Steve Flammia Apr 04 2017 13:13 UTC

I would like to publicly thank the authors for using the term "advantage" instead of the tainted word "supremacy" that makes me cringe every time I hear it.

Also, great result!

Ashley Apr 04 2017 08:35 UTC

A provable separation between analogous quantum and classical circuit classes!

Māris Ozols Feb 21 2017 15:35 UTC

I'm wondering if this result could have any interesting consequences for Hamiltonian complexity. The LCL problem sounds very much like a local Hamiltonian problem, with the run-time of an LCL algorithm corresponding to the range of local interactions in the Hamiltonian.

Maybe one caveat is that thi

Jānis Iraids Jan 25 2017 11:35 UTC

You are correct, that is a mistake -- it should be $\\{0,1\\}^n\rightarrow\\{0,1\\}$. Thank you for spotting it!

Christopher Chubb Jan 25 2017 02:27 UTC

In the abstract, should the domain of $f$ be $\lbrace0,1\rbrace^n$ instead of just $\lbrace0,1\rbrace$?

Zoltán Zimborás Jan 12 2017 20:38 UTC

Here is a nice description, with additional links, about the importance of this work if it turns out to be flawless (thanks a lot to Martin Schwarz for this link): [dichotomy conjecture][1].