C. Seshadhri 0001

SODA Conference 2025 Conference Paper

A Dichotomy Hierarchy for Linear Time Subgraph Counting in Bounded Degeneracy Graphs

• Daniel Paul-Pena
• C. Seshadhri 0001

STOC Conference 2025 Conference Paper

Monotonicity Testing of High-Dimensional Distributions with Subcube Conditioning

• Deeparnab Chakrabarty
• Xi Chen 0001
• Simeon Ristic
• C. Seshadhri 0001
• Erik Waingarten

We study monotonicity testing of high-dimensional distributions on {−1,1} n in the model of subcube conditioning, suggested and studied by Canonne, Ron, and Servedio and Bhattacharyya and Chakraborty. Previous work shows that the sample complexity of monotonicity testing must be exponential in n (Rubinfeld, Vasilian, and Aliakbarpour, Gouleakis, Peebles, Rubinfeld, Yodpinyanee). We show that the subcube query complexity is Θ( n /є 2 ), by proving nearly matching upper and lower bounds. Our work is the first to use directed isoperimetric inequalities (developed for function monotonicity testing) for analyzing a distribution testing algorithm. Along the way, we generalize an inequality of Khot, Minzer, and Safra to real-valued functions on {−1,1} n . We also study uniformity testing of distributions that are promised to be monotone, a problem introduced by Rubinfeld, Servedio, using subcube conditioning. We show that the query complexity is Θ(√ n /є 2 ). Our work proves the lower bound, which matches (up to poly-logarithmic factors) the uniformity testing upper bound for general distributions (Canonne, Chen, Kamath, Levi, Waingarten). Hence, we show that monotonicity does not help, beyond logarithmic factors, in testing uniformity of distributions with subcube conditional queries.

FOCS Conference 2023 Conference Paper

A d 1/2+o(1) Monotonicity Tester for Boolean Functions on d-Dimensional Hypergrids

• Hadley Black
• Deeparnab Chakrabarty
• C. Seshadhri 0001

Monotonicity testing of Boolean functions on the hypergrid, $f: [n]^{d} \rightarrow\{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}\left(\varepsilon^{-4 / 3} d^{5 / 6}\right)$. This complexity is independent of n, but has a suboptimal dependence on d. Recently, [Braverman-Khot-Kindler-Minzer, ITCS 2023] and [Black-Chakrabarty-Seshadhri, STOC 2023] describe $\widetilde{O}\left(\varepsilon^{-2} n^{3} \sqrt{d}\right)$ and $\widetilde{O}\left(\varepsilon^{-2} n \sqrt{d}\right)$-query testers, respectively. These testers have an almost optimal dependence on d, but a suboptimal polynomial dependence on n. In this paper, we describe a non-adaptive, onesided monotonicity tester with query complexity $O\left(\varepsilon^{-2} d^{1 / 2+o(1)}\right)$, independent of n. Up to the $d^{o(1)}$. factors, our result resolves the non-adaptive complexity of monotonicity testing for Boolean functions on hypergrids. The independence of n yields a non-adaptive, one-sided $O\left(\varepsilon^{-2} d^{1 / 2+o(1)}\right)$-query monotonicity tester for Boolean functions $f: \mathbb{R}^{d} \rightarrow\{0, 1\}$ associated with an arbitrary product measure.

STOC Conference 2023 Conference Paper

Directed Isoperimetric Theorems for Boolean Functions on the Hypergrid and an Õ(n√d) Monotonicity Tester

• Hadley Black
• Deeparnab Chakrabarty
• C. Seshadhri 0001

The problem of testing monotonicity for Boolean functions on the hypergrid, f :[ n ] d → {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 O (ε −2 √ d ) queries. Up to polylog d and ε factors, this bound matches the Ω(√ d )-query non-adaptive lower bound (Chen-De-Servedio-Tan (STOC 2015), Chen-Waingarten-Xie (STOC 2017)). For any n > 2, the optimal non-adaptive complexity was unknown. A previous result of the authors achieves a O ( d 5/6 )-query upper bound (SODA 2020), quite far from the √ d bound for the hypercube. In this paper, we resolve the non-adaptive complexity of monotonicity testing for all constant n , up to poly (ε −1 log d ) factors. Specifically, we give a non-adaptive, one-sided monotonicity tester making O (ε −2 n √ d ) queries. From a technical standpoint, we prove new directed isoperimetric theorems over the hypergrid [ n ] d . These results generalize the celebrated directed Talagrand inequalities that were only known for the hypercube.

ICML Conference 2023 Conference Paper

Theoretical Bounds on the Network Community Profile from Low-rank Semi-definite Programming

• Yufan Huang
• C. Seshadhri 0001
• David F. Gleich

We study a new connection between a technical measure called $\mu$-conductance that arises in the study of Markov chains for sampling convex bodies and the network community profile that characterizes size-resolved properties of clusters and communities in social and information networks. The idea of $\mu$-conductance is similar to the traditional graph conductance, but disregards sets with small volume. We derive a sequence of optimization problems including a low-rank semi-definite program from which we can derive a lower bound on the optimal $\mu$-conductance value. These ideas give the first theoretically sound bound on the behavior of the network community profile for a wide range of cluster sizes. The algorithm scales up to graphs with hundreds of thousands of nodes and we demonstrate how our framework validates the predicted structures of real-world graphs.

SODA Conference 2022 Conference Paper

The complexity of testing all properties of planar graphs, and the role of isomorphism

• Sabyasachi Basu
• Akash Kumar 0003
• C. Seshadhri 0001

Consider property testing on bounded degree graphs and let ∊ > 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 ∊. Recent advances in testing minor-freeness have proven that all additive and monotone properties of planar graphs can be tested in poly( ∊ –1 ) queries. Some properties falling outside this class, such as Hamiltonicity, also have a similar complexity for planar graphs. Motivated by these results, we ask: can all properties of planar graphs can be tested in poly( ∊ –1 ) queries? Is there a uniform query complexity upper bound for all planar properties, and what is the “hardest” such property to test? We discover a surprisingly clean and optimal answer. Any property of bounded degree planar graphs can be tested in exp( O ( ∊ –2 )) queries. Moreover, there is a matching lower bound, up to constant factors in the exponent. The natural property of testing isomorphism to a fixed graph requires exp(Ω( ∊ –2 )) queries, thereby showing that (up to polynomial dependencies) isomorphism to an explicit fixed graph is the hardest property of planar graphs. The upper bound is a straightforward adaptation of the Newman-Sohler analysis that tracks dependencies on ∊ more carefully. The main technical contribution is the lower bound construction, which is achieved by a special family of planar graphs that are all mutually far from each other. We can also apply our techniques to get analogous results for bounded treewidth graphs. We prove that all properties of bounded treewidth graphs can be tested in exp( O ( ∊ –1 log ∊ –1 )) queries. Moreover, testing isomorphism to a fixed forest requires exp(Ω( ∊ –1 )) queries.

SODA Conference 2021 Conference Paper

Near-Linear Time Homomorphism Counting in Bounded Degeneracy Graphs: The Barrier of Long Induced Cycles

• Suman K. Bera 0001
• Noujan Pashanasangi
• C. Seshadhri 0001

Counting homomorphisms of a constant sized pattern graph H in an input graph G is a fundamental computational problem. There is a rich history of studying the complexity of this problem, under various constraints on the input G and the pattern H. Given the significance of this problem and the large sizes of modern inputs, we investigate when near-linear time algorithms are possible. We focus on the case when the input graph has bounded degeneracy, a commonly studied and practically relevant class for homomorphism counting. It is known from previous work that for certain classes of H, H -homomorphisms can be counted exactly in near-linear time in bounded degeneracy graphs. Can we precisely characterize the patterns H for which near-linear time algorithms are possible? We completely resolve this problem, discovering a clean dichotomy using fine-grained complexity. Let m denote the number of edges in G. We prove the following: if the largest induced cycle in H has length at most 5, then there is an O(m log m ) algorithm for counting H -homomorphisms in bounded degeneracy graphs. If the largest induced cycle in H has length at least 6, then (assuming standard fine-grained complexity conjectures) there is a constant γ > 0, such that there is no o ( m 1+ γ ) time algorithm for counting H -homomorphisms.

FOCS Conference 2021 Conference Paper

Random walks and forbidden minors III: $\text{poly}\left(d\varepsilon ^{-1}\right)$-time partition oracles for minor-free graph classes

• Akash Kumar 0003
• C. Seshadhri 0001
• 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, one removes a small fraction of edges of the graph controlled by a proximity parameter to get connected components of size independent of $n$. An important tool for sublinear algorithms and property testing for such classes is the partition oracle, introduced by the seminal work of Hassidim-Kelner-Nguyen-Onak (FOCS 2009). A partition oracle is a local procedure that gives consistent access to a hyperfinite decomposition, without any preprocessing. Given a query vertex v, the partition oracle outputs the component containing v in time independent of n. All the answers are consistent with a single hyperfinite decomposition. The partition oracle of Hassidim et al. runs in time exponential in the proximity parameter per query. They pose the open problem of whether partition oracles which run in time polynomial in reciprocal of proximity parameter can be built. Levi-Ron (ICALP 2013) give a refinement of the previous approach, to get a partition oracle that runs in quasipolynomial time per query. In this paper, we resolve this open problem and give polynomial time partition oracles (in reciprocal of proximity parameter) for bounded degree graphs in any minor-closed family. Unlike the previous line of work based on combinatorial methods, we employ techniques from spectral graph theory. We build on a recent spectral graph theoretical toolkit for minor-closed graph families, introduced by the authors to develop efficient property testers. A consequence of our result is an efficient property tester for any monotone and additive with running time property of minor-closed families (such as bipartite planar graphs). Our result also gives query efficient algorithms for additive approximations for problems such as maximum matching, minimum vertex cover, maximum independent set, and minimum dominating set for these graph families.

SODA Conference 2020 Conference Paper

Domain Reduction for Monotonicity Testing: A o ( d ) Tester for Boolean Functions in d -Dimensions

• Hadley Black
• Deeparnab Chakrabarty
• C. Seshadhri 0001

We describe a Õ ( d 5/6 )-query monotonicity tester for Boolean functions f: [ n ] d → {0, 1} on the n hypergrid. This is the first o ( d ) monotonicity tester with query complexity independent of n. Motivated by this independence of n, we initiate the study of monotonicity testing of measurable Boolean functions f: ℝ d → {0, 1} over the continuous domain, where the distance is measured with respect to a product distribution over ℝ d. We give a Õ ( d 5/6 )-query monotonicity tester for such functions. Our main technical result is a domain reduction theorem for monotonicity. For any function f: [ n ] d → {0, 1}, let ε f be its distance to monotonicity. Consider the restriction of the function on a random [ k ] d sub-hypergrid of the original domain. We show that for k = poly( d / ε f ), the expected distance of the restriction is. Previously, such a result was only known for d = 1 (Berman-Raskhodnikova-Yaroslavtsev, STOC 2014). Our result for testing Boolean functions over [ n ] d then follows by applying the d 5/6 · poly(1/ ε log n, log d )-query hypergrid tester of Black-Chakrabarty-Seshadhri (SODA 2018). To obtain the result for testing Boolean functions over ℝ d, we use standard measure theoretic tools to reduce monotonicity testing of a measurable function f to monotonicity testing of a discretized version of f over a hypergrid domain [ N ] d for large, but finite, N (that may depend on f ). The independence of N in the hypergrid tester is crucial to getting the final tester over ℝ d.

SODA Conference 2020 Conference Paper

Faster sublinear approximation of the number of k -cliques in low-arboricity graphs

• Talya Eden
• Dana Ron
• C. Seshadhri 0001

STOC Conference 2019 Conference Paper

Random walks and forbidden minors II: a poly( d ε -1 )-query tester for minor-closed properties of bounded degree graphs

• Akash Kumar 0003
• C. Seshadhri 0001
• Andrew Stolman

Let G be a graph with n vertices and maximum degree d . Fix some minor-closed property P (such as planarity). We say that G is ε-far from P if one has to remove ε dn edges to make it have P . The problem of property testing P was introduced in the seminal work of Benjamini-Schramm-Shapira (STOC 2008) that gave a tester with query complexity triply exponential in ε −1 . Levi-Ron (TALG 2015) have given the best tester to date, with a quasipolynomial (in ε −1 ) query complexity. It is an open problem to get property testers whose query complexity is ( d ε −1 ), even for planarity.

SODA Conference 2018 Conference Paper

A o ( d ) · polylog n Monotonicity Tester for Boolean Functions over the Hypergrid [ n ] d

• Hadley Black
• Deeparnab Chakrabarty
• C. Seshadhri 0001

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 Õ ( d 5/6 ). poly(log n, 1/ ε ). Previous to our work, the best known testers had query complexity linear in d but independent of n. We improve upon these testers as long as n = 2 d o (1). To obtain our results, we work with what we call the augmented hypergrid, which adds extra edges to the hypergrid. Our main technical contribution is a Margulis-style isoperimetric result for the augmented hypergrid, and our tester, like previous testers for the hypercube domain, performs directed random walks on this structure.

FOCS Conference 2018 Conference Paper

Finding Forbidden Minors in Sublinear Time: A n^1/2+o(1)-Query One-Sided Tester for Minor Closed Properties on Bounded Degree Graphs

• Akash Kumar 0003
• C. Seshadhri 0001
• Andrew Stolman

Let G be an undirected, bounded degree graph with n vertices. Fix a finite graph H, and suppose one must remove ε n edges from G to make it H-minor free (for some small constant ε > 0). We give an n 1/2+o(1) -time randomized procedure that, with high probability, finds an H-minor in such a graph. As an application, suppose one must remove ε n edges from a bounded degree graph G to make it planar. This result implies an algorithm, with the same running time, that produces a K 3, 3 or K 5 minor in G. No prior sublinear time bound was known for this problem. By the graph minor theorem, we get an analogous result for any minor-closed property. Up to n o(1) factors, this resolves a conjecture of Benjamini-Schramm-Shapira (STOC 2008) on the existence of one-sided property testers for minor-closed properties. Furthermore, our algorithm is nearly optimal, by an Ω(√n) lower bound of Czumaj et al (RSA 2014). Prior to this work, the only graphs H for which non-trivial one-sided property testers were known for H-minor freeness are the following: H being a forest or a cycle (Czumaj et al, RSA 2014), K 2, k, (k× 2)-grid, and the k-circus (Fichtenberger et al, Arxiv 2017).

STOC Conference 2018 Conference Paper

On approximating the number of k-cliques in sublinear time

• Talya Eden
• Dana Ron
• C. Seshadhri 0001

We study the problem of approximating the number of k -cliques in a graph when given query access to the graph. We consider the standard query model for general graphs via (1) degree queries, (2) neighbor queries and (3) pair queries. Let n denote the number of vertices in the graph, m the number of edges, and C k the number of k -cliques. We design an algorithm that outputs a (1+ε)-approximation (with high probability) for C k , whose expected query complexity and running time are O ( n / C k 1/ k + m k /2 / C k )(log n , 1/ε, k ). Hence, the complexity of the algorithm is sublinear in the size of the graph for C k = ω( m k /2−1 ). Furthermore, we prove a lower bound showing that the query complexity of our algorithm is essentially optimal (up to the dependence on log n , 1/ε and k ). The previous results in this vein are by Feige (SICOMP 06) and by Goldreich and Ron (RSA 08) for edge counting ( k =2) and by Eden et al. (FOCS 2015) for triangle counting ( k =3). Our result matches the complexities of these results. The previous result by Eden et al. hinges on a certain amortization technique that works only for triangle counting, and does not generalize for larger cliques. We obtain a general algorithm that works for any k ≥ 3 by designing a procedure that samples each k -clique incident to a given set S of vertices with approximately equal probability. The primary difficulty is in finding cliques incident to purely high-degree vertices, since random sampling within neighbors has a low success probability. This is achieved by an algorithm that samples uniform random high degree vertices and a careful tradeoff between estimating cliques incident purely to high-degree vertices and those that include a low-degree vertex.

SODA Conference 2017 Conference Paper

Accurate and Nearly Optimal Sublinear Approximations to Ulam Distance

• Timothy Naumovitz
• Michael E. Saks
• C. Seshadhri 0001

The Ulam distance between two permutations of length η is the minimum number of insertions and deletions needed to transform one sequence into the other. Equivalently, the Ulam distance d is n minus the length of the longest common subsequence (LCS) between the permutations. Our main result is an algorithm, that for any fixed ∊ > 0, provides a (1 + ∊)-multiplicative approximation for d in time, which has been shown to be optimal up to polylogarithmic factors. This is the first sublinear time algorithm (provided that d = (log n ) ω(1) ) that obtains arbitrarily good multiplicative approximations to the Ulam distance. The previous best bound is an O (1)-approximation (with a large constant) by Andoni and Nguyen (2010) with the same running time bound (ignoring polylogarithmic factors). The improvement in the approximation factor from O (1) to (1 + ∊) allows for significantly more powerful sublinear algorithms. For example, for any fixed δ > 0, we can get additive δη approximations for the LCS between permutations in time. Previous sublinear algorithms require δ to be at least 1–1 /C, where c is the approximation factor, which is close to 1 when c is large. Our algorithm is obtained by abstracting the basic algorithmic framework of Andoni and Nguyen, and combining it with the sublinear approximations for the longest increasing subsequence by Saks and Seshadhri (2010).

FOCS Conference 2015 Conference Paper

Approximately Counting Triangles in Sublinear Time

• Talya Eden
• Amit Levi
• Dana Ron
• C. Seshadhri 0001

We consider the problem of estimating the number of triangles in a graph. This problem has been extensively studied in both theory and practice, but all existing algorithms read the entire graph. In this work we design a sublinear-time algorithm for approximating the number of triangles in a graph, where the algorithm is given query access to the graph. The allowed queries are degree queries, vertex-pair queries and neighbor queries. We show that for any given approximation parameter 0<; epsilon<; 1, the algorithm provides an estimate hat{t} such that with high constant probability, (1-epsilon) t<; hat{t}κ(1+epsilon)t, where t is the number of triangles in the graph G. The expected query complexity of the algorithm is O(n/t̂{1/3} + min {m, m̂{3/2}/t}) poly(log n, 1/epsilon), where n is the number of vertices in the graph and m is the number of edges, and the expected running time is (n/t̂{1/3} + m̂{3/2}/t) poly(log n, 1/epsilon). We also prove that Omega(n/t̂{1/3} + min {m, m̂{3/2}/t}) queries are necessary, thus establishing that the query complexity of this algorithm is optimal up to polylogarithmic factors in n (and the dependence on 1/epsilon).

SODA Conference 2015 Conference Paper

Property Testing on Product Distributions: Optimal Testers for Bounded Derivative Properties

• Deeparnab Chakrabarty
• Kashyap Dixit
• Madhav Jha
• C. Seshadhri 0001

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 uniform distribution on the domain. This restriction to uniformity is rather limiting, and it is important to investigate distances induced by more general distributions. In this paper, we give simple and optimal testers for bounded derivative properties over arbitrary product distributions. Bounded derivative properties include fundamental properties such as monotonicity and Lipschitz continuity. Our results subsume almost all known results (upper and lower bounds) on monotonicity and Lipschitz testing. We prove an intimate connection between bounded derivative property testing and binary search trees (BSTs). We exhibit a tester whose query complexity is the sum of expected depths of optimal BSTs for each marginal. Furthermore, we show this sum-of-depths is also a lower bound. A technical contribution of our work is an optimal dimension reduction theorem for all bounded derivative properties, which relates the distance of a function from the property to the distance of restrictions of the function to random lines. Such a theorem has been elusive even for monotonicity, and our theorem is an exponential improvement to the previous best known result.

STOC Conference 2013 Conference Paper

A o(n) monotonicity tester for boolean functions over the hypercube

• Deeparnab Chakrabarty
• C. Seshadhri 0001

Given oracle access to a Boolean function f:{0,1} n -> {0,1}, we design a randomized tester that takes as input a parameter ε>0, and outputs Yes if the function is monotonically non-increasing, and outputs No with probability >2/3, if the function is ε-far from being monotone, that is, f needs to be modified at ε-fraction of the points to make it monotone. Our non-adaptive, one-sided tester makes ~O(n 5/6 ε -5/3 ) queries to the oracle.

STOC Conference 2013 Conference Paper

Optimal bounds for monotonicity and lipschitz testing over hypercubes and hypergrids

• Deeparnab Chakrabarty
• C. Seshadhri 0001

The problem of monotonicity testing over the hypergrid and its special case, the hypercube, is a classic question in property testing. We are given query access to f:[k] n -> R (for some ordered range R). The hypergrid/cube has a natural partial order given by coordinate-wise ordering, denoted by prec. A function is monotone if for all pairs x prec y, f(x) ≤ f(y). The distance to monotonicity, ε f , is the minimum fraction of values of f that need to be changed to make f monotone. For k=2 (the boolean hypercube), the usual tester is the edge tester , which checks monotonicity on adjacent pairs of domain points. It is known that the edge tester using O(ε -1 n log|R|) samples can distinguish a monotone function from one where ε f > ε. On the other hand, the best lower bound for monotonicity testing over general R is Ω(n). We resolve this long standing open problem and prove that O(n/ε) samples suffice for the edge tester. For hypergrids, known testers require O(ε -1 n log k log |R|) samples, while the best known (non-adaptive) lower bound is Ω(ε -1 n log k). We give a (non-adaptive) monotonicity tester for hypergrids running in O(ε {-1} n log k) time.

SODA Conference 2013 Conference Paper

Space efficient streaming algorithms for the distance to monotonicity and asymmetric edit distance

• Michael E. Saks
• C. Seshadhri 0001

Approximating the length of the longest increasing sequence (LIS) of an array is a well-studied problem. We study this problem in the data stream model, where the algorithm is allowed to make a single left-to-right pass through the array and the key resource to be minimized is the amount of additional memory used. We present an algorithm which, for any δ > 0, given streaming access to an array of length n provides a (1 + δ)-multiplicative approximation to the distance to monotonicity ( n minus the length of the LIS), and uses only O((log 2 n )/δ) space. The previous best known approximation using polylogarithmic space was a multiplicative 2-factor. The improved approximation factor reflects a qualitative difference between our algorithm and previous algorithms: previous polylogarithmic space algorithms could not reliably detect increasing subsequences of length as large as n /2, while ours can detect increasing subsequences of length βn for any β > 0. More precisely, our algorithm can be used to estimate the length of the LIS to within an additive δn for any δ > 0 while previous algorithms could only achieve additive error n (1/2 − o (1)). Our algorithm is very simple, being just 3 lines of pseudocode, and has a small update time. It is essentially a polylogarithmic space approximate implementation of a classic dynamic program that computes the LIS. We also show how our technique can be applied to other problems solvable by dynamic programs. For example, we give a streaming algorithm for approximating LCS ( x, y ), the length of the longest common subsequence between strings x and y, each of length n. Our algorithm works in the asymmetric setting (inspired by [AKO10]), in which we have random access to y and streaming access to x, and runs in small space provided that no single symbol appears very often in y. More precisely, it gives an additive- δn approximation to LCS ( x, y ) (and hence also to E ( x, y ) = n − LCS ( x, y ), the edit distance between x and y when insertions and deletions, but not substitutions, are allowed), with space complexity O ( k (log 2 n )/δ), where k is the maximum number of times any one symbol appears in y. We also provide a deterministic 1-pass streaming algorithm that outputs a (1 + δ)-multiplicative approximation for E ( x, y ) (which is also an additive δn-approximation), in the asymmetric setting, and uses ) space. All these algorithms are obtained by carefully trading space and accuracy within a standard dynamic program.

STOC Conference 2011 Conference Paper

Blackbox identity testing for bounded top fanin depth-3 circuits: the field doesn't matter

• Nitin Saxena 0001
• C. Seshadhri 0001

Let C be a depth-3 circuit with n variables, degree d and top fanin k (called ΣΠΣ(k,d,n) circuits) over base field FF. 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 that the problem is open even when k is a constant. This case has been subjected to a serious study over the past few years, starting from the work of Dvir & Shpilka (STOC 2005).

FOCS Conference 2010 Conference Paper

Estimating the Longest Increasing Sequence in Polylogarithmic Time

• Michael E. Saks
• C. Seshadhri 0001

Finding the length of the longest increasing subsequence (LIS) is a classic algorithmic problem. Let n denote the size of the array. Simple O(n log n) time algorithms are known that determine the LIS exactly. In this paper, we develop a randomized approximation algorithm, that for any constant δ > 0, runs in time polylogarithmic in n and estimates the length of the LIS of an array up to an additive error of δn. The algorithm presented in this extended abstract runs in time (log n) O(1/δ). In the full paper, we will give an improved version of the algorithm with running time (log n) c (1/δ) O(1/δ) where the exponent c is independent of δ. Previously, the best known polylogarithmic time algorithms could only achieve an additive n/2-approximation. Our techniques also yield a fast algorithm for estimating the distance to monotonicity to within a small multiplicative factor. The distance of f to monotonicity, ε f, is equal to 1 - |LIS|/n (the fractional length of the complement of the LIS). For any δ > 0, we give an algorithm with running time O((ε f -1 log n) O(1/δ) ) that outputs a (1 + δ)-multiplicative approximation to ε f. This can be improved so that the exponent is a fixed constant. The previously known polylogarithmic algorithms gave only a 2-approximation.

FOCS Conference 2010 Conference Paper

From Sylvester-Gallai Configurations to Rank Bounds: Improved Black-Box Identity Test for Depth-3 Circuits

• Nitin Saxena 0001
• C. Seshadhri 0001

We study the problem of identity testing for depth-3 circuits of top fanin k and degree d. We give a new structure theorem for such identities. A direct application of our theorem improves the known deterministic d -time black-box identity test over rationals (Kayal & Saraf, FOCS 2009) to one that takes d(O(k 2 ))-time. Our structure theorem essentially says that the number of independent variables in a real depth-3 identity is very small. This theorem affirmatively settles the strong rank conjecture posed by Dvir & Shpilka (STOC 2005). We devise a powerful algebraic framework and develop tools to study depth-3 identities. We use these tools to show that any depth-3 identity contains a much smaller nucleus identity that contains most of the "complexity" of the main identity. The special properties of this nucleus allow us to get almost optimal rank bounds for depth-3 identities.

SODA Conference 2010 Conference Paper

Self-improving Algorithms for Convex Hulls

• Kenneth L. Clarkson
• Wolfgang Mulzer
• C. Seshadhri 0001

We describe an algorithm for computing planar convex hulls in the self-improving model: given a sequence I 1, I 2, … of planar n -point sets, the upper convex hull conv( I ) of each set I is desired. We assume that there exists a probability distribution D on n -point sets, such that the inputs I j are drawn independently according to D. Furthermore, D is such that the individual points are distributed independently of each other. In other words, the i 'th point is distributed according to D i. The D i 's can be arbitrary but are independent of each other. The distribution D is not known to the algorithm in advance. After a learning phase of n ε rounds, the expected time to compute conv( I ) is O ( n + H (conv( I ))). Here, H (conv( I )) is the entropy of the output, which is a lower bound for the expected running time of any algebraic computation tree that computes the convex hull. (More precisely, H (conv( I )) is the minimum entropy of any random variable that maps I to a description of conv( I ) and to a labeling scheme that proves nonextremality for every point in I not on the hull.) Our algorithm is thus asymptotically optimal for D. (An erratum has been attached to the previously published proceedings.)

ICML Conference 2009 Conference Paper

Efficient learning algorithms for changing environments

• Elad Hazan
• C. Seshadhri 0001

We study online learning in an oblivious changing environment. The standard measure of regret bounds the difference between the cost of the online learner and the best decision in hindsight. Hence, regret minimizing algorithms tend to converge to the static best optimum, clearly a suboptimal behavior in changing environments. On the other hand, various metrics proposed to strengthen regret and allow for more dynamic algorithms produce inefficient algorithms. We propose a different performance metric which strengthens the standard metric of regret and measures performance with respect to a changing comparator. We then describe a series of data-streaming-based reductions which transform algorithms for minimizing (standard) regret into adaptive algorithms albeit incurring only poly-logarithmic computational overhead. Using this reduction, we obtain efficient low adaptive-regret algorithms for the problem of online convex optimization. This can be applied to various learning scenarios, i.e. online portfolio selection, for which we describe experimental results showing the advantage of adaptivity.

FOCS Conference 2008 Conference Paper

Noise Tolerance of Expanders and Sublinear Expander Reconstruction

• Satyen Kale
• Yuval Peres
• C. Seshadhri 0001

We consider the problem of online sublinear expander reconstruction and its relation to random walks in ``noisy" expanders. Given access to an adjacency list representation of a bounded-degree graph G, we want to convert this graph into a bounded-degree expander G' changing G as little aspossible. The graph G' will be output by a distributed filter: this is sublinear time procedure that given a query vertex, outputs all its neighbors in G', and can do so even in a distributed manner, ensuring consistency in all the answers. One of the main tools in our analysis is a result on the behavior of random walks in graph that are almost expanders: graphs that are formed by arbitrarily connecting a small unknown graph (the noise) to a large expander. We show that a random walk from almost any vertex in the expander part will have fast mixing properties, in the general setting of irreducible finite Markov chains. We alsodesign sublinear time procedures to distinguish vertices of the expander part from those in the noise part, and use this procedure in the reconstruction algorithm.

SODA Conference 2008 Conference Paper

Parallel monotonicity reconstruction

• Michael E. Saks
• C. Seshadhri 0001

SODA Conference 2006 Conference Paper

Self-improving algorithms

• Nir Ailon
• Bernard Chazelle
• C. Seshadhri 0001
• Ding Liu