Fetching the paper…
Reading the bibliography…
We give an approximation algorithm for MaxCut and provide guarantees on the average fraction of edges cut on $d$-regular graphs of girth $\geq 2k$.
Classical and quantum bounded depth approximation algorithms, 2019
M. B. Hastings · 1905
Earlier work this paper cites.
On even subgraphs of graphs
P. Erdös · 1967
Earlier work this paper cites.
A note on bipartite subgraphs of triangle-free graphs
J. B. Shearer · 1992
Earlier work this paper cites.
Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
M. X. Goemans and D. P. Williamson · 1995
Earlier work this paper cites.
Optimization of mean-field spin glasses, 2020
A. E. Alaoui, A. Montanari, and M. Sellke · 2001
Earlier work this paper cites.
On the power of unique 2-prover 1-round games
S. Khot · 2002
Earlier work this paper cites.
Max cut in cubic graphs
E. Halperin, D. Livnat, and U. Zwick · 2004
Earlier work this paper cites.
Quantum approximate optimization of non-planar graph problems on a planar superconducting processor
M. P. Harrigan, K. J. Sung, M. Neeley, et al · 2004
Earlier work this paper cites.
Optimal inapproximability results for MAX-CUT and other 2-variable csps?
S. Khot, G. Kindler, E. Mossel, and R. O’Donnell · 2004
Earlier work this paper cites.
An optimal sdp algorithm for max-cut, and equally optimal long code tests
R. O’Donnell and Y. Wu · 2008
Cited alongside, same era.
Warm-starting quantum optimization
D. J. Egger, J. Mareček, and S. Woerner · 2009
Cited alongside, same era.
Tridiagonal toeplitz matrices: properties and novel applications
S. Noschese, L. Pasquini, and L. Reichel · 2013
Cited alongside, same era.
A quantum approximate optimization algorithm
E. Farhi, J. Goldstone, and S. Gutmann · 2014
Cited alongside, same era.
Large cuts with local algorithms on triangle-free graphs
J. Hirvonen, J. Rybicki, S. Schmid, and J. Suomela · 2014
Cited alongside, same era.
R. Lyons · 2017
Later among the works it cites.
Quantum algorithms, architecture, and error correction, 2018
C. Ryan-Anderson · 2018
Later among the works it cites.
Quantum approximate optimization algorithm for maxcut: A fermionic view
Z. Wang, S. Hadfield, Z. Jiang, and E. G. Rieffel · 2018
Later among the works it cites.
In search of degree-4 sum-of-squares lower bounds for maxcut
C. de Boor · 2019
Later among the works it cites.
Lower bounds for max-cut via semidefinite programming
C. Carlson, A. Kolla, R. Li, N. Mani, B. Sudakov, and L. Trevisan · 2020
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
E. Csóka, B. Gerencsér, V. Harangi, and B. Virág · 2015
Cited alongside, same era.
E. Farhi, J. Goldstone, and S. Gutmann · 2015
Cited alongside, same era.
Independent sets and cuts in large-girth regular graphs, 2016
E. Csóka · 2016
Cited alongside, same era.
Extremal cuts of sparse random graphs
A. Dembo, A. Montanari, and S. Sen · 2017
Cited alongside, same era.
Classical algorithms and quantum limitations for maximum cut on high-girth graphs, 2021
B. Barak and K. Marwaha · 2021
Closest in time.
Local classical MAX-CUT algorithm outperforms p = 2 p=2 QAOA on high-girth regular graphs
K. Marwaha · 2021
Closest in time.
Optimization of the sherrington–kirkpatrick hamiltonian
A. Montanari · 2021
Closest in time.