> Detailanzeige

Chou, Chi-Ning [VerfasserIn]; Golovnev, Alexander [VerfasserIn]; Shahrasbi, Amirbehshad [VerfasserIn]; Sudan, Madhu [VerfasserIn]; Velusamy, Santhoshini [VerfasserIn] ; Chi-Ning Chou and Alexander Golovnev and Amirbehshad Shahrasbi and Madhu Sudan and Santhoshini Velusamy [MitwirkendeR]

Sketching Approximability of (Weak) Monarchy Predicates

Literatur-
verwaltung

Zur
Merkliste

Lösche von
Merkliste

Per Whatsapp teilen

Schließen

Merkliste



Sie können Bookmarks mittels Listen verwalten, loggen Sie sich dafür bitte in Ihr SLUB Benutzerkonto ein.
  • Medientyp: E-Artikel; Elektronischer Konferenzbericht; Sonstige Veröffentlichung
  • Titel: Sketching Approximability of (Weak) Monarchy Predicates
  • Beteiligte: Chou, Chi-Ning [VerfasserIn]; Golovnev, Alexander [VerfasserIn]; Shahrasbi, Amirbehshad [VerfasserIn]; Sudan, Madhu [VerfasserIn]; Velusamy, Santhoshini [VerfasserIn]
  • Erschienen: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022
  • Sprache: Englisch
  • DOI: https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2022.35
  • Schlagwörter: approximability ; linear threshold functions ; sketching algorithms
  • Entstehung:
  • Anmerkungen: Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
  • Beschreibung: We analyze the sketching approximability of constraint satisfaction problems on Boolean domains, where the constraints are balanced linear threshold functions applied to literals. In particular, we explore the approximability of monarchy-like functions where the value of the function is determined by a weighted combination of the vote of the first variable (the president) and the sum of the votes of all remaining variables. The pure version of this function is when the president can only be overruled by when all remaining variables agree. For every k ≥ 5, we show that CSPs where the underlying predicate is a pure monarchy function on k variables have no non-trivial sketching approximation algorithm in o(√n) space. We also show infinitely many weaker monarchy functions for which CSPs using such constraints are non-trivially approximable by O(log(n)) space sketching algorithms. Moreover, we give the first example of sketching approximable asymmetric Boolean CSPs. Our results work within the framework of Chou, Golovnev, Sudan, and Velusamy (FOCS 2021) that characterizes the sketching approximability of all CSPs. Their framework can be applied naturally to get a computer-aided analysis of the approximability of any specific constraint satisfaction problem. The novelty of our work is in using their work to get an analysis that applies to infinitely many problems simultaneously.
  • Zugangsstatus: Freier Zugang