A symbolic determinant under rank-one restriction computes a polynomial of the form det(A0 + A1y1 + … + Anyn), where A0, A1, …, An are square matrices over a field F and rank(Ai) = 1 for each i ∈ [n]. This class of polynomials has been studied extensively, since the work of Edmonds (1967), in the context of linear matroids, matching, matrix completion and polynomial identity testing. We study the following learning problem for this class: Given black-box access to an n-variate polynomial f = det(A0 + A1y1 + … + Anyn), where A0, A1, …, An are unknown square matrices over F and rank(Ai) = 1 for each i ∈ [n], find a square matrix B0 and rank-one square matrices B1, …, Bn over F such that f = det(B0 + B1y1 + … + Bnyn). In this work, we give a randomized poly(n) time algorithm to solve this problem; the algorithm can be derandomized in quasi-polynomial time. To our knowledge, this is the first efficient learning algorithm for this class. As the above-mentioned class is known to be equivalent to the class of read-once determinants (RODs), we will refer to the problem as learning RODs. An ROD computes the determinant of a matrix whose entries are field constants or variables and every variable appears at most once in the matrix. Thus, the class of RODs is a rare example of a well-studied class of polynomials that admits efficient proper learning.

Let$X=X_{1} \sqcup X_{2} \sqcup \ldots \sqcup X_{k}$be a partitioned set of variables such that the variables in each part$X_{i}$are noncommuting but for any$i\neq j$, the variables$x\in X_{i}$commute with the variables$x^{\prime}\in X_{j}$. Given as input a square matrix$T$whose entries are linear forms over$\mathbb{Q}\langle X\rangle$〉, we consider the problem of checking if$T$is invertible or not over the universal skew field of fractions of the partially commutative polynomial ring$\mathbb{Q}\langle X\rangle$[1]. In this paper, we design a deterministic polynomial-time algorithm for this problem for constant$k$. The special case$k=1$is the noncommutative Edmonds' problem (NSINGULAR) which has a deterministic polynomial-time algorithm by recent results [2]–[4]. En-route, we obtain the first deterministic polynomial-time algorithm for the equivalence testing problem of$k$-tape weighted automata (for constant$k$) resolving a longstanding open problem [5], [6]. Algebraically, the equivalence problem reduces to testing whether a partially commutative rational series over the partitioned set$X$is zero or not [6]. Decidability of this problem was established by Harju and Karhumäki [5]. Prior to this work, a randomized polynomial-time algorithm for this problem was given by Worrell [6] and, subsequently, a deterministic quasipolynomial-time algorithm was also developed [7].

Rational Identity Testing (RIT) is the decision problem of determining whether or not a noncommutative rational formula computes zero in the free skew field. It admits a deterministic polynomial-time white-box algorithm [Garg, Gurvits, Oliveira, and Wigderson (2016); Ivanyos, Qiao, Subrahmanyam (2018); Hamada and Hirai (2021)], and a randomized polynomial-time algorithm [Derksen and Makam (2017)] in the black-box setting, via singularity testing of linear matrices over the free skew field. Indeed, a randomized NC algorithm for RIT in the white-box setting follows from the result of Derksen and Makam (2017). Designing an efficient deterministic black-box algorithm for RIT and understanding the parallel complexity of RIT are major open problems in this area. Despite being open since the work of Garg, Gurvits, Oliveira, and Wigderson (2016), these questions have seen limited progress. In fact, the only known result in this direction is the construction of a quasipolynomial-size hitting set for rational formulas of only inversion height two [Arvind, Chatterjee, and Mukhopadhyay (2022)]. In this paper, we significantly improve the black-box complexity of this problem and obtain the first quasipolynomial-size hitting set for all rational formulas of polynomial size. Our construction also yields the first deterministic quasi-NC upper bound for RIT in the white-box setting.

Hrubeš and Wigderson [Hrubeš and Wigderson, 2015] initiated the complexity-theoretic study of noncommutative formulas with inverse gates. They introduced the Rational Identity Testing (RIT) problem which is to decide whether a noncommutative rational formula computes zero in the free skew field. In the white-box setting, there are deterministic polynomial-time algorithms due to Garg, Gurvits, Oliveira, and Wigderson [Ankit Garg et al., 2016] and Ivanyos, Qiao, and Subrahmanyam [Ivanyos et al., 2018]. A central open problem in this area is to design an efficient deterministic black-box identity testing algorithm for rational formulas. In this paper, we solve this for the first nested inverse case. More precisely, we obtain a deterministic quasipolynomial-time black-box RIT algorithm for noncommutative rational formulas of inversion height two via a hitting set construction. Several new technical ideas are involved in the hitting set construction, including concepts from matrix coefficient realization theory [Volčič, 2018] and properties of cyclic division algebras [T.Y. Lam, 2001]. En route to the proof, an important step is to embed the hitting set of Forbes and Shpilka for noncommutative formulas [Michael A. Forbes and Amir Shpilka, 2013] inside a cyclic division algebra of small index.

Let \({\mathbb {F}}[X]\) be the polynomial ring in the variables X = { x 1 , x 2 ,…, x n } over a field \({\mathbb {F}}\) . An ideal I = 〈 p 1 ( x 1 ),…, p n ( x n )〉 generated by univariate polynomials \(\{p_{i}(x_{i})\}_{i=1}^{n}\) is a univariate ideal . Motivated by Alon’s Combinatorial Nullstellensatz we study the complexity of univariate ideal membership : Given \(f\in {\mathbb {F}}[X]\) by a circuit and polynomials p i the problem is test if f ∈ I . We obtain the following results. Suppose f is a degree- d , rank- r polynomial given by an arithmetic circuit where ℓ i : 1 ≤ i ≤ r are linear forms in X . We give a deterministic time d O ( r ) ⋅poly( n ) division algorithm for evaluating the (unique) remainder polynomial f ( X )mod I at any point \(\vec {a}\in {\mathbb {F}}^{n}\) . This yields a randomized n O ( r ) algorithm for minimum vertex cover in graphs with rank- r adjacency matrices. It also yields a new n O ( r ) algorithm for evaluating the permanent of a n × n matrix of rank r , over any field \(\mathbb {F}\) . Let f be over rationals with \(\deg (f)=k\) treated as fixed parameter. When the ideal \(I=\left \langle {x_{1}^{e_{1}}, \ldots , x_{n}^{e_{n}}}\right \rangle \) , we can test ideal membership in randomized O ∗ ((2 e ) k ). On the other hand, if each p i has all distinct rational roots we can check if f ∈ I in randomized O ∗ ( n k /2 ) time, improving on the brute-force \(\left (\begin {array}{cc}{n+k}\\ k \end {array}\right )\) -time search. If \(I=\left \langle {p_{1}(x_{1}), \ldots , p_{k}(x_{k})}\right \rangle \) , with k as fixed parameter, then ideal membership testing is W[2]-hard. The problem is MINI[1]-hard in the special case when \(I=\left \langle {x_{1}^{e_{1}}, \ldots , x_{k}^{e_{k}}}\right \rangle \) .

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.

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

Hrubeš and Wigderson [Pavel Hrubeš and Avi Wigderson, 2014] initiated the study of noncommutative arithmetic circuits with division computing a noncommutative rational function in the free skew field, and raised the question of rational identity testing. For noncommutative formulas with inverses the problem can be solved in deterministic polynomial time in the white-box model [Ankit Garg et al., 2016; Ivanyos et al., 2018]. It can be solved in randomized polynomial time in the black-box model [Harm Derksen and Visu Makam, 2017], where the running time is polynomial in the size of the formula. The complexity of identity testing of noncommutative rational functions, in general, remains open for noncommutative circuits with inverses. We solve the problem for a natural special case. We consider expressions in the free group algebra F(X,X^{-1}) where X={x_1, x_2, ..., x_n}. Our main results are the following. 1) Given a degree d expression f in F(X,X^{-1}) as a black-box, we obtain a randomized poly(n,d) algorithm to check whether f is an identically zero expression or not. The technical contribution is an Amitsur-Levitzki type theorem [A. S. Amitsur and J. Levitzki, 1950] for F(X, X^{-1}). This also yields a deterministic identity testing algorithm (and even an expression reconstruction algorithm) that is polynomial time in the sparsity of the input expression. 2) Given an expression f in F(X,X^{-1}) of degree D and sparsity s, as black-box, we can check whether f is identically zero or not in randomized poly(n,log s, log D) time. This yields a randomized polynomial-time algorithm when D and s are exponential in n.

Let C be an arithmetic circuit of poly(n) size given as input that computes a polynomial f in F[X], where X={x_1,x_2,...,x_n} and F is any field where the field arithmetic can be performed efficiently. We obtain new algorithms for the following two problems first studied by Koutis and Williams [Ioannis Koutis, 2008; Ryan Williams, 2009; Ioannis Koutis and Ryan Williams, 2016]. - (k,n)-MLC: Compute the sum of the coefficients of all degree-k multilinear monomials in the polynomial f. - k-MMD: Test if there is a nonzero degree-k multilinear monomial in the polynomial f. Our algorithms are based on the fact that the Hadamard product f o S_{n,k}, is the degree-k multilinear part of f, where S_{n,k} is the k^{th} elementary symmetric polynomial. - For (k,n)-MLC problem, we give a deterministic algorithm of run time O^*(n^(k/2+c log k)) (where c is a constant), answering an open question of Koutis and Williams [Ioannis Koutis and Ryan Williams, 2016]. As corollaries, we show O^*(binom{n}{downarrow k/2})-time exact counting algorithms for several combinatorial problems: k-Tree, t-Dominating Set, m-Dimensional k-Matching. - For k-MMD problem, we give a randomized algorithm of run time 4.32^k * poly(n,k). Our algorithm uses only poly(n,k) space. This matches the run time of a recent algorithm [Cornelius Brand et al., 2018] for k-MMD which requires exponential (in k) space. Other results include fast deterministic algorithms for (k,n)-MLC and k-MMD problems for depth three circuits.

We study the arithmetic circuit complexity of some well-known family of polynomials through the lens of parameterized complexity. Our main focus is on the construction of explicit algebraic branching programs (ABP) for determinant and permanent polynomials of the rectangular symbolic matrix in both commutative and noncommutative settings. The main results are: - We show an explicit O^*(binom{n}{downarrow k/2})-size ABP construction for noncommutative permanent polynomial of k x n symbolic matrix. We obtain this via an explicit ABP construction of size O^*(binom{n}{downarrow k/2}) for S_{n,k}^*, noncommutative symmetrized version of the elementary symmetric polynomial S_{n,k}. - We obtain an explicit O^*(2^k)-size ABP construction for the commutative rectangular determinant polynomial of the k x n symbolic matrix. - In contrast, we show that evaluating the rectangular noncommutative determinant over rational matrices is #W[1]-hard.