Cover Image

Finding hardness reductions automatically using SAT solvers

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bergold, Helena, Scheucher, Manfred, Schröder, Felix
Format:	Preprint
Published:	2024
Subjects:	Computational Complexity Artificial Intelligence Data Structures and Algorithms Logic in Computer Science Combinatorics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

SAT Requires Exhaustive Search
by: Xu, Ke, et al.
Published: (2023)

First Order Logic on Pathwidth Revisited Again
by: Lampis, Michael
Published: (2022)

Toward a Uniform Algorithm and Uniform Reduction for Constraint Problems
by: Barto, Libor, et al.
Published: (2026)

Fine-grained Meta-Theorems for Vertex Integrity
by: Lampis, Michael, et al.
Published: (2021)

New Algorithms and Hardness Results for Robust Satisfiability of (Promise) CSPs
by: Brakensiek, Joshua, et al.
Published: (2026)

Enumeration and updates for conjunctive linear algebra queries through expressibility
by: Muñoz, Thomas, et al.
Published: (2023)

SAT Encoding of Partial Ordering Models for Graph Coloring Problems
by: Faber, Daniel, et al.
Published: (2024)

Strong Sparsification for 1-in-3-SAT via Polynomial Freiman-Ruzsa
by: Bedert, Benjamin, et al.
Published: (2025)

Computational hardness of detecting graph lifts and certifying lift-monotone properties of random regular graphs
by: Kunisky, Dmitriy, et al.
Published: (2024)

Transductive Learning Is Compact
by: Asilis, Julian, et al.
Published: (2024)

Homomorphism Indistinguishability, Multiplicity Automata Equivalence, and Polynomial Identity Testing
by: Černý, Marek, et al.
Published: (2025)

On Numbers of Simplicial Walks and Equivalent Canonizations for Graph Recognition
by: Černý, Marek
Published: (2026)

Polynomial Logical Zonotope: A Set Representation for Reachability Analysis of Logical Systems
by: Alanwar, Amr, et al.
Published: (2023)

A faster FPRAS for #NFA
by: Meel, Kuldeep S., et al.
Published: (2023)

Smaller Circuits for Bit Addition
by: Goncharov, Mikhail, et al.
Published: (2025)

Elementary first-order model checking for sparse graphs
by: Gajarský, Jakub, et al.
Published: (2024)

On merge-models
by: Buffière, Hector, et al.
Published: (2026)

CNFs and DNFs with Exactly $k$ Solutions
by: Chandran, L. Sunil, et al.
Published: (2025)

Flipper games for monadically stable graph classes
by: Gajarský, Jakub, et al.
Published: (2023)

Finding $d$-Cuts in Probe $H$-Free Graphs
by: Dabrowski, Konrad K., et al.
Published: (2025)

Parameterized Shortest Path Reconfiguration
by: Bousquet, Nicolas, et al.
Published: (2024)

Forest Covers and Bounded Forest Covers
by: Gaur, Daya Ram, et al.
Published: (2024)

Constant congestion linkages in polynomially strong digraphs in polynomial time
by: Lopes, Raul, et al.
Published: (2024)

Complexity of Paired Domination Problems on Circle and $k$-Polygon Graphs
by: Mu, Ta-Yu, et al.
Published: (2024)

On $[1,2]$-Domination in Interval and Circle Graphs
by: Meybodi, Mohsen Alambardar, et al.
Published: (2024)

Fourier Analysis of Iterative Algorithms
by: Jones, Chris, et al.
Published: (2024)

Kernelization Complexity of Solution Discovery Problems
by: Grobler, Mario, et al.
Published: (2024)

Computing the $D$-base and $D$-relation in finite closure systems
by: Adaricheva, Kira, et al.
Published: (2024)

Testing Sumsets is Hard
by: Chen, Xi, et al.
Published: (2024)

Smoothed analysis for graph isomorphism
by: Anastos, Michael, et al.
Published: (2024)

Characterizing and Testing Principal Minor Equivalence of Matrices
by: Chatterjee, Abhranil, et al.
Published: (2024)

Asymptotically Optimal Hardness for $k$-Set Packing and $k$-Matroid Intersection
by: Lee, Euiwoong, et al.
Published: (2024)

Computational Complexity of Swish
by: Horiyama, Takashi, et al.
Published: (2026)

Trickle-down Theorems via C-Lorentzian Polynomials II: Pairwise Spectral Influence and Improved Dobrushin's Condition
by: Leake, Jonathan, et al.
Published: (2025)

Faster Algorithms for Sparse ILP and Hypergraph Multi-Packing/Multi-Cover Problems
by: Gribanov, Dmitry, et al.
Published: (2022)

A General Framework for Low Soundness Homomorphism Testing
by: Mittal, Tushant, et al.
Published: (2025)

Equivalent Dichotomies for Triangle Detection in Subgraph, Induced, and Colored H-Free Graphs
by: Abboud, Amir, et al.
Published: (2026)

Hypergraph Samplers: Typical and Worst Case Behavior
by: Alev, Vedat Levi, et al.
Published: (2026)

Optimal Trickle-Down Theorems for Path Complexes via C-Lorentzian Polynomials with Applications to Sampling and Log-Concave Sequences
by: Leake, Jonathan, et al.
Published: (2025)

Vector TSP: A Traveling Salesperson Problem with Racetrack-like Acceleration Constraints
by: Casteigts, Arnaud, et al.
Published: (2020)