
A Sublinear Tester for Outerplanarity (and Other Forbidden Minors) With OneSided Error.
with Hendrik Fichtenberger, Reut Levi, and Maximilian Wötzel
ICALP 2018.
[arXiv]
[Abstract]
We consider onesided error property testing of \( \cal F \)minor freeness in boundeddegree graphs for any finite family of graphs \( \cal F\) that contains a minor of \( K_{2,k} \), the \( k \)circus graph, or the \( (k\times 2) \)grid for any \( k\in\mathbb{N} \).
This includes, for instance, testing whether a graph is outerplanar or a cactus graph.
The query complexity of our algorithm in terms of the number of vertices in the graph, \( n \), is \( \tilde{O}(n^{2/3} / \epsilon^5) \).
Czumaj et~al.\ showed that cyclefreeness and \( C_k \)minor freeness can be tested with query complexity \( \tilde{O}(\sqrt{n}) \) by using random walks, and that testing \( H \)minor freeness for any \( H \) that contains a cycles requires \( \Omega(\sqrt{n}) \) queries.
In contrast to these results, we analyze the structure of the graph and show that either we can find a subgraph of sublinear size that includes the forbidden minor \( H \),
or we can find a pair of disjoint subsets of vertices whose edgecut is large, which induces an \( H \)minor.

A TwoSided Error Distributed Property Tester For Conductance.
with Hendrik Fichtenberger
MFCS 2018.
[arXiv]
[Abstract]
We study the problem of testing conductance in the distributed computing model and give a twosided tester that takes \(O(\log n)\) rounds to decide if a graph has conductance at least \( \Phi \) or is \( \epsilon \)far from having conductance at least \( c\Phi^2 \) in the distributed CONGEST model. We also show that \( \Omega(\log n) \) rounds are necessary for testing conductance even in the LOCAL model. In the case of a connected graph, we show that we can perform the test even when the number of vertices in the graph is not known a priori. The key idea in our algorithm is a way to perform a polynomial number of random walks from a set of vertices, avoiding the congestion on the edges.

Improving and extending with testing of distributions for shaperestricted properties.
with Eldar Fischer and
Oded Lachish,
STACS 2017.
[arXiv] [Proceedings]
[Abstract]
Distribution testing deals with what information can be deduced about an unknown distribution over \( \{1,...,n\} \), where the algorithm is only allowed to obtain a relatively small number of independent samples from the distribution. In the extended conditional sampling model, the algorithm is also allowed to obtain samples from the restriction of the original distribution on subsets of \( \{1,...,n\} \). In 2015, Canonne, Diakonikolas, Gouleakis and Rubinfeld unified several previous results, and showed that for any property of distributions satisfying a "decomposability" criterion, there exists an algorithm (in the basic model) that can distinguish with high probability distributions satisfying the property from distributions that are far from it in variation distance. We present here a more efficient yet simpler algorithm for the basic model, as well as very efficient algorithms for the conditional model, which until now was not investigated under the umbrella of decomposable properties. Additionally, we provide an algorithm for the conditional model that handles a much larger class of properties. Our core mechanism is a way of efficiently producing an intervalpartition of {1,...,n} that satisfies a "finegrain" quality. We show that with such a partition at hand we can directly move forward with testing individual intervals, instead of first searching for the "correct" partition of \( \{1,...,n\} \).

Fast distributed algorithms for testing graph properties.
with Keren CensorHillel ,
Eldar Fischer and
Gregory Schwartzman
DISC 2016.
[arXiv]
[Abstract]
We provide a thorough study of distributed property testing – producing algorithms for the approximation problems of property testing in the CONGEST model. In particular, for the socalled dense graph testing model we emulate sequential tests for nearly all graph properties having 1sided tests, while in the general and sparse models we obtain faster tests for trianglefreeness, cyclefreeness and bipartiteness, respectively. In addition, we show a logarithmic lower bound for testing bipartiteness and cyclefreeness, which holds even in the LOCAL model.
In most cases, aided by parallelism, the distributed algorithms have a much shorter running time as compared to their counterparts from the sequential querying model of traditional property testing. The simplest property testing algorithms allow a relatively smooth transitioning to the distributed model. For the more complex tasks we develop new machinery that may be of independent interest.

Trading query complexity for samplebased testing and multitesting scalability.
with Eldar Fischer and
Oded Lachish,
FOCS 2015.
[arXiv]
[Abstract]
We show that every nonadaptive property testing algorithm making a constant number of queries, over a fixed alphabet, can be converted to a samplebased testing algorithm whose average number of queries is a fixed, smaller than 1, power of n. Since the query distribution of the samplebased algorithm is not dependent at all on the property, or the original algorithm, this has many implications in scenarios where there are many properties that need to be tested for concurrently. The proof involves analyzing the tester as a uniform hypergraph, and finding sunflowerlike structures within it.

On the isomorphism problem for decision trees and decision lists.
with V. Arvind,
Johannes Köbler,
Sebastian Kuhnert
and Gaurav Rattan ,
Theoretical Computer Science 590:3854, 2015.
Preliminary version in FCT 2013.
[Abstract]
We study the complexity of testing isomorphism for boolean functions given as decision trees and decision lists. First, we show that the isomorphism problem for rank 1 decision trees is complete for logspace. For decision trees of rank greater than 2, the isomorphism testing problem is polynomialtime equivalent to graph isomorphism. Finally, we show that isomorphism testing of boolean functions given as decision lists admits a Schaefertype trichotomy theorem: depending on the class of base functions, either it is in L, or polynomialtime equivalent to graph isomorphism or coNPhard.

Isomorphism testing of boolean functions computable by constantdepth circuits.
with V. Arvind,
Information and Computation 239:312, 2014.
Preliminary version in LATA 2012.
[ECCC]
[Abstract]
Given two boolean functions as \( AC^0 \) circuits, we study the problem of computing approximate isomorphisms between the functions. We give an algorithm that runs in exp(\( \sqrt{n}\)) time. The best known algorithm for testing the exact isomorphism between two functions has running time \(2^{O(n)}\). The algorithm reduces this problem to testing isomorpshism of hypergraphs of bounded edge size, and uses the approximation of AC0 circuits by lowdegree polynomials by Linial, Mansour and Nisan.

Approximate graph isomorphism.
with V. Arvind,
Johannes Köbler and
Sebastian Kuhnert.
MFCS 2012.
[ECCC]
[Abstract]
We study optimization versions of Graph Isomorphism. Given two graphs \(G_1,G_2\), we are interested in finding a bijection from \(V(G_1)\) to \(V(G_2)\) that maximizes the number of matches (edges mapped to edges or nonedges mapped to nonedges). We give an quasipolynomial time approximation scheme for this problem. We also consider the corresponding minimization problem (of mismatches) and prove that it is NPhard to capproximate for any constant factor c. Further, we show that it is also NPhard to approximate the maximum number of edges mapped to edges beyond a factor of 0.94.
We also explore these optimization problems for bounded color class graphs which is a well studied tractable special case of Graph Isomorphism. Surprisingly, the bounded color class case turns out to be harder than the uncolored case in the approximate setting.

Nearoptimal expanding generator sets for solvable permutation groups.
with V. Arvind,
Partha Mukhopadhyay and
Prajakta Nimbhorkar .
MFCS 2012.
[arXiv]
[Abstract]
Alon and Roichman showed that for any group G, a random subset of size \(O(\log G) \) is an expanding generating set with high probability. In this paper, we show that if G is a solvable subgroup of \( S_n \) that is given by a set of generating permutations, there is a deterministic algorithm to obtain an expanding generating set of size about \( n^2 \). As a byproduct of this construction, we also obtain new constructions of \( \epsilon \)bias spaces for \( \mathbb{Z}_d^n \).