More Like this

1. Some bounds arising from a polynomial ideal associated to any $t$-design

   https://doi.org/10.13069/jacodesmath.729446  

   MARTIN, William J ; STINSON, Douglas R ( May 2020 , Journal of Algebra Combinatorics Discrete Structures and Applications)

   null (Ed.)

   We consider ordered pairs (X,B) where X is a finite set of size v and B is some collection of k-element subsets of X such that every t-element subset of X is contained in exactly λ "blocks'' b ∈B for some fixed λ. We represent each block b by a zero-one vector c_b of length v and explore the ideal I(B) of polynomials in v variables with complex coefficients which vanish on the set { c_b ∣ b ∈ B}. After setting up the basic theory, we investigate two parameters related to this ideal: γ1(B) is the smallest degree of a non-trivial polynomial in the ideal I(B) and γ2(B) is the smallest integer s such that I(B) is generated by a set of polynomials of degree at most s. We first prove the general bounds t/2 < γ1(B) ≤ γ2(B) ≤ k. Examining important families of examples, we find that, for symmetric 2-designs and Steiner systems, we have γ2(B) ≤ t. But we expect γ2(B) to be closer to k for less structured designs and we indicate this by constructing infinitely many triple systems satisfying γ2(B) = k. 

   more » « less
2. Certified Hermite Matrices from Approximate Roots - Univariate Case

   https://doi.org/10.1007/978-3-030-43120-4_1  

   Ayyildiz Akoglu, T ; Szanto, A. ( March 2020 , Part of the Lecture Notes in Computer Science book series (LNCS, volume 11989))

   Let 𝑓1,…,𝑓𝑚 be univariate polynomials with rational coefficients and I:=⟨𝑓1,…,𝑓𝑚⟩⊂ℚ[𝑥] be the ideal they generate. Assume that we are given approximations {𝑧1,…,𝑧𝑘}⊂ℚ[𝑖] for the common roots {𝜉1,…,𝜉𝑘}=𝑉(I)⊆ℂ . In this study, we describe a symbolic-numeric algorithm to construct a rational matrix, called Hermite matrix, from the approximate roots {𝑧1,…,𝑧𝑘} and certify that this matrix is the true Hermite matrix corresponding to the roots V(I) . Applications of Hermite matrices include counting and locating real roots of the polynomials and certifying their existence. 

   more » « less
3. Efficient Algorithms for Least Square Piecewise Polynomial Regression

   Lokshtanov, Daniel ; Suri, Subhash ; Xue, Jie ( September 2021 , ESA21: Proceedings of European Symposium on Algorithms)

   null (Ed.)

   We present approximation and exact algorithms for piecewise regression of univariate and bivariate data using fixed-degree polynomials. Specifically, given a set S of n data points (x1, y1), . . . , (xn, yn) ∈ Rd × R where d ∈ {1, 2}, the goal is to segment xi’s into some (arbitrary) number of disjoint pieces P1, . . . , Pk, where each piece Pj is associated with a fixed-degree polynomial fj : Rd → R, to minimize the total loss function λk+􏰄ni=1(yi −f(xi))2, where λ ≥ 0 is a regularization term that penalizes model complexity (number of pieces) and f : 􏰇kj=1 Pj → R is the piecewise polynomial function defined as f|Pj = fj. The pieces P1,...,Pk are disjoint intervals of R in the case of univariate data and disjoint axis-aligned rectangles in the case of bivariate data. Our error approximation allows use of any fixed-degree polynomial, not just linear functions. Our main results are the following. For univariate data, we present a (1 + ε)-approximation algorithm with time complexity O(nε log1ε), assuming that data is presented in sorted order of xi’s. For bivariate data, we √ present three results: a sub-exponential exact algorithm with running time nO( n); a polynomial-time constant- approximation algorithm; and a quasi-polynomial time approximation scheme (QPTAS). The bivariate case is believed to be NP-hard in the folklore but we could not find a published record in the literature, so in this paper we also present a hardness proof for completeness. 

   more » « less
4. On correlation bounds against polynomials Leibniz International Proceedings in Informatics (LIPIcs):38th Computational Complexity Conference (CCC 2023)

   https://doi.org/10.4230/LIPIcs.CCC.2023.3  

   Ivanov, Peter ; Pavlovic, Liam ; Viola, Emanuele ( January 2023 , Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Ta-Shma, Amnon (Ed.)

   We study the fundamental challenge of exhibiting explicit functions that have small correlation with low-degree polynomials over 𝔽₂. Our main contributions include: 1) In STOC 2020, CHHLZ introduced a new technique to prove correlation bounds. Using their technique they established new correlation bounds for low-degree polynomials. They conjectured that their technique generalizes to higher degree polynomials as well. We give a counterexample to their conjecture, in fact ruling out weaker parameters and showing what they prove is essentially the best possible. 2) We propose a new approach for proving correlation bounds with the central "mod functions," consisting of two steps: (I) the polynomials that maximize correlation are symmetric and (II) symmetric polynomials have small correlation. Contrary to related results in the literature, we conjecture that (I) is true. We argue this approach is not affected by existing "barrier results." 3) We prove our conjecture for quadratic polynomials. Specifically, we determine the maximum possible correlation between quadratic polynomials modulo 2 and the functions (x_1,… ,x_n) → z^{∑ x_i} for any z on the complex unit circle, and show that it is achieved by symmetric polynomials. To obtain our results we develop a new proof technique: we express correlation in terms of directional derivatives and analyze it by slowly restricting the direction. 4) We make partial progress on the conjecture for cubic polynomials, in particular proving tight correlation bounds for cubic polynomials whose degree-3 part is symmetric. 

   more » « less
5. Low-Rank Univariate Sum of Squares Has No Spurious Local Minima

   https://doi.org/10.1137/22M1516208  

   Legat, Benoît ; Yuan, Chenyang ; Parrilo, Pablo ( September 2023 , SIAM Journal on Optimization)

   We study the problem of decomposing a polynomial p into a sum of r squares by minimizing a quadratically penalized objective fp(u)=‖‖∑ri=1u2i−p‖‖2. This objective is nonconvex and is equivalent to the rank-r Burer-Monteiro factorization of a semidefinite program (SDP) encoding the sum of squares decomposition. We show that for all univariate polynomials p, if r≥2 then fp(u) has no spurious second-order critical points, showing that all local optima are also global optima. This is in contrast to previous work showing that for general SDPs, in addition to genericity conditions, r has to be roughly the square root of the number of constraints (the degree of p) for there to be no spurious second-order critical points. Our proof uses tools from computational algebraic geometry and can be interpreted as constructing a certificate using the first- and second-order necessary conditions. We also show that by choosing a norm based on sampling equally-spaced points on the circle, the gradient ∇fp can be computed in nearly linear time using fast Fourier transforms. Experimentally we demonstrate that this method has very fast convergence using first-order optimization algorithms such as L-BFGS, with near-linear scaling to million-degree polynomials. 

   more » « less