Conference item
Sparsification of Binary CSPs
- Abstract:
- A cut ε-sparsifier of a weighted graph G is a re-weighted subgraph of G of (quasi)linear size that preserves the size of all cuts up to a multiplicative factor of ε. Since their introduction by Benczúr and Karger [STOC’96], cut sparsifiers have proved extremely influential and found various applications. Going beyond cut sparsifiers, Filtser and Krauthgamer [SIDMA’17] gave a precise classification of which binary Boolean CSPs are sparsifiable. In this paper, we extend their result to binary CSPs on arbitrary finite domains.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Version of record, pdf, 427.2KB, Terms of use)
-
- Publisher copy:
- 10.4230/LIPIcs.STACS.2019.16
Authors
- Publisher:
- Schloss Dagstuhl - Leibniz-Zentrum für Informatik
- Host title:
- 36th International Symposium on Theoretical Aspects of Computer Science
- Journal:
- 36th International Symposium on Theoretical Aspects of Computer Science More from this journal
- Volume:
- 16
- Pages:
- 16:1–16:8
- Publication date:
- 2019-03-12
- Acceptance date:
- 2018-12-20
- Event location:
- Berlin, Germany
- DOI:
- EISSN:
-
1868-8969
- Pubs id:
-
pubs:955987
- UUID:
-
uuid:da7375d5-ac8f-4806-a2ca-bd84580ee15e
- Local pid:
-
pubs:955987
- Source identifiers:
-
955987
- Deposit date:
-
2019-01-03
Terms of use
- Copyright holder:
- Butti et al
- Copyright date:
- 2019
- Notes:
- © Silvia Butti and Stanislav Živný. This item was presented at STACS 2019 and is licensed under Creative Commons License CC-BY
If you are the owner of this record, you can report an update to it here: Report update to this record