Fetching the paper…
Reading the bibliography…
The problem of identifying a planted assignment given a random $k$-SAT formula consistent with the assignment exhibits a large algorithmic gap: while the planted solution becomes unique and can be identified given a formula with $O(n\log n)$ clauses, there are distributions over clauses for which the best known efficient algorithms require $n^{k/2}$ clauses.
On an algorithm for the minimization of convex functions
A.Yu. Levin · 1965
Earlier work this paper cites.
Étude des coefficients de fourier des fonctions de l p ( g ) l_{p}(g)
Aline Bonami · 1970
Earlier work this paper cites.
Inequalities in fourier analysis
William Beckner · 1975
Earlier work this paper cites.
Maximum likelihood from incomplete data via the em algorithm
A.P. Dempster, N.M. Laird, and D.B. Rubin · 1977
Earlier work this paper cites.
Optimization by simmulated annealing
Scott Kirkpatrick, D. Gelatt Jr., and Mario P. Vecchi · 1983
Earlier work this paper cites.
Problem Complexity and Method Efficiency in Optimization
A.S. Nemirovsky and D.B. Yudin · 1983
Earlier work this paper cites.
Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm
V. Černý · 1985
Earlier work this paper cites.
Eigenvalues and graph bisection: An average-case analysis
Ravi B Boppana · 1987
Earlier work this paper cites.
The calculation of posterior distributions by data augmentation (with discussion)
Martin A Tanner and Wing Hung Wong · 1987
Earlier work this paper cites.
Sampling based approaches to calculating marginal densities
Alan E. Gelfand and Adrian F.M. Smith · 1990
Earlier work this paper cites.
Weakly learning DNF and characterizing statistical query learning using Fourier analysis
Avrim Blum, Merrick Furst, Jeffrey Jackson, Michael Kearns, Yishay Mansour, and Steven Rudich · 1994
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.
Gaussian Hilbert spaces
Svante Janson · 1997
Earlier work this paper cites.
Learning with restricted focus of attention
Shai Ben-David and Eli Dichterman · 1998
Earlier work this paper cites.
A polynomial-time algorithm for learning noisy linear threshold functions
Avrim Blum, Alan Frieze, Ravi Kannan, and Santosh Vempala · 1998
Earlier work this paper cites.
Efficient noise-tolerant learning from statistical queries
Michael Kearns · 1998
Earlier work this paper cites.
Candidate one-way functions based on expander graphs
Oded Goldreich · 2000
Earlier work this paper cites.
Spectral partitioning of random graphs
Frank McSherry · 2001
Earlier work this paper cites.
Hiding solutions in random satisfiability problems: A statistical mechanics approach
Wolfgang Barthel, Alexander K Hartmann, Michele Leone, Federico Ricci-Tersenghi, Martin Weigt, and Riccardo Zecchina · 2002
Earlier work this paper cites.
Relations between average case complexity and approximation complexity
Uriel Feige · 2002
Earlier work this paper cites.
A spectral technique for random satisfiable 3cnf formulas
Abraham Flaxman · 2003
Earlier work this paper cites.
Recognizing more random unsatisfiable 3-SAT instances efficiently
Andreas Goerdt and André Lanka · 2003
Earlier work this paper cites.
Strong refutation heuristics for random k-SAT
Amin Coja-Oghlan, Andreas Goerdt, and André Lanka · 2004
Earlier work this paper cites.
Techniques from combinatorial approximation algorithms yield efficient algorithms for random 2k-SAT
Amin Coja-Oghlan, Andreas Goerdt, André Lanka, and Frank Schädlich · 2004
Earlier work this paper cites.
Maximizing quadratic programs: Extending Grothendieck’s inequality
Moses Charikar and Anthony Wirth · 2004
Earlier work this paper cites.
Easily refutable subformulas of large random 3-CNF formulas
Uriel Feige and Eran Ofek · 2004
Earlier work this paper cites.
Hiding satisfying assignments: Two are better than one
Dimitris Achlioptas, Haixia Jia, and Cristopher Moore · 2005
Earlier work this paper cites.
Practical privacy: the SuLQ framework
Avrim Blum, Cynthia Dwork, Frank McSherry, and Kobbi Nissim · 2005
Earlier work this paper cites.
Recognizing more unsatisfiable random k-SAT instances efficiently
Joel Friedman, Andreas Goerdt, and Michael Krivelevich · 2005
Earlier work this paper cites.
Generating hard satisfiable formulas by hiding solutions deceptively
Haixia Jia, Cristopher Moore, and Doug Strain · 2005
Cited alongside, same era.
Map-reduce for machine learning on multicore
Cheng-Tao Chu, Sang Kyun Kim, Yi-An Lin, YuanYuan Yu, Gary Bradski, Andrew Y. Ng, and Kunle Olukotun · 2006
Cited alongside, same era.
A spectral heuristic for bisecting random graphs
Amin Coja-Oghlan · 2006
Cited alongside, same era.
Simulated annealing for convex optimization
A. T. Kalai and S. Vempala · 2006
Cited alongside, same era.
Solving random satisfiable 3cnf formulas in expected polynomial time
Michael Krivelevich and Dan Vilenchik · 2006
Cited alongside, same era.
Fast algorithms for logconcave functions: Sampling, rounding, integration and optimization
László Lovász and Santosh Vempala · 2006
Cited alongside, same era.
Large sample properties of generalized method of moments estimators
Lars Peter Hansen · 2012
Later among the works it cites.
Pseudorandom generators with long stretch and low locality from random local one-way functions
Benny Applebaum · 2013
Closest in time.
On the optimality of semidefinite relaxations for average-case and generalized constraint satisfaction
Boaz Barak, Guy Kindler, and David Steurer · 2013
Closest in time.
More data speeds up training time in learning halfspaces over sparse vectors
Amit Daniely, Nati Linial, and Shai Shalev-Shwartz · 2013
Closest in time.
Statistical algorithms and a lower bound for detecting planted cliques
Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh Vempala, and Ying Xiao · 2013
Closest in time.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
On ε \varepsilon -biased generators in NC0
Elchanan Mossel, Amir Shpilka, and Luca Trevisan · 2006
Cited alongside, same era.
On the Fourier tails of bounded functions over the discrete cube
Irit Dinur, Ehud Friedgut, Guy Kindler, and Ryan O’Donnell · 2007
Cited alongside, same era.
Gibbs states and the set of solutions of random constraint satisfaction problems
Florent Krzakała, Andrea Montanari, Federico Ricci-Tersenghi, Guilhem Semerjian, and Lenka Zdeborová · 2007
Cited alongside, same era.
Algorithmic barriers from phase transitions
Dimitris Achlioptas and Amin Coja-Oghlan · 2008
Cited alongside, same era.
A simple polynomial-time rescaling algorithm for solving linear programs
John Dunagan and Santosh Vempala · 2008
Cited alongside, same era.
Cryptography with constant computational overhead
Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, and Amit Sahai · 2008
Cited alongside, same era.
Elchanan Mossel, Joe Neeman, and Allan Sly · 2013
Closest in time.
Decoding binary node labels from censored edge measurements: Phase transition and efficient recovery
Emmanuel Abbe, Afonso S Bandeira, Annina Bracher, and Amit Singer · 2014
Closest in time.
Jeremiah Blocki, Manuel Blum, Anupam Datta, and Santosh Vempala · 2014
Closest in time.
Performance of the survey propagation-guided decimation algorithm for the random NAE-K-SAT problem
David Gamarnik and Madhu Sudan · 2014
Closest in time.
Reweighted belief propagation and quiet planting for random k-sat
Florent Krzakala, Marc Mézard, and Lenka Zdeborová · 2014
Closest in time.
Community detection thresholds and the weak Ramanujan property
Laurent Massoulié · 2014
Closest in time.
Goldreich’s PRG: Evidence for near-optimal polynomial stretch
Ryan O’Donnell and David Witmer · 2014
Closest in time.
Conditional random fields, planted constraint satisfaction, and entropy concentration
Emmanuel Abbe and Andrea Montanari · 2015
Closest in time.
How to refute a random CSP
Sarah R. Allen, Ryan O’Donnell, and David Witmer · 2015
Closest in time.
Statistical active learning algorithms for noise tolerance and differential privacy
Maria-Florina Balcan and Vitaly Feldman · 2015
Closest in time.
On the complexity of random satisfiability problems with planted solutions
Vitaly Feldman, Will Perkins, and Santosh Vempala · 2015
Closest in time.
Subsampled power iteration: a new algorithm for block models and planted CSP’s
Vitaly Feldman, Will Perkins, and Santosh Vempala · 2015
Closest in time.
On the complexity of random satisfiability problems with planted solutions
Vitaly Feldman, Will Perkins, and Santosh Vempala · 2015
Closest in time.
Reconstruction and estimation in the planted partition model
Elchanan Mossel, Joe Neeman, and Allan Sly · 2015
Closest in time.
Minimax rates for memory-bounded sparse linear regression
Jacob Steinhardt and John C. Duchi · 2015
Closest in time.
Memory, communication, and statistical queries
J. Steinhardt, G. Valiant, and S. Wager · 2015
Closest in time.
Algebraic attacks against random local functions and their countermeasures
Benny Applebaum and Shachar Lovett · 2016
Closest in time.
Cryptographic hardness of random local functions
Benny Applebaum · 2016
Closest in time.
The backtracking survey propagation algorithm for solving random k-sat problems
Raffaele Marino, Giorgio Parisi, and Federico Ricci-Tersenghi · 2016
Closest in time.
A general characterization of the statistical query complexity
Vitaly Feldman · 2017
Closest in time.
Statistical query learning
Vitaly Feldman · 2017
Closest in time.
Statistical query algorithms for mean vector estimation and stochastic convex optimization
Vitaly Feldman, Cristobal Guzman, and Santosh Vempala · 2017
Closest in time.
Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of csps
Pravesh K. Kothari, Raghu Meka, and Prasad Raghavendra · 2017
Closest in time.