We consider the problem of functional decomposition of univariate sparse polynomials. Suppose \(f\in {\mathsf {F}}[x]\) is a polynomial over a field \({\mathsf {F}}\) which has a non-trivial decomposition into \(g,h\in {\mathsf {F}}[x]\) such that f(x) = g(h(x)). Given f and \(\deg g\), our algorithm produces both decomposition factors \(g,h\in {\mathsf {F}}[x]\) in polynomial time in the number of nonzero terms in f, h, the degree of g, and \(\log \deg f\). Work by Zannier implies that \(\deg g\) is typically bounded quadratically by the number of non-zero terms of f, so that we can say the algorithm runs in polynomial time in the sparse sizes of the inputs and outputs. Our algorithm works when the characteristic of \({\mathsf {F}}\) is 0 or does not divide \(\deg g\). We also develop a heuristic and probabilistic classifier, based on random sampling of evaluations in a finite field, which can (on average) distinguish whether a given polynomial is decomposable or not, in sub-linear time in \(\deg f\). Finally, we give a generalization to sparse systems of linear differential equations.

We give a new, constructive uniqueness theorem for tensor decomposition. It applies to order 3 tensors of format n x n x p and can prove uniqueness of decomposition for generic tensors up to rank r = 4n/3 as soon as p ≥ 4. One major advantage over Kruskal’s uniqueness theorem is that our theorem has an algorithmic proof, and the resulting algorithm is efficient. Like the uniqueness theorem, it applies in the range n ≤ r ≤ 4n/3. As a result, we obtain the first efficient algorithm for overcomplete decomposition of generic tensors of order 3. For instance, prior to this work it was not known how to efficiently decompose generic tensors of format n × n × n and rank r = 1.01n (or rank r ≤ (1 + ∈)n, for some constant ∈ > 0). Efficient overcomplete decomposition of generic tensors of format n × n × 3 remains an open problem.

We study the decomposition of multivariate polynomials as sums of powers of linear forms. We give a randomized algorithm for the following problem: If a homogeneous polynomial f ∈ K[x_1 , . . . , x_n] (where K ⊆ ℂ) of degree d is given as a blackbox, decide whether it can be written as a linear combination of d-th powers of linearly independent complex linear forms. The main novel features of the algorithm are: - For d = 3, we improve by a factor of n on the running time from the algorithm in [Pascal Koiran and Mateusz Skomra, 2021]. The price to be paid for this improvement is that the algorithm now has two-sided error. - For d > 3, we provide the first randomized blackbox algorithm for this problem that runs in time poly(n,d) (in an algebraic model where only arithmetic operations and equality tests are allowed). Previous algorithms for this problem [Kayal, 2011] as well as most of the existing reconstruction algorithms for other classes appeal to a polynomial factorization subroutine. This requires extraction of complex polynomial roots at unit cost and in standard models such as the unit-cost RAM or the Turing machine this approach does not yield polynomial time algorithms. - For d > 3, when f has rational coefficients (i.e. K = ℚ), the running time of the blackbox algorithm is polynomial in n,d and the maximal bit size of any coefficient of f. This yields the first algorithm for this problem over ℂ with polynomial running time in the bit model of computation. These results are true even when we replace ℂ by ℝ. We view the problem as a tensor decomposition problem and use linear algebraic methods such as checking the simultaneous diagonalisability of the slices of a tensor. The number of such slices is exponential in d. But surprisingly, we show that after a random change of variables, computing just 3 special slices is enough. We also show that our approach can be extended to the computation of the actual decomposition. In forthcoming work we plan to extend these results to overcomplete decompositions, i.e., decompositions in more than n powers of linear forms.

A sum of affine powers is an expression of the form [f(x1,...,xn) = ∑i=1s αi li(x1,...,xn)ei] where li is an affine form. We propose polynomial time black-box algorithms that find the decomposition with the smallest value of s for an input polynomial f . Our algorithms work in situations where s is small enough compared to the number of variables or to the exponents ei. Although quite simple, this model is a generalization of Waring decomposition. This paper extends previous work on Waring decomposition as well as our work on univariate sums of affine powers (ISSAC'17).

A sum of affine powers is an expression of the form f(x) = s∑/i=1 αi (x - ai)ei. Although quite simple, this model is a generalization of two well-studied models: Waring decomposition and Sparsest Shift. For these three models there are natural extensions to several variables, but this paper is mostly focused on univariate polynomials. We propose algorithms that find the smallest decomposition of f in the first model (sums of affine powers) for an input polynomial f given in dense representation. Our algorithms only work in situations where the smallest decomposition is unique, and we provide conditions that guarantee the uniqueness of the smallest decomposition.

The method of partial derivatives is one of the most successful lower bound methods for arithmetic circuits. It uses as a complexity measure the dimension of the span of the partial derivatives of a polynomial. In this paper, we consider this complexity measure as a computational problem: for an input polynomial given as the sum of its nonzero monomials, what is the complexity of computing the dimension of its space of partial derivatives? We show that this problem is #P-hard and we ask whether it belongs to #P. We analyze the "trace method", recently used in combinatorics and in algebraic complexity to lower bound the rank of certain matrices. We show that this method provides a polynomial-time computable lower bound on the dimension of the span of partial derivatives, and from this method we derive closed-form lower bounds. We leave as an open problem the existence of an approximation algorithm with reasonable performance guarantees.A slightly shorter version of this paper was presented at STACS'17. In this new version we have corrected a typo in Section 4.1, and added a reference to Shitov's work on tensor rank.

Compressed sensing is a technique for finding sparse solutions to underdetermined linear systems. This technique relies on properties of the sensing matrix such as the restricted isometry property. Sensing matrices that satisfy this property with optimal parameters are mainly obtained via probabilistic arguments. Deciding whether a given matrix satisfies the restricted isometry property is a nontrivial computational problem. Indeed, it is shown in this paper that restricted isometry parameters cannot be approximated in polynomial time within any constant factor under the assumption that the hidden clique problem is hard. In addition, on the positive side, an improvement on the brute-force enumeration algorithm for checking the restricted isometry property is proposed.

We present an algorithm which computes the multilinear factors of bivariate lacunary polynomials. It is based on a new Gap theorem which allows to test whether P(X)=∑kj=1 αjXαj(1+X)βjis identically zero in polynomial time. The algorithm we obtain is more elementary than the one by Kaltofen and Koiran (ISSAC'05) since it relies on the valuation of polynomials of the previous form instead of the height of the coefficients. As a result, it can be used to find some linear factors of bivariate lacunary polynomials over a field of large finite characteristic in probabilistic polynomial time.

No abstract available.

In their paper on the “chasm at depth four”, Agrawal and Vinay have shown that polynomials in m variables of degree O ( m ) which admit arithmetic circuits of size 2 o ( m ) also admit arithmetic circuits of depth four and size 2 o ( m ) . This theorem shows that for problems such as arithmetic circuit lower bounds or black-box derandomization of identity testing, the case of depth four circuits is in a certain sense the general case. In this paper we show that smaller depth four circuits can be obtained if we start from polynomial size arithmetic circuits. For instance, we show that if the permanent of n × n matrices has circuits of size polynomial in n , then it also has depth 4 circuits of size n O ( n log n ) . If the original circuit uses only integer constants of polynomial size, then the same is true for the resulting depth four circuit. These results have potential applications to lower bounds and deterministic identity testing, in particular for sums of products of sparse univariate polynomials. We also use our techniques to reprove two results on: – the existence of nontrivial boolean circuits of constant depth for languages in LOGCFL ; – reduction to polylogarithmic depth for arithmetic circuits of polynomial size and polynomially bounded degree.

Polynomial identity testing and arithmetic circuit lower bounds are two central questions in algebraic complexity theory. It is an intriguing fact that these questions are actually related. One of the authors of the present paper has recently proposed a "real {\tau}-conjecture" which is inspired by this connection. The real {\tau}-conjecture states that the number of real roots of a sum of products of sparse univariate polynomials should be polynomially bounded. It implies a superpolynomial lower bound on the size of arithmetic circuits computing the permanent polynomial. In this paper we show that the real {\tau}-conjecture holds true for a restricted class of sums of products of sparse polynomials. This result yields lower bounds for a restricted class of depth-4 circuits: we show that polynomial size circuits from this class cannot compute the permanent, and we also give a deterministic polynomial identity testing algorithm for the same class of circuits.

We deploy algebraic complexity theoretic techniques for constructing symmetric determinantal representations of weakly-skew circuits, which include formulas. Our representations produce matrices of much smaller dimensions than those given in the convex geometry literature when applied to polynomials having a concise representation (as a sum of monomials, or more generally as an arithmetic formula or a weakly-skew circuit). These representations are valid in any field of characteristic different from 2. In characteristic 2 we are led to an almost complete solution to a question of Buergisser on the VNP-completeness of the partial permanent. In particular, we show that the partial permanent cannot be VNP-complete in a finite field of characteristic 2 unless the polynomial hierarchy collapses.

We show that the permanent cannot be computed by DLOGTIME-uniform threshold or arithmetic circuits of depth o(log log n) and polynomial size.

Suppose the polynomials f and g in K[x1,...,xr] over the field K are determinants of non-singular m x m and n x n matrices, respectively, whose entries are in K ∪ x1,...,xr. Furthermore, suppose h = f/g is a polynomial in K[x1,..., xr]. We construct an s x s matrix C whose entries are in K ∪ x1,...,xr, such that h = det(C) and s = γ (m+n)6, where γ = O(1) if K is an infinite field or if for the finite field K = F{q} with q elements we have m = O(q), and where γ = (logq m)1+o(1) if q = o(m). Our construction utilizes the notion of skew circuits by Toda and WSK circuits by Malod and Portier. Our problem was motivated by resultant formulas derived from Chow forms.

We present algorithms that compute all irreducible factors of degree ≤ d of supersparse (lacunary) multivariate polynomials in n variables over an algebraic number field in deterministic polynomial-time in (l+d)n, where l is the size of the input polynomial. In supersparse polynomials, the term degrees enter logarithmically as their numbers of binary digits into the size measure l. The factors are again represented as supersparse polynomials. If the factors are represented as straight-line programs or black box polynomials, we can achieve randomized polynomial-time in (l+d)O(1). Our approach follows that by H. W. Lenstra, Jr., on computing factors of univariate supersparse polynomials over algebraic number fields. We generalize our ISSAC 2005 results for computing linear factors of supersparse bivariate polynomials over the rational numbers by appealing to recent lower bounds on the height of algebraic numbers and to a special case of the former Lang conjecture.

We present algorithms that compute the linear and quadratic factors of supersparse (lacunary) bivariate polynomials over the rational numbers in polynomial-time in the input size. In supersparse polynomials, the term degrees can have hundreds of digits as binary numbers. Our algorithms are Monte Carlo randomized for quadratic factors and deterministic for linear factors. Our approach relies on the results by H. W. Lenstra, Jr., on computing factors of univariate supersparse polynomials over the rational numbers. Furthermore, we show that the problem of determining the irreducibility of a supersparse bivariate polynomial over a large finite field of any characteristic is co-NP-hard via randomized reductions.

We study the following decision problem: is the language recognized by a quantum finite automaton empty or nonempty? We prove that this problem is decidable or undecidable depending on whether recognition is defined by strict or nonstrict thresholds. This result is in contrast with the corresponding situation for probabilistic finite automata, for which it is known that strict andnonstrict thresholds both lead to undecidable problems.

Abstract A Liouville function is an analytic function H: ℂ → ℂ with a Taylor series such the an's form a “very fast growing” sequence of integers. In this paper we exhibit the complete first-order theory of the complex field expanded with H.

International audience

We show that proving lower bounds in algebraic models of computntion may not be easier than in the standard %ring machine model.For instance, a superpolynomial lower bound on the size of an algebraic circuit solving the real knapsack problem (or on the running time of a real 'Brring machine) would imply a separation of P from PSPACE.A more general result relates parallel complexity classes in boolean and real models of computation.We also propose a few problems in algebraic complexity and topological complexity,

We prove old and new results on the complexity of computing the dimension of algebraic varieties. In particular, we show that this problem is NP-complete in the Blum-Shub-Smale model of computation over C, that it admits a s/sup O(1)/D/sup O(n)/ deterministic algorithm, and that for systems with integer coefficients it is in the Arthur-Merlin class under the Generalized Riemann Hypothesis. The first two results are based on a general derandomization argument.

The main result of this paper is a /spl Omega/(n/sup 1/4/) lower bound on the size of a sigmoidal circuit computing a specific AC/sub 2//sup 0/ function. This is the first lower bound for the computation model of sigmoidal circuits with unbounded weights. We also give upper and lower bounds for the same function in a few other computation models: circuits of AND/OR gates, threshold circuits, and circuits of piecewise-rational gates.

The first part of this paper deals with finite-precision arithmetic. We give an upper bound on the precision that should be used in a Monte-Carlo integration method. Such bounds have been known only for convex sets; our bound applies to almost any "reasonable" set. In the second part of the paper, we show how to construct in polynomial time first-order formulas that approximately define the volume of definable sets. This result is based on a VC dimension hypothesis, and is inspired from the well-known complexity-theoretic result "BPP/spl sube//sub 2/". Finally, we show how these results can be applied to sets defined by systems of inequalities involving polynomial or exponential functions. In particular, we describe an application to a problem of structural complexity in the Blum-Shub-Smale model of computation over the reals.

In this paper we consider real counterparts of classical probabilistic complexity classes in the framework of real Turing machines as introduced by Blum, Shub, and Smale [2].We give an extension of the well-known "BPP ~P/poly" result from discrete complexity theory to a very general setting in the real number model.This result holds for real inputs, real outputs, and random elements drawn from an arbitrary probability distribution over lR~.Then we turn to the study of Boolean parts, that is, classes of languages of zero-one vectors accepted by real machines.In particular we show that the classes BPP, PP, PH, and PSPACE are not enlarged by allowing the use of real constants and arithmetic at unit cost provided we restrict branching to equality tests.

We describe an efficient algorithm for learning from examples a class of feedforward neural networks with real inputs and outputs in a real-value generalization of the Probably Approximately Correct (PAC) model. These networks can approximate an arbitrary function with an arbitrary precision. The learning algorithm can accommodate a fairly general worst-case noise model. The main improvement over previous work is that the running time of the algorithm grows only polynomially as the size of the target network increases (there is still an exponential dependence on the dimension of the input space, however). The main computational tool is an iterative “loading” algorithm which adds new hidden units to the hypothesis network sequentially. This avoids the difficult problem of optimizing the weights of all units simultaneously.

The dynamics of discrete time, continuous state Hopfield networks is driven by an energy function. In this paper, we use this tool to prove under mild hypotheses that any trajectory converges to a fixed point for the sequential iteration, and to a cycle of length 2 or a fixed point for the parallel iteration. Perhaps surprisingly, it seems that no rigorous proof of these results was published before.

We propose a weak version of the Blum-Shub-Smale model (1989) of computation over the real numbers. In this weak model only a "moderate" usage of multiplications and divisions is allowed. The class of languages recognizable in polynomial time as shown to be the complexity class P/poly. This implies under a standard complexity-theoretic assumption that P/spl ne/NP in the weak model, and that problems such as the real traveling salesman problem cannot be solved in polynomial time. As an application, we generalize recent results of H.T. Siegelmann and E.D. Sontag (1993) on recurrent neural networks, and of W. Maass (1993) on feedforward nets.>