|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'504'928
Articles rated: 2609
25 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Domain Reduction for Monotonicity Testing: A $o(d)$ Tester for Boolean Functions on Hypergrids | | Hadley Black
; Deeparnab Chakrabarty
; C. Seshadhri
; | | Date: |
4 Nov 2018 | | Abstract: | Testing monotonicity of Boolean functions over the hypergrid, $f:[n]^d o
{0,1}$, is a classic problem in property testing. When the range is
real-valued, there are $Theta(dlog n)$-query testers and this is tight. In
contrast, the Boolean range qualitatively differs in two ways:
(1) Independence of $n$: There are testers with query complexity independent
of $n$ [Dodis et al. (RANDOM 1999); Berman et al. (STOC 2014)], with linear
dependence on $d$.
(2) Sublinear in $d$: For the $n=2$ hypercube case, there are testers with
$o(d)$ query complexity [Chakrabarty, Seshadhri (STOC 2013); Khot et al. (FOCS
2015)].
It was open whether one could obtain both properties simultaneously. This
paper answers this question in the affirmative. We describe a
$ ilde{O}(d^{5/6})$-query monotonicity tester for $f:[n]^d o {0,1}$.
Our main technical result is a domain reduction theorem for monotonicity. For
any function $f$, let $epsilon_f$ be its distance to monotonicity. Consider
the restriction $hat{f}$ of the function on a random $[k]^d$ sub-hypergrid of
the original domain. We show that for $k = ext{poly}(d/epsilon)$, the
expected distance of the restriction $mathbf{E}[epsilon_{hat{f}}] =
Omega(epsilon_f)$. Therefore, for monotonicity testing in $d$ dimensions, we
can restrict to testing over $[n]^d$, where $n = ext{poly}(d/epsilon)$. Our
result follows by applying the $d^{5/6}cdot ext{poly}(1/epsilon,log n,
log d)$-query hypergrid tester of Black-Chakrabarty-Seshadhri (SODA 2018). | | Source: | arXiv, 1811.1427 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER