Research map / Learning theory and algorithms / Sample complexity
General Bounds on Satisfiability Thresholds for Random CSPs via Fourier Analysis
Colin Wei, Stefano Ermon
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use a lower-bound formula that incorporates constraint-specific Fourier-spectrum symmetry | Random boolean CSPs · General boolean CSPs | lower bound on satisfiability threshold | Improved |
| Weight satisfying assignments to reduce correlations before applying the second moment method | Second-moment analysis of random CSPs · General boolean CSPs | lower bound on satisfiability probability | Improved |
| Use the unweighted solution count directly in the second moment method | Random k-SAT · k-SAT | second-moment lower bound | Hurt |
| Use the unweighted solution count directly in the second moment method | Random k-NAESAT · k-NAESAT | second-moment lower bound | Improved |
| Apply the proposed lower and first-moment upper bounds to TRIBES constraints | Fourier-based satisfiability-threshold bounds · TRIBES random CSPs | tightness of lower bound relative to upper bound | Mixed |
Closest papers by meaning
- Learning-Augmented Streaming Algorithms for Approximating Boolean Max-CSPs (NeurIPS 2026 · similarity 0.86)
- Unifying Decision and Function Queries in Stochastic Boolean Satisfiability (AAAI 2024 · similarity 0.86)
- Sample complexity of stochastic optimization with integer variables (NeurIPS 2026 · similarity 0.84)
- Hardness of Random Reordered Encodings of Parity for Resolution and CDCL (AAAI 2024 · similarity 0.84)
- Finding Simple Proofs for First-Order Optimization (NeurIPS 2026 · similarity 0.84)
- Span-Based Optimal Sample Complexity for Weakly Communicating and General Average Reward MDPs (NeurIPS 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
