  Under the auspices of the Computational Complexity Foundation (CCF)     REPORTS > AUTHORS > AKASH KUMAR:
All reports by Author Akash Kumar:

TR19-046 | 1st April 2019
Akash Kumar, C. Seshadhri, Andrew Stolman

#### andom walks and forbidden minors II: A $\poly(d\eps^{-1})$-query tester for minor-closed properties of bounded degree graphs

Revisions: 1

Let $G$ be a graph with $n$ vertices and maximum degree $d$. Fix some minor-closed property $\mathcal{P}$ (such as planarity).
We say that $G$ is $\varepsilon$-far from $\mathcal{P}$ if one has to remove $\varepsilon dn$ edges to make it have $\mathcal{P}$.
The problem of property testing $\mathcal{P}$ was introduced in ... more >>>

TR18-148 | 25th August 2018
Akash Kumar, C. Seshadhri, Andrew Stolman

#### Finding forbidden minors in sublinear time: a $n^{1/2+o(1)}$-query one-sided tester for minor closed properties on bounded degree graphs

Let $G$ be an undirected, bounded degree graph
with $n$ vertices. Fix a finite graph $H$, and suppose one must remove $\varepsilon n$ edges from $G$ to make it $H$-minor free (for some small constant $\varepsilon > 0$). We give an $n^{1/2+o(1)}$-time randomized procedure that, with high probability, finds an ... more >>>

TR18-101 | 20th May 2018
Akash Kumar, C. Seshadhri, Andrew Stolman

#### Finding forbidden minors in sublinear time: a $O(n^{1/2+o(1)})$-query one-sided tester for minor closed properties on bounded degree graphs

Let $G$ be an undirected, bounded degree graph with $n$ vertices. Fix a finite graph $H$, and suppose one must remove $\varepsilon n$ edges from $G$ to make it $H$-minor free (for some small constant $\varepsilon > 0$).
We give an $n^{1/2+o(1)}$-time randomized procedure that, with high probability, finds an ... more >>>

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

#### K-Monotonicity is Not Testable on the Hypercube

Revisions: 1

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