Imagen de Portada

Toward a Uniform Algorithm and Uniform Reduction for Constraint Problems

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Barto, Libor, Hadek, Maximilian, Zhuk, Dmitriy
Formato:	Preprint
Publicado:	2026
Materias:	Logic in Computer Science Computational Complexity Data Structures and Algorithms
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

The Sherali-Adams and Weisfeiler-Leman hierarchies in (Promise Valued) Constraint Satisfaction Problems
por: Barto, Libor, et al.
Publicado: (2024)

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

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

Singleton algorithms for the Constraint Satisfaction Problem
por: Zhuk, Dmitriy
Publicado: (2025)

Unifying the Three Algebraic Approaches to the CSP via Minimal Taylor Algebras
por: Barto, Libor, et al.
Publicado: (2021)

First Order Logic on Pathwidth Revisited Again
por: Lampis, Michael
Publicado: (2022)

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

Parameterized Algorithms for Editing to Uniform Cluster Graph
por: Gaikwad, Ajinkya, et al.
Publicado: (2024)

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

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

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

Transductive Learning Is Compact
por: Asilis, Julian, et al.
Publicado: (2024)

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

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

Smaller Circuits for Bit Addition
por: Goncharov, Mikhail, et al.
Publicado: (2025)

The Ideal Membership Problem and Abelian Groups
por: Bulatov, Andrei A., et al.
Publicado: (2022)

Fair Vertex Problems Parameterized by Cluster Vertex Deletion
por: Masařík, Tomáš, et al.
Publicado: (2025)

Multi-Pass Streaming Lower Bounds for Uniformity Testing
por: Li, Qian, et al.
Publicado: (2025)

Finding hardness reductions automatically using SAT solvers
por: Bergold, Helena, et al.
Publicado: (2024)

Search-space Reduction for Boolean MinCSPs via Essential Constraints
por: Jansen, Bart M. P., et al.
Publicado: (2026)

Uniform Sampling of Proper Graph Colorings via Soft Coloring and Partial Rejection Sampling
por: Moka, Sarat, et al.
Publicado: (2026)

Pseudodeterministic Algorithms for Minimum Cut Problems
por: Agarwala, Aryan, et al.
Publicado: (2025)

Approximate Model Counting, Sparse XOR Constraints and Minimum Distance
por: Boreale, Michele, et al.
Publicado: (2019)

Algorithms and Complexity of Difference Logic
por: Dabrowski, Konrad K., et al.
Publicado: (2024)

Uniformity testing when you have the source code
por: Canonne, Clément L., et al.
Publicado: (2024)

Self-referential instances of the dominating set problem are irreducible
por: Zhou, Guangyan
Publicado: (2026)

A simplified proof of the CSP Dichotomy Conjecture and XY-symmetric operations
por: Zhuk, Dmitriy
Publicado: (2024)

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

Finitely (In)tractable Promise Constraint Satisfaction Problems
por: Asimi, Kristina, et al.
Publicado: (2020)

End Cover for Initial Value Problem: Complete Validated Algorithms with Complexity Analysis
por: Zhang, Bingwei, et al.
Publicado: (2026)

On the Length of Strongly Monotone Descending Chains over $\mathbb{N}^d$
por: Schmitz, Sylvain, et al.
Publicado: (2023)

The Existential Theory of the Reals as a Complexity Class: A Compendium
por: Schaefer, Marcus, et al.
Publicado: (2024)

Ineffectiveness for Search and Undecidability of PCSP Meta-Problems
por: Larrauri, Alberto
Publicado: (2025)

Towards Deterministic Algorithms for Constant-Depth Factors of Constant-Depth Circuits
por: Kumar, Mrinal, et al.
Publicado: (2024)

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

Alphabet Reduction for Reconfiguration Problems
por: Ohsaka, Naoto
Publicado: (2024)

Knapsack on Graphs with Relaxed Neighborhood Constraints
por: Dey, Palash, et al.
Publicado: (2025)

NP-Hardness and a PTAS for the Pinwheel Problem
por: Kleinberg, Robert, et al.
Publicado: (2026)

On the formalization of the notion of an algorithm
por: Middelburg, C. A.
Publicado: (2024)

Submodular Maximization under Supermodular Constraint: Greedy Guarantees
por: Srivastava, Ajitesh, et al.
Publicado: (2026)