License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2023.25
URN: urn:nbn:de:0030-drops-180774
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18077/
Go to the corresponding LIPIcs Volume Portal

Black, Hadley ; Kalemaj, Iden ; Raskhodnikova, Sofya

Isoperimetric Inequalities for Real-Valued Functions with Applications to Monotonicity Testing

pdf-format:
LIPIcs-ICALP-2023-25.pdf (1.0 MB)

Abstract

We generalize the celebrated isoperimetric inequality of Khot, Minzer, and Safra (SICOMP 2018) for Boolean functions to the case of real-valued functions f:{0,1}^d → ℝ. Our main tool in the proof of the generalized inequality is a new Boolean decomposition that represents every real-valued function f over an arbitrary partially ordered domain as a collection of Boolean functions over the same domain, roughly capturing the distance of f to monotonicity and the structure of violations of f to monotonicity.
We apply our generalized isoperimetric inequality to improve algorithms for testing monotonicity and approximating the distance to monotonicity for real-valued functions. Our tester for monotonicity has query complexity Õ(min(r √d,d)), where r is the size of the image of the input function. (The best previously known tester makes O(d) queries, as shown by Chakrabarty and Seshadhri (STOC 2013).) Our tester is nonadaptive and has 1-sided error. We prove a matching lower bound for nonadaptive, 1-sided error testers for monotonicity. We also show that the distance to monotonicity of real-valued functions that are α-far from monotone can be approximated nonadaptively within a factor of O(√{d log d}) with query complexity polynomial in 1/α and the dimension d. This query complexity is known to be nearly optimal for nonadaptive algorithms even for the special case of Boolean functions. (The best previously known distance approximation algorithm for real-valued functions, by Fattal and Ron (TALG 2010) achieves O(d log r)-approximation.)

BibTeX - Entry

@InProceedings{black_et_al:LIPIcs.ICALP.2023.25,
  author =	{Black, Hadley and Kalemaj, Iden and Raskhodnikova, Sofya},
  title =	{{Isoperimetric Inequalities for Real-Valued Functions with Applications to Monotonicity Testing}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{25:1--25:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/18077},
  URN =		{urn:nbn:de:0030-drops-180774},
  doi =		{10.4230/LIPIcs.ICALP.2023.25},
  annote =	{Keywords: Isoperimetric inequalities, property testing, monotonicity testing}
}

Keywords: Isoperimetric inequalities, property testing, monotonicity testing
Collection: 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Issue Date: 2023
Date of publication: 05.07.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI