Search

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'\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$ [Klep-Vinnikov-Volcic (2020)]. 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 [Garg-Gurvits-Oliveira-Wigderson (2016), Ivanyos-Qiao-Subrahmanyam (2018), Hamada-Hirai (2021)]. En-route, we obtain the first deterministic polynomial-time algorithm for the equivalence testing problem of $k$-tape \emph{weighted} automata (for constant $k$) resolving a long-standing open problem [Harju and Karhum"{a}ki(1991), Worrell (2013)]. Algebraically, the equivalence problem reduces to testing whether a partially commutative rational series over the partitioned set $X$ is zero or not [Worrell (2013)]. Decidability of this problem was established by Harju and Karhum\"{a}ki (1991). Prior to this work, a \emph{randomized} polynomial-time algorithm for this problem was given by Worrell (2013) and, subsequently, a deterministic quasipolynomial-time algorithm was also developed [Arvind et al. (2021)].

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

Let $T$ be a matrix whose entries are linear forms over the noncommutative variables $x_1, x_2, \ldots, x_n$. The noncommutative Edmonds' problem (NSINGULAR) aims to determine whether $T$ is invertible in the free skew field generated by $x_1,x_2,\ldots,x_n$. Currently, there are three different deterministic polynomial-time algorithms to solve this problem: using operator scaling [Garg, Gurvits, Oliveira, and Wigserdon (2016)], algebraic methods [Ivanyos, Qiao, and Subrahmanyam (2018)], and convex optimization [Hamada and Hirai (2021)]. In this paper, we present a simpler algorithm for the NSINGULAR problem. While our algorithmic template is similar to the one in Ivanyos et. al.(2018), it significantly differs in its implementation of the rank increment step. Instead of computing the limit of a second Wong sequence, we reduce the problem to the polynomial identity testing (PIT) of noncommutative algebraic branching programs (ABPs). This enables us to bound the bit-complexity of the algorithm over $\mathbb{Q}$ without requiring special care. Moreover, the rank increment step can be implemented in quasipolynomial-time even without an explicit description of the coefficient matrices in $T$. This is possible by exploiting the connection with the black-box PIT of noncommutative ABPs [Forbes and Shpilka (2013)].

The identity testing of rational formulas (RIT) in the free skew field efficiently reduces to computing the rank of a matrix whose entries are linear polynomials in noncommuting variables\cite{HW15}. This rank computation problem has deterministic polynomial-time white-box algorithms \cite{GGOW16, IQS18} and a randomized polynomial-time algorithm in the black-box setting \cite{DM17}. In this paper, we propose a new approach for efficient derandomization of \emph{black-box} RIT. Additionally, we obtain results for matrix rank computation over the free skew field, and construct efficient linear pencil representations for a new class of rational expressions. More precisely, we show the following results: 1. Under the hardness assumption that the ABP (algebraic branching program) complexity of every polynomial identity for the $k\times k$ matrix algebra is $2^{\Omega(k)}$ \cite{BW05}, we obtain a subexponential-time black-box algorithm for RIT in almost general setting. This can be seen as the first "hardness implies derandomization" type theorem for rational formulas. 2. We show that the noncommutative rank of any matrix over the free skew field whose entries have small linear pencil representations can be computed in deterministic polynomial time. Prior to this, an efficient rank computation was only known for matrices with noncommutative formulas as entries\cite{GGOW20}. As special cases of our algorithm, we obtain the first deterministic polynomial-time algorithms for rank computation of matrices whose entries are noncommutative ABPs or rational formulas. 3. Motivated by the definition given by Bergman\cite{Ber76}, we define a new class that contains noncommutative ABPs and rational formulas. We obtain a polynomial-size linear pencil representation for this class. As a by-product, we obtain a white-box deterministic polynomial-time identity testing algorithm for the class.

Hrube\v{s} 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, deterministic polynomial-time algorithms are known for this problem following the works of Garg, Gurvits, Oliveira, and Wigderson (2016) and Ivanyos, Qiao, and Subrahmanyam (2018). A central open problem in this area is to design efficient deterministic black-box identity testing algorithm for rational formulas. In this paper, we solve this problem 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 key concepts from matrix coefficient realization theory (Vol\v{c}i\v{c}, 2018) and properties of cyclic division algebra (Lam, 2001). En route to the proof, an important step is to embed the hitting set of Forbes and Shpilka for noncommutative formulas (2013) inside a cyclic division algebra of small index.

We prove two results that shed new light on the monotone complexity of the spanning tree polynomial, a classic polynomial in algebraic complexity and beyond. First, we show that the spanning tree polynomials having $n$ variables and defined over constant-degree expander graphs, have monotone arithmetic complexity $2^{\Omega(n)}$. This yields the first strongly exponential lower bound on the monotone arithmetic circuit complexity for a polynomial in VP. Before this result, strongly exponential size monotone lower bounds were known only for explicit polynomials in VNP (Gashkov-Sergeev'12, Raz-Yehudayoff'11, Srinivasan'20, Cavalar-Kumar-Rossman'20, Hrubes-Yehudayoff'21). Recently, Hrubes'20 initiated a program to prove lower bounds against general arithmetic circuits by proving $\epsilon$-sensitive lower bounds for monotone arithmetic circuits for a specific range of values for $\epsilon \in (0,1)$. We consider the spanning tree polynomial $ST_{n}$ defined over the complete graph on $n$ vertices and show that the polynomials $F_{n-1,n} - \epsilon \cdot ST_{n}$ and $F_{n-1,n} + \epsilon \cdot ST_{n}$ defined over $n^2$ variables, have monotone circuit complexity $2^{\Omega(n)}$ if $\epsilon \geq 2^{-\Omega(n)}$ and $F_{n-1,n} = \prod_{i=2}^n (x_{i,1} +\cdots + x_{i,n})$ is the complete set-multilinear polynomial. This provides the first $\epsilon$-sensitive exponential lower bound for a family of polynomials inside VP. En-route, we consider a problem in 2-party, best partition communication complexity of deciding whether two sets of oriented edges distributed among Alice and Bob form a spanning tree or not. We prove that there exists a fixed distribution, under which the problem has low discrepancy with respect to every nearly-balanced partition. This result could be of interest beyond algebraic complexity., Comment: 20 pages, 3 figures

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 \emph{rectangular} symbolic matrix in both commutative and noncommutative settings. The main results are: 1. We show an explicit $O^{*}({n\choose {\downarrow k/2}})$-size ABP construction for noncommutative permanent polynomial of $k\times n$ symbolic matrix. We obtain this via an explicit ABP construction of size $O^{*}({n\choose {\downarrow k/2}})$ for $S_{n,k}^*$, noncommutative symmetrized version of the elementary symmetric polynomial $S_{n,k}$. 2. We obtain an explicit $O^{*}(2^k)$-size ABP construction for the commutative rectangular determinant polynomial of the $k\times n$ symbolic matrix. 3. In contrast, we show that evaluating the rectangular noncommutative determinant over rational matrices is $W[1]$-hard.

Hrube\v{s} and Wigderson [HW14] 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. It is now known that the problem can be solved in deterministic polynomial time in the white-box model for noncommutative formulas with inverses, and in randomized polynomial time in the black-box model [GGOW16, IQS18, DM18], where the running time is polynomial in the size of the formula. The complexity of identity testing of noncommutative rational functions remains open in general (when the formula size is not polynomially bounded). We solve the problem for a natural special case. We consider polynomial expressions in the free group algebra $\mathbb{F}\langle X, X^{-1}\rangle$ where $X=\{x_1, x_2, \ldots, x_n\}$, a subclass of rational expressions of inversion height one. Our main results are the following. 1. Given a degree $d$ expression $f$ in $\mathbb{F}\langle X, X^{-1}\rangle$ as a black-box, we obtain a randomized $\text{poly}(n,d)$ algorithm to check whether $f$ is an identically zero expression or not. We obtain this by generalizing the Amitsur-Levitzki theorem [AL50] to $\mathbb{F}\langle X, X^{-1}\rangle$. 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 $\mathbb{F}\langle X, X^{-1}\rangle$ of degree at most $D$, and sparsity $s$, as black-box, we can check whether $f$ is identically zero or not in randomized $\text{poly}(n,\log s, \log D)$ time.

Let $C$ be a depth-3 arithmetic circuit of size at most $s$, computing a polynomial $ f \in \mathbb{F}[x_1,\ldots, x_n] $ (where $\mathbb{F}$ = $\mathbb{Q}$ or $\mathbb{C}$) and the fan-in of the product gates of $C$ is bounded by $d$. We give a deterministic polynomial identity testing algorithm to check whether $f\equiv 0$ or not in time $ 2^d \text{ poly}(n,s) $., Comment: Result for finite fields has been added

In this paper we study arithmetic computations in the nonassociative, and noncommutative free polynomial ring $\mathbb{F}\{x_1,x_2,\ldots,x_n\}$. Prior to this work, nonassociative arithmetic computation was considered by Hrubes, Wigderson, and Yehudayoff [HWY10], and they showed lower bounds and proved completeness results. We consider Polynomial Identity Testing (PIT) and polynomial factorization over $\mathbb{F}\{x_1,x_2,\ldots,x_n\}$ and show the following results. (1) Given an arithmetic circuit $C$ of size $s$ computing a polynomial $f\in \mathbb{F} \{x_1,x_2,\ldots,x_n\}$ of degree $d$, we give a deterministic $poly(n,s,d)$ algorithm to decide if $f$ is identically zero polynomial or not. Our result is obtained by a suitable adaptation of the PIT algorithm of Raz-Shpilka [RS05] for noncommutative ABPs. (2) Given an arithmetic circuit $C$ of size $s$ computing a polynomial $f\in \mathbb{F} \{x_1,x_2,\ldots,x_n\}$ of degree $d$, we give an efficient deterministic algorithm to compute circuits for the irreducible factors of $f$ in time $poly(n,s,d)$ when $\mathbb{F}=\mathbb{Q}$. Over finite fields of characteristic $p$, our algorithm runs in time $poly(n,s,d,p)$.

An efficient randomized polynomial identity test for noncommutative polynomials given by noncommutative arithmetic circuits remains an open problem. The main bottleneck to applying known techniques is that a noncommutative circuit of size $s$ can compute a polynomial of degree exponential in $s$ with a double-exponential number of nonzero monomials. In this paper, we report some progress by dealing with two natural subcases (both allow for polynomials of exponential degree and a double exponential number of monomials): (1) We consider \emph{$+$-regular} noncommutative circuits: these are homogeneous noncommutative circuits with the additional property that all the $+$-gates are layered, and in each $+$-layer all gates have the same syntactic degree. We give a \emph{white-box} polynomial-time deterministic polynomial identity test for such circuits. Our algorithm combines some new structural results for $+$-regular circuits with known results for noncommutative ABP identity testing [RS05PIT], rank bound of commutative depth three identities [SS13], and equivalence testing problem for words [Loh15, MSU97, Pla94]. (2) Next, we consider $\Sigma\Pi^*\Sigma$ noncommutative circuits: these are noncommutative circuits with layered $+$-gates such that there are only two layers of $+$-gates. These $+$-layers are the output $+$-gate and linear forms at the bottom layer; between the $+$-layers the circuit could have any number of $\times$ gates. We given an efficient randomized \emph{black-box} identity testing problem for $\Sigma\Pi^*\Sigma$ circuits. In particular, we show if $f\in F$ is a nonzero noncommutative polynomial computed by a $\Sigma\Pi^*\Sigma$ circuit of size $s$, then $f$ cannot be a polynomial identity for the matrix algebra $\mathbb{M}_s(F)$, where the field $F$ is a sufficiently large extension of $F$ depending on the degree of $f$.

In this paper we show that the black-box polynomial identity testing for noncommutative polynomials $f\in\mathbb{F}\langle z_1,z_2,\cdots,z_n \rangle$ of degree $D$ and sparsity $t$, can be done in randomized $\poly(n,\log t,\log D)$ time. As a consequence, if the black-box contains a circuit $C$ of size $s$ computing $f\in\mathbb{F}\langle z_1,z_2,\cdots,z_n \rangle$ which has at most $t$ non-zero monomials, then the identity testing can be done by a randomized algorithm with running time polynomial in $s$ and $n$ and $\log t$. This makes significant progress on a question that has been open for over ten years. The earlier result by Bogdanov and Wee [BW05], using the classical Amitsur-Levitski theorem, gives a randomized polynomial-time algorithm only for circuits of polynomially bounded syntactic degree. In our result, we place no restriction on the degree of the circuit. Our algorithm is based on automata-theoretic ideas introduced in [AMS08,AM08]. In those papers, the main idea was to construct deterministic finite automata that isolate a single monomial from the set of nonzero monomials of a polynomial $f$ in $\mathbb{F}\langle z_1,z_2,\cdots,z_n \rangle$. In the present paper, since we need to deal with exponential degree monomials, we carry out a different kind of monomial isolation using nondeterministic automata., Comment: As the number of monomials in a noncommutative polynomial which has anarithmetic circuit of size $s$ can actually be doubly exponential in $s$, our result does not imply a randomized polynomial-time identity test for all size s noncommutative circuits. The algorithm works only for noncommutative size s circuits which computes a polynomial with exp(s) many monomials

Recently, Gupta et.al. [GKKS2013] proved that over Q any $n^{O(1)}$-variate and $n$-degree polynomial in VP can also be computed by a depth three $\Sigma\Pi\Sigma$ circuit of size $2^{O(\sqrt{n}\log^{3/2}n)}$. Over fixed-size finite fields, Grigoriev and Karpinski proved that any $\Sigma\Pi\Sigma$ circuit that computes $Det_n$ (or $Perm_n$) must be of size $2^{\Omega(n)}$ [GK1998]. In this paper, we prove that over fixed-size finite fields, any $\Sigma\Pi\Sigma$ circuit for computing the iterated matrix multiplication polynomial of $n$ generic matrices of size $n\times n$, must be of size $2^{\Omega(n\log n)}$. The importance of this result is that over fixed-size fields there is no depth reduction technique that can be used to compute all the $n^{O(1)}$-variate and $n$-degree polynomials in VP by depth 3 circuits of size $2^{o(n\log n)}$. The result [GK1998] can only rule out such a possibility for depth 3 circuits of size $2^{o(n)}$. We also give an example of an explicit polynomial ($NW_{n,\epsilon}(X)$) in VNP (not known to be in VP), for which any $\Sigma\Pi\Sigma$ circuit computing it (over fixed-size fields) must be of size $2^{\Omega(n\log n)}$. The polynomial we consider is constructed from the combinatorial design. An interesting feature of this result is that we get the first examples of two polynomials (one in VP and one in VNP) such that they have provably stronger circuit size lower bounds than Permanent in a reasonably strong model of computation. Next, we prove that any depth 4 $\Sigma\Pi^{[O(\sqrt{n})]}\Sigma\Pi^{[\sqrt{n}]}$ circuit computing $NW_{n,\epsilon}(X)$ (over any field) must be of size $2^{\Omega(\sqrt{n}\log n)}$. To the best of our knowledge, the polynomial $NW_{n,\epsilon}(X)$ is the first example of an explicit polynomial in VNP such that it requires $2^{\Omega(\sqrt{n}\log n)}$ size depth four circuits, but no known matching upper bound.

Tavenas has recently proved that any n^{O(1)}-variate and degree n polynomial in VP can be computed by a depth-4 circuit of size 2^{O(\sqrt{n}\log n)}. So to prove VP not equal to VNP, it is sufficient to show that an explicit polynomial in VNP of degree n requires 2^{\omega(\sqrt{n}\log n)} size depth-4 circuits. Soon after Tavenas's result, for two different explicit polynomials, depth-4 circuit size lower bounds of 2^{\Omega(\sqrt{n}\log n)} have been proved Kayal et al. and Fournier et al. In particular, using combinatorial design Kayal et al.\ construct an explicit polynomial in VNP that requires depth-4 circuits of size 2^{\Omega(\sqrt{n}\log n)} and Fournier et al.\ show that iterated matrix multiplication polynomial (which is in VP) also requires 2^{\Omega(\sqrt{n}\log n)} size depth-4 circuits. In this paper, we identify a simple combinatorial property such that any polynomial f that satisfies the property would achieve similar circuit size lower bound for depth-4 circuits. In particular, it does not matter whether f is in VP or in VNP. As a result, we get a very simple unified lower bound analysis for the above mentioned polynomials. Another goal of this paper is to compare between our current knowledge of depth-4 circuit size lower bounds and determinantal complexity lower bounds. We prove the that the determinantal complexity of iterated matrix multiplication polynomial is \Omega(dn) where d is the number of matrices and n is the dimension of the matrices. So for d=n, we get that the iterated matrix multiplication polynomial achieves the current best known lower bounds in both fronts: depth-4 circuit size and determinantal complexity. To the best of our knowledge, a \Theta(n) bound for the determinantal complexity for the iterated matrix multiplication polynomial was known only for constant d>1 by Jansen., Comment: Extension of the previous upload

Let $G =$ be a solvable permutation group of the symmetric group $S_n$ given as input by the generating set $S$. We give a deterministic polynomial-time algorithm that computes an \emph{expanding generating set} of size $\tilde{O}(n^2)$ for $G$. More precisely, the algorithm computes a subset $T\subset G$ of size $\tilde{O}(n^2)(1/\lambda)^{O(1)}$ such that the undirected Cayley graph $Cay(G,T)$ is a $\lambda$-spectral expander (the $\tilde{O}$ notation suppresses $\log ^{O(1)}n$ factors). As a byproduct of our proof, we get a new explicit construction of $\varepsilon$-bias spaces of size $\tilde{O}(n\poly(\log d))(\frac{1}{\varepsilon})^{O(1)}$ for the groups $\Z_d^n$. The earlier known size bound was $O((d+n/\varepsilon^2))^{11/2}$ given by \cite{AMN98}., Comment: 15 pages