General Bounds on Satisfiability Thresholds for Random CSPs via Fourier Analysis
Authors: Colin Wei, Stefano Ermon
AAAI 2017 | Conference PDF | Archive PDF | Plain Text | 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 {colinwei,ermon}@cs.stanford.edu |
| 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. |