Document Open Access Logo

Sketching Approximability of (Weak) Monarchy Predicates

Authors Chi-Ning Chou, Alexander Golovnev, Amirbehshad Shahrasbi, Madhu Sudan, Santhoshini Velusamy

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2022.35.pdf
  • Filesize: 0.82 MB
  • 17 pages

Document Identifiers

Author Details

Chi-Ning Chou
  • School of Engineering and Applied Sciences, Harvard University, Cambridge, MA, USA
Alexander Golovnev
  • Department of Computer Science, Georgetown University, Washington, D.C., USA
Amirbehshad Shahrasbi
  • Microsoft, Redmond, WA, USA
Madhu Sudan
  • School of Engineering and Applied Sciences, Harvard University, Cambridge, MA USA
Santhoshini Velusamy
  • School of Engineering and Applied Sciences, Harvard University, Cambridge, MA, USA

Funding

  • Chou, Chi-Ning: Partially supported by NSF grants DMS-2134157 and CCF-1565264, DOE grant DE-SC0022199, and the Simons foundation.
  • Shahrasbi, Amirbehshad: The author was with Harvard University and supported by CRA-CCC Computing Innovations Fellowship (CIFellowship 2020) during this work.
  • Sudan, Madhu: Supported in part by a Simons Investigator Award and NSF Awards CCF 1715187 and CCF 2152413.
  • Velusamy, Santhoshini: Supported in part by a Google Ph.D. Fellowship, a Simons Investigator Award to Madhu Sudan, and NSF Awards CCF 1715187 and CCF 2152413.

Acknowledgements

We thank the anonymous reviewers for their helpful and constructive comments.

Cite As Get BibTex

Chi-Ning Chou, Alexander Golovnev, Amirbehshad Shahrasbi, Madhu Sudan, and Santhoshini Velusamy. Sketching Approximability of (Weak) Monarchy Predicates. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 35:1-35:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2022.35

Abstract

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Sketching and sampling
  • Theory of computation → Approximation algorithms analysis
Keywords
  • sketching algorithms
  • approximability
  • linear threshold functions

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Per Austrin, Siavosh Benabbas, and Avner Magen. On quadratic threshold csps. In LATIN 2010, pages 332-343. Springer, 2010. Google Scholar
  2. Joanna Boyland, Michael Hwang, Tarun Prasad, Noah Singer, and Santhoshini Velusamy. Closed-form expressions for the sketching approximability of (some) symmetric Boolean CSPs. CoRR, abs/2112.06319, February 2022. Google Scholar
  3. Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Ameya Velingker, and Santhoshini Velusamy. Linear Space Streaming Lower Bounds for Approximating CSPs. In STOC 2022, 2022. To appear. Google Scholar
  4. Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, and Santhoshini Velusamy. Approximability of all finite CSPs with linear sketches. In FOCS 2021, pages 1197-1208. IEEE, 2021. URL: https://doi.org/10.1109/FOCS52979.2021.00117.
  5. Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, and Santhoshini Velusamy. Approximability of all Boolean CSPs with linear sketches. CoRR, abs/2102.12351v8, 11th february 2022. Google Scholar
  6. Chi-Ning Chou, Alexander Golovnev, and Santhoshini Velusamy. Optimal Streaming Approximations for all Boolean Max-2CSPs and Max-kSAT. In FOCS 2020, pages 330-341. IEEE, 2020. URL: https://doi.org/10.1109/FOCS46700.2020.00039.
  7. Venkatesan Guruswami and Runzhou Tao. Streaming Hardness of Unique Games. In APPROX 2019, pages 5:1-5:12. Schloss Dagstuhl, 2019. Google Scholar
  8. Venkatesan Guruswami, Ameya Velingker, and Santhoshini Velusamy. Streaming Complexity of Approximating Max 2CSP and Max Acyclic Subgraph. In APPROX 2017, pages 8:1-8:19. Schloss Dagstuhl, 2017. Google Scholar
  9. Gustav Hast. Beating a random assignment: Approximating constraint satisfaction problems. PhD thesis, KTH, 2005. Google Scholar
  10. Neng Huang and Aaron Potechin. On the approximability of presidential type predicates. In APPROX 2020, pages 58:1-58:20. Schloss Dagstuhl, 2020. Google Scholar
  11. Piotr Indyk. Stable distributions, pseudorandom generators, embeddings and data stream computation. In FOCS 2000, pages 189-197. IEEE, 2000. Google Scholar
  12. Daniel M. Kane, Jelani Nelson, and David P. Woodruff. On the exact space complexity of sketching and streaming small norms. In SODA 2010, pages 1161-1178. SIAM, 2010. Google Scholar
  13. Michael Kapralov, Sanjeev Khanna, and Madhu Sudan. Streaming lower bounds for approximating MAX-CUT. In SODA 2015, pages 1263-1282. SIAM, 2015. Google Scholar
  14. Michael Kapralov, Sanjeev Khanna, Madhu Sudan, and Ameya Velingker. (1 + ω(1))-approximation to MAX-CUT requires linear space. In SODA 2017, pages 1703-1722. SIAM, 2017. Google Scholar
  15. Michael Kapralov and Dmitry Krachun. An optimal space lower bound for approximating MAX-CUT. In STOC 2019, pages 277-288. ACM, 2019. URL: https://doi.org/10.1145/3313276.3316364.
  16. Dmitry Kogan and Robert Krauthgamer. Sketching cuts in graphs and hypergraphs. In ITCS 2015, pages 367-376. ACM, 2015. Google Scholar
  17. Ryan O'Donnell. Analysis of Boolean functions. Cambridge University Press, 2014. Google Scholar
  18. Aaron Potechin. On the approximation resistance of balanced linear threshold functions. In STOC 2019, pages 430-441. ACM, 2019. Google Scholar
  19. Noah Singer, Madhu Sudan, and Santhoshini Velusamy. Streaming approximation resistance of every ordering CSP. In APPROX 2021, pages 17:1-17:19. Schloss Dagstuhl, 2021. Google Scholar
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 About DROPS Imprint Privacy Contact