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..
Evolving Solutions to Community-Structured Satisfiability Formulas
Authors: Frank Neumann, Andrew M. Sutton2346-2353
AAAI 2019 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We study the performance of a simple evolutionary algorithm tasked with finding a satisfying assignment to structured (non-uniform) propositional formulas... In order to characterize the leading constants and demonstrate the tightness of the bound, we perform a number of numerical experiments to measure the run time of the (1+1) EA on the community attachment model. In Figure 3, we fix n = 1000, s = 100 and p = 3/4 and vary m to plot the empirical RLD curves. |
| Researcher Affiliation | Academia | Frank Neumann Optimisation and Logistics School of Computer Science The University of Adelaide Adelaide, Australia Andrew M. Sutton Department of Computer Science University of Minnesota Duluth Duluth, MN, USA |
| Pseudocode | Yes | Algorithm 1: (1+1) EA 1 Choose x uniformly at random from {0, 1}n; 2 while stopping criterion not met do 4 foreach i {1, . . . , n} do 5 With probability 1/n, yi (1 yi); 6 if f(y) f(x) then x y; |
| Open Source Code | No | The paper does not contain any statements or links indicating that its source code is publicly available. |
| Open Datasets | No | The paper describes generating synthetic formulas using the "community attachment model" rather than using a publicly available dataset with concrete access information. |
| Dataset Splits | No | The paper does not specify exact training, validation, or test dataset splits. It describes generating formulas for experiments without partitioning a pre-existing dataset. |
| Hardware Specification | No | The paper does not provide specific details about the hardware used to run the experiments. |
| Software Dependencies | No | The paper does not list specific software dependencies with version numbers used for the experiments. |
| Experiment Setup | Yes | For each s = {100, 110, 120, . . . , 1000}, we generate 10 modular formulas using the community attachment model with n = s3/2 and m/n = 5e. On each formula, we measure the run time of the (1+1) EA for 10 trials... We identify t(1 ε) communities as dense and choose localized clauses uniformly from dense communities with probability 1 t ε. The remaining communities are chosen uniformly with probability t ε... We plot the median run time divided by n ln n measured in the experiments for p {3/4, 1/4} and ε = 1/5. |