We consider solutions to the equation f = h^r for polynomials f and h and integer r > 1. Given a polynomial f in the lacunary (also called sparse or super-sparse) representation, we first show how to determine if f can be written as h^r and, if so, to find such an r. This is a Monte Carlo randomized algorithm whose cost is polynomial in the number of non-zero terms of f and in log(deg f), i.e., polynomial in the size of the lacunary representation, and it works over GF(q)[x] (for large characteristic) as well as Q[x]. We also give two deterministic algorithms to compute the perfect root h given f and r. The first is output-sensitive (based on the sparsity of h) and works only over Q[x]. A sparsity-sensitive Newton iteration forms the basis for the second approach to computing h, which is extremely efficient and works over both GF(q)[x] (for large characteristic) and Q[x], but depends on a number-theoretic conjecture. Work of Erdos, Schinzel, Zannier, and others suggests that both of these algorithms are unconditionally polynomial-time in the lacunary size of the input polynomial f. Finally, we demonstrate the efficiency of the randomized detection algorithm and the latter perfect root computation algorithm with an implementation in the C++ library NTL.
Closest to this current work, @cite_14 shows how to recognize whether @math for a lacunary polynomial @math . Shparlinski uses random evaluations and tests for quadratic residues. How to determine whether a lacunary polynomial is perfect power is posed as an open question.
@cite_14
2170546552 2159268377 2091602684 2949121808
Mulmuley [Mul12a] recently gave an explicit version of Noether’s Normalization lemma for ring of invariants of matrices under simultaneous conjugation, under the conjecture that there are deterministic black-box algorithms for polynomial identity testing (PIT). He argued that this gives evidence that constructing such algorithms for PIT is beyond current techniques. In this work, we show this is not the case. That is, we improve Mulmuley’s reduction and correspondingly weaken the conjecture regarding PIT needed to give explicit Noether Normalization. We then observe that the weaker conjecture has recently been nearly settled by the authors ([FS12]), who gave quasipolynomial size hitting sets for the class of read-once oblivious algebraic branching programs (ROABPs). This gives the desired explicit Noether Normalization unconditionally, up to quasipolynomial factors. As a consequence of our proof we give a deterministic parallel polynomial-time algorithm for deciding if two matrix tuples have intersecting orbit closures, under simultaneous conjugation. We also study the strength of conjectures that Mulmuley requires to obtain similar results as ours. We prove that his conjectures are stronger, in the sense that the computational model he needs PIT algorithms for is equivalent to the well-known algebraic branching program (ABP) model, which is provably stronger than the ROABP model. Finally, we consider the depth-3 diagonal circuit model as defined by Saxena [Sax08], as PIT algorithms for this model also have implications in Mulmuley’s work. Previous work (such as [ASS12] and [FS12]) have given quasipolynomial size hitting sets for this model. In this work, we give a much simpler construction of such hitting sets, using techniques of Shpilka and Volkovich [SV09]. We study the complexity of computing the kth-power of an element of F2n by constant depth arithmetic circuits over F2 (also known as ACP). Our study encompasses the complexity of basic arithmetic operations such as computing cube-root and computing cubic-residuosity of elements of F2n. Our main result is that these problems require exponential size circuits. We also derive strong average-case versions of these results. For example, we show that no subexponential-size, constant-depth, arithmetic circuit over F2 can correctly compute the cubic residue symbol for more than 1 3 + o(1) fraction of the elements of F2n. As a corollary, we deduce a character sum bound showing that the cubic residue character over F2n is uncorrelated with all degree-d n-variate F2 polynomials (viewed as functions over F2n in a natural way), provided d l ne for some universal e > 0. Classical methods (based on van der Corput differencing and the Weil bounds) show this only for d l log(n). Our proof revisits the classical Razborov-Smolensky method for circuit lower bounds, and executes an analogue of it in the land of univariate polynomials over F2n. The tools we use come from both F2n and F2n. In recent years, this interplay between F2n and F2n has played an important role in many results in pseudorandomness, property testing and coding theory. Assuming that NP @math @math BPTIME( @math ), we show that graph min-bisection, dense @math -subgraph, and bipartite clique have no polynomial time approximation scheme (PTAS). We give a reduction from the minimum distance of code (MDC) problem. Starting with an instance of MDC, we build a quasi-random probabilistically checkable proof (PCP) that suffices to prove the desired inapproximability results. In a quasi-random PCP, the query pattern of the verifier looks random in a certain precise sense. Among the several new techniques we introduce, the most interesting one gives a way of certifying that a given polynomial belongs to a given linear subspace of polynomials. As is important for our purpose, the certificate itself happens to be another polynomial, and it can be checked probabilistically by reading a constant number of its values. Let @math be a @math -ary predicate over a finite alphabet. Consider a random CSP @math instance @math over @math variables with @math constraints. When @math the instance @math will be unsatisfiable with high probability, and we want to find a refutation - i.e., a certificate of unsatisfiability. When @math is the @math -ary OR predicate, this is the well studied problem of refuting random @math -SAT formulas, and an efficient algorithm is known only when @math . Understanding the density required for refutation of other predicates is important in cryptography, proof complexity, and learning theory. Previously, it was known that for a @math -ary predicate, having @math constraints suffices for refutation. We give a criterion for predicates that often yields efficient refutation algorithms at much lower densities. Specifically, if @math fails to support a @math -wise uniform distribution, then there is an efficient algorithm that refutes random CSP @math instances @math whp when @math . Indeed, our algorithm will "somewhat strongly" refute @math , certifying @math , if @math then we get the strongest possible refutation, certifying @math . This last result is new even in the context of random @math -SAT. Regarding the optimality of our @math requirement, prior work on SDP hierarchies has given some evidence that efficient refutation of random CSP @math may be impossible when @math . Thus there is an indication our algorithm's dependence on @math is optimal for every @math , at least in the context of SDP hierarchies. Along these lines, we show that our refutation algorithm can be carried out by the @math -round SOS SDP hierarchy. Finally, as an application of our result, we falsify assumptions used to show hardness-of-learning results in recent work of Daniely, Linial, and Shalev-Shwartz.