Fetching the paper…
Reading the bibliography…
Let $P:\{0,1\}^k \to \{0,1\}$ be a nontrivial $k$-ary predicate.
Many hard examples for resolution
Vašek Chvátal and Endre Szemerédi · 1988
Earlier work this paper cites.
Random CNF’s are hard for the polynomial calculus
Eli Ben-Sasson and Russell Impagliazzo · 1999
Earlier work this paper cites.
Candidate One-Way Functions Based on Expander Graphs
Oded Goldreich · 2000
Earlier work this paper cites.
Lower bounds for polynomial calculus: non-binomial case
Michael Alekhnovich and Alexander A. Razborov · 2001
Earlier work this paper cites.
Expansion in Proof Complexity
Eli Ben-Sasson · 2001
Earlier work this paper cites.
Short proofs are narrow—resolution made simple
Eli Ben-Sasson and Avi Wigderson · 2001
Earlier work this paper cites.
Recognizing more unsatisfiable random 3-SAT instances efficiently
Joel Friedman and Andreas Goerdt · 2001
Earlier work this paper cites.
Efficient recognition of random unsatisfiable k k -SAT instances by spectral methods
Andreas Goerdt and Michael Krivelevich · 2001
Earlier work this paper cites.
Complexity of positivstellensatz proofs for the knapsack
Dima Grigoriev · 2001
Earlier work this paper cites.
A gap in average proof complexity
Eli Ben-Sasson and Yonatan Bilu · 2002
Earlier work this paper cites.
The 3-sat problem with large number of clauses in the ∞ \infty -replica symmetry breaking scheme
A Crisanti, L Leuzzi, and G Parisi · 2002
Earlier work this paper cites.
Relations Between Average Case Complexity and Approximation Complexity
Uriel Feige · 2002
Earlier work this paper cites.
More on average case vs approximation complexity
M. Alekhnovich · 2003
Earlier work this paper cites.
Rank bounds and integrality gaps for cutting planes procedures
Joshua Buresh-Oppenheim, Nicola Galesi, Shlomo Hoory, Avner Magen, and Toniann Pitassi · 2003
Earlier work this paper cites.
On ϵ \epsilon -biased generators in NC 0 \text{NC}^{0}
Elchanan Mossel, Amir Shpilka, and Luca Trevisan · 2003
Earlier work this paper cites.
Efficient multicast on a terabit router
Punit Bhargava, Sriram C. Krishnan, and Rina Panigrahy · 2004
Earlier work this paper cites.
An approximation hardness result for bipartite Clique
Andreas Goerdt and André Lanka · 2004
Earlier work this paper cites.
Towards strong nonapproximability results in the Lovász-Schrijver hierarchy
Mikhail Alekhnovich, Sanjeev Arora, and Iannis Tourlakis · 2005
Earlier work this paper cites.
Classifying the complexity of constraints using finite algebras
Andrei Bulatov, Peter Jeavons, and Andrei Krokhin · 2005
Earlier work this paper cites.
Cryptography in NC 0 \text{NC}^{0}
Benny Applebaum, Yuval Ishai, and Eyal Kushilevitz · 2006
Earlier work this paper cites.
Combination can be hard: Approximability of the unique coverage problem
Erik D. Demaine, Uriel Feige, Mohammad Taghi Hajiaghayi, and Mohammad R. Salavatipour · 2006
Earlier work this paper cites.
Witnesses for non-satisfiability of dense random 3CNF formulas
Uriel Feige, Jeong Han Kim, and Eran Ofek · 2006
Earlier work this paper cites.
Approximation resistant predicates from pairwise independence
Per Austrin and Elchanan Mossel · 2008
Earlier work this paper cites.
Uniform Budgets and the Envy-Free Pricing Problem
Patrick Briest · 2008
Cited alongside, same era.
A new upper bound for 3-SAT
Josep Diaz, Lefteris Kirousis, Dieter Mitsche, and Xavier Perez-Gimenez · 2008
Cited alongside, same era.
Cryptography with constant computational overhead
Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, and Amit Sahai · 2008
Cited alongside, same era.
Optimal Algorithms and Inapproximability Results for Every CSP?
Prasad Raghavendra · 2008
Cited alongside, same era.
Linear Level Lasserre Lower Bounds for Certain k k -CSPs
Grant Schoenebeck · 2008
Cited alongside, same era.
On the security of Goldreich’s one-way function
Andrej Bogdanov and Youming Qiao · 2009
Cited alongside, same era.
L S + {LS}_{+} lower bounds from pairwise independence
Madhur Tulsiani and Pratik Worah · 2013
Later among the works it cites.
Sum-of-squares proofs and the quest toward optimal algorithms
Boaz Barak and David Steurer · 2014
Later among the works it cites.
From average case complexity to improper learning complexity
Amit Daniely, Nati Linial, and Shai Shalev-Shwartz · 2014
Later among the works it cites.
Complexity theoretic limitations on learning DNF’s
Amit Daniely and Shai Shalev-Shwartz · 2014
Later among the works it cites.
Approximation Resistance on Satisfiable Instances for Predicates with Few Accepting Inputs
Sangxia Huang · 2014
Later among the works it cites.
Hypercontractive inequalities via SOS, and the Frankl-Rödl graph
Manuel Kauers, Ryan O’Donnell, Li-Yang Tan, and Yuan Zhou · 2014
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
The SAT-UNSAT transition for random constraint satisfaction problems
Nadia Creignou and Hervé Daudé · 2009
Cited alongside, same era.
Sums of squares, moment matrices and optimization over polynomials
Monique Laurent · 2009
Cited alongside, same era.
CSP gaps and reductions in the lasserre hierarchy
Madhur Tulsiani · 2009
Cited alongside, same era.
Public-key cryptography from different assumptions
Benny Applebaum, Boaz Barak, and Avi Wigderson · 2010
Cited alongside, same era.
Inapproximability of densest κ \kappa -subgraph from average case hardness
Noga Alon, Sanjeev Arora, Rajsekar Manokaran, Dana Moshkovitz, and Omri Weinstein · 2011
Cited alongside, same era.
A dichotomy for local small-bias generators
Benny Applebaum, Andrej Bogdanov, and Alon Rosen · 2012
Cited alongside, same era.
Later among the works it cites.
Goldreich’s PRG: Evidence for near-optimal polynomial stretch
Ryan O’Donnell and David Witmer · 2014
Later among the works it cites.
Hardness of robust graph isomorphism, Lasserre gaps, and asymmetry of random graphs
Ryan O’Donnell, John Wright, Chenggang Wu, and Yuan Zhou · 2014
Later among the works it cites.
http://satcompetition.org/2014/certunsat.shtml
2014
Later among the works it cites.
How to refute a random CSP
Sarah R. Allen, Ryan O’Donnell, and David Witmer · 2015
Later among the works it cites.
Sum of squares lower bounds from pairwise independence
Boaz Barak, Siu On Chan, and Pravesh K. Kothari · 2015
Later among the works it cites.
Complexity Theoretic Limitations on Learning Halfspaces
Amit Daniely · 2015
Later among the works it cites.
Proof of the satisfiability conjecture for large k k
Jian Ding, Allan Sly, and Nike Sun · 2015
Later among the works it cites.
On the Complexity of Random Satisfiability Problems with Planted Solutions
Vitaly Feldman, Will Perkins, and Santosh Vempala · 2015
Later among the works it cites.
Lower bounds on the size of semidefinite programming relaxations
James R Lee, Prasad Raghavendra, and David Steurer · 2015
Later among the works it cites.
Algebraic Attacks against Random Local Functions and Their Countermeasures
Benny Applebaum and Shachar Lovett · 2016
Later among the works it cites.
Noisy Tensor Completion via the Sum-of-Squares Hierarchy
Boaz Barak and Ankur Moitra · 2016
Later among the works it cites.
dimetheus
Oliver Gableske · 2016
Later among the works it cites.
Candidate hard unique game
Subhash Khot and Dana Moshkovitz · 2016
Later among the works it cites.
The backtracking survey propagation algorithm for solving random K-SAT problems
Raffaele Marino, Giorgio Parisi, and Federico Ricci-Tersenghi · 2016
Later among the works it cites.
Lower bounds for CSP refutation by SDP hierarchies
Ryuhei Mori and David Witmer · 2016
Later among the works it cites.
Strongly refuting random csps below the spectral threshold
Prasad Raghavendra, Satish Rao, and Tselil Schramm · 2016
Later among the works it cites.
Weighted low rank approximations with provable guarantees
Ilya Razenshteyn, Zhao Song, and David P. Woodruff · 2016
Later among the works it cites.