ColBERT introduced a late interaction mechanism that independently encodes queries and documents using BERT, and computes similarity via fine-grained interactions over token-level vector representations. This design enables expressive matching while allowing efficient computation of scores, as the multi-vector document representations could be pre-computed offline. ColBERT models distance using a Chamfer-style function: for each query token, it selects the closest document token and sums these distances across all query tokens. In our work, we explore enhancements to the Chamfer distance function by computing a weighted sum over query token contributions, where weights reflect the token importance. Empirically, we show that this simple extension, requiring only token-weight training while keeping the multi-vector representations fixed, further enhances the expressiveness of late interaction multi-vector mechanism. In particular, on the BEIR benchmark, our method achieves an average improvement of 1.28% in Recall@10 in the zero-shot setting using IDF-based weights, and 3.66% through few-shot fine-tuning.

We present a general framework for designing efficient algorithms for unsupervised learning problems, such as mixtures of Gaussians and subspace clustering. Our framework is based on a meta algorithm that learns arithmetic circuits in the presence of noise, using lower bounds. This builds upon the recent work of Garg, Kayal and Saha (FOCS 20), who designed such a framework for learning arithmetic circuits without any noise. A key ingredient of our meta algorithm is an efficient algorithm for a novel problem called Robust Vector Space Decomposition. We show that our meta algorithm works well when certain matrices have sufficiently large smallest non-zero singular values. We conjecture that this condition holds for smoothed instances of our problems, and thus our framework would yield efficient algorithms for these problems in the smoothed setting.

An s-sparse polynomial has at most s monomials with nonzero coefficients. The Equivalence Testing problem for sparse polynomials (ETsparse) asks to decide if a given polynomial f is equivalent to (i.e., in the orbit of) some s-sparse polynomial. In other words, given f ∈ 𝔽[𝐱] and s ∈ ℕ, ETsparse asks to check if there exist A ∈ GL(|𝐱|, 𝔽) and 𝐛 ∈ 𝔽^|𝐱| such that f(A𝐱 + 𝐛) is s-sparse. We show that ETsparse is NP-hard over any field 𝔽, if f is given in the sparse representation, i.e., as a list of nonzero coefficients and exponent vectors. This answers a question posed by Gupta, Saha and Thankey (SODA 2023) and also, more explicitly, by Baraskar, Dewan and Saha (STACS 2024). The result implies that the Minimum Circuit Size Problem (MCSP) is NP-hard for a dense subclass of depth-3 arithmetic circuits if the input is given in sparse representation. We also show that approximating the smallest s₀ such that a given s-sparse polynomial f is in the orbit of some s₀-sparse polynomial to within a factor of s^{1/3 - ε} is NP-hard for any ε > 0; observe that s-factor approximation is trivial as the input is s-sparse. Finally, we show that for any constant σ ≥ 6, checking if a polynomial (given in sparse representation) is in the orbit of some support-σ polynomial is NP-hard. Support of a polynomial f is the maximum number of variables present in any monomial of f. These results are obtained via direct reductions from the 3-SAT problem.

We develop algorithms for writing a polynomial as sums of powers of low degree polynomials in the non-degenerate case. This problem generalizes symmetric tensor decomposition which is widely studied, having many applications in machine learning. Our algorithm for this more general problem allows us to solve the moment problem for mixtures of zero-mean Gaussians in the nondegenerate case. Our algorithm is based on a scheme for obtaining a learning algorithm for an arithmetic circuit model from lower bound for the same model, provided certain non-degeneracy conditions hold. The scheme reduces the learning problem to the problem of decomposing two vector spaces under the action of a set of linear operators, where the spaces and the operators are derived from the input circuit and the complexity measure used in a typical lower bound proof. The non-degeneracy conditions are certain restrictions on how the spaces decompose. Such a scheme is present in a rudimentary form in an earlier work of Kayal and Saha. Here, we make it more general and detailed, and potentially applicable to learning other circuit models. An exponential lower bound on the representation above is known using the shifted partials measure. However, the number of linear operators in shifted partials is exponential and also the non-degeneracy condition emerging out of this measure is unlikely to be satisfied by a random such circuit when the number of variables is large with respect to the degree. We bypass this hurdle by proving a lower bound (which is nearly as strong as the previous bound) using a novel variant of the partial derivatives measure, namely affine projections of partials (APP). The non-degeneracy conditions appearing from this new measure are satisfied by a random circuit of the above kind. The APP measure could be of independent interest for proving other lower bounds.

The determinant polynomial Det_n(x) of degree n is the determinant of a n x n matrix of formal variables. A polynomial f is equivalent to Det_n(x) over a field F if there exists a A in GL(n^2,F) such that f = Det_n(A * x). Determinant equivalence test over F is the following algorithmic task: Given black-box access to a f in F[x], check if f is equivalent to Det_n(x) over F, and if so then output a transformation matrix A in GL(n^2,F). In (Kayal, STOC 2012), a randomized polynomial time determinant equivalence test was given over F = C. But, to our knowledge, the complexity of the problem over finite fields and over Q was not well understood. In this work, we give a randomized poly(n,log |F|) time determinant equivalence test over finite fields F (under mild restrictions on the characteristic and size of F). Over Q, we give an efficient randomized reduction from factoring square-free integers to determinant equivalence test for quadratic forms (i.e. the n=2 case), assuming GRH. This shows that designing a polynomial-time determinant equivalence test over Q is a challenging task. Nevertheless, we show that determinant equivalence test over Q is decidable: For bounded n, there is a randomized polynomial-time determinant equivalence test over Q with access to an oracle for integer factoring. Moreover, for any n, there is a randomized polynomial-time algorithm that takes input black-box access to a f in Q[x] and if f is equivalent to Det_n over Q then it returns a A in GL(n^2,L) such that f = Det_n(A * x), where L is an extension field of Q and [L : Q] <= n. The above algorithms over finite fields and over Q are obtained by giving a polynomial-time randomized reduction from determinant equivalence test to another problem, namely the full matrix algebra isomorphism problem. We also show a reduction in the converse direction which is efficient if n is bounded. These reductions, which hold over any F (under mild restrictions on the characteristic and size of F), establish a close connection between the complexity of the two problems. This then leads to our results via applications of known results on the full algebra isomorphism problem over finite fields (Rónyai, STOC 1987 and Rónyai, J. Symb. Comput. 1990) and over Q (Ivanyos {et al}., Journal of Algebra 2012 and Babai {et al}., Mathematics of Computation 1990).

A homogeneous depth three circuit C computes a polynomial f = T1 + T2 + ... + Ts, where each Ti is a product of d linear forms in n variables over some underlying field F. Given black-box access to f, can we efficiently reconstruct (i.e. proper learn) a homogeneous depth three circuit computing f? Learning various subclasses of circuits is natural and interesting from both theoretical and practical standpoints and in particular, properly learning homogeneous depth three circuits efficiently is stated as an open problem in a work by Klivans and Shpilka (COLT 2003) and is well-studied. Unfortunately, there is substantial amount of evidence to show that this is a hard problem in the worst case. We give a (randomized) poly(n,d,s)-time algorithm to reconstruct non-degenerate homogeneous depth three circuits for n = Ω(d2) (with some additional mild requirements on s and the characteristic of F). We call a circuit C as non-degenerate if the dimension of the partial derivative space of f equals the sum of the dimensions of the partial derivative spaces of the terms T1, T2, …, Ts. In this sense, the terms are “independent” of each other in a non-degenerate circuit. A random homogeneous depth three circuit (where the coefficients of the linear forms are chosen according to the uniform distribution or any other reasonable distribution) is almost surely non-degenerate. In comparison, previous learning algorithms for this circuit class were either improper (with an exponential dependence on d), or they only worked for s < n (with a doubly exponential dependence of the running time on s). The main contribution of this work is to formulate the following paradigm for efficiently handling addition gates and to successfully implement it for the class of homogeneous depth three circuits. The problem of finding the children of an addition gate with large fan-in s is first reduced to the problem of decomposing a suitable vector space U into a (direct) sum of simpler subspaces U1, U2, …, Us. One then constructs a suitable space of operators S consisting of linear maps acting on U such that analyzing the simultaneous global structure of S enables us to efficiently decompose U. In our case, we exploit the structure of the set of low rank matrices in S and of the invariant subspaces of U induced by S. We feel that this paradigm is novel and powerful: it should lead to efficient reconstruction of many other subclasses of circuits for which the efficient reconstruction problem had hitherto looked unapproachable because of the presence of large fan-in addition gates.

An algebraic branching program (ABP) A can be modelled as a product expression X_1 X_2 ... X_d, where X_1 and X_d are 1 x w and w x 1 matrices respectively, and every other X_k is a w x w matrix; the entries of these matrices are linear forms in m variables over a field F (which we assume to be either Q or a field of characteristic poly(m)). The polynomial computed by A is the entry of the 1 x 1 matrix obtained from the product X_1 X_2 ... X_d. We say A is a full rank ABP if the w^2(d-2) + 2w linear forms occurring in the matrices X_1, X_2, ... , X_d are F-linearly independent. Our main result is a randomized reconstruction algorithm for full rank ABPs: Given blackbox access to an m-variate polynomial f of degree at most m, the algorithm outputs a full rank ABP computing f if such an ABP exists, or outputs 'no full rank ABP exists' (with high probability). The running time of the algorithm is polynomial in m and b, where b is the bit length of the coefficients of f. The algorithm works even if X_k is a w_{k-1} x w_k matrix (with w_0 = w_d = 1), and v = (w_1, ..., w_{d-1}) is unknown. The result is obtained by designing a randomized polynomial time equivalence test for the family of iterated matrix multiplication polynomial IMM_{v,d}, the (1,1)-th entry of a product of d rectangular symbolic matrices whose dimensions are according to v in N^{d-1}. At its core, the algorithm exploits a connection between the irreducible invariant subspaces of the Lie algebra of the group of symmetries of a polynomial f that is equivalent to IMM_{v,d} and the 'layer spaces' of a full rank ABP computing f. This connection also helps determine the group of symmetries of IMM_{v,d} and show that IMM_{v,d} is characterized by its group of symmetries.

In a multi- k -ic depth three circuit every variable appears in at most k of the linear polynomials in every product gate of the circuit. This model is a natural generalization of multilinear depth three circuits that allows the formal degree of the circuit to exceed the number of underlying variables (as the formal degree of a multi- k -ic depth three circuit can be kn where n is the number of variables). The problem of proving lower bounds for depth three circuits with high formal degree has gained in importance following a work by Gupta et al. ( 2013 ) on depth reduction to high formal degree depth three circuits. In this work, we show an exponential lower bound for multi- k -ic depth three circuits for any arbitrary constant k .

We show here a $2^{\Omega(\sqrt{d} \cdot \log N)}$ size lower bound for homogeneous depth four arithmetic formulas over fields of characteristic zero. That is, we give an explicit family of polynomials of degree $d$ on $N$ variables (with $N = d^3$ in our case) with 0, 1-coefficients such that for any representation of a polynomial $f$ in this family of the form $ f = \sum_{i} \prod_{j} Q_{ij}, $ where the $Q_{ij}$'s are homogeneous polynomials (recall that a polynomial is said to be homogeneous if all its monomials have the same degree), it must hold that $ \sum_{i, j} (\text{number of monomials of~} Q_{ij}) \geq 2^{\Omega (\sqrt{d} \cdot \log N)}. $ The abovementioned family, which we refer to as the Nisan--Wigderson design-based family of polynomials, is in the complexity class $\mathsf{VNP}$. Our work builds on recent lower bound results and yields an improved quantitative bound as compared to the quasi-polynomial lower bound of [N. Kayal et al., in Symposium on Theory of Computing, ACM, New York, 2014, pp. 119--127] and the $N^{\Omega(\log \log N)}$ lower bound in the independent work of [M. Kumar and S. Saraf, in Automata, Languages, and Programming, Part I, Springer, Berlin, 2014, pp. 751--762].

We show an exponential separation between two well-studied models of algebraic computation, namely read-once oblivious algebraic branching programs (ROABPs) and multilinear depth three circuits. In particular we show the following: 1. There exists an explicit n-variate polynomial computable by linear sized multilinear depth three circuits (with only two product gates) such that every ROABP computing it requires 2^{Omega(n)} size. 2. Any multilinear depth three circuit computing IMM_{n,d} (the iterated matrix multiplication polynomial formed by multiplying d, n * n symbolic matrices) has n^{Omega(d)} size. IMM_{n,d} can be easily computed by a poly(n,d) sized ROABP. 3. Further, the proof of 2 yields an exponential separation between multilinear depth four and multilinear depth three circuits: There is an explicit n-variate, degree d polynomial computable by a poly(n,d) sized multilinear depth four circuit such that any multilinear depth three circuit computing it has size n^{Omega(d)}. This improves upon the quasi-polynomial separation result by Raz and Yehudayoff [2009] between these two models. The hard polynomial in 1 is constructed using a novel application of expander graphs in conjunction with the evaluation dimension measure used previously in Nisan [1991], Raz [2006,2009], Raz and Yehudayoff [2009], and Forbes and Shpilka [2013], while 2 is proved via a new adaptation of the dimension of the partial derivatives measure used by Nisan and Wigderson [1997]. Our lower bounds hold over any field.

Let r be an integer. Let us call a polynomial f as a multi-r-ic polynomial if the degree of f with respect to any variable is at most r (this generalizes the notion of multilinear polynomials). We investigate arithmetic circuits in which the output is syntactically forced to be a multi-r-ic polynomial and refer to these as multi-r-ic circuits. Specifically, first define the formal degree of a node a with respect to a variable x inductively as follows. For a leaf it is 1 if a is labelled with x and zero otherwise; for an internal node labelled with * (respectively +) it is the sum of (respectively the maximum of) the formal degrees of the children with respect to x. We call an arithmetic circuit as a multi-r-ic circuit if the formal degree of the output node with respect to any variable is at most r. We prove lower bounds for various subclasses of multi-r-ic circuits.

Shpilka & Wigderson (IEEE conference on computational complexity, vol 87, 1999) had posed the problem of proving exponential lower bounds for (nonhomogeneous) depth-three arithmetic circuits with bounded bottom fanin over a field $${{\mathbb{F}}}$$ of characteristic zero. We resolve this problem by proving a $${N^{\Omega(\frac{d}{\tau})}}$$ lower bound for (nonhomogeneous) depth-three arithmetic circuits with bottom fanin at most $${\tau}$$ computing an explicit $${N}$$ -variate polynomial of degree $${d}$$ over $${{\mathbb{F}}}$$ . Meanwhile, Nisan & Wigderson (Comp Complex 6(3):217–234, 1997) had posed the problem of proving super-polynomial lower bounds for homogeneous depth-five arithmetic circuits. Over fields of characteristic zero, we show a lower bound of $${N^{\Omega(\sqrt{d})}}$$ for homogeneous depth-five circuits (resp. also for depth-three circuits) with bottom fanin at most $${N^{\mu}}$$ , for any fixed $${\mu < 1}$$ . This resolves the problem posed by Nisan and Wigderson only partially because of the added restriction on the bottom fanin (a general homogeneous depth-five circuit has bottom fanin at most $${N}$$ ).

We show that, over ${\mathbb Q}$, if an $n$-variate polynomial of degree $d = n^{O(1)}$ is computable by an arithmetic circuit of size $s$ (respectively, by an arithmetic branching program of size $s$), then it can also be computed by a depth-3 circuit (i.e., a $\Sigma \Pi \Sigma$ circuit) of size $\exp(O(\sqrt{d \log n \log d\log s}))$ (respectively, of size $\exp(O(\sqrt{d \log n \log s}))$. In particular this yields a $\Sigma \Pi \Sigma$ circuit of size $\exp(O(\sqrt{d} \cdot \log d))$ computing the $d \times d$ determinant $\mathsf{Det}_d$. It also means that if we can prove a lower bound of $\exp(\omega(\sqrt{d} \cdot \log d))$ on the size of any $\Sigma \Pi \Sigma$ circuit computing the $d \times d$ permanent $\mathsf{Perm}_d$, then we get superpolynomial lower bounds for the size of any arithmetic branching program computing $\mathsf{Perm}_d$. We then give some further results pertaining to derandomizing polynomial identity testing and circuit lower bounds. The $\Sigma \Pi \Sigma $ circuits that we construct have the property that (some of) the intermediate polynomials have degree much higher than $d$. Indeed such a counterintuitive construction is unavoidable---it is known that in any $\Sigma \Pi \Sigma$ circuit $C$ computing either $\mathsf{Det}_d$ or $\mathsf{Perm}_d$, if every multiplication gate has fanin at most $d$ (or any constant multiple thereof), then $C$ must have size at least $\exp(\Omega(d))$.

We show here a 2Ω(√d ⋅ log N) size lower bound for homogeneous depth four arithmetic formulas. That is, we give an explicit family of polynomials of degree d on N variables (with N = d3 in our case) with 0, 1-coefficients such that for any representation of a polynomial f in this family of the form f = Σi ∏j Qij, where the Qij's are homogeneous polynomials (recall that a polynomial is said to be homogeneous if all its monomials have the same degree), it must hold that ∑i, j (Number of monomials of Qij)) ≥2Ω(√d ⋅log N). The above mentioned family, which we refer to as the Nisan-Wigderson design-based family of polynomials, is in the complexity class VNP. Our work builds on recent lower bound results [1], [2], [3], [4], [5] and yields an improved quantitative bound as compared to the quasi-polynomial lower bound from an earlier work of the same authors and the NΩ(log log N) lower bound in the independent work of [7].

Arithmetic Circuits compute polynomial functions over their inputs via a sequence of arithmetic operations (additions, subtractions, multiplications, divisions, etc.). This tutorial will give an overview of arithmetic circuit complexity, focusing on the problem of proving lower bounds for arithmetic circuits. In the first part, we begin with a few nontrivial upper bounds - matrix multiplication and the computation of symmetric polynomials. We then motivate some open problems we deal with in arithmetic circuit complexity. We will look at the problem of polynomial identity testing - motivating it by its application to bipartite matching, the problem of learning arithmetic circuits or circuit reconstruction and the problem of proving lower bounds for arithmetic circuits (motivating it via the problem of computing the permanent and the Hamiltonian polynomials). We will also see depth reduction for circuits - the tradeoffs involved (with respect to size) in squashing a circuit into one with smaller depth. In the second part, we will see some classical lower bounds. In particular, we will see lower bounds for monotone arithmetic circuits and multilinear formulas. We then give a very quick overview of approaches being investigated (including geometric complexity theory and tau-conjecture) aiming to prove lower bounds. In the third part, we begin with a warm-up by proving lower bounds for homogeneous depth three circuits. We will then see recent lower bounds for homogeneous depth four circuits and its consequences.

We show that any depth-4 homogeneous arithmetic formula computing the Iterated Matrix Multiplication polynomial IMMn,d -- the (1, 1)-th entry of the product of d generic n × n matrices -- has size nΩ(log n), if d = Ω (log2 n). More-over, any depth-4 homogeneous formula computing the determinant polynomial Detn -- the determinant of a generic n × n matrix -- has size nΩ(log n).

We consider arithmetic formulas consisting of alternating layers of addition (+) and multiplication (×) gates such that the fanin of all the gates in any fixed layer is the same. Such a formula Φ which additionally has the property that its formal/syntactic degree is at most twice the (total) degree of its output polynomial, we refer to as a regular formula. As usual, we allow arbitrary constants from the underlying field F on the incoming edges to a + gate so that a + gate can in fact compute an arbitrary F-linear combination of its inputs. We show that there is an (n2 + 1)-variate polynomial of degree 2n in VNP such that any regular formula computing it must be of size at least nΩ(log n).

Agrawal and Vinay [2008], Koiran [2012], and Tavenas [2013] have recently shown that an exp (ω(√ n log n )) lower bound for depth four homogeneous circuits computing the permanent with bottom layer of × gates having fanin bounded by √n translates to a superpolynomial lower bound for general arithmetic circuits computing the permanent. Motivated by this, we examine the complexity of computing the permanent and determinant via such homogeneous depth four circuits with bounded bottom fanin. We show here that any homogeneous depth four arithmetic circuit with bottom fanin bounded by √n computing the permanent (or the determinant) must be of size exp,(Ω(√ n )).

Agrawal-Vinay [AV08] and Koiran [Koi12] have recently shown that an exp(ω(√n log2n)) lower bound for depth four homogeneous circuits computing the permanent with bottom layer of × gates having fanin bounded by √n translates to super-polynomial lower bound for general arithmetic circuits computing the permanent. Motivated by this, we examine the complexity of computing the permanent and determinant via such homogeneous depth four circuits with bounded bottom fanin. We show here that any homogeneous depth four arithmetic circuit with bottom fanin bounded by √n computing the permanent (or the determinant) must be of size exp(Ω(√n)).

Informally stated, we present here a randomized algorithm that given blackbox access to the polynomial f computed by an unknown/hidden arithmetic formula φ reconstructs, on average, an equivalent or smaller formula φ̂ in time polynomial in the size of its output φ̂. Specifically, we consider arithmetic formulas wherein the underlying tree is a complete binary tree, the leaf nodes are labelled by affine forms (i.e. degree one polynomials) over the input variables and where the internal nodes consist of alternating layers of addition and multiplication gates. We call these alternating normal form (ANF) formulas. If a polynomial f can be computed by an arithmetic formula μ of size s, it can also be computed by an ANF formula φ, possibly of slightly larger size sO(1). Our algorithm gets as input blackbox access to the output polynomial f (i.e. for any point x in the domain, it can query the blackbox and obtain f(x) in one step) of a random ANF formula φ of size s (wherein the coefficients of the affine forms in the leaf nodes of φ are chosen independently and uniformly at random from a large enough subset of the underlying field). With high probability (over the choice of coefficients in the leaf nodes), the algorithm efficiently (i.e. in timesO(1)) computes an ANF formula φ̂ of size s computing f. This then is the strongest model of arithmetic computation for which a reconstruction algorithm is presently known, albeit efficient in a distributional sense rather than in the worst case.

We show that, over Q, if an n-variate polynomial of degree d = nO(1)is computable by an arithmetic circuit of size s (respectively by an arithmetic branching program of size s) then it can also be computed by a depth three circuit (i.e. a ΣΠΣ-circuit) of size exp(O(√(d log n log d log s))) (respectively of size exp(O(√(d log n log s))). In particular this yields a ΣΠΣ circuit of size exp(O(√(d log d))) computing the d × d determinant Detd. It also means that if we can prove a lower bound of exp(omega(√(d log d))) on the size of any ΣΠΣ-circuit computing the d × d permanent Permdthen we get super polynomial lower bounds for the size of any arithmetic branching program computing Permd. We then give some further results pertaining to derandomizing polynomial identity testing and circuit lower bounds. The ΣΠΣ circuits that we construct have the property that (some of) the intermediate polynomials have degree much higher than d. Indeed such a counterintuitive construction is unavoidable - it is known that in any ΣΠΣ circuit C computing either Detdor Perm_d, if every multiplication gate has fanin at most d (or any constant multiple thereof) then C must have size at least exp(Ω(d)).

We present a randomized algorithm for reconstructing multilinear ΣΠΣΠ(2) circuits, i.e., multilinear depth-4 circuits with fan-in 2 at the top + gate. The algorithm is given blackbox access to a polynomial f ∈ F[x1,...,xn] computable by a multilinear ΣΠΣΠ(2) circuit of size s and outputs an equivalent multilinear ΣΠΣΠ(2) circuit, runs in time poly(n,s), and works over any field F. This is the first reconstruction result for any model of depth-4 arithmetic circuits. Prior to our work, reconstruction results for bounded depth circuits were known only for depth-2 arithmetic circuits (Klivans & Spielman, STOC 2001), ΣΠΣ(2) circuits (depth-3 arithmetic circuits with top fan-in 2) (Shpilka, STOC 2007), and ΣΠΣ(k) with k=O(1) (Karnin & Shpilka, CCC 2009). Moreover, the running times of these algorithms have a polynomial dependence on |F| and hence do not work for infinite fields such as Q.

An m-variate polynomial f is said to be an affine projection of some n-variate polynomial g if there exists an nm matrix A and an n-dimensional vector b such that f(x)=g(Ax+b). In other words, if f can be obtained by replacing each variable of g by an affine combination of the variables occurring in f, then it is said to be an affine projection of g. Some well known problems (such as the determinant versus permanent and matrix multiplication for example) are instances of this problem. Given f and g can we determine whether f is an affine projection of g? The intention of this paper is to understand the complexity of the corresponding computational problem: given polynomials f and g find A and b such that f=g(Ax+b), if such an (Ab) exists. We first show that this is an NP-hard problem. We then focus our attention on instances where g is a member of some fixed, well known family of polynomials so that the input consists only of the polynomial f(x) having m variables and degree d. We consider the situation where f(x) is given to us as a blackbox (i.e. for any point aFm we can query the blackbox and obtain f(a) in one step) and devise randomized algorithms with running time poly(mnd) in the following special cases. Firstly where g is the Permanent (respectively the Determinant) of an nxn matrix and A is of rank n2. Secondly where g is the sum of powers polynomial (respectively the sum of products polynomial), and A is a random matrix of the appropriate dimensions (also d should not be too small).

The sum of square roots problem over integers is the task of deciding the sign of a non-zero sum, S = Σi=1nδi· √(ai), where δiϵ { +1, -1} and ai's are positive integers that are upper bounded by N (say). A fundamental open question in numerical analysis and computational geometry is whether |S| ≥ 1/2(n·logN)O(1)when S ≠ 0. We study a formulation of this problem over polynomials: Given an expression S = Σi=1nci· √(fi(x)), where ci's belong to a field of characteristic 0 and fi's are univariate polynomials with degree bounded by d and fi(0) ≠ 0 for all i, is it true that the minimum exponent of x which has a nonzero coefficient in the power series S is upper bounded by (n · d)O(1), unless S = 0? We answer this question affirmatively. Further, we show that this result over polynomials can be used to settle (positively) the sum of square roots problem for a special class of integers: Suppose each integer at is of the form, ai= Xdi+ bi1Xdi-1+ ⋯ +bidi, di>; 0, where X is a positive real number and bij's are integers. Let B = maxi,j{|bij|} and d = maxi{di}. If X >; (B + 1)(n·d)O(1)then a non-zero S = Σi=1nδi· √(ai) is lower bounded as |S| ≥ 1/X(n·d)O(1). The constant in the O(1) notation, as fixed by our analysis, is roughly 2. We then consider the following more general problem: given an arithmetic circuit computing a multivariate polynomial f(X) and integer d, is the degree of f(X) less than or equal to d? We give a coRPPP-algorithm for this problem, improving previous results of and.

In the reconstruction problem for a multivariate polynomial f, we have black box access to f and the goal is to efficiently reconstruct a representation of f in a suitable model of computation. We give a polynomial time randomized algorithm for reconstructing random multilinear formulas. Our algorithm succeeds with high probability when given black box access to the polynomial computed by a random multilinear formula according to a natural distribution. This is the strongest model of computation for which a reconstruction algorithm is presently known, albeit efficient in a distributional sense rather than in the worst-case. Previous results on this problem considered much weaker models such as depth-3 circuits with various restrictions or read-once formulas. Our proof uses ranks of partial derivative matrices as a key ingredient and combines it with analysis of the algebraic structure of random multilinear formulas. Partial derivative matrices have earlier been used to prove lower bounds in a number of models of arithmetic complexity, including multilinear formulas and constant depth circuits. As such, our results give supporting evidence to the general thesis that mathematical properties that capture efficient computation in a model should also enable learning algorithms for functions efficiently computable in that model.

We consider the following computational problem. Let F be a field. Given two n-variate polynomials f(x1, …, xn) and g(x1, …, xn) over the field F, is there an invertible linear transformation of the variables which sends f to g? In other words, can we substitute a linear combination of the xi's for each xj appearing in f and obtain the polynomial g? This problem is known to be at least as difficult as the graph isomorphism problem even for homogeneous degree three polynomials. There is even a cryptographic authentication scheme (Patarin, 1996) based on the presumed average-case hardness of this problem. Here we show that at least in certain (interesting) special cases there is a polynomial-time randomized algorithm for determining this equivalence, if it exists. Somewhat surprisingly, the algorithms that we present are efficient even if the input polynomials are given as arithmetic circuits. As an application, we show that if in the key generation phase of Patarin's authentication scheme, a random multilinear polynomial is used to generate the secret, then the scheme can be broken and the secret recovered in randomized polynomial-time.

Let F be a field and f1,..., fkin F[x1, ..., xn] be a set of k polynomials of degree d in n variables over the field F. These polynomials are said to be algebraically dependent if there exists a nonzero k-variate polynomial A(t1, ..., tk) in F[t1, ..., tk] such that A(f1, ..., fk) = 0. A is then called an (f1, ..., fk)-annihilating polynomial. Within computer science, the notion of algebraic dependence was used in Dvir, Gabizon and Wigderson to construct explicit deterministic extractors from low-degree polynomial sources. They also observed that given (f1, ..., fk) as arithmetic circuits, there exists an efficient randomized algorithm for testing their algebraic independence. The problems of determining good bounds on the degree of the annihilating polynomial and of computing it explicitly were posed as open questions. We solve the two posed problems in the following way: 1) We give closely matching upper and lower bounds for the degree of the annihilating polynomial. 2) We show that it is NP-hard to decide if A(0, .. ,0) equals zero and #P-hard to evaluate A(0,...,0)(mod p) for a given prime p. Indeed the annihilating polynomial A(t1, .., tk)$ does not even admit a small circuit representation unless the polynomial hierarchy collapses. This then, to the best of our knowledge, is the only natural computational problem where determining the existence of an object (the annihilating polynomial in our case) can be done efficiently but the actual computation of the object is provably hard.

We study ¿¿¿(k) circuits, i.e., depth three arithmetic circuits with top fanin k. We give the first deterministic polynomial time blackbox identity test for ¿¿¿(k) circuits over the field Q of rational numbers, thus resolving a question posed by Klivans and Spielman (STOC 2001). Our main technical result is a structural theorem for ¿¿¿(k) circuits that compute the zero polynomial. In particular we show that if a ¿¿¿(k) circuit C = ¿i¿[k]Ai= ¿i¿[k]¿j¿[d]¿ijcomputing the zero polynomial, where each Aiis a product of linear forms with coefficients in ¿, is simple (gcd{Ai| i ¿ [k]} = 1) and minimal (for all proper nonempty subsets S ¿ [k], ¿i¿SAi¿ 0), then the rank (dimension of the span of the linear forms {¿ij| i ¿ [k],j ¿ [d]}) of C can be upper bounded by a function only of k. This proves a weak form of a conjecture of Dvir and Shpilka (STOC 2005) on the structure of identically zero depth three arithmetic circuits. Our blackbox identity test follows from this structural theorem by combining it with a construction of Karnin and Shpilka (CCC 2008). Our proof of the structure theorem exploits the geometry of finite point sets in ¿n. We identify the linear forms appearing in the circuit C with points in ¿n. We then show how to apply high dimensional versions of the Sylvester-Gallai Theorem, a theorem from incidence-geometry, to identify a special linear form appearing in C, such that on the subspace where the linear form vanishes, C restricts to a simpler circuit computing the zero polynomial. This allows us to build an inductive argument bounding the rank of our circuit. While the utility of such theorems from incidence geometry for identity testing has been hinted at before, our proof is the first to develop the connection fully and utilize it effectively.

We study the identity testing problem for depth 3 arithmetic circuits (SigmaPiSigma circuit). We give the first deterministic polynomial time identity test for SigmaPiSigma circuits with bounded top fanin. We also show that the rank of a minimal and simple SigmaPiSigma circuit with bounded top fanin, computing zero, can be unbounded. These results answer the open questions posed by Klivans-Spielman (2001) and Dvir-Shpilka (2005)

We study the complexity of the isomorphism and automorphism problems for finite rings. We show that both integer factorization and graph isomorphism reduce to the problem of counting automorphisms of a ring. This counting problem is shown to be in the functional version of the complexity class AM ∩ coAM and hence is not NP-complete unless the polynomial hierarchy collapses. As a “positive” result we show that deciding whether a given ring has a non-trivial automorphism can be done in deterministic polynomial time. Finding such an automorphism is, however, shown to be randomly equivalent to integer factorization.

We study the complexity of the isomorphism and automorphism problems for finite rings with unity. We show that both integer factorization and graph isomorphism reduce to the problem of counting automorphisms of rings. The problem is shown to be in the complexity class AM /spl cap/ coAM and hence is not NP-complete unless the polynomial hierarchy collapses. Integer factorization also reduces to the problem of finding nontrivial automorphism of a ring and to the problem of finding isomorphism between two rings. We also show that deciding whether a given ring has a non-trivial automorphism can be done in deterministic polynomial time.