All reports by Author Akash Kumar:

__
TR21-122
| 24th August 2021
__

Sabyasachi Basu, Akash Kumar, C. Seshadhri#### The complexity of testing all properties of planar graphs, and the role of isomorphism

__
TR21-008
| 30th January 2021
__

Akash Kumar, C. Seshadhri, Andrew Stolman#### Random walks and forbidden minors III: poly(d/?)-time partition oracles for minor-free graph classes

Revisions: 3

__
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

__
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

__
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

__
TR17-088
| 10th May 2017
__

Elena Grigorescu, Akash Kumar, Karl Wimmer#### K-Monotonicity is Not Testable on the Hypercube

Revisions: 1

__
TR16-136
| 31st August 2016
__

Clement Canonne, Elena Grigorescu, Siyao Guo, Akash Kumar, Karl Wimmer#### Testing k-Monotonicity

Revisions: 1

Sabyasachi Basu, Akash Kumar, C. Seshadhri

Consider property testing on bounded degree graphs and let $\varepsilon > 0$ denote the proximity parameter. A remarkable theorem of Newman-Sohler (SICOMP 2013) asserts that all properties of planar graphs (more generally hyperfinite) are testable with query complexity only depending on $\varepsilon$. Recent advances in testing minor-freeness have proven that ... more >>>

Akash Kumar, C. Seshadhri, Andrew Stolman

Consider the family of bounded degree graphs in any minor-closed family (such as planar graphs). Let d be the degree bound and n be the number of vertices of such a graph. Graphs in these classes have hyperfinite decompositions, where, for a sufficiently small ? > 0, one removes

?dn ...
more >>>

Akash Kumar, C. Seshadhri, Andrew Stolman

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

Akash Kumar, C. Seshadhri, Andrew Stolman

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

Akash Kumar, C. Seshadhri, Andrew Stolman

We give an $n^{1/2+o(1)}$-time randomized procedure that, with high probability, finds an ...
more >>>

Elena Grigorescu, Akash Kumar, Karl Wimmer

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

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