Improved Monotonicity Testers via Hypercube Embeddings

Mark Braverman, Subhash Khot, Guy Kindler, Dor Minzer

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Scopus citations

Abstract

We show improved monotonicity testers for the Boolean hypercube under the p-biased measure, as well as over the hypergrid [m]n. Our results are: 1. For any p ∈ (0,1), for the p-biased hypercube we show a non-adaptive tester that makes Õ(√n/ε2) queries, accepts monotone functions with probability 1 and rejects functions that are ε-far from monotone with probability at least 2/3. 2. For all m ∈ N, we show an Õ(√nm32) query monotonicity tester over [m]n. We also establish corresponding directed isoperimetric inequalities in these domains, analogous to the isoperimetric inequality in [15]. Previously, the best known tester due to Black, Chakrabarty and Seshadhri [2] had Ω(n5/6) query complexity. Our results are optimal up to poly-logarithmic factors and the dependency on m. Our proof uses a notion of monotone embeddings of measures into the Boolean hypercube that can be used to reduce the problem of monotonicity testing over an arbitrary product domains to the Boolean cube. The embedding maps a function over a product domain of dimension n into a function over a Boolean cube of a larger dimension n, while preserving its distance from being monotone; an embedding is considered efficient if n is not much larger than n, and we show how to construct efficient embeddings in the above mentioned settings.

Original languageEnglish (US)
Title of host publication14th Innovations in Theoretical Computer Science Conference, ITCS 2023
EditorsYael Tauman Kalai
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959772631
DOIs
StatePublished - Jan 1 2023
Event14th Innovations in Theoretical Computer Science Conference, ITCS 2023 - Cambridge, United States
Duration: Jan 10 2023Jan 13 2023

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume251
ISSN (Print)1868-8969

Conference

Conference14th Innovations in Theoretical Computer Science Conference, ITCS 2023
Country/TerritoryUnited States
CityCambridge
Period1/10/231/13/23

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Isoperimetric Inequalities
  • Monotonicity Testing
  • Property Testing

Fingerprint

Dive into the research topics of 'Improved Monotonicity Testers via Hypercube Embeddings'. Together they form a unique fingerprint.

Cite this