Sparsification of Binary CSPs

DOI10.4230/LIPIcs.STACS.2019.17OpenAlexW2963916529MaRDI QIDQ5090464

Stanislav Živný, Silvia Butti

Publication date: 18 July 2022

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2019/10256/pdf/LIPIcs-STACS-2019-17.pdf/

zbMATH Keywords

constraint satisfaction problemssparsificationminimum cuts

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (2)

The algebraic structure of the densification and the sparsification tasks for CSPs ⋮ Sparsification of Binary CSPs

Cites Work

• Unnamed Item
• Best-case and worst-case sparsifiability of Boolean CSPs
• On Sketching Quadratic Forms
• On Multiplicative $\lambda$-Approximations and Some Geometric Applications
• Sketching Cuts in Graphs and Hypergraphs
• Spectral Sparsification of Graphs
• Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
• Graph Sparsification in the Semi-streaming Model
• Bigraphs versus digraphs via matrices
• Twice-Ramanujan Sparsifiers
• Spectral Sparsification of Hypergraphs
• Sparsification of Two-Variable Valued Constraint Satisfaction Problems
• The Complexity of General-Valued CSPs
• A general framework for graph sparsification
• Graph Sparsification by Effective Resistances

This page was built for publication: Sparsification of Binary CSPs