Author name cluster

V. Arvind

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.

20 papers

1 author row

TCS Journal 2025 Journal Article

On the expressibility of the reconstructional color refinement

V. Arvind
Johannes Köbler
Oleg Verbitsky

In this note we explore the color refinement procedure — also known as the 1-dimensional Weisfeiler-Leman procedure, well-studied in connection with the Graph Isomorphism problem — in the context of the Graph Reconstruction conjecture of Ulam. A basic fact about the Ulam reconstruction conjecture is that the connectedness of a graph is determined by the deck of its vertex-deleted subgraphs, which are considered up to isomorphism. We strengthen this result by proving that connectedness of a graph can even be determined from the deck of its vertex-deleted subgraphs given only by their stable colorings (i. e. , up to equivalence under color refinement). It follows as a consequence that connectedness is recognizable by Reconstruction Graph Neural Networks, which is a recently introduced GNN architecture inspired by the reconstruction conjecture (Cotta, Morris, Ribeiro 2021).

I&C Journal 2024 Journal Article

Multivariate to bivariate reduction for noncommutative polynomial factorization

V. Arvind
Pushkar S. Joglekar

Based on Bergman's theorem, we show that multivariate noncommutative polynomial factorization is deterministic polynomial-time reducible to the factorization of bivariate noncommutative polynomials. More precisely, 1. Given an n-variate noncommutative polynomial f ∈ F 〈 X 〉 over a field F as an arithmetic circuit, computing a complete factorization of f into irreducible factors is deterministic polynomial-time reducible to factorization of a noncommutative bivariate polynomial g ∈ F 〈 x, y 〉; the reduction transforms f into a circuit for g, and given a complete factorization of g, the reduction recovers a complete factorization of f in polynomial time. The reduction works both in the white-box and the black-box setting. 2. We show over the field of rationals that bivariate linear matrix factorization problem for 4 × 4 matrices is at least as hard as factoring square-free integers and for 3 × 3 matrices it is in polynomial time.

I&C Journal 2022 Journal Article

On the Weisfeiler-Leman dimension of fractional packing

V. Arvind
Frank Fuhlbrück
Johannes Köbler
Oleg Verbitsky

The k-dimensional Weisfeiler-Leman procedure ( k - WL ), which colors k-tuples of vertices in rounds based on the neighborhood structure in the graph, has proven to be immensely fruitful in the algorithmic study of Graph Isomorphism. More generally, it is of fundamental importance in understanding and exploiting symmetries in graphs in various settings. Two graphs are k - WL -equivalent if the k-dimensional Weisfeiler-Leman procedure produces the same final coloring on both graphs. 1 - WL -equivalence is known as fractional isomorphism of graphs, and the k - WL -equivalence relation becomes finer as k increases. We investigate to what extent standard graph parameters are preserved by k - WL -equivalence, focusing on fractional graph packing numbers. The integral packing numbers are typically NP-hard to compute, and we discuss applicability of k - WL -invariance for estimating the integrality gap of the LP relaxation provided by their fractional counterparts.

I&C Journal 2018 Journal Article

On the complexity of noncommutative polynomial factorization

V. Arvind
Pushkar Joglekar
Gaurav Rattan

In this paper we study the complexity of factorization of polynomials in the free noncommutative ring F 〈 x 1, x 2, …, x n 〉 of polynomials over the field F and noncommuting variables x 1, x 2, …, x n. Our main results are the following: • Although F 〈 x 1, …, x n 〉 is not a unique factorization ring, we note that variable-disjoint factorization in F 〈 x 1, …, x n 〉 has the uniqueness property. Furthermore, we prove that computing the variable-disjoint factorization is polynomial-time equivalent to Polynomial Identity Testing (both when the input polynomial is given by an arithmetic circuit or an algebraic branching program). We also show that variable-disjoint factorization in the black-box setting can be efficiently computed (where the computed factors will be also given by black-boxes). • As a consequence of the previous result we show that homogeneous noncommutative polynomials and multilinear noncommutative polynomials have unique factorizations in the usual sense, which can be efficiently computed. • Finally, we discuss a polynomial decomposition problem in F 〈 x 1, …, x n 〉 which is a natural generalization of homogeneous polynomial factorization and prove some complexity bounds for it.

TCS Journal 2017 Journal Article

Finding fixed point free elements and small bases in permutation groups

V. Arvind

In this paper we study the parameterized complexity of two well-known permutation group problems which are NP-complete. 1. Given a permutation group G = 〈 S 〉 ≤ S n and a parameter k, find a permutation π ∈ G such that | { i ∈ [ n ] | π ( i ) ≠ i } | ≥ k. This generalizes the NP -complete problem of finding a fixed-point free permutation in G [8, 17] (this is the case when k = n ). We show that this problem with parameter k is fixed-parameter tractable. In the process, we give a simple deterministic polynomial-time algorithm for finding a fixed point free element in a transitive permutation group, answering an open question of Cameron [9, 8] (also see [10]). 2. A base for G is a subset B ⊆ [ n ] such that the subgroup of G that fixes B pointwise is trivial. We consider the parameterized complexity of checking if a given permutation group G = 〈 S 〉 ≤ S n has a base of size k, where k is the parameter for the problem. This problem is known to be NP -complete [5]. We show that it is fixed-parameter tractable for cyclic permutation groups and for permutation groups of constant orbit size. For more general classes of permutation groups we do not know whether the problem is in FPT or is W[1]-hard.

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.

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

I&C Journal 2012 Journal Article

The isomorphism problem for k-trees is complete for logspace

V. Arvind
Bireswar Das
Johannes Köbler
Sebastian Kuhnert

We show that, for k constant, k-tree isomorphism can be decided in logarithmic space by giving an O ( k log n ) space canonical labeling algorithm. The algorithm computes a unique tree decomposition, uses colors to fully encode the structure of the original graph in the decomposition tree and invokes Lindellʼs tree canonization algorithm. As a consequence, the isomorphism, the automorphism, as well as the canonization problem for k-trees are all complete for deterministic logspace. Completeness for logspace holds even for simple structural properties of k-trees. We also show that a variant of our canonical labeling algorithm runs in time O ( ( k + 1 )! n ), where n is the number of vertices, yielding the fastest known FPT algorithm for k-tree isomorphism.

I&C Journal 2010 Journal Article

The ideal membership problem and polynomial identity testing

V. Arvind
Partha Mukhopadhyay

Given a monomial ideal I = 〈 m 1, m 2, …, m k 〉 where m i are monomials and a polynomial f by an arithmetic circuit, the Ideal Membership Problem is to test if f ∈ I. We study this problem and show the following results. (a) When the ideal I = 〈 m 1, m 2, …, m k 〉 for a constant k, we can test whether f ∈ I in randomized polynomial time. This result holds even for f given by a black-box, when f is of small degree. (b) When I = 〈 m 1, m 2, …, m k 〉 for a constant k and f is computed by a Σ Π Σ circuit with output gate of bounded fanin, we can test whether f ∈ I in deterministic polynomial time. This generalizes the Kayal–Saxena result [11] of deterministic polynomial-time identity testing for Σ Π Σ circuits with bounded fanin output gate. (c) When k is not constant the problem is coNP-hard. We also show that the problem is upper bounded by coMA PP over the field of rationals, and by coNP ModpP over finite fields. (d) Finally, we discuss identity testing for certain restricted depth 4 arithmetic circuits. For ideals I = 〈 f 1, …, f ℓ 〉 where each f i ∈ F [ x 1, …, x k ] is an arbitrary polynomial but k is a constant, we show similar results as (a) and (b) above.

TCS Journal 2009 Journal Article

Parameterized learnability of juntas

V. Arvind
Johannes Köbler
Wolfgang Lindner

We study the parameterized complexity of learning k -juntas and some variations of juntas. We show the hardness of learning k -juntas and subclasses of k -juntas in the PAC model by reductions from a W [ 2 ] -complete problem. On the other hand, as a consequence of a more general result, we show that k -juntas are exactly learnable with improper equivalence queries and access to a W [ P ] oracle.

I&C Journal 2006 Journal Article

Graph Isomorphism is in SPP

V. Arvind
Piyush P. Kurur

We show that Graph Isomorphism is in the complexity class SPP, and hence it is in ⊕P (in fact, in Mod k P for each k ⩾2). These inclusions for Graph Isomorphism were not known prior to membership in SPP. We derive this result as a corollary of a more general result: we show that a generic problem FIND-GROUP has an FPSPP algorithm. This general result has other consequences: for example, it follows that the hidden subgroup problem for permutation groups, studied in the context of quantum algorithms, has an FPSPP algorithm. Also, some other algorithmic problems over permutation groups known to be at least as hard as Graph Isomorphism (e. g. , coset intersection) are in SPP, and thus in Mod k P for each k ⩾2.

TCS Journal 2001 Journal Article

A nonadaptive NC checker for permutation group intersection

V. Arvind
Jacobo Torán

We design a nonadaptive NC checker for permutation group intersection, sharpening a result of Blum and Kannan (J. ACM 43 (1995) 269–291). Additionally, we also get nonadaptive NC checkers for some related group-theoretic problems.

TCS Journal 2001 Journal Article

On pseudorandomness and resource-bounded measure

V. Arvind
Johannes Köbler

In this paper we extend a key result of Nisan and Wigderson (J. Comput. System Sci. 49 (1994) 149–167) to the nondeterministic setting: for all α>0 we show that if there is a language in E=DTIME(2 O(n)) that is hard to approximate by nondeterministic circuits of size 2αn, then there is a pseudorandom generator that can be used to derandomize BP· NP (in symbols, BP· NP=NP ). By applying this extension we are able to answer some open questions in Lutz (Theory Comput. Systems 30 (1997) 429–442) regarding the derandomization of the classes BP·Σ P k and BP· Θ P k under plausible measure theoretic assumptions. As a consequence, if Θ P 2 does not have p-measure 0, then AM∩coAM is low for Θ P 2. Thus, in this case, the graph isomorphism problem is low for Θ P 2. By using the Nisan–Wigderson design of a pseudorandom generator we unconditionally show the inclusion MA ⊆ ZPP NP and that MA∩coMA is low for ZPP NP.

TCS Journal 2000 Journal Article

Exact learning via teaching assistants

V. Arvind
N.V. Vinodchandran

In this paper we introduce and study a new model of exact learning called the teaching assistant model. The new ingredient in this model, as compared to Angluin's model, is that apart from the learner and teacher there is a third agent called teaching assistant. We compare the teaching assistant model with Angluin's model and show that in this model we can do a fine classification of concept classes with respect to the complexity of exact learning. In particular, we consider two algebraic concept classes, namely, permutation groups and linear spaces over finite fields. These concept classes can be seen as special subclasses of the concept class of circuits. In Angluin's exact-learning model these concept classes are, just as the concept class 3-CNF, learnable with equivalence queries but not learnable with membership queries. However, we show that in the teaching assistant model permutation groups are exactly learnable with an LWPP-assistant, and linear spaces over finite fields are exactly learnable with an SPP-assistant. As a negative result, we show that if 3-CNFs are exactly learnable with an LWPP-assistant (SPP-assistant), then NP⊆LWPP (respectively, NP⊆SPP ).

TCS Journal 2000 Journal Article

The counting complexity of group-definable languages

V. Arvind
N.V. Vinodchandran

A group family is a countable family B={Bn}n>0 of finite black-box groups, i. e. , the elements of each group B n are uniquely encoded as strings of uniform length (polynomial in n) and for each B n the group operations are computable in time polynomial in n. In this paper we study the complexity of NP sets A which has the following property: the set of solutions for every x∈A is a subgroup (or is the right coset of a subgroup) of a group B i(|x|) from a given group family B, where i is a polynomial. Such an NP set A is said to be defined over the group family B. Decision problems like Graph Automorphism, Graph Isomorphism, Group Intersection, Coset Intersection, and Group Factorization for permutation groups give natural examples of such NP sets defined over the group family of all permutation groups. We show that any such NP set defined over permutation groups is low for PP and C=P. As one of our main results we prove that NP sets defined over abelian black-box groups are low for PP. The proof of this result is based on the decomposition theorem for finite abelian groups. As an interesting consequence of this result we obtain new lowness results: Membership Testing, Group Intersection, Group Factorization, and some other problems for abelian black-box groups are low for PP and C=P. As regards the corresponding counting problem for NP sets over any group family of arbitrary black-box groups, we prove that exact counting of number of solutions is in FPAM. Consequently, none of these counting problems can be #P-complete unless PH collapses.

TCS Journal 1997 Journal Article

Solvable black-box group problems are low for PP

V. Arvind
N.V. Vinodchandran

Let B = B m m>0 be a countable family of finite groups whose elements are uniquely encoded as strings of uniform length, and group operations are computable in time bounded by a polynomial in m. A black-box group over a group family B is a subgroup of some member of B and is presented by a generator set. In this paper we study the complexity of several algorithmic problems for abelian black-box groups and solvable black-box groups. We design a suitable oracle algorithm that computes an independent set of generators for a given abelian black-box group. Using this we show that the problems of Membership Testing, Group Intersection, Order Verification, and Group Isomorphism over abelian black-box groups are in SPP. We also show that Group Factorization, Coset Intersection, and Double Coset Membership problems over abelian black-box groups are in LWPP. As a consequence, all these problems are low for PP and CP. We define the notion of canonical generator sets for classes of groups and show that solvable black-box groups have canonical generator sets. We design a suitable randomized oracle algorithm that computes a canonical generator set for a given solvable black-box group. Using this algorithm we show that Membership Testing, Order Verification, and Group Isomorphism for solvable groups are in ZPPSPP and hence low for PP. We also show that Group Intersection, Group Factorization, Coset Intersection, and Double Coset Membership for solvable groups are low for PP.

I&C Journal 1996 Journal Article

A Note on Decision versus Search for Graph Automorphism

M. Agrawal
V. Arvind

We show that for any graphG, knontrivial automorphisms ofG—if as many exist—can be computed in time |G| O(log k)with nonadaptive queries to GA, the decision problem for Graph Automorphism. As a consequence, we show that some problems related to GA are actually polynomial-time truth-table equivalent to GA. One of these results provides an answer to an open question of Lubiw [SIAM J. Comput. 10(1981), 11–21].

TCS Journal 1996 Journal Article

Geometric sets of low information content

M. Agrawal
V. Arvind

In this paper we study language classes defined by nonuniform families of hyperplanes and halfspaces. These are subclasses of P/poly. Upto many-one equivalence these classes are essentially the classes ELT1 (and LT1) of languages accepted by nonuniform families of polynomial size depth-1 circuits with a weighted exact threshold gate at the root (respectively, weighted threshold gate at the root). We investigate the consequences of intractable sets being reducible to sets in ELT1 and LT1. Using the polynomial-time algorithm for linear programming and ideas from the theory of convex polytopes we prove that every disjunctively self-reducible bd-cylinder that is many-one reducible to a set in ELT1 or LT1 is already in P. As a consequence we derive that if a complete set for any class K > ϵ {NP, ModkP, PP, C=P} many-one reduces to a set in ELT1 or LT1 then K >= P. For families of hyperplanes over finite fields, we prove that every Turing self-reducible set that is many-one reducible to a set defined by such a family is in P, and every word-decreasing self-reducible set that is many-one reducible to a set defined by such a family is in NP ∩ co-NP. Furthermore, as an interesting connection, it turns out that several sparse and tally reduction classes are many-one reducible to ELT1 or LT1. Thus, our results concerning reductions to ELT1 and LT1 subsume the strongest existing collapse results concerning reductions of any class K > ϵ {NP, ModkP, PP, C=P} to sparse sets for various reducibilities.

TCS Journal 1996 Journal Article

Quasi-linear truth-table reductions to p-selective sets

M. Agrawal
V. Arvind

We show that if SAT is quasi-linear truth-table reducible to a p-selective set then NP = P. As a consequence it follows that for a class K ϵ {PP, C = P}, if every set in K is quasi-linear truth-table reducible to a p-selective set then K = P.

TCS Journal 1989 Journal Article

On some bandwidth restricted versions of the satisfiability problem of propositional CNF formulas

V. Arvind
S. Biswas

In the present paper we study the complexity of some restricted versions of the satisfiability problem for propositional CNF formulas. We define these restrictions through their corresponding languages which are identified using the self-reducibility property of satisfiable propositional CNF formulas. The notion of kernel constructibility (similar to self-reducibility) and that of bandwidth are used to define these languages. The results throw some light on the structure of the satisfiability problem. The proof methods illustrate the application of a certain method for reducing Turing machine acceptance problems to decision problems for logics.