Author name cluster

Yadu Vasudev

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

6 papers

2 author rows

MFCS Conference 2018 Conference Paper

A Two-Sided Error Distributed Property Tester For Conductance

Hendrik Fichtenberger
Yadu Vasudev

We study property testing in the distributed model and extend its setting from testing with one-sided error to testing with two-sided error. In particular, we develop a two-sided error property tester for general graphs with round complexity O(log(n) / (epsilon Phi^2)) in the CONGEST model, which accepts graphs with conductance Phi and rejects graphs that are epsilon-far from having conductance at least Phi^2 / 1000 with constant probability. Our main insight is that one can start poly(n) random walks from a few random vertices without violating the congestion and unite the results to obtain a consistent answer from all vertices. For connected graphs, this is even possible when the number of vertices is unknown. We also obtain a matching Omega(log n) lower bound for the LOCAL and CONGEST models by an indistinguishability argument. Although the power of vertex labels that arises from two-sided error might seem to be much stronger than in the sequential query model, we can show that this is not the case.

Details

TCS Journal 2015 Journal Article

On the isomorphism problem for decision trees and decision lists

V. Arvind
Johannes Köbler
Sebastian Kuhnert
Gaurav Rattan
Yadu Vasudev

We study the complexity of isomorphism testing for boolean functions that are represented by decision trees or decision lists. Our results are the following: • Isomorphism testing of rank 1 decision trees is complete for logspace. • For any constant r ≥ 2, isomorphism testing for rank r decision trees is polynomial-time equivalent to Graph Isomorphism. As a consequence of our reduction, we obtain our main result for decision trees: A 2 n ( log ⁡ s ) O ( 1 ) time algorithm for isomorphism testing of decision trees of size s over n variables. • The isomorphism problem for decision lists admits a Schaefer-type trichotomy: depending on the class of base functions, the isomorphism problem is either in L, or polynomial-time equivalent to Graph Isomorphism, or coNP -hard.

Details DOI

FOCS Conference 2015 Conference Paper

Trading Query Complexity for Sample-Based Testing and Multi-testing Scalability

Eldar Fischer
Oded Lachish
Yadu Vasudev

We show that every non-adaptive property testing algorithm making a constant number of queries, over a fixed alphabet, can be converted to a sample-based (as per [Gold Reich and Ron, 2015]) testing algorithm whose average number of queries is a fixed, smaller than 1, power of n. Since the query distribution of the sample-based 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, such as testing (relatively large) unions of properties, or converting a Merlin-Arthur Proximity proof (as per [Gur and Rothblum, 2013]) to a proper testing algorithm. The proof method involves preparing the original testing algorithm for a combinatorial analysis. For the analysis we develop a structural lemma for hyper graphs that may be of independent interest. When analyzing a hyper graph that was extracted from a 2-sided test, it allows for finding generalized sunflowers that provide for a large-deviation type analysis. For 1-sided tests the bounds can be improved further by applying Janson's inequality directly over our structures.

Details

I&C Journal 2014 Journal Article

Isomorphism testing of Boolean functions computable by constant-depth circuits

V. Arvind
Yadu Vasudev

Given two n-variable Boolean functions f and g, we study the problem of computing an ε-approximate isomorphism between them. An ε-approximate isomorphism is a permutation π of the n Boolean variables such that f ( x 1, x 2, …, x n ) and g ( x π ( 1 ), x π ( 2 ), …, x π ( n ) ) differ on at most an ε fraction of all Boolean inputs { 0, 1 } n. We give a randomized 2 O ( n log ⁡ ( n / ε ) O ( d ) ) time algorithm that computes an ε-approximate isomorphism between two isomorphic Boolean functions f and g that are given by depth d circuits of poly ( n ) size, where d is a constant independent of n, for any positive ε. In contrast, the best known algorithm for computing an exact isomorphism between n-ary Boolean functions has running time 2 O ( n ) [12] even for functions computed by poly ( n ) size DNF formulas. Our algorithm is based on a result for hypergraph isomorphism with bounded edge size [4] and the classical Linial–Mansour–Nisan result on approximating small depth and size Boolean circuits by small degree polynomials using Fourier analysis [11].

Details DOI

MFCS Conference 2012 Conference Paper

Approximate Graph Isomorphism

Vikraman Arvind
Johannes Köbler
Sebastian Kuhnert
Yadu Vasudev

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 non-edges mapped to non-edges). We give an n O (log n ) time approximation scheme that for any constant factor α < 1, computes an α -approximation. We prove this by combining the n O (log n ) time additive error approximation algorithm of Arora et al. [ Math. Program. , 92, 2002] with a simple averaging algorithm. We also consider the corresponding minimization problem (of mismatches) and prove that it is NP -hard to α -approximate for any constant factor α. Further, we show that it is also NP -hard 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.

Details

MFCS Conference 2012 Conference Paper

Near-Optimal Expanding Generator Sets for Solvable Permutation Groups

Vikraman Arvind
Partha Mukhopadhyay
Prajakta Nimbhorkar
Yadu Vasudev

Abstract Let G = 〈 S 〉 be a solvable subgroup of the symmetric group S n given as input by the generator set S. We give a deterministic polynomial-time algorithm that computes an expanding generator set of size Õ( n 2 ) for G. As a byproduct of our proof, we obtain a new explicit construction of ε -bias spaces of size Õ \((n{\rm poly}({\rm log} d))({{1}\over{\varepsilon}})^{O(1)}\) for the groups \(\mathbb{Z}_d^n\).

Details