Bounds on the quantum satisfiability threshold

C.R. Laumann, R. Moessner, A. Scardicchio, and S.L. Sondhi. Phase transitions and random quantum satisfiability. Preprint, arXiv:0903.1904

Original

1904

Earlier work this paper cites.

L.G. Valiant, The complexity of enumeration and reliability problems. SIAM J. Comput. 8

1979

Earlier work this paper cites.

V. Chvátal and B. Reed. Mick gets some (the odds are on his side), Proc. 33rd Symposium on the Foundations of Computer Science, 620–627 (1992)

1992

Earlier work this paper cites.

Nicholas C. Wormald, Differential equations for random processes and random graphs. Annals of Applied Probability

1995

Earlier work this paper cites.

W. Dür, G. Vidal, and J. I. Cirac, Three qubits can be entangled in two inequivalent ways. Phys. Rev. A 62

2000

Cited alongside, same era.

M. Mezard, G. Parisi, and R. Zecchina, Science 297

2002

Cited alongside, same era.

D. Achlioptas and C. Moore, “Almost all graphs of degree 4 are 3-colorable.” Journal of Computer and System Sciences

2002

Cited alongside, same era.

Alexis Kaporis, Lefteris Kirousis, Efthimios Lalas, Selecting complementary pairs of literals. Proc. LICS Workshop on Typical Case Complexity and Phase Transitions, 2003

2003

Cited alongside, same era.

S. Bravyi, Efficient algorithm for a quantum analogue of 2-SAT. Preprint, quant-ph/0602108

Cited in the paper.

S. Bravyi and B. Terhal, Complexity of stoquastic frustration-free Hamiltonians. Preprint, arXiv:0806.1746

Original

Cited in the paper.

Mohammad Hajiaghayi and Gregory Sorkin, The satisfiability threshold for random 3-SAT is at least 3.52 3.52 . Preprint, citeseer.ist.psu.edu/hajiaghayi03satisfiability.html

2003

Later among the works it cites.

D. Achlioptas and Y. Peres, The threshold for random k k -SAT is 2 k ​ ln ⁡ 2 − O ⁡ ( k ) 2^{k}\ln 2-O(k) . Proc. STOC 2003, 223–231

2003

Later among the works it cites.

M. Molloy, Cores in random hypergraphs and Boolean formulas. Random Struct. Algorithms 27

2005

Later among the works it cites.

J. Díaz, L. Kirousis, D. Mitsche, and X. Pérez-Giménez, A new upper bound for 3-SAT. Proc. FSTTCS 2008, 163–174

2008

Later among the works it cites.