How to refute a random CSP

DOI10.1109/FOCS.2015.48MaRDI QIDQ6946864zbMATH OpenFDO

Authors Sarah R. Allen, Ryan O'Donnell, David Witmer

Publication date 5 August 2025

Full work available at URL https://doi.org/10.1109/FOCS.2015.48

Mathematics Subject Classification ID

Theory of computing (68Qxx) Discrete mathematics in relation to computer science (68Rxx) Algorithms in computer science (68Wxx)

Cited in

(8)

• Faster random k-CNF satisfiability
• The Kikuchi hierarchy and tensor PCA
• Somewhat homomorphic encryption from linear homomorphism and sparse LPN
• Indistinguishability obfuscation from bilinear maps and LPN variants
• Hardness of improper one-sided learning of conjunctions for all uniformly falsifiable CSPs
• Tight hardness results for training depth-2 ReLU networks
• Computational complexity of deep learning: fundamental limitations and empirical phenomena
• Spectral refutations of semirandom k-LIN over larger fields

This page was built for publication: How to refute a random CSP

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6946864)