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 2963964051 1430582609 2012329067 1988229094 2962824725 2016576580 2083449425 2952621790 2621688363 1988307095 1859301526 1562749094 2086684904 2115831572 1990538552 1973836644
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. We prove conditional near-quadratic running time lower bounds for approximate Bichromatic Closest Pair with Euclidean, Manhattan, Hamming, or edit distance. Specifically, unless the Strong Exponential Time Hypothesis (SETH) is false, for every δ>0 there exists a constant e>0 such that computing a (1+e)-approximation to the Bichromatic Closest Pair requires Ω(n2−δ) time. In particular, this implies a near-linear query time for Approximate Nearest Neighbor search with polynomial preprocessing time. Our reduction uses the recently introduced Distributed PCP framework, but obtains improved efficiency using Algebraic Geometry (AG) codes. Efficient PCPs from AG codes have been constructed in other settings before, but our construction is the first to yield new hardness results. We show how to compute any symmetric Boolean function on n variables over any field (as well as the integers) with a probabilistic polynomial of degree O(a#x221A;n log(1 a#x03B5;))) and error at most a#x03B5;. The degree dependence on n and a#x03B5; is optimal, matching a lower bound of Razborov (1987) and Smolensky (1987) for the MAJORITY function. The proof is constructive: a low-degree polynomial can be efficiently sampled from the distribution. This polynomial construction is combined with other algebraic ideas to give the first sub quadratic time algorithm for computing a (worst-case) batch of Hamming distances in super logarithmic dimensions, exactly. To illustrate, let c(n): N -> N. Suppose we are given a database D of n vectors in 0, 1 (c(n) log n) and a collection of n query vectors Q in the same dimension. For all u in Q, we wish to compute a v in D with minimum Hamming distance from u. We solve this problem in n(2-1 O(c(n) log2 c(n))) randomized time. Hence, the problem is in "truly sub quadratic" time for O(log n) dimensions, and in sub quadratic time for d = o((log2 n) (log log n)2). We apply the algorithm to computing pairs with maximum inner product, closest pair in l1 for vectors with bounded integer entries, and pairs with maximum Jaccard coefficients. L. G. Khachiyan recently published a polynomial algorithm to check feasibility of a system of linear inequalities. The method is an adaptation of an algorithm proposed by Shor for non-linear optimization problems. In this paper we show that the method also yields interesting results in combinatorial optimization. Thus it yields polynomial algorithms for vertex packing in perfect graphs; for the matching and matroid intersection problems; for optimum covering of directed cuts of a digraph; for the minimum value of a submodular set function; and for other important combinatorial problems. On the negative side, it yields a proof that weighted fractional chromatic number is NP-hard. Let H be a (k+1)-uniform, D-regular hypergraph on n vertices and let (H) be the minimum number of vertices left uncovered by a matching in H. Cj(H), the j-codegree of H, is the maximum number of edges sharing a set of j vertices in common. We prove a general upper bound on (H), based on the codegree sequence C2 (H), C3 (H),…. Our bound improves and generalizes many results on the topic, including those of Grable, Alon, Kim, and Spencer, and Kostochka and Rodl. It also leads to a substantial improvement in several applications. The key ingredient of the proof is the so-called polynomial technique, which is a new and useful tool to prove concentration results for functions with large Lipschitz coefficient. This technique is of independent interest. © 2000 John Wiley & Sons, Inc. Random Struct. Alg., 17: 29–63, 2000 Freedman, Kitaev, and Wang (2002), and later Aharonov, Jones, and Landau (2009), established a quantum algorithm to "additively" approximate the Jones polynomial V(L;t) at any principal root of unity t. The strength of this additive approximation depends exponentially on the bridge number of the link presentation. Freedman, Larsen, and Wang (2002) established that the approximation is universal for quantum computation at a non- lattice, principal root of unity. We show that any value-distinguishing approximation of the Jones polynomial at these non-lattice roots of unity is #P-hard. Given the power to decide whetherjV(L;t)j b for fixed constants 0 1, T(G; x; y) is #P-hard to approximate within a factor of c even for planar graphs G. Along the way, we clarify and generalize both Aaronson's theorem and the Solovay- Kitaev theorem. 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 nxn matrices has circuits of size polynomial in n, then it also has depth 4 circuits of size n^O^(^n^l^o^g^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. Let S= [email protected]?R^n|g"1(x)>=0,...,g"m(x)>=0 be a basic closed semialgebraic set defined by real polynomials g"i. Putinar's Positivstellensatz says that, under a certain condition stronger than compactness of S, every real polynomial f positive on S possesses a representation [email protected]?"i"="0^[email protected]"ig"i where g"[email protected]?1 and each @s"i is a sum of squares of polynomials. Such a representation is a certificate for the nonnegativity of f on S. We give a bound on the degrees of the terms @s"ig"i in this representation which depends on the description of S, the degree of f and a measure of how close f is to having a zero on S. As a consequence, we get information about the convergence rate of Lasserre's procedure for optimization of a polynomial subject to polynomial constraints. Let @math be a nontrivial @math -ary predicate. Consider a random instance of the constraint satisfaction problem @math on @math variables with @math constraints, each being @math applied to @math randomly chosen literals. Provided the constraint density satisfies @math , such an instance is unsatisfiable with high probability. The problem is to efficiently find a proof of unsatisfiability. We show that whenever the predicate @math supports a @math - probability distribution on its satisfying assignments, the sum of squares (SOS) algorithm of degree @math (which runs in time @math ) refute a random instance of @math . In particular, the polynomial-time SOS algorithm requires @math constraints to refute random instances of CSP @math when @math supports a @math -wise uniform distribution on its satisfying assignments. Together with recent work of [LRS15], our result also implies that polynomial-size semidefinite programming relaxation for refutation requires at least @math constraints. Our results (which also extend with no change to CSPs over larger alphabets) subsume all previously known lower bounds for semialgebraic refutation of random CSPs. For every constraint predicate @math , they give a three-way hardness tradeoff between the density of constraints, the SOS degree (hence running time), and the strength of the refutation. By recent algorithmic results of [AOW15] and [RRS16], this full three-way tradeoff is , up to lower-order factors. We consider the problem of single-round private information retrieval (PIR) from @math replicated databases. We consider the case when @math databases are outdated (unsynchronized), or even worse, adversarial (Byzantine), and therefore, can return incorrect answers. In the PIR problem with Byzantine databases (BPIR), a user wishes to retrieve a specific message from a set of @math messages with zero-error, irrespective of the actions performed by the Byzantine databases. We consider the @math -privacy constraint in this paper, where any @math databases can collude, and exchange the queries submitted by the user. We derive the information-theoretic capacity of this problem, which is the maximum number of that can be retrieved privately (under the @math -privacy constraint) for every symbol of the downloaded data. We determine the exact BPIR capacity to be @math , if @math . This capacity expression shows that the effect of Byzantine databases on the retrieval rate is equivalent to removing @math databases from the system, with a penalty factor of @math , which signifies that even though the number of databases needed for PIR is effectively @math , the user still needs to access the entire @math databases. The result shows that for the unsynchronized PIR problem, if the user does not have any knowledge about the fraction of the messages that are mis-synchronized, the single-round capacity is the same as the BPIR capacity. Our achievable scheme extends the optimal achievable scheme for the robust PIR (RPIR) problem to correct the introduced by the Byzantine databases as opposed to in the RPIR problem. Our converse proof uses the idea of the cut-set bound in the network coding problem against adversarial nodes. We consider two problems: randomly generating labeled bipartite graphs with a given degree sequence and randomly generating labeled tournaments with a given score sequence. We analyze simple Markov chains for both problems. For the first problem, we cannot prove that our chain is rapidly mixing in general, but in the near-regular case, i.e., when all the degrees are almost equal, we give a proof of rapid mixing. Our methods also apply to the corresponding problem for general (nonbipartite) regular graphs, which was studied earlier by several researchers. One significant difference in our approach is that our chain has one state for every graph (or bipartite graph) with the given degree sequence; in particular, there are no auxiliary states as in the chain used by Jerrum and Sinclair. For the problem of generating tournaments, we are able to prove that our Markov chain on tournaments is rapidly mixing, if the score sequence is near-regular. The proof techniques we use for the two problems are similar. ©1999 John Wiley & Sons, Inc. Random Struct. Alg., 14: 293–308, 1999 Given a large data matrix @math , we consider the problem of determining whether its entries are i.i.d. with some known marginal distribution @math , or instead @math contains a principal submatrix @math whose entries have marginal distribution @math . As a special case, the hidden (or planted) clique problem requires to find a planted clique in an otherwise uniformly random graph. Assuming unbounded computational resources, this hypothesis testing problem is statistically solvable provided @math for a suitable constant @math . However, despite substantial effort, no polynomial time algorithm is known that succeeds with high probability when @math . Recently Meka and Wigderson meka2013association , proposed a method to establish lower bounds within the Sum of Squares (SOS) semidefinite hierarchy. Here we consider the degree- @math SOS relaxation, and study the construction of meka2013association to prove that SOS fails unless @math . An argument presented by Barak implies that this lower bound cannot be substantially improved unless the witness construction is changed in the proof. Our proof uses the moments method to bound the spectrum of a certain random association scheme, i.e. a symmetric random matrix whose rows and columns are indexed by the edges of an Erd "os-Renyi random graph. In this paper we study polynomial identity testing of sums of @math read-once algebraic branching programs ( @math -RO-ABPs), generalizing the work in (Shpilka and Volkovich 2008,2009), who considered sums of @math read-once formulas ( @math -RO-formulas). We show that @math -RO-ABPs are strictly more powerful than @math -RO-formulas, for any @math , where @math is the number of variables. We obtain the following results: 1) Given free access to the RO-ABPs in the sum, we get a deterministic algorithm that runs in time @math , where @math bounds the size of any largest RO-ABP given on the input. This implies we have a deterministic polynomial time algorithm for testing whether the sum of a constant number of RO-ABPs computes the zero polynomial. 2) Given black-box access to the RO-ABPs computing the individual polynomials in the sum, we get a deterministic algorithm that runs in time @math . 3) Finally, given only black-box access to the polynomial computed by the sum of the @math RO-ABPs, we obtain an @math time deterministic algorithm. Motivated by the numerical treatment of parametric and stochastic PDEs, we analyze the least-squares method for polynomial approximation of multivariate functions based on random sampling according to a given probability measure. Recent work has shown that in the univariate case, the least-squares method is quasi-optimal in expectation in [A. Cohen, M A. Davenport and D. Leviatan. Found. Comput. Math. 13 (2013) 819–834] and in probability in [G. Migliorati, F. Nobile, E. von Schwerin, R. Tempone, Found. Comput. Math. 14 (2014) 419–456], under suitable conditions that relate the number of samples with respect to the dimension of the polynomial space. Here “quasi-optimal” means that the accuracy of the least-squares approximation is comparable with that of the best approximation in the given polynomial space. In this paper, we discuss the quasi-optimality of the polynomial least-squares method in arbitrary dimension. Our analysis applies to any arbitrary multivariate polynomial space (including tensor product, total degree or hyperbolic crosses), under the minimal requirement that its associated index set is downward closed. The optimality criterion only involves the relation between the number of samples and the dimension of the polynomial space, independently of the anisotropic shape and of the number of variables. We extend our results to the approximation of Hilbert space-valued functions in order to apply them to the approximation of parametric and stochastic elliptic PDEs. As a particular case, we discuss “inclusion type” elliptic PDE models, and derive an exponential convergence estimate for the least-squares method. Numerical results confirm our estimate, yet pointing out a gap between the condition necessary to achieve optimality in the theory, and the condition that in practice yields the optimal convergence rate. For many random constraint satisfaction problems, by now there exist asymptotically tight estimates of the largest constraint density for which solutions exist. At the same time, for many of these problems, all known polynomial-time algorithms stop finding solutions at much smaller densities. For example, it is well-known that it is easy to color a random graph using twice as many colors as its chromatic number. Indeed, some of the simplest possible coloring algorithms achieve this goal. Given the simplicity of those algorithms, one would expect room for improvement. Yet, to date, no algorithm is known that uses (2 - epsiv)chi colors, in spite of efforts by numerous researchers over the years. In view of the remarkable resilience of this factor of 2 against every algorithm hurled at it, we find it natural to inquire into its origin. We do so by analyzing the evolution of the set of k-colorings of a random graph, viewed as a subset of 1,...,k n, as edges are added. We prove that the factor of 2 corresponds in a precise mathematical sense to a phase transition in the geometry of this set. Roughly speaking, we prove that the set of k-colorings looks like a giant ball for k ges 2chi, but like an error-correcting code for k les (2 - epsiv)chi. We also prove that an analogous phase transition occurs both in random k-SAT and in random hypergraph 2-coloring. And that for each of these three problems, the location of the transition corresponds to the point where all known polynomial-time algorithms fail. To prove our results we develop a general technique that allows us to establish rigorously much of the celebrated 1-step replica-symmetry-breaking hypothesis of statistical physics for random CSPs. We consider the problem of approximating a Boolean functionf∶ 0,1 n → 0,1 by the sign of an integer polynomialp of degreek. For us, a polynomialp(x) predicts the value off(x) if, wheneverp(x)≥0,f(x)=1, and wheneverp(x)<0,f(x)=0. A low-degree polynomialp is a good approximator forf if it predictsf at almost all points. Given a positive integerk, and a Boolean functionf, we ask, “how good is the best degreek approximation tof?” We introduce a new lower bound technique which applies to any Boolean function. We show that the lower bound technique yields tight bounds in the casef is parity. Minsky and Papert [10] proved that a perceptron cannot compute parity; our bounds indicate exactly how well a perceptron canapproximate it. As a consequence, we are able to give the first correct proof that, for a random oracleA, PP A is properly contained in PSPACE A . We are also able to prove the old AC0 exponential-size lower bounds in a new way. This allows us to prove the new result that an AC0 circuit with one majority gate cannot approximate parity. Our proof depends only on basic properties of integer polynomials. In the study of the spectra of power-law graphs, there are basically two competing approaches. One is to prove analogues of Wigner's semicircle law, whereas the other predicts that the eigenvalues follow a power-law distribution. Although the semicircle law and the power law have nothing in common, we will show that both approaches are essentially correct if one considers the appropriate matrices. We will prove that (under certain mild conditions) the eigenvalues of the (normalized) Laplacian of a random power-law graph follow the semicircle law, whereas the spectrum of the adjacency matrix of a power-law graph obeys the power law. Our results are based on the analysis of random graphs with given expected degrees and their relations to several key invariants. Of interest are a number of (new) values for the exponent β, where phase transitions for eigenvalue distributions occur. The spectrum distributions have direct implications to numerous graph algorithms such as, for example, randomized algorithms that involve rapidly mixing Markov chains.