Beating the random assignment on constraint satisfaction problems of bounded degree

Bonnie Berger and Peter W. Shor, Approximation alogorithms for the maximum acyclic subgraph problem , Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms (Philadelphia, PA, USA), SODA ’90, Society for Industrial and Applied Mathematics, 1990, pp. 236–243

1990

Earlier work this paper cites.

James B. Shearer, A note on bipartite subgraphs of triangle-free graphs , Random Structures Algorithms 3

Original

1992

Earlier work this paper cites.

Noga Alon, On the edge-expansion of graphs , Combin. Probab. Comput. 6

1997

Earlier work this paper cites.

Johan Håstad, On bounded occurrence constraint satisfaction , Inform. Process. Lett. 74

2000

Earlier work this paper cites.

Johan Håstad and S. Venkatesh, On the advantage over a random assignment , Random Structures Algorithms 25

2004

Cited alongside, same era.

Irit Dinur, Ehud Friedgut, Guy Kindler, and Ryan O’Donnell, On the Fourier tails of bounded functions over the discrete cube , Israel J. Math. 160

2007

Cited alongside, same era.

Subhash Khot and Assaf Naor, Linear equations modulo 2 and the L 1 L_{1} diameter of convex bodies , SIAM J. Comput. 38

2008

Cited alongside, same era.

Venkatesan Guruswami and Yuan Zhou, Approximating bounded occurrence ordering csps , Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Anupam Gupta, Klaus Jansen, José Rolim, and Rocco Servedio, eds.), Lecture Notes in Computer Science, vol. 7408, Springer Berlin Heidelberg, 2012, pp. 158–169 (English)

2012

Cited alongside, same era.

Konstantin Makarychev, Local search is better than random assignment for bounded occurrence ordering k-csps , 30th International Symposium on Theoretical Aspects of Computer Science, STACS 2013, February 27 - March 2, 2013, Kiel, Germany, 2013, pp. 139–147

2013

Later among the works it cites.

Edward Farhi, Jeffrey Goldstone, and Sam Gutmann, A quantum approximate optimization algorithm applied to a bounded occurrence constraint problem , 2014, arXiv:1412.6062

Original

2014

Later among the works it cites.

Ryan O’Donnell, Analysis of Boolean functions , Cambridge University Press, 2014

2014

Later among the works it cites.