Fetching the paper…
Reading the bibliography…
We describe a quantum algorithm for the Planted Noisy $k$XOR problem (also known as sparse Learning Parity with Noise) that achieves a nearly quartic ($4$th power) speedup over the best known classical algorithm while also only using logarithmically many qubits.
R. Kikuchi, A theory of cooperative phenomena, Phys. Rev. 81
1951
Earlier work this paper cites.
J. Håstad, An NP-complete problem — some aspects of its solution and some possible applications , Master’s thesis, Uppsala University (1984)
1984
Earlier work this paper cites.
M. Mézard, G. Parisi, and M. A. Virasoro, Spin glass theory and beyond: An Introduction to the Replica Method and Its Applications , Vol. 9 (World Scientific Publishing Company, 1987)
1987
Earlier work this paper cites.
L. K. Grover, A fast quantum mechanical algorithm for database search, in Proceedings of the twenty-eighth annual ACM symposium on Theory of computing (1996) pp. 212–219
1996
Earlier work this paper cites.
N. Alon, M. Krivelevich, and B. Sudakov, Finding a large hidden clique in a random graph, Random Structures & Algorithms 13
1998
Earlier work this paper cites.
P. W. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM review 41
1999
Earlier work this paper cites.
A. Goerdt and M. Krivelevich, Efficient recognition of random unsatisfiable k k -SAT instances by spectral methods, in Proceedings of the 18th Annual Symposium on Theoretical Aspects of Computer Science (2001) pp. 294–304
2001
Earlier work this paper cites.
M. Alekhnovich and A. Razborov, Lower bounds for polynomial calculus: Non-binomial case, in Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science (2001) pp. 190–199
2001
Earlier work this paper cites.
U. Feige, Relations between average case complexity and approximation complexity, in Proceedings of the 34th Annual ACM Symposium on Theory of Computing (2002) pp. 543–543
2002
Earlier work this paper cites.
A. Goerdt and T. Jurdziński, Some results on random unsatisfiable k k -SAT instances and approximation algorithms applied to random structures, in Proceedings of the 27th Annual International Symposium on Mathematical Foundations of Computer Science (2002) pp. 280–291
2002
Earlier work this paper cites.
A. Kitaev, A. Shen, and M. Vyalyi, Classical and Quantum Computation , Graduate studies in mathematics (American Mathematical Society, 2002)
2002
Earlier work this paper cites.
M. Alekhnovich, More on average case vs approximation complexity, in Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (IEEE, 2003) pp. 298–307
2003
Earlier work this paper cites.
M. B. Hastings, Community detection as an inference problem, Physical Review E—Statistical, Nonlinear, and Soft Matter Physics 74
2006
Earlier work this paper cites.
V. V. Shende, S. S. Bullock, and I. L. Markov, Synthesis of quantum-logic circuits, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 25
2006
Earlier work this paper cites.
A. Coja-Oghlan, A. Goerdt, and A. Lanka, Strong refutation heuristics for random k k -SAT, Combinatorics, Probability and Computing 16
2007
Earlier work this paper cites.
M. Christandl, R. König, G. Mitchison, and R. Renner, One-and-a-half quantum de Finetti theorems, Communications in mathematical physics 273
2007
Earlier work this paper cites.
G. Schoenebeck, Linear level Lasserre lower bounds for certain k k -CSPs, in Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (2008) pp. 593–602
2008
Earlier work this paper cites.
2008
Earlier work this paper cites.
A. M. Childs, On the relationship between continuous- and discrete-time quantum walk, Communications in Mathematical Physics 294
2009
Earlier work this paper cites.
B. Applebaum, B. Barak, and A. Wigderson, Public-key cryptography from different assumptions, in Proceedings of the 42nd Annual ACM Symposium on Theory of Computing (2010) pp. 171–180
2010
Earlier work this paper cites.
A. Coja-Oghlan, C. Cooper, and A. Frieze, An efficient sparse regularity concept, SIAM Journal on Discrete Mathematics 23
2010
Earlier work this paper cites.
R. P. Brent and P. Zimmermann, Modern Computer Arithmetic (Cambridge University Press, 2010)
2010
Earlier work this paper cites.
A. Singer, Angular synchronization by eigenvectors and semidefinite programming, Applied and computational harmonic analysis 30
2011
Earlier work this paper cites.
J. Tropp, User-friendly tail bounds for sums of random matrices, Foundations of Computational Mathematics. The Journal of the Society for the Foundations of Computational Mathematics 12
2012
Cited alongside, same era.
2014
Cited alongside, same era.
R. O’Donnell and D. Witmer, Goldreich’s PRG: Evidence for near-optimal polynomial stretch, in Proceedings of the 29th Annual Computational Complexity Conference (2014) pp. 1–12
2014
Cited alongside, same era.
A. D. Bookatz, QMA-complete problems, Quantum Inf. Comput. 14
2014
Cited alongside, same era.
A. Jain, H. Lin, and A. Sahai, Indistinguishability obfuscation from well-founded assumptions, in Proceedings of the 53rd Annual ACM Symposium on Theory of Computing (2021) pp. 60–73
2021
Later among the works it cites.
E. Malvetti, R. Iten, and R. Colbeck, Quantum Circuits for Sparse Isometries, Quantum 5
2021
Later among the works it cites.
S. Gharibian and F. Le Gall, Dequantizing the quantum singular value transformation: hardness and applications to quantum chemistry and the quantum pcp conjecture, in Proceedings of the 54th Annual ACM Symposium on Theory of Computing (2022) p. 19–32
2022
Later among the works it cites.
A. Jain, H. Lin, and A. Sahai, Indistinguishability obfuscation from LPN over 𝔽 p \mathbb{F}_{p} , DLIN, and PRGs in 𝖭𝖢 0 \mathsf{NC}^{0} , in Advances in Cryptology – EUROCRYPT 2022 (2022) pp. 670–699
2022
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
2015
Cited alongside, same era.
S. Allen, R. O’Donnell, and D. Witmer, How to refute a random CSP, in Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science (IEEE, 2015) pp. 689–708
2015
Cited alongside, same era.
2015
Cited alongside, same era.
D. W. Berry, A. M. Childs, and R. Kothari, Hamiltonian simulation with nearly optimal dependence on all parameters, in 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (2015) pp. 792–809
2015
Cited alongside, same era.
R. Mori and D. Witmer, Lower bounds for CSP refutation by SDP hierarchies, in Proceedings of the 20th Annual International Workshop on Randomized Techniques in Computation , Leibniz International Proceedings in Informatics (LIPIcs), Vol. 60 (2016) pp. 41:1–41:30
2016
Cited alongside, same era.
2017
Cited alongside, same era.
P. Kothari, R. Mori, R. O’Donnell, and D. Witmer, Sum of squares lower bounds for refuting any CSP, in Proceedings of the 49th Annual ACM Symposium on Theory of Computing (2017) pp. 132–145
2017
Cited alongside, same era.
P. Raghavendra, S. Rao, and T. Schramm, Strongly refuting random CSPs below the spectral threshold, in Proceedings of the 49th Annual ACM Symposium on Theory of Computing (2017) pp. 121–131
2017
Cited alongside, same era.
B. Barak and A. Moitra, Noisy tensor completion via the sum-of-squares hierarchy, Mathematical Programming 193
2022
Later among the works it cites.
2022
Later among the works it cites.
V. Guruswami, P. K. Kothari, and P. Manohar, Algorithms and certificates for boolean CSP refutation: smoothed is no harder than random, in Proceedings of the 54th Annual ACM Symposium on Theory of Computing (2022) pp. 678–689
2022
Later among the works it cites.
T. Hoefler, T. Häner, and M. Troyer, Disentangling hype from practicality: On realistically achieving quantum advantage, Communications of the ACM 66
2023
Later among the works it cites.
Q. Dao, Y. Ishai, A. Jain, and H. Lin, Multi-party homomorphic secret sharing and sublinear MPC from sparse LPN, in Proceedings of the 43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques (2023) pp. 315–348
2023
Later among the works it cites.
T. d’Orsi and L. Trevisan, A Ihara-Bass Formula for Non-Boolean Matrices and Strong Refutations of Random CSPs, in Proceedings of the 38th Annual Computational Complexity Conference , Leibniz International Proceedings in Informatics (LIPIcs), Vol. 264 (2023) pp. 27:1–27:16
2023
Later among the works it cites.
C. Cade, M. Folkertsma, S. Gharibian, R. Hayakawa, F. Le Gall, T. Morimae, and J. Weggemans, Improved Hardness Results for the Guided Local Hamiltonian Problem, in 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) , Leibniz International Proceedings in Informatics (LIPIcs), Vol. 261 (2023) pp. 32:1–32:19
2023
Later among the works it cites.
A. M. Dalzell, N. Pancotti, E. T. Campbell, and F. G. Brandão, Mind the gap: Achieving a super-grover quantum speedup by jumping to the end, in Proceedings of the 55th Annual ACM Symposium on Theory of Computing (2023) pp. 1131–1144
2023
Later among the works it cites.
2023
Later among the works it cites.
J.-T. Hsieh, P. K. Kothari, and S. Mohanty, A simple and sharper proof of the hypergraph moore bound, in Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (SIAM, 2023) pp. 2324–2344
2023
Later among the works it cites.
O. Alrabiah, V. Guruswami, P. K. Kothari, and P. Manohar, A near-cubic lower bound for 3-query locally decodable codes from semirandom CSP refutation, in Proceedings of the 55th Annual ACM Symposium on Theory of Computing (2023) pp. 1438–1448
2023
Later among the works it cites.
J. Haah, R. Kothari, R. O’Donnell, and E. Tang, Query-optimal estimation of unitary channels in diamond distance, in 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS) (2023) pp. 363–390
2023
Later among the works it cites.
2024
Closest in time.
2024
Closest in time.
2024
Closest in time.
A. Prabhu, [wip] algorithm for planted noisy kxor, https://github.com/quantumlib/Qualtran/pull/1348 (2024), gitHub pull request #1348, quantumlib/Qualtran
2024
Closest in time.
2024
Closest in time.
2024
Closest in time.