Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in Coakley et alK. L. Coakley, T. Snelleman, H. Hoos, and O. E. Gundersen, "The embrace of open science: An analysis of a decade of AI research and 56 800 conference papers," Under Review, 2026..
General Bounds on Satisfiability Thresholds for Random CSPs via Fourier Analysis
Authors: Colin Wei, Stefano Ermon
AAAI 2017 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We demonstrate that our bounds can be easily instantiated to obtain thresholds for many constraint functions that had not been previously studied, and evaluate them experimentally. [...] We empirically test our bounds with the goal of examining their tightness. |
| Researcher Affiliation | Academia | Colin Wei and Stefano Ermon Computer Science Department Stanford University EMAIL |
| Pseudocode | No | The paper does not contain any structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide concrete access to source code for the methodology described. |
| Open Datasets | No | For our experiments, we randomly generate CSP formulas based on TRIBESa,b. The paper describes a method for generating problem instances rather than using a public dataset, and no information is provided on accessing these generated instances. |
| Dataset Splits | No | The paper describes generating random CSP formulas and running experiments on them, not splitting a pre-existing dataset into train/validation/test sets. |
| Hardware Specification | No | The paper does not provide specific hardware details (exact GPU/CPU models, processor types, or memory amounts) used for running its experiments. |
| Software Dependencies | No | The paper mentions using the 'Dimetheus1 random CSP solver' but does not provide a specific version number for it or any other software dependencies. |
| Experiment Setup | Yes | For our experiments, we randomly generate CSP formulas based on TRIBESa,b. [...] We show our results in Figure 3. As expected, our values for lower bounds rf,low are looser than the upper bounds rf,up. [...] Proportion of CSPs satisfiable out of 50 trials vs. r for tribes functions. |