Search

The problem PosSLP is the problem of determining whether a given straight-line program (SLP) computes a positive integer. PosSLP was introduced by Allender et al. to study the complexity of numerical analysis (Allender et al., 2009). PosSLP can also be reformulated as the problem of deciding whether the integer computed by a given SLP can be expressed as the sum of squares of four integers, based on the well-known result by Lagrange in 1770, which demonstrated that every natural number can be represented as the sum of four non-negative integer squares. In this paper, we explore several natural extensions of this problem by investigating whether the positive integer computed by a given SLP can be written as the sum of squares of two or three integers. We delve into the complexity of these variations and demonstrate relations between the complexity of the original PosSLP problem and the complexity of these related problems. Additionally, we introduce a new intriguing problem called Div2SLP and illustrate how Div2SLP is connected to DegSLP and the problem of whether an SLP computes an integer expressible as the sum of three squares. By comprehending the connections between these problems, our results offer a deeper understanding of decision problems associated with SLPs and open avenues for further exciting research

The Skolem Problem asks, given an integer linear recurrence sequence (LRS), to determine whether the sequence contains a zero term or not. Its decidability is a longstanding open problem in theoretical computer science and automata theory. Currently, decidability is only known for LRS of order at most 4. On the other hand, the sole known complexity result is NP-hardness, due to Blondel and Portier. A fundamental result in this area is the celebrated Skolem-Mahler-Lech theorem, which asserts that the zero set of any LRS is the union of a finite set and finitely many arithmetic progressions. This paper focuses on a computational perspective of the Skolem-Mahler-Lech theorem: we show that the problem of counting the zeros of a given LRS is #P-hard, and in fact #P-complete for the instances generated in our reduction.

Border complexity measures are defined via limits (or topological closures), so that any function which can approximated arbitrarily closely by low complexity functions itself has low border complexity. Debordering is the task of proving an upper bound on some non-border complexity measure in terms of a border complexity measure, thus getting rid of limits. Debordering is at the heart of understanding the difference between Valiant's determinant vs permanent conjecture, and Mulmuley and Sohoni's variation which uses border determinantal complexity. The debordering of matrix multiplication tensors by Bini played a pivotal role in the development of efficient matrix multiplication algorithms. Consequently, debordering finds applications in both establishing computational complexity lower bounds and facilitating algorithm design. Currently, very few debordering results are known. In this work, we study the question of debordering the border Waring rank of polynomials. Waring and border Waring rank are very well studied measures in the context of invariant theory, algebraic geometry, and matrix multiplication algorithms. For the first time, we obtain a Waring rank upper bound that is exponential in the border Waring rank and only linear in the degree. All previous known results were exponential in the degree. For polynomials with constant border Waring rank, our results imply an upper bound on the Waring rank linear in degree, which previously was only known for polynomials with border Waring rank at most 5., Comment: 22 pages; accepted at STACS 2024; this is an edited part of the preprint arXiv:2211.07055

We study algebraic complexity classes and their complete polynomials under \emph{homogeneous linear} projections, not just under the usual affine linear projections that were originally introduced by Valiant in 1979. These reductions are weaker yet more natural from a geometric complexity theory (GCT) standpoint, because the corresponding orbit closure formulations do not require the padding of polynomials. We give the \emph{first} complete polynomials for VF, the class of sequences of polynomials that admit small algebraic formulas, under homogeneous linear projections: The sum of the entries of the non-commutative elementary symmetric polynomial in 3 by 3 matrices of homogeneous linear forms. Even simpler variants of the elementary symmetric polynomial are hard for the topological closure of a large subclass of VF: the sum of the entries of the non-commutative elementary symmetric polynomial in 2 by 2 matrices of homogeneous linear forms, and homogeneous variants of the continuant polynomial (Bringmann, Ikenmeyer, Zuiddam, JACM '18). This requires a careful study of circuits with arity-3 product gates., Comment: This is edited part of preprint arXiv:2211.07055

The problem $\textrm{PosSLP}$ involves determining whether an integer computed by a given straight-line program is positive. This problem has attracted considerable attention within the field of computational complexity as it provides a complete characterization of the complexity associated with numerical computation. However, non-trivial lower bounds for $\textrm{PosSLP}$ remain unknown. In this paper, we demonstrate that $\textrm{PosSLP} \in \textrm{BPP}$ would imply that $\textrm{NP} \subseteq \textrm{BPP}$, under the assumption of a conjecture concerning the complexity of the radical of a polynomial proposed by Dutta, Saxena, and Sinhababu (STOC'2018). Our proof builds upon the established $\textrm{NP}$-hardness of determining if a univariate polynomial computed by an SLP has a real root, as demonstrated by Perrucci and Sabia (JDA'2005). Therefore, our lower bound for $\textrm{PosSLP}$ represents a significant advancement in understanding the complexity of this problem. It constitutes the first non-trivial lower bound for $\textrm{PosSLP}$ , albeit conditionally. Additionally, we show that counting the real roots of an integer univariate polynomial, given as input by a straight-line program, is $\#\textrm{P}$-hard.

This paper focuses on the study of the order of power series that are linear combinations of a given finite set of power series. The order of a formal power series, known as $\textrm{ord}(f)$, is defined as the minimum exponent of $x$ that has a non-zero coefficient in $f(x)$. Our first result is that the order of the Wronskian of these power series is equivalent up to a polynomial factor, to the maximum order which occurs in the linear combination of these power series. This implies that the Wronskian approach used in (Kayal and Saha, TOCT'2012) to upper bound the order of sum of square roots is optimal up to a polynomial blowup. We also demonstrate similar upper bounds, similar to those of (Kayal and Saha, TOCT'2012), for the order of power series in a variety of other scenarios. We also solve a special case of the inequality testing problem outlined in (Etessami et al., TOCT'2014). In the second part of the paper, we study the equality variant of the sum of square roots problem, which is decidable in polynomial time due to (Bl\"omer, FOCS'1991). We investigate a natural generalization of this problem when the input integers are given as straight line programs. Under the assumption of the Generalized Riemann Hypothesis (GRH), we show that this problem can be reduced to the so-called ``one dimensional'' variant. We identify the key mathematical challenges for solving this ``one dimensional'' variant.

De-bordering is the task of proving that a border complexity measure is bounded from below, by a non-border complexity measure. This task is at the heart of understanding the difference between Valiant's determinant vs permanent conjecture, and Mulmuley and Sohoni's Geometric Complexity Theory (GCT) approach to settle the P \neq NP conjecture. Currently, very few de-bordering results are known. In this work, we study the question of de-bordering the border Waring rank of polynomials. Waring and border Waring rank are very well studied measures, in the context of invariant theory, algebraic geometry and matrix multiplication algorithms. For the first time, we obtain a Waring rank upper bound that is exponential in the border Waring rank and only *linear* in the degree. All previous results were known to be exponential in the degree. According to Kumar's recent surprising result (ToCT'20), a small border Waring rank implies that the polynomial can be approximated as a sum of a constant and a small product of linear polynomials. We prove the converse of Kumar's result, and in this way we de-border Kumar's complexity, and obtain a new formulation of border Waring rank, up to a factor of the degree. We phrase this new formulation as the orbit closure problem of the product-plus-power polynomial, and we successfully de-border this orbit closure. We fully implement the GCT approach against the power sum, and we generalize the ideas of Ikenmeyer-Kandasamy (STOC'20) to this new orbit closure. In this way, we obtain new multiplicity obstructions that are constructed from just the symmetries of the points and representation theoretic branching rules, rather than explicit multilinear computations. Furthermore, we realize that the generalization of our converse of Kumar's theorem to square matrices gives a homogeneous formulation of Ben-Or and Cleve (SICOMP'92). This results ...

We investigate the number of real zeros of a univariate $k$-sparse polynomial $f$ over the reals, when the coefficients of $f$ come from independent standard normal distributions. Recently B\"urgisser, Erg\"ur and Tonelli-Cueto showed that the expected number of real zeros of $f$ in such cases is bounded by $O(\sqrt{k} \log k)$. In this work, we improve the bound to $O(\sqrt{k})$ and also show that this bound is tight by constructing a family of sparse support whose expected number of real zeros is lower bounded by $\Omega(\sqrt{k})$. Our main technique is an alternative formulation of the Kac integral by Edelman-Kostlan which allows us to bound the expected number of zeros of $f$ in terms of the expected number of zeros of polynomials of lower sparsity. Using our technique, we also recover the $O(\log n)$ bound on the expected number of real zeros of a dense polynomial of degree $n$ with coefficients coming from independent standard normal distributions.

We propose an efficient algorithm to compute the real roots of a sparse polynomial $f\in\mathbb{R}[x]$ having $k$ non-zero real-valued coefficients. It is assumed that arbitrarily good approximations of the non-zero coefficients are given by means of a coefficient oracle. For a given positive integer $L$, our algorithm returns disjoint disks $\Delta_{1},\ldots,\Delta_{s}\subset\mathbb{C}$, with $s<2k$, centered at the real axis and of radius less than $2^{-L}$ together with positive integers $\mu_{1},\ldots,\mu_{s}$ such that each disk $\Delta_{i}$ contains exactly $\mu_{i}$ roots of $f$ counted with multiplicity. In addition, it is ensured that each real root of $f$ is contained in one of the disks. If $f$ has only simple real roots, our algorithm can also be used to isolate all real roots. The bit complexity of our algorithm is polynomial in $k$ and $\log n$, and near-linear in $L$ and $\tau$, where $2^{-\tau}$ and $2^{\tau}$ constitute lower and upper bounds on the absolute values of the non-zero coefficients of $f$, and $n$ is the degree of $f$. For root isolation, the bit complexity is polynomial in $k$ and $\log n$, and near-linear in $\tau$ and $\log\sigma^{-1}$, where $\sigma$ denotes the separation of the real roots.

We give faster algorithms for producing sparse approximations of the transition matrices of $k$-step random walks on undirected, weighted graphs. These transition matrices also form graphs, and arise as intermediate objects in a variety of graph algorithms. Our improvements are based on a better understanding of processes that sample such walks, as well as tighter bounds on key weights underlying these sampling processes. On a graph with $n$ vertices and $m$ edges, our algorithm produces a graph with about $n\log{n}$ edges that approximates the $k$-step random walk graph in about $m + n \log^4{n}$ time. In order to obtain this runtime bound, we also revisit "density independent" algorithms for sparsifying graphs whose runtime overhead is expressed only in terms of the number of vertices.

For "large" class $\mathcal{C}$ of continuous probability density functions (p.d.f.), we demonstrate that for every $w\in\mathcal{C}$ there is mixture of discrete Binomial distributions (MDBD) with $T\geq N\sqrt{\phi_{w}/\delta}$ distinct Binomial distributions $B(\cdot,N)$ that $\delta$-approximates a discretized p.d.f. $\widehat{w}(i/N)\triangleq w(i/N)/[\sum_{\ell=0}^{N}w(\ell/N)]$ for all $i\in[3:N-3]$, where $\phi_{w}\geq\max_{x\in[0,1]}|w(x)|$. Also, we give two efficient parallel algorithms to find such MDBD. Moreover, we propose a sequential algorithm that on input MDBD with $N=2^k$ for $k\in\mathbb{N}_{+}$ that induces a discretized p.d.f. $\beta$, $B=D-M$ that is either Laplacian or SDDM matrix and parameter $\epsilon\in(0,1)$, outputs in $\widehat{O}(\epsilon^{-2}m + \epsilon^{-4}nT)$ time a spectral sparsifier $D-\widehat{M}_{N} \approx_{\epsilon} D-D\sum_{i=0}^{N}\beta_{i}(D^{-1} M)^i$ of a matrix-polynomial, where $\widehat{O}(\cdot)$ notation hides $\mathrm{poly}(\log n,\log N)$ factors. This improves the Cheng et al.'s [CCLPT15] algorithm whose run time is $\widehat{O}(\epsilon^{-2} m N^2 + NT)$. Furthermore, our algorithm is parallelizable and runs in work $\widehat{O}(\epsilon^{-2}m + \epsilon^{-4}nT)$ and depth $O(\log N\cdot\mathrm{poly}(\log n)+\log T)$. Our main algorithmic contribution is to propose the first efficient parallel algorithm that on input continuous p.d.f. $w\in\mathcal{C}$, matrix $B=D-M$ as above, outputs a spectral sparsifier of matrix-polynomial whose coefficients approximate component-wise the discretized p.d.f. $\widehat{w}$. Our results yield the first efficient and parallel algorithm that runs in nearly linear work and poly-logarithmic depth and analyzes the long term behaviour of Markov chains in non-trivial settings. In addition, we strengthen the Spielman and Peng's [PS14] parallel SDD solver.

We show some facts regarding the question whether, for any number $n$, the length of the shortest Addition Multiplications Chain (AMC) computing $n$ is polynomial in the length of the shortest division-free Straight Line Program (SLP) that computes $n$. If the answer to this question is "yes", then we can show a stronger upper bound for $\mathrm{PosSLP}$, the important problem which essentially captures the notion of efficient computation over the reals. If the answer is "no", then this would demonstrate how subtraction helps generating integers super-polynomially faster, given that addition and multiplication can be done in unit time. In this paper, we show that, for almost all numbers, AMCs and SLPs need same asymptotic length for computation. However, for one specific form of numbers, SLPs are strictly more powerful than AMCs by at least one step of computation.