DROPS

Artifact

Software

Global Benchmark Database

Authors: Ashlin Iser and Frederick Gehm

Abstract

Cite as

Ashlin Iser, Frederick Gehm. Global Benchmark Database (Software). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-26969,
   title = {{Global Benchmark Database}}, 
   author = {Iser, Ashlin and Gehm, Frederick},
   note = {Software, swhId: \href{https://archive.softwareheritage.org/swh:1:dir:2553a0109d95559020fb87331f2d49502d4c4c67;origin=https://github.com/udopia/gbdc;visit=swh:1:snp:f8ee95852dcfcfd38c0eec4340954c1002a4daa7;anchor=swh:1:rev:d03875b98d3062fec717c231975a4fb5e2ebe551}{\texttt{swh:1:dir:2553a0109d95559020fb87331f2d49502d4c4c67}} (visited on 2026-07-16)},
   url = {https://github.com/udopia/gbdc},
   doi = {10.4230/artifacts.26969},
}

Document

Tool Paper

DOI: 10.4230/LIPIcs.SAT.2026.35

Efficient Identification of Isomorphic SAT Instances (Tool Paper)

Authors: Ashlin Iser and Frederick Gehm

Published in: LIPIcs, Volume 377, 29th International Conference on Theory and Applications of Satisfiability Testing (SAT 2026)

Abstract

Many SAT benchmark datasets contain structurally identical instances arising from repeated shuffling, generators producing identical formulas under different seeds, or duplicate encodings from different tools. We present an efficient, open-source, isomorphism-invariant hashing algorithm for SAT instances, based on Weisfeiler-Leman (WL) label refinement. Each instance is represented as a bipartite clause-literal graph, and iterative label refinement computes a canonical signature, with instances having identical signatures treated as isomorphic. When integrated into our benchmark toolset Global Benchmark Database (GBD), the method substantially reduces false positives from naive degree-sequence hashing with minimal overhead.

Cite as

Ashlin Iser and Frederick Gehm. Efficient Identification of Isomorphic SAT Instances (Tool Paper). In 29th International Conference on Theory and Applications of Satisfiability Testing (SAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 377, pp. 35:1-35:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{iser_et_al:LIPIcs.SAT.2026.35,
  author =	{Iser, Ashlin and Gehm, Frederick},
  title =	{{Efficient Identification of Isomorphic SAT Instances}},
  booktitle =	{29th International Conference on Theory and Applications of Satisfiability Testing (SAT 2026)},
  pages =	{35:1--35:8},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-431-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{377},
  editor =	{Ignatiev, Alexey and Szeider, Stefan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAT.2026.35},
  URN =		{urn:nbn:de:0030-drops-263418},
  doi =		{10.4230/LIPIcs.SAT.2026.35},
  annote =	{Keywords: Isomorphism, Benchmarking, Boolean Satisfiability}
}

Search Results

Documents authored by Gehm, Frederick

Global Benchmark Database

Abstract

Cite as

Efficient Identification of Isomorphic SAT Instances (Tool Paper)

Abstract

Cite as

Thanks for your feedback!

Could not send message