Imagen de Portada

New Algorithms and Hardness Results for Robust Satisfiability of (Promise) CSPs

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Brakensiek, Joshua, Ciardo, Lorenzo, Guruswami, Venkatesan, Potechin, Aaron, Živný, Stanislav
Formato:	Preprint
Publicado:	2026
Materias:	Data Structures and Algorithms Computational Complexity Logic in Computer Science
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

SDPs and Robust Satisfiability of Promise CSP
por: Brakensiek, Joshua, et al.
Publicado: (2022)

The periodic structure of local consistency
por: Ciardo, Lorenzo, et al.
Publicado: (2024)

Redundancy Is All You Need (for CSP Sparsification)
por: Brakensiek, Joshua, et al.
Publicado: (2024)

Semidefinite programming and linear equations vs. homomorphism problems
por: Ciardo, Lorenzo, et al.
Publicado: (2023)

On the Mysteries of MAX NAE-SAT
por: Brakensiek, Joshua, et al.
Publicado: (2020)

MAX BISECTION might be harder to approximate than MAX CUT
por: Brakensiek, Joshua, et al.
Publicado: (2025)

On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results
por: Guruswami, Venkatesan, et al.
Publicado: (2023)

Satisfiability of commutative vs. non-commutative CSPs
por: Bulatov, Andrei A., et al.
Publicado: (2024)

Tight Bounds for Sparsifying Random CSPs
por: Brakensiek, Joshua, et al.
Publicado: (2025)

Hardness of Learning Boolean Functions from Label Proportions
por: Guruswami, Venkatesan, et al.
Publicado: (2024)

1-in-3 vs. Not-All-Equal: Dichotomy of a broken promise
por: Ciardo, Lorenzo, et al.
Publicado: (2023)

Hardness of sampling for the anti-ferromagnetic Ising model on random graphs
por: Huang, Neng, et al.
Publicado: (2024)

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

A Strongly Polynomial-Time Algorithm for Weighted General Factors with Three Feasible Degrees
por: Shao, Shuai, et al.
Publicado: (2023)

Scheduling Problems with Constrained Rejections
por: Davies, Sami, et al.
Publicado: (2025)

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)

Maximum $k$- vs. $\ell$-colourings of graphs
por: Nakajima, Tamio-Vesa, et al.
Publicado: (2023)

On the complexity of symmetric vs. functional PCSPs
por: Nakajima, Tamio-Vesa, et al.
Publicado: (2022)

A Dichotomy for Maximum PCSPs on Graphs
por: Nakajima, Tamio-Vesa, et al.
Publicado: (2024)

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

Hardness and Algorithmic Results for Roman \{3\}-Domination
por: Reddy, Sangam Balchandar
Publicado: (2025)

Cell-Probe Lower Bounds via Semi-Random CSP Refutation: Simplified and the Odd-Locality Case
por: Guruswami, Venkatesan, et al.
Publicado: (2025)

Certifying Euclidean Sections and Finding Planted Sparse Vectors Beyond the $\sqrt{n}$ Dimension Threshold
por: Guruswami, Venkatesan, et al.
Publicado: (2024)

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)

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

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)

Characterizing Streaming Decidability of CSPs via Non-Redundancy
por: Sharma, Amatya, et al.
Publicado: (2026)

Linear Space Streaming Lower Bounds for Approximating CSPs
por: Chou, Chi-Ning, et al.
Publicado: (2021)

A Dichotomy Theorem for Multi-Pass Streaming CSPs
por: Fei, Yumou, et al.
Publicado: (2025)

Sketching approximations and LP approximations for finite CSPs are related
por: Singer, Noah G., et al.
Publicado: (2025)

Non-Redundancy of Low-Arity Symmetric Boolean CSPs
por: Sharma, Amatya, et al.
Publicado: (2026)

Near-Optimal Space Lower Bounds for Streaming CSPs
por: Fei, Yumou, et al.
Publicado: (2026)

Improved Approximation Algorithms for Multiway Cut by Large Mixtures of New and Old Rounding Schemes
por: Brakensiek, Joshua, et al.
Publicado: (2026)

Optimal Single-Pass Streaming Lower Bounds for Approximating CSPs
por: Singer, Noah G., et al.
Publicado: (2026)

Unbounded-width CSPs are Untestable in a Sublinear Number of Queries
por: Fei, Yumou
Publicado: (2025)

Nine lower bound conjectures on streaming approximation algorithms for CSPs
por: Singer, Noah G.
Publicado: (2025)