Fetching the paper…
Reading the bibliography…
We consider the algorithmic problem of finding a near-optimal solution for the number partitioning problem (NPP).
Paul Erdös and George Szekeres, A combinatorial problem in geometry , Compositio mathematica 2
1935
Earlier work this paper cites.
AJ Hoffman and HW Wielandt, The variation of the spectrum of a normal matrix , Duke Mathematical Journal 20
1953
Earlier work this paper cites.
Ralph Merkle and Martin Hellman, Hiding information and signatures in trapdoor knapsacks , IEEE transactions on Information Theory 24
1978
Earlier work this paper cites.
Bernard Derrida, Random-energy model: Limit of a family of disordered models , Physical Review Letters 45
1980
Earlier work this paper cites.
Narendra Karmarkar and Richard M Karp, The differencing method of set partitioning , Computer Science Division (EECS), University of California Berkeley, 1982
1982
Earlier work this paper cites.
Joel Spencer, Six standard deviations suffice , Transactions of the American mathematical society 289
1985
Earlier work this paper cites.
Narendra Karmarkar, Richard M Karp, George S Lueker, and Andrew M Odlyzko, Probabilistic analysis of optimum partitioning , Journal of Applied Probability (1986), 626–645
1986
Earlier work this paper cites.
Hanno Lefmann, A note on ramsey numbers , Studia Sci. Math. Hungar 22
1987
Earlier work this paper cites.
George S Lueker, A note on the average-case behavior of a simple differencing method for partitioning , Operations Research Letters 6
1987
Earlier work this paper cites.
Alan M Frieze, On the independence number of random graphs , Discrete Mathematics 81
1990
Earlier work this paper cites.
Michael R. Garey and David S. Johnson, Computers and intractability; a guide to the theory of np-completeness , W. H. Freeman & Co., USA, 1990
1990
Earlier work this paper cites.
Edward Grady Coffman and George S Lueker, Probabilistic analysis of packing and partitioning algorithms , Wiley-Interscience, 1991
1991
Earlier work this paper cites.
Alan M Frieze and T Łuczak, On the independence and chromatic numbers of random regular graphs , Journal of Combinatorial Theory, Series B 54
1992
Earlier work this paper cites.
Mark Jerrum, Large cliques elude the metropolis process , Random Structures & Algorithms 3
1992
Earlier work this paper cites.
Li-Hui Tsai, Asymptotic analysis of an algorithm for balanced parallel processor scheduling , SIAM Journal on Computing 21
1992
Earlier work this paper cites.
Ian P Gent and Toby Walsh, Phase transitions and annealed theories: Number partitioning as a case study’ , ECAI, PITMAN, 1996, pp. 170–174
1996
Earlier work this paper cites.
Benjamin Yakir, The differencing algorithm ldm for partitioning: a proof of a conjecture of karmarkar and karp , Mathematics of Operations Research 21
1996
Earlier work this paper cites.
Michael Kearns, Efficient noise-tolerant learning from statistical queries , Journal of the ACM (JACM) 45
1998
Earlier work this paper cites.
Stephan Mertens, Phase transition in the number partitioning problem , Physical Review Letters 81
1998
Earlier work this paper cites.
Christian Borgs, Jennifer Chayes, and Boris Pittel, Phase transition and finite-size scaling for the integer partitioning problem , Random Structures & Algorithms 19
2001
Earlier work this paper cites.
Dimitris Achlioptas, Jeong Han Kim, Michael Krivelevich, and Prasad Tetali, Two-coloring random hypergraphs , Random Structures & Algorithms 20
2002
Earlier work this paper cites.
Heiko Bauke and Stephan Mertens, Universality in the level statistics of disordered systems , Physical Review E 70
2004
Earlier work this paper cites.
Marc Mézard, Thierry Mora, and Riccardo Zecchina, Clustering of solutions in the random satisfiability problem , Physical Review Letters 94
2005
Earlier work this paper cites.
Joseph Lauer and Nicholas Wormald, Large independent sets in regular graphs of large girth , Journal of Combinatorial Theory, Series B 97
2007
Earlier work this paper cites.
Dimitris Achlioptas and Amin Coja-Oghlan, Algorithmic barriers from phase transitions , 2008 49th Annual IEEE Symposium on Foundations of Computer Science, IEEE, 2008, pp. 793–802
2008
Earlier work this paper cites.
Stefan Boettcher and Stephan Mertens, Analysis of the karmarkar-karp differencing algorithm , The European Physical Journal B 65
2008
Earlier work this paper cites.
Christian Borgs, Jennifer Chayes, Stephan Mertens, and Chandra Nair, Proof of the local rem conjecture for number partitioning. i: Constant energy scales , Random Structures & Algorithms 34
2009
Cited alongside, same era.
Kevin P Costello, Balancing gaussian vectors , Israel Journal of Mathematics 172
2009
Cited alongside, same era.
Nikhil Bansal, Constructive algorithms for discrepancy minimization , 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, IEEE, 2010, pp. 3–10
2010
Cited alongside, same era.
Mohsen Bayati, David Gamarnik, and Prasad Tetali, Combinatorial approach to the interpolation method and scaling limits in sparse random graphs , Proceedings of the forty-second ACM symposium on Theory of computing, 2010, pp. 105–114
2010
Cited alongside, same era.
Michel Talagrand, Mean field models for spin glasses: Volume i: Basic examples , vol. 54, Springer Science & Business Media, 2010
Samuel B Hopkins, Pravesh K Kothari, Aaron Potechin, Prasad Raghavendra, Tselil Schramm, and David Steurer, The power of sum-of-squares for detecting hidden structures , 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), IEEE, 2017, pp. 720–731
2017
Later among the works it cites.
Rebecca Hoberg, Harishchandra Ramadas, Thomas Rothvoss, and Xin Yang, Number balancing is as hard as minkowski’s theorem and shortest vector , International Conference on Integer Programming and Combinatorial Optimization, Springer, 2017, pp. 254–266
2017
Later among the works it cites.
Pravesh K Kothari, Ryuhei Mori, Ryan O’Donnell, and David Witmer, Sum of squares lower bounds for refuting any csp , Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017, pp. 132–145
2017
Later among the works it cites.
Avi Levy, Harishchandra Ramadas, and Thomas Rothvoss, Deterministic discrepancy minimization via the multiplicative weight update method , International Conference on Integer Programming and Combinatorial Optimization, Springer, 2017, pp. 380–391
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
2010
Cited alongside, same era.
2010
Cited alongside, same era.
Dimitris Achlioptas, Amin Coja-Oghlan, and Federico Ricci-Tersenghi, On the solution-space geometry of random constraint satisfaction problems , Random Structures & Algorithms 38
2011
Cited alongside, same era.
Amin Coja-Oglan and Konstantinos Panagiotou, Catching the k-naesat threshold , Proceedings of the forty-fourth annual ACM symposium on Theory of computing, 2012, pp. 899–908
2012
Cited alongside, same era.
Roger A Horn and Charles R Johnson, Matrix analysis , Cambridge University Press, 2012
2012
Cited alongside, same era.
Stéphane Boucheron, Gábor Lugosi, and Pascal Massart, Concentration inequalities: A nonasymptotic theory of independence , Oxford university press, 2013
2013
Cited alongside, same era.
2013
Cited alongside, same era.
Karthekeyan Chandrasekaran and Santosh S Vempala, Integer feasibility of random polytopes: random integer programs , Proceedings of the 5th conference on Innovations in theoretical computer science, 2014, pp. 449–458
2014
Cited alongside, same era.
2017
Later among the works it cites.
Thomas Rothvoss, Constructive discrepancy minimization for convex sets , SIAM Journal on Computing 46
2017
Later among the works it cites.
Mustazee Rahman and Bálint Virág, Local algorithms for independent sets are half-optimal , Ann. Probab. 45
2017
Later among the works it cites.
2018
Later among the works it cites.
2018
Later among the works it cites.
David Gamarnik, Quan Li, et al., Finding a large submatrix of a gaussian random matrix , The Annals of Statistics 46
2018
Later among the works it cites.
2018
Later among the works it cites.
Louigi Addario-Berry, Luc Devroye, Gábor Lugosi, and Roberto I Oliveira, Local optima of the sherrington-kirkpatrick hamiltonian , Journal of Mathematical Physics 60
2019
Later among the works it cites.
Benjamin Aubin, Will Perkins, and Lenka Zdeborova, Storage capacity in symmetric binary perceptrons , Journal of Physics A: Mathematical and Theoretical 52
2019
Later among the works it cites.
2019
Later among the works it cites.
Boaz Barak, Samuel Hopkins, Jonathan Kelner, Pravesh K Kothari, Ankur Moitra, and Aaron Potechin, A nearly tight sum-of-squares lower bound for the planted clique problem , SIAM Journal on Computing 48
2019
Later among the works it cites.
Wei-Kuo Chen, David Gamarnik, Dmitry Panchenko, Mustazee Rahman, et al., Suboptimality of local algorithms for a class of max-cut problems , Annals of Probability 47
2019
Later among the works it cites.
2019
Later among the works it cites.
2019
Later among the works it cites.
Abba M Krieger, David Azriel, and Adam Kapelner, Nearly random designs with greatly improved balance , Biometrika 106
2019
Later among the works it cites.
2019
Later among the works it cites.
Andrea Montanari, Optimization of the sherrington-kirkpatrick hamiltonian , 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), IEEE, 2019, pp. 1417–1433
2019
Later among the works it cites.
David Conlon and Asaf Ferber, Lower bounds for multicolor ramsey numbers , Advances in Mathematics 378
2020
Later among the works it cites.
David Gamarnik, Aukosh Jagannath, and Alexander S Wein, Low-degree hardness of random optimization problems , 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), 2020
2020
Later among the works it cites.
Paxton Turner, Raghu Meka, and Philippe Rigollet, Balancing gaussian vectors in high dimension , Conference on Learning Theory, PMLR, 2020, pp. 3455–3486
2020
Later among the works it cites.
2020
Later among the works it cites.
David Gamarnik and Aukosh Jagannath, The overlap gap property and approximate message passing algorithms for p p -spin models , Annals of Probability 49
2021
Closest in time.
Gerard Ben Arous, Reza Gheissari, Aukosh Jagannath, et al., Algorithmic thresholds for tensor pca , Annals of Probability 48
2087
Closest in time.