Cover Image

Completeness Theorems for k-SUM and Geometric Friends: Deciding Fragments of Integer Linear Arithmetic

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Gokaj, Geri, Künnemann, Marvin
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity Computational Geometry Logic in Computer Science
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

A SUBSET-SUM Characterisation of the A-Hierarchy
by: Gutleben, Jan, et al.
Published: (2024)

Computing $L_\infty$ Hausdorff Distances Under Translations: The Interplay of Dimensionality, Symmetry and Discreteness
by: Angrick, Sebastian, et al.
Published: (2026)

Approximating Pareto Sum via Bounded Monotone Min-Plus Convolution
by: Gokaj, Geri, et al.
Published: (2026)

Devil's Games and $\text{Q}\mathbb{R}$: Continuous Games complete for the First-Order Theory of the Reals
by: Meijer, Lucas, et al.
Published: (2025)

Measuring Decidability as Related to Busy Beaver Numbers
by: Tandi, Gurpreet, et al.
Published: (2026)

Functional variant of Polynomial Analogue of Gandy's Fixed Point Theorem
by: Nechesov, Andrey
Published: (2024)

On Deciding the Data Complexity of Answering Linear Monadic Datalog Queries with LTL Operators(Extended Version)
by: Artale, Alessandro, et al.
Published: (2025)

Proof Complexity of Linear Logics
by: Tabatabai, Amirhossein Akbar, et al.
Published: (2026)

Complexity of the Guarded Two-Variable Fragment with Counting Quantifiers
by: Pratt-Hartmann, Ian
Published: (2006)

Fagin's Theorem for Semiring Turing Machines
by: Badia, Guillermo, et al.
Published: (2025)

Termination of Real Linear Loops
by: Neumann, Eike, et al.
Published: (2026)

Network Satisfaction Problems Solved by k-Consistency
by: Bodirsky, Manuel, et al.
Published: (2023)

Witnessing Flows in Arithmetic
by: Tabatabai, Amirhossein Akbar
Published: (2024)

Verifying Quantized GNNs With Readout Is Decidable But Highly Intractable
by: Chernobrovkin, Artem, et al.
Published: (2025)

Feasibility of Primality in Bounded Arithmetic
by: Jalali, Raheleh, et al.
Published: (2025)

The Proof Analysis Problem
by: Arteche, Noel, et al.
Published: (2025)

Effective Versions of Strong Measure Zero
by: Rayman, Matthew
Published: (2025)

Meta-Mathematics of Computational Complexity Theory
by: Oliveira, Igor C.
Published: (2025)

On the consistency of stronger lower bounds for NEXP
by: Thapen, Neil
Published: (2025)

An order out of nowhere: a new algorithm for infinite-domain CSPs
by: Mottet, Antoine, et al.
Published: (2023)

Proof complexity of positive branching programs
by: Das, Anupam, et al.
Published: (2021)

Parallelism and Adaptivity in Student-Teacher Witnessing
by: Ježil, Ondřej, et al.
Published: (2026)

The complete classification for quantified equality constraints
by: Zhuk, Dmitriy, et al.
Published: (2021)

Feasibly Constructive Proof of Schwartz-Zippel Lemma and the Complexity of Finding Hitting Sets
by: Atserias, Albert, et al.
Published: (2024)

$Π_{2}^{P}$ vs PSpace Dichotomy for the Quantified Constraint Satisfaction Problem
by: Zhuk, Dmitriy
Published: (2024)

Program Synthesis is $Σ_3^0$-Complete
by: Kim, Jinwoo
Published: (2024)

Toward a Characterization of Simulation Between Arithmetic Theories
by: Monroe, Hunter
Published: (2026)

Small unsatisfiable $k$-CNFs with bounded literal occurrence
by: Zhang, Tianwei, et al.
Published: (2024)

Complete and tractable machine-independent characterizations of second-order polytime
by: Hainry, Emmanuel, et al.
Published: (2022)

An Algorithmic Meta Theorem for Homomorphism Indistinguishability
by: Seppelt, Tim
Published: (2024)

On Polynomial-Time Decidability of k-Negations Fragments of First-Order Theories
by: Haase, Christoph, et al.
Published: (2024)

Search-Driven Clause Learning for Product-State Quantum $k$-SAT (PRODSAT-QSAT)
by: González-Castillo, Samuel, et al.
Published: (2026)

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

Symmetric Linear Arc Monadic Datalog and Gadget Reductions
by: Bodirsky, Manuel, et al.
Published: (2024)

On Extremal Properties of k-CNF: Capturing Threshold Functions
by: Gurumukhani, Mohit, et al.
Published: (2024)

Galois Energy Games: To Solve All Kinds of Quantitative Reachability Problems
by: Lemke, Caroline, et al.
Published: (2025)

Better Extension Variables in DQBF via Independence
by: Chew, Leroy, et al.
Published: (2025)

Discrete Homotopy and Promise Constraint Satisfaction Problem
by: Beikmohammadi, Arash, et al.
Published: (2025)

Modular Counting CSP: Reductions and Algorithms
by: Kazeminia, Amirhossein, et al.
Published: (2025)

On the Interplay of Cube Learning and Dependency Schemes in QCDCL Proof Systems
by: Choudhury, Abhimanyu, et al.
Published: (2025)