Yevgeniy Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova, Dana Ron, Alex Samorodnitsky

We present improved algorithms for testing monotonicity of functions.

Namely, given the ability to query an unknown function $f$, where

$\Sigma$ and $\Xi$ are finite ordered sets, the test always accepts a

monotone $f$, and rejects $f$ with high probability if it is $\e$-far

from being monotone (i.e., every ...
more >>>

Eldar Fischer

An $\epsilon$-test for a property $P$ of functions from

${\cal D}=\{1,\ldots,d\}$ to the positive integers is a randomized

algorithm, which makes queries on the value of an input function at

specified locations, and distinguishes with high probability between the

case of the function satisfying $P$, and the case that it ...
more >>>

Michal Parnas, Dana Ron, Ronitt Rubinfeld

A standard property testing algorithm is required to determine

with high probability whether a given object has property

P or whether it is \epsilon-far from having P, for any given

distance parameter \epsilon. An object is said to be \epsilon-far

from having ...
more >>>

David GarcĂa Soriano, Arie Matsliah, Sourav Chakraborty, Jop Briet

We study the problem of monotonicity testing over the hypercube. As

previously observed in several works, a positive answer to a natural question about routing

properties of the hypercube network would imply the existence of efficient

monotonicity testers. In particular, if any $\ell$ disjoint source-sink pairs

on the directed hypercube ...
more >>>

Deeparnab Chakrabarty, C. Seshadhri

The problem of monotonicity testing of the boolean hypercube is a classic well-studied, yet unsolved

question in property testing. We are given query access to $f:\{0,1\}^n \mapsto R$

(for some ordered range $R$). The boolean hypercube ${\cal B}^n$ has a natural partial order, denoted by $\prec$ (defined by the product ...
more >>>

Pranjal Awasthi, Madhav Jha, Marco Molinaro, Sofya Raskhodnikova

We study local filters for two properties of functions $f:\B^d\to \mathbb{R}$: the Lipschitz property and monotonicity. A local filter with additive error $a$ is a randomized algorithm that is given black-box access to a function $f$ and a query point $x$ in the domain of $f$. Its output is a ... more >>>

Deeparnab Chakrabarty, C. Seshadhri

Given oracle access to a Boolean function $f:\{0,1\}^n \mapsto \{0,1\}$, we design a randomized tester that takes as input a parameter $\eps>0$, and outputs {\sf Yes} if the function is monotone, and outputs {\sf No} with probability $>2/3$, if the function is $\eps$-far from monotone. That is, $f$ needs to ... more >>>

Eric Blais, Sofya Raskhodnikova, Grigory Yaroslavtsev

We introduce strong, and in many cases optimal, lower bounds for the number of queries required to nonadaptively test three fundamental properties of functions $ f : [n]^d \rightarrow \mathbb R$ on the hypergrid: monotonicity, convexity, and the Lipschitz property.

Our lower bounds also apply to the more restricted setting ...
more >>>

Peyman Afshani, Kevin Matulef, Bryan Wilkinson

We define a new property testing model for algorithms that do not have arbitrary query access to the input, but must instead traverse it in a manner that respects the underlying data structure in which it is stored. In particular, we consider the case when the underlying data structure is ... more >>>

Eric Blais, Clement Canonne, Igor Carboni Oliveira, Rocco Servedio, Li-Yang Tan

Monotone Boolean functions, and the monotone Boolean circuits that compute them, have been intensively studied in complexity theory. In this paper we study the structure of Boolean functions in terms of the minimum number of negations in any circuit computing them, a complexity measure that interpolates between monotone functions and ... more >>>

Clement Canonne, Elena Grigorescu, Siyao Guo, Akash Kumar, Karl Wimmer

A Boolean $k$-monotone function defined over a finite poset domain ${\cal D}$ alternates between the values $0$ and $1$ at most $k$ times on any ascending chain in ${\cal D}$. Therefore, $k$-monotone functions are natural generalizations of the classical monotone functions, which are the $1$-monotone functions.

Motivated by the ... more >>>

Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Nithin Varma

We investigate the parameters in terms of which the complexity of sublinear-time algorithms should be expressed. Our goal is to find input parameters that are tailored to the combinatorics of the specific problem being studied and design algorithms that run faster when these parameters are small. This direction enables us ... more >>>