1 Search Results for "Pelleg, Eden"

Document
DOI: 10.4230/LIPIcs.ESA.2021.75
Additive Sparsification of CSPs

Authors: Eden Pelleg and Stanislav Živný

Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)

Abstract
Multiplicative cut sparsifiers, introduced by Benczúr and Karger [STOC'96], have proved extremely influential and found various applications. Precise characterisations were established for sparsifiability of graphs with other 2-variable predicates on Boolean domains by Filtser and Krauthgamer [SIDMA'17] and non-Boolean domains by Butti and Živný [SIDMA'20]. Bansal, Svensson and Trevisan [FOCS'19] introduced a weaker notion of sparsification termed "additive sparsification", which does not require weights on the edges of the graph. In particular, Bansal et al. designed algorithms for additive sparsifiers for cuts in graphs and hypergraphs. As our main result, we establish that all Boolean Constraint Satisfaction Problems (CSPs) admit an additive sparsifier; that is, for every Boolean predicate P:{0,1}^k → {0,1} of a fixed arity k, we show that CSP(P)} admits an additive sparsifier. Under our newly introduced notion of all-but-one sparsification for non-Boolean predicates, we show that CSP(P)} admits an additive sparsifier for any predicate P:D^k → {0,1} of a fixed arity k on an arbitrary finite domain D.
Cite as

Eden Pelleg and Stanislav Živný. Additive Sparsification of CSPs. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 75:1-75:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{pelleg_et_al:LIPIcs.ESA.2021.75,
  author =	{Pelleg, Eden and \v{Z}ivn\'{y}, Stanislav},
  title =	{{Additive Sparsification of CSPs}},
  booktitle =	{29th Annual European Symposium on Algorithms (ESA 2021)},
  pages =	{75:1--75:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-204-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{204},
  editor =	{Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.75},
  URN =		{urn:nbn:de:0030-drops-146562},
  doi =		{10.4230/LIPIcs.ESA.2021.75},
  annote =	{Keywords: additive sparsification, graphs, hypergraphs, minimum cuts}
}
  • Refine by Author
  • 1 Pelleg, Eden
  • 1 Živný, Stanislav

  • Refine by Classification
  • 1 Theory of computation → Design and analysis of algorithms
  • 1 Theory of computation → Sparsification and spanners

  • Refine by Keyword
  • 1 additive sparsification
  • 1 graphs
  • 1 hypergraphs
  • 1 minimum cuts

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2021

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact