Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Akash Kumar:

TR17-088 | 10th May 2017
Elena Grigorescu, Akash Kumar, Karl Wimmer

K-Monotonicity is Not Testable on the Hypercube

We continue the study of $k$-monotone Boolean functions in the property testing model, initiated by Canonne et al. (ITCS 2017). A function $f:\{0,1\}^n\rightarrow \{0,1\}$ is said to be $k$-monotone if it alternates between $0$ and $1$ at most $k$ times on every ascending chain. Such functions represent a natural generalization ... more >>>

TR16-136 | 31st August 2016
Clement Canonne, Elena Grigorescu, Siyao Guo, Akash Kumar, Karl Wimmer

Testing k-Monotonicity

Revisions: 1

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 >>>

ISSN 1433-8092 | Imprint