Abstract

We say that two given polynomials f, g ∈ R[x_1, ..., x_n], over a ring R, are equivalent under shifts if there exists a vector (a_1, ..., a_n) ∈ Rⁿ such that f(x_1+a_1, ..., x_n+a_n) = g(x_1, ..., x_n). This is a special variant of the polynomial projection problem in Algebraic Complexity Theory. Grigoriev and Karpinski (FOCS 1990), Lakshman and Saunders (SIAM J. Computing, 1995), and Grigoriev and Lakshman (ISSAC 1995) studied the problem of testing polynomial equivalence of a given polynomial to any t-sparse polynomial, over the rational numbers, and gave exponential time algorithms. In this paper, we provide hardness results for this problem. Formally, for a ring R, let SparseShift_R be the following decision problem - Given a polynomial P(X), is there a vector 𝐚 such that P(X+𝐚) contains fewer monomials than P(X). We show that SparseShift_R is at least as hard as checking if a given system of polynomial equations over R[x_1,..., x_n] has a solution (Hilbert’s Nullstellensatz). As a consequence of this reduction, we get the following results. 1) SparseShift_ℤ is undecidable. 2) For any ring R (which is not a field) such that HN_R is NP_R-complete over the Blum-Shub-Smale model of computation, SparseShift_ is also NP_R-complete. In particular, SparseShift_ℤ is also NP_ℤ-complete. We also study the gap version of the SparseShift_R and show the following. 1) For every function β:ℕ → ℝ_+ such that β ∈ o(1), N^β-gap-SparseShift_ℤ is also undecidable (where N is the input length). 2) For R = 𝔽_p, ℚ, ℝ or ℤ_q and for every β > 1 the β-gap-SparseShift_R problem is NP-hard. Furthermore, there exists a constant α > 1 such that for every d = O(1) in the sparse representation model, and for every d ≤ n^O(1) in the arithmetic circuit model, the α^d-gap-SparseShift_R problem is NP-hard when given polynomials of degree at most d, in O(nd) many variables, as input.

Abstract

Recently, Forbes, Kumar and Saptharishi [CCC, 2016] proved that there exists an explicit d O(1) - variate and degree d polynomial Pd ∈ VNP such that if any depth four circuit C of bounded formal degree d which computes a polynomial of bounded individual degree O(1), that is functionally equivalent to Pd, then C must have size 2 Ω(√ d log d) . The motivation for their work comes from Boolean Circuit Complexity. Based on a characterization for ACC0 circuits by Yao [FOCS, 1985] and Beigel and Tarui [CC, 1994], Forbes, Kumar and Saptharishi [CCC, 2016] observed that functions in ACC0 can also be computed by algebraic Σ∧ΣΠ circuits (i.e., circuits of the form – sums of powers of polynomials) of 2 logO(1) n size. Thus they argued that a 2 ω(poly log n) “functional” lower bound for an explicit polynomial Q against Σ∧ΣΠ circuits would imply a lower bound for the “corresponding Boolean function” of Q against non-uniform ACC0 . In their work, they ask if their lower bound be extended to Σ∧ΣΠ circuits. In this paper, for large integers n and d such that ω(log2 n) ≤ d ≤ n 0.01, we show that any Σ∧ΣΠ circuit of bounded individual degree at most O d k2
that functionally computes Iterated Matrix Multiplication polynomial IMMn,d (∈ VP) over {0, 1} n 2d must have size n Ω(k) . Since Iterated Matrix Multiplication IMMn,d over {0, 1} n 2d is functionally in GapL, improvement of the afore mentioned lower bound to hold for quasipolynomially large values of individual degree would imply a fine-grained separation of ACC0 from GapL. For the sake of completeness, we also show a syntactic size lower bound against any Σ∧ΣΠ circuit computing IMMn,d (for the same regime of d) which is tight over large fields. Like Forbes, Kumar and Saptharishi [CCC, 2016], we too prove lower bounds against circuits of bounded formal degree which functionally compute IMMn,d, for a slightly larger range of individual degree. 2012 ACM Subject Classification Theory of computation → Circuit complexity; Theory of computation → Algebraic complexity theory Keywords and phrases Functional Lower