Author name cluster

Rajit Datta

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.

5 papers

2 author rows

MFCS Conference 2021 Conference Paper

Equivalence Testing of Weighted Automata over Partially Commutative Monoids

Vikraman Arvind
Abhranil Chatterjee 0001
Rajit Datta
Partha Mukhopadhyay

Motivated by equivalence testing of k-tape automata, we study the equivalence testing of weighted automata in the more general setting, over partially commutative monoids (in short, pc monoids), and show efficient algorithms in some special cases, exploiting the structure of the underlying non-commutation graph of the monoid. Specifically, if the edge clique cover number of the non-commutation graph of the pc monoid is a constant, we obtain a deterministic quasi-polynomial time algorithm for equivalence testing. As a corollary, we obtain the first deterministic quasi-polynomial time algorithms for equivalence testing of k-tape weighted automata and for equivalence testing of deterministic k-tape automata for constant k. Prior to this, the best complexity upper bound for these k-tape automata problems were randomized polynomial-time, shown by Worrell [James Worrell, 2013]. Finding a polynomial-time deterministic algorithm for equivalence testing of deterministic k-tape automata for constant k has been open for several years [Emily P. Friedman and Sheila A. Greibach, 1982] and our results make progress. We also consider pc monoids for which the non-commutation graphs have an edge cover consisting of at most k cliques and star graphs for any constant k. We obtain a randomized polynomial-time algorithm for equivalence testing of weighted automata over such monoids. Our results are obtained by designing efficient zero-testing algorithms for weighted automata over such pc monoids.

Details

STOC Conference 2021 Conference Paper

Lower bounds for monotone arithmetic circuits via communication complexity

Arkadev Chattopadhyay
Rajit Datta
Partha Mukhopadhyay

Valiant (1980) showed that general arithmetic circuits with negation can be exponentially more powerful than monotone ones. We give the first improvement to this classical result: we construct a family of polynomials P n in n variables, each of its monomials has non-negative coefficient, such that P n can be computed by a polynomial-size depth-three formula but every monotone circuit computing it has size 2 Ω( n 1/4 /log( n )) . The polynomial P n embeds the SINK∘ XOR function devised recently by Chattopadhyay, Mande and Sherif (2020) to refute the Log-Approximate-Rank Conjecture in communication complexity. To prove our lower bound for P n , we develop a general connection between corruption of combinatorial rectangles by any function f ∘ XOR and corruption of product polynomials by a certain polynomial P f that is an arithmetic embedding of f . This connection should be of independent interest. Using further ideas from communication complexity, we construct another family of set-multilinear polynomials f n , m such that both F n , m − є· f n , m and F n , m + є· f n , m have monotone circuit complexity 2 Ω( n /log( n )) if є ≥ 2 − Ω( m ) and F n , m ∏ i =1 n ( x i ,1 +⋯+ x i , m ), with m = O ( n /log n ). The polynomials f n , m have 0/1 coefficients and are in VNP. Proving such lower bounds for monotone circuits has been advocated recently by Hrubeš (2020) as a first step towards proving lower bounds against general circuits via his new approach.

Details

MFCS Conference 2020 Conference Paper

A Special Case of Rational Identity Testing and the Brešar-Klep Theorem

Vikraman Arvind
Abhranil Chatterjee 0001
Rajit Datta
Partha Mukhopadhyay

We explore a special case of rational identity testing and algorithmic versions of two theorems on noncommutative polynomials, namely, Amitsur's theorem [S. A Amitsur, 1966] and the Brešar-Klep theorem [Brešar and Klep, 2008] when the input polynomial is given by an algebraic branching program (ABP). Let f be a degree-d n-variate noncommutative polynomial in the free ring Q<x_1, x_2, .. ., x_n> over rationals. 1) We consider the following special case of rational identity testing: Given a noncommutative ABP as white-box, whose edge labels are linear forms or inverses of linear forms, we show a deterministic polynomial-time algorithm to decide if the rational function computed by it is equivalent to zero in the free skew field Q<(X)>. Given black-box access to the ABP, we give a deterministic quasi-polynomial time algorithm for this problem. 2) Amitsur's theorem implies that if a noncommutative polynomial f is nonzero on k x k matrices then, in fact, f(M_1, M_2, .. ., M_n) is invertible for some matrix tuple (M_1, M_2, .. ., M_n) in (M_k(ℚ))^n. While a randomized polynomial time algorithm to find such (M_1, M_2, .. ., M_n) given black-box access to f is simple, we obtain a deterministic s^{O(log d)} time algorithm for the problem with black-box access to f, where s is the minimum ABP size for f and d is the degree of f. 3) The Brešar-Klep Theorem states that the span of the range of any noncommutative polynomial f on k x k matrices over Q is one of the following: zero, scalar multiples of I_k, trace-zero matrices in M_k(Q), or all of M_k(Q). We obtain a deterministic polynomial-time algorithm to decide which case occurs, given white-box access to an ABP for f. We also give a deterministic s^{O(log d)} time algorithm given black-box access to an ABP of size s for f. Our algorithms work when k >= d. Our techniques are based on some automata theory combined with known techniques for noncommutative ABP identity testing [Ran Raz and Amir Shpilka, 2005; Michael A. Forbes and Amir Shpilka, 2013].

Details

Highlights Conference 2020 Conference Abstract

Equivalence Testing of Weighted Automata over Partially Commutative Monoids

Rajit Datta

We study the equivalence testing of automata over partially commutative monoids (pc monoids) and show efficient algorithms in special cases, exploiting the structure of the underlying non-commutation graph of the monoid. Specifically, if the clique edge cover number of the non-commutation graph of the pc monoid is a constant, we obtain a deterministic quasi-polynomial time algorithm. As a consequence, we also obtain the first deterministic quasi-polynomial time algorithms for equivalence testing of k-tape weighted automata and for equivalence testing of deterministic k-tape automata for constant k. Prior to this, a randomized polynomial-time algorithm for the above problems was shown by Worrell [ICALP 2013]. We also consider pc monoids for which the non-commutation graphs have cover consisting of at most k cliques and star graphs for any constant k. We obtain randomized polynomial-time algorithm for equivalence testing of weighted automata over such monoids. Our results are obtained by designing efficient zero testing algorithms for weighted automata over such pc monoids.

PDF Details

MFCS Conference 2017 Conference Paper

Efficient Identity Testing and Polynomial Factorization in Nonassociative Free Rings

Vikraman Arvind
Rajit Datta
Partha Mukhopadhyay
S. Raja 0001

In this paper we study arithmetic computations in the nonassociative, and noncommutative free polynomial ring F{X}. Prior to this work, nonassociative arithmetic computation was considered by Hrubes, Wigderson, and Yehudayoff, and they showed lower bounds and proved completeness results. We consider Polynomial Identity Testing and Polynomial Factorization in F{X} and show the following results. 1. Given an arithmetic circuit C computing a polynomial f in F{X} of degree d, we give a deterministic polynomial algorithm to decide if f is identically zero. Our result is obtained by a suitable adaptation of the PIT algorithm of Raz and Shpilka for noncommutative ABPs. 2. Given an arithmetic circuit C computing a polynomial f in F{X} of degree d, we give an efficient deterministic algorithm to compute circuits for the irreducible factors of f in polynomial time when F is the field of rationals. Over finite fields of characteristic p, our algorithm runs in time polynomial in input size and p.

Details