All reports by Author C. Seshadhri:

__
TR23-048
| 4th April 2023
__

Hadley Black, Deeparnab Chakrabarty, C. Seshadhri#### A $d^{1/2+o(1)}$ Monotonicity Tester for Boolean Functions on $d$-Dimensional Hypergrids

__
TR22-162
| 10th November 2022
__

Hadley Black, Deeparnab Chakrabarty, C. Seshadhri#### Directed Isoperimetric Theorems for Boolean Functions on the Hypergrid and an $\widetilde{O}(n\sqrt{d})$ Monotonicity Tester

__
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-187
| 4th November 2018
__

Hadley Black, Deeparnab Chakrabarty, C. Seshadhri#### Domain Reduction for Monotonicity Testing: A $o(d)$ Tester for Boolean Functions on Hypergrids

Revisions: 4

__
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

__
TR18-005
| 9th January 2018
__

C. Seshadhri, Deeparnab Chakrabarty#### Adaptive Boolean Monotonicity Testing in Total Influence Time

__
TR17-159
| 28th October 2017
__

Hadley Black, Deeparnab Chakrabarty, C. Seshadhri#### A $o(d) \cdot \text{polylog}~n$ Monotonicity Tester for Boolean Functions over the Hypergrid $[n]^d$

__
TR17-111
| 2nd June 2017
__

Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, C. Seshadhri#### A Lower Bound for Nonadaptive, One-Sided Error Testing of Unateness of Boolean Functions over the Hypercube

__
TR17-049
| 14th March 2017
__

Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, C. Seshadhri#### Optimal Unateness Testers for Real-Valued Functions: Adaptivity Helps

__
TR16-133
| 25th August 2016
__

C. Seshadhri, Deeparnab Chakrabarty#### A $\widetilde{O}(n)$ Non-Adaptive Tester for Unateness

Revisions: 1

__
TR14-042
| 2nd April 2014
__

Kashyap Dixit, Deeparnab Chakrabarty, Madhav Jha, C. Seshadhri#### Property Testing on Product Distributions: Optimal Testers for Bounded Derivative Properties

__
TR13-062
| 18th April 2013
__

C. Seshadhri, Deeparnab Chakrabarty#### An optimal lower bound for monotonicity testing over hypergrids

__
TR13-029
| 19th February 2013
__

C. Seshadhri, Deeparnab Chakrabarty#### A {\huge ${o(n)}$} monotonicity tester for Boolean functions over the hypercube

Revisions: 1

__
TR12-035
| 5th April 2012
__

Artur Czumaj, Oded Goldreich, Dana Ron, C. Seshadhri, Asaf Shapira, Christian Sohler#### Finding Cycles and Trees in Sublinear Time

Revisions: 1
,
Comments: 1

__
TR12-030
| 4th April 2012
__

C. Seshadhri, Deeparnab Chakrabarty#### Optimal bounds for monotonicity and Lipschitz testing over the hypercube

Revisions: 2

__
TR10-167
| 5th November 2010
__

Nitin Saxena, C. Seshadhri#### Blackbox identity testing for bounded top fanin depth-3 circuits: the field doesn't matter

__
TR10-013
| 31st January 2010
__

Nitin Saxena, C. Seshadhri#### From Sylvester-Gallai Configurations to Rank Bounds: Improved Black-box Identity Test for Depth-3 Circuits

Revisions: 1

__
TR08-108
| 19th November 2008
__

Nitin Saxena, C. Seshadhri#### An Almost Optimal Rank Bound for Depth-3 Identities

__
TR07-088
| 7th September 2007
__

Elad Hazan, C. Seshadhri#### Adaptive Algorithms for Online Decision Problems

Revisions: 1

__
TR07-076
| 25th July 2007
__

Satyen Kale, C. Seshadhri#### Testing Expansion in Bounded Degree Graphs

Revisions: 1

Hadley Black, Deeparnab Chakrabarty, C. Seshadhri

Monotonicity testing of Boolean functions on the hypergrid, $f:[n]^d \to \{0,1\}$, is a classic topic in property testing. Determining the non-adaptive complexity of this problem is an important open question. For arbitrary $n$, [Black-Chakrabarty-Seshadhri, SODA 2020] describe a tester with query complexity $\widetilde{O}(\varepsilon^{-4/3}d^{5/6})$. This complexity is independent of $n$, but ... more >>>

Hadley Black, Deeparnab Chakrabarty, C. Seshadhri

The problem of testing monotonicity for Boolean functions on the hypergrid, $f:[n]^d \to \{0,1\}$ is a classic topic in property testing. When $n=2$, the domain is the hypercube. For the hypercube case, a breakthrough result of Khot-Minzer-Safra (FOCS 2015) gave a non-adaptive, one-sided tester making $\widetilde{O}(\varepsilon^{-2}\sqrt{d})$ queries. Up to polylog ... more >>>

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

Hadley Black, Deeparnab Chakrabarty, C. Seshadhri

Testing monotonicity of Boolean functions over the hypergrid, $f:[n]^d \to \{0,1\}$, is a classic problem in property testing. When the range is real-valued, there are $\Theta(d\log n)$-query testers and this is tight. In contrast, the Boolean range qualitatively differs in two ways:

(1) Independence of $n$: There are testers ...
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 >>>

C. Seshadhri, Deeparnab Chakrabarty

The problem of testing monotonicity

of a Boolean function $f:\{0,1\}^n \to \{0,1\}$ has received much attention

recently. Denoting the proximity parameter by $\varepsilon$, the best tester is the non-adaptive $\widetilde{O}(\sqrt{n}/\varepsilon^2)$ tester

of Khot-Minzer-Safra (FOCS 2015). Let $I(f)$ denote the total influence

of $f$. We give an adaptive tester whose running ...
more >>>

Hadley Black, Deeparnab Chakrabarty, C. Seshadhri

We study monotonicity testing of Boolean functions over the hypergrid $[n]^d$ and design a non-adaptive tester with $1$-sided error whose query complexity is $\tilde{O}(d^{5/6})\cdot \text{poly}(\log n,1/\epsilon)$. Previous to our work, the best known testers had query complexity linear in $d$ but independent of $n$. We improve upon these testers as ... more >>>

Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, C. Seshadhri

A Boolean function $f:\{0,1\}^d \to \{0,1\}$ is unate if, along each coordinate, the function is either nondecreasing or nonincreasing. In this note, we prove that any nonadaptive, one-sided error unateness tester must make $\Omega(\frac{d}{\log d})$ queries. This result improves upon the $\Omega(\frac{d}{\log^2 d})$ lower bound for the same class of ... more >>>

Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, C. Seshadhri

We study the problem of testing unateness of functions $f:\{0,1\}^d \to \mathbb{R}.$ We give a $O(\frac{d}{\epsilon} \cdot \log\frac{d}{\epsilon})$-query nonadaptive tester and a $O(\frac{d}{\epsilon})$-query adaptive tester and show that both testers are optimal for a fixed distance parameter $\epsilon$. Previously known unateness testers worked only for Boolean functions, and their query ... more >>>

C. Seshadhri, Deeparnab Chakrabarty

Khot and Shinkar (RANDOM, 2016) recently describe an adaptive, $O(n\log(n)/\varepsilon)$-query tester for unateness of Boolean functions $f:\{0,1\}^n \mapsto \{0,1\}$. In this note we describe a simple non-adaptive, $O(n\log(n/\varepsilon)/\varepsilon)$ -query tester for unateness for functions over the hypercube with any ordered range.

Kashyap Dixit, Deeparnab Chakrabarty, Madhav Jha, C. Seshadhri

The primary problem in property testing is to decide whether a given function satisfies a certain property, or is far from any function satisfying it. This crucially requires a notion of distance between functions. The most prevalent notion is the Hamming distance over the {\em uniform} distribution on the domain. ... more >>>

C. Seshadhri, Deeparnab Chakrabarty

For positive integers $n, d$, consider the hypergrid $[n]^d$ with the coordinate-wise product partial ordering denoted by $\prec$.

A function $f: [n]^d \mapsto \mathbb{N}$ is monotone if $\forall x \prec y$, $f(x) \leq f(y)$.

A function $f$ is $\varepsilon$-far from monotone if at least an $\varepsilon$-fraction of values must ...
more >>>

C. Seshadhri, Deeparnab Chakrabarty

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

Artur Czumaj, Oded Goldreich, Dana Ron, C. Seshadhri, Asaf Shapira, Christian Sohler

(This is a revised version of work that was posted on arXiv in July 2010.)

We present sublinear-time (randomized) algorithms for finding simple cycles of length at least $k\geq3$ and tree-minors in bounded-degree graphs.

The complexity of these algorithms is related to the distance

of the graph from being ...
more >>>

C. Seshadhri, Deeparnab Chakrabarty

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

Nitin Saxena, C. Seshadhri

Let C be a depth-3 circuit with n variables, degree d and top fanin k (called sps(k,d,n) circuits) over base field F.

It is a major open problem to design a deterministic polynomial time blackbox algorithm

that tests if C is identically zero.

Klivans & Spielman (STOC 2001) observed ...
more >>>

Nitin Saxena, C. Seshadhri

We study the problem of identity testing for depth-3 circuits, over the

field of reals, of top fanin k and degree d (called sps(k,d)

identities). We give a new structure theorem for such identities and improve

the known deterministic d^{k^k}-time black-box identity test (Kayal &

Saraf, FOCS 2009) to one ...
more >>>

Nitin Saxena, C. Seshadhri

We show that the rank of a depth-3 circuit (over any field) that is simple,

minimal and zero is at most O(k^3\log d). The previous best rank bound known was

2^{O(k^2)}(\log d)^{k-2} by Dvir and Shpilka (STOC 2005).

This almost resolves the rank question first posed by ...
more >>>

Elad Hazan, C. Seshadhri

We study the notion of learning in an oblivious changing environment. Existing online learning algorithms which minimize regret are shown to converge to the average of all locally optimal solutions. We propose a new performance metric, strengthening the standard metric of regret, to capture convergence to locally optimal solutions, and ... more >>>

Satyen Kale, C. Seshadhri

We consider the problem of testing graph expansion in the bounded degree model. We give a property tester that given a graph with degree bound $d$, an expansion bound $\alpha$, and a parameter $\epsilon > 0$, accepts the graph with high probability if its expansion is more than $\alpha$, and ... more >>>