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
1993714280
For an @math -variate degree– @math real polynomial @math , we prove that @math is determined up to an additive @math as long as @math is a @math -wise independent distribution over @math for @math . This gives a broad class of explicit pseudorandom generators against degree- @math boolean threshold functions, and answers an open question of (FOCS 2009). Let @math be an arbitrary polynomial of degree @math with @math non-zero integer coefficients of absolute value less than @math . In this paper, we answer the open question whether the real roots of @math can be computed with a number of arithmetic operations over the rational numbers that is polynomial in the input size of the sparse representation of @math . More precisely, we give a deterministic, complete, and certified algorithm that determines isolating intervals for all real roots of @math with @math many exact arithmetic operations over the rational numbers. When using approximate but certified arithmetic, the bit complexity of our algorithm is bounded by @math , where @math means that we ignore logarithmic. Hence, for sufficiently sparse polynomials (i.e. @math for a positive constant @math ), the bit complexity is @math . We also prove that the latter bound is optimal up to logarithmic factors. We show that positive @math -equivariant symplectic homology is a contact invariant for a subclass of contact manifolds which are boundaries of Liouville domains. In nice cases, when the set of Conley-Zehnder indices of all good periodic Reeb orbits on the boundary of the Liouville domain is lacunary, the positive @math -equivariant symplectic homology can be computed; it is generated by those orbits. We prove a "Viterbo functoriality" property: when one Liouville domain is embedded into an other one, there is a morphism (reversing arrows) between their positive @math -equivariant symplectic homologies and morphisms compose nicely. These properties allow us to give a proof of Ustilovsky's result on the number of non isomorphic contact structures on the spheres @math . They also give a new proof of a Theorem by Ekeland and Lasry on the minimal number of periodic Reeb orbits on some hypersurfaces in @math . We extend this result to some hypersurfaces in some negative line bundles. 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. Improving on the Voronoi cell based techniques of Micciancio and Voulgaris (SIAM J. Comp. 13), and Sommer, Feder and Shalvi (SIAM J. Disc. Math. 09), we give a Las Vegas @math expected time and space algorithm for CVPP (the preprocessing version of the Closest Vector Problem, CVP). This improves on the @math deterministic runtime of the Micciancio Voulgaris algorithm, henceforth MV, for CVPP (which also solves CVP) at the cost of a polynomial amount of randomness (which only affects runtime, not correctness). As in MV, our algorithm proceeds by computing a short path on the Voronoi graph of the lattice, where lattice points are adjacent if their Voronoi cells share a common facet, from the origin to a closest lattice vector. Our main technical contribution is a randomized procedure that given the Voronoi relevant vectors of a lattice - the lattice vectors inducing facets of the Voronoi cell - as preprocessing and any "close enough" lattice point to the target, computes a path to a closest lattice vector of expected polynomial size. This improves on the @math path length given by the MV algorithm. Furthermore, as in MV, each edge of the path can be computed using a single iteration over the Voronoi relevant vectors. As a byproduct of our work, we also give an optimal relationship between geometric and path distance on the Voronoi graph, which we believe to be of independent interest. The problems of finding shortest common supersequences (SCS) and longest common subsequences (LCS) are two well-known NP -hard problems that have applications in many areas including computational molecular biology, data compression, robot motion planning and scheduling, text editing, etc. A lot of fruitless effort has been spent in searching for good approximation algorithms for these problems. In this paper, we show that these problems are inherently hard to approximate in the worst case. In particular, we prove that (i) SCS does not have a polynomial time linear approximation algorithm, unless P = NP ; (ii) There exists a constant @math such that, if SCS has a polynomial time approximation algorithm with ratio @math , where @math is the number of input sequences, then NP is contained in DTIME @math ; (iii) There exists a constant @math such that, if LCS has a polynomial time approximation algorithm with performance ratio @math , then P = NP . The proofs utilize the recent results of [Proc. 23rd IEEE Symposium on Foundations of Computer Science, 1992, pp. 14-23] on the complexity of approximation problems. In the second part of the paper, we introduce a new method for analyzing the average-case performance of algorithms for sequences, based on Kolmogorov complexity. Despite the above nonapproximability results, we show that near optimal solutions for both SCS and LCS can be found on the average. More precisely, consider a fixed alphabet @math and suppose that the input sequences are generated randomly according to the uniform probability distribution and are of the same length @math . Moreover, assume that the number of input sequences is polynomial in @math . Then, there are simple greedy algorithms which approximate SCS and LCS with expected additive errors @math and @math for any @math , respectively. Incidentally, our analyses also provide tight upper and lower bounds on the expected LCS and SCS lengths for a set of random sequences, solving a generalization of another well-known open question on the expected LCS length for two random sequences [K. Alexander, The rate of convergence of the mean length of the longest common subsequence, 1992, manuscript],[V. Chvatal and D. Sankoff, J. Appl. Probab., 12 (1975), pp. 306-315], [D. Sankoff and J. Kruskall, eds., Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparison, Addison-Wesley, Reading, MA, 1983]. The problem of estimating the phases (angles) of a complex unit-modulus vector @math from their noisy pairwise relative measurements @math , where @math is a complex-valued Gaussian random matrix, is known as phase synchronization. The maximum likelihood estimator (MLE) is a solution to a unit--modulus-constrained quadratic programming problem, which is nonconvex. Existing works have proposed polynomial-time algorithms such as a semidefinite programming (SDP) relaxation or the generalized power method (GPM). Numerical experiments suggest that both of these methods succeed with high probability for @math up to @math , yet existing analyses only confirm this observation for @math up to @math . In this paper, we bridge the gap by proving that the SDP relaxation is tight for @math , and GPM converges to the global optimum under the same regime. Moreover, we establish a linear convergence rate for GPM, and derive a tight... In this paper we show a new way of constructing deterministic polynomial-time approximation algorithms for computing complex-valued evaluations of a large class of graph polynomials on bounded degree graphs. In particular, our approach works for the Tutte polynomial and independence polynomial, as well as partition functions of complex-valued spin and edge-coloring models. More specifically, we define a large class of graph polynomials @math and show that if @math and there is a disk @math centered at zero in the complex plane such that @math does not vanish on @math for all bounded degree graphs @math , then for each @math in the interior of @math there exists a deterministic polynomial-time approximation algorithm for evaluating @math at @math . This gives an explicit connection between absence of zeros of graph polynomials and the existence of efficient approximation algorithms, allowing us to show new relationships between well-known conjectures. Our work builds on a recent line of work initiated b... Index Coding has received considerable attention recently motivated in part by real-world applications and in part by its connection to Network Coding. The basic setting of Index Coding encodes the problem input as an undirected graph and the fundamental parameter is the broadcast rate @math , the average communication cost per bit for sufficiently long messages (i.e. the non-linear vector capacity). Recent nontrivial bounds on @math were derived from the study of other Index Coding capacities (e.g. the scalar capacity @math ) by Bar- (2006), Lubetzky and Stav (2007) and (2008). However, these indirect bounds shed little light on the behavior of @math : there was no known polynomial-time algorithm for approximating @math in a general network to within a nontrivial (i.e. @math ) factor, and the exact value of @math remained unknown for any graph where Index Coding is nontrivial. Our main contribution is a direct information-theoretic analysis of the broadcast rate @math using linear programs, in contrast to previous approaches that compared @math with graph-theoretic parameters. This allows us to resolve the aforementioned two open questions. We provide a polynomial-time algorithm with a nontrivial approximation ratio for computing @math in a general network along with a polynomial-time decision procedure for recognizing instances with @math . In addition, we pinpoint @math precisely for various classes of graphs (e.g. for various Cayley graphs of cyclic groups) thereby simultaneously improving the previously known upper and lower bounds for these graphs. Via this approach we construct graphs where the difference between @math and its trivial lower bound is linear in the number of vertices and ones where @math is uniformly bounded while its upper bound derived from the naive encoding scheme is polynomially worse. There are many classical problems in P whose time complexities have not been improved over the past decades. Recent studies of "Hardness in P" have revealed that, for several of such problems, the current fastest algorithm is the best possible under some complexity assumptions. To bypass this difficulty, (SODA 2017) introduced the concept of fully polynomial FPT algorithms. For a problem with the current best time complexity @math , the goal is to design an algorithm running in @math time for a parameter @math and a constant @math . In this paper, we investigate the complexity of graph problems in P parameterized by tree-depth, a graph parameter related to tree-width. We show that a simple divide-and-conquer method can solve many graph problems, including Weighted Matching, Negative Cycle Detection, Minimum Weight Cycle, Replacement Paths, and 2-hop Cover, in @math time or @math time, where @math is the tree-depth of the input graph. Because any graph of tree-width @math has tree-depth at most @math , our algorithms also run in @math time or @math time. These results match or improve the previous best algorithms parameterized by tree-width. Especially, we solve an open problem of fully polynomial FPT algorithm for Weighted Matching parameterized by tree-width posed by The discrete Gaussian @math is the distribution that assigns to each vector @math in a shifted lattice @math probability proportional to @math . It has long been an important tool in the study of lattices. More recently, algorithms for discrete Gaussian sampling (DGS) have found many applications in computer science. In particular, polynomial-time algorithms for DGS with very high parameters @math have found many uses in cryptography and in reductions between lattice problems. And, in the past year, Aggarwal, Dadush, Regev, and Stephens-Davidowitz showed @math -time algorithms for DGS with a much wider range of parameters and used them to obtain the current fastest known algorithms for the two most important lattice problems, the Shortest Vector Problem (SVP) and the Closest Vector Problem (CVP). Motivated by its increasing importance, we investigate the complexity of DGS itself and its relationship to CVP and SVP. Our first result is a polynomial-time dimension-preserving reduction from DGS to CVP. There is a simple reduction from CVP to DGS, so this shows that DGS is equivalent to CVP. Our second result, which we find to be more surprising, is a polynomial-time dimension-preserving reduction from centered DGS (the important special case when @math ) to SVP. In the other direction, there is a simple reduction from @math -approximate SVP for any @math , and we present some (relatively weak) evidence to suggest that this might be the best achievable approximation factor. We also show that our CVP result extends to a much wider class of distributions and even to other norms. In the distributed all-pairs shortest paths problem (APSP), every node in the weighted undirected distributed network (the CONGEST model) needs to know the distance from every other node using least number of communication rounds (typically called time complexity ). The problem admits @math -approximation @math -time algorithm and a nearly-tight @math lower bound [Nanongkai, STOC'14; Lenzen and Patt-Shamir PODC'15] @math , @math and @math hide polylogarithmic factors. Note that the lower bounds also hold even in the unweighted case and in the weighted case with polynomial approximation ratios LenzenP_podc13,HolzerW12,PelegRT12,Nanongkai-STOC14 . . For the exact case, Elkin [STOC'17] presented an @math time bound, which was later improved to @math [Huang, Nanongkai, Saranurak FOCS'17]. It was shown that any super-linear lower bound (in @math ) requires a new technique [Censor-Hillel, Khoury, Paz, DISC'17], but otherwise it remained widely open whether there exists a @math -time algorithm for the exact case, which would match the best possible approximation algorithm. This paper resolves this question positively: we present a randomized (Las Vegas) @math -time algorithm, matching the lower bound up to polylogarithmic factors. Like the previous @math bound, our result works for directed graphs with zero (and even negative) edge weights. In addition to the improved running time, our algorithm works in a more general setting than that required by the previous @math bound; in our setting (i) the communication is only along edge directions (as opposed to bidirectional), and (ii) edge weights are arbitrary (as opposed to integers in 1, 2, ... poly(n) ). ... Binary Exponential Backoff (BEB) is a key component of the IEEE 802.11 DCF protocol. It has been shown that BEB can achieve the theoretical limit of throughput as long as the initial backoff window size is properly selected. It, however, suffers from significant delay degradation when the network becomes saturated. It is thus of special interest for us to further design backoff schemes for IEEE 802.11 DCF networks that can achieve comparable throughput as BEB, but provide better delay performance. This paper presents a systematic study on the effect of backoff schemes on throughput and delay performance of saturated IEEE 802.11 DCF networks. In particular, a backoff scheme is defined as a sequence of backoff window sizes @math . The analysis shows that a saturated IEEE 802.11 DCF network has a single steady-state operating point as long as @math is a monotonic increasing sequence. The maximum throughput is found to be independent of @math , yet the growth rate of @math determines a fundamental tradeoff between throughput and delay performance. For illustration, Polynomial Backoff is proposed, and the effect of polynomial power @math on the network performance is characterized. It is demonstrated that Polynomial Backoff with a larger @math is more robust against the fluctuation of the network size, but in the meanwhile suffers from a larger second moment of access delay. Quadratic Backoff (QB), i.e., Polynomial Backoff with @math , stands out to be a favorable option as it strikes a good balance between throughput and delay performance. The comparative study between QB and BEB confirms that QB well preserves the robust nature of BEB and achieves much better queueing performance than BEB. The classic all-terminal network reliability problem posits a graph, each of whose edges fails independently with some given probability. The goal is to determine the probability that the network becomes disconnected due to edge failures. This problem has obvious applications in the design of communication networks. Since the problem is @math -complete and thus believed hard to solve exactly, a great deal of research has been devoted to estimating the failure probability. In this paper, we give a fully polynomial randomized approximation scheme that, given any n-vertex graph with specified failure probabilities, computes in time polynomial in n and @math an estimate for the failure probability that is accurate to within a relative error of @math with high probability. We also give a deterministic polynomial approximation scheme for the case of small failure probabilities. Some extensions to evaluating probabilities of @math -connectivity, strong connectivity in directed Eulerian graphs and @math -way disconnection, and to evaluating the Tutte polynomial are also described. This version of the paper corrects several errata that appeared in the previous journal publication [D. R. Karger, SIAM J. Comput., 29 (1999), pp. 492--514]. We study the problem of fair allocation for indivisible goods. We use the the maxmin share paradigm introduced by Budish as a measure for fairness. Procacciafirst (EC'14) were first to investigate this fundamental problem in the additive setting. In contrast to what real-world experiments suggest, they show that a maxmin guarantee (1- @math allocation) is not always possible even when the number of agents is limited to 3. While the existence of an approximation solution (e.g. a @math - @math allocation) is quite straightforward, improving the guarantee becomes subtler for larger constants. Procaccia provide a proof for existence of a @math - @math allocation and leave the question open for better guarantees. Our main contribution is an answer to the above question. We improve the result of ! to a @math factor in the additive setting. The main idea for our @math - @math allocation method is clustering the agents. To this end, we introduce three notions and techniques, namely reducibility, matching allocation, and cycle-envy-freeness, and prove the approximation guarantee of our algorithm via non-trivial applications of these techniques. Our analysis involves coloring and double counting arguments that might be of independent interest. One major shortcoming of the current studies on fair allocation is the additivity assumption on the valuations. We alleviate this by extending our results to the case of submodular, fractionally subadditive, and subadditive settings. More precisely, we give constant approximation guarantees for submodular and XOS agents, and a logarithmic approximation for the case of subadditive agents. Furthermore, we complement our results by providing close upper bounds for each class of valuation functions. Finally, we present algorithms to find such allocations for additive, submodular, and XOS settings in polynomial time. This paper presents a polynomial-time @math -approximation algorithm for maximizing nonnegative @math -submodular functions. This improves upon the previous @math -approximation by Ward and Z ivn 'y (SODA'14), where @math . We also show that for monotone @math -submodular functions there is a polynomial-time @math -approximation algorithm while for any @math a @math -approximation algorithm for maximizing monotone @math -submodular functions would require exponentially many queries. In particular, our hardness result implies that our algorithms are asymptotically tight. We also extend the approach to provide constant factor approximation algorithms for maximizing skew-bisubmodular functions, which were recently introduced as generalizations of bisubmodular functions. Recently a great deal of attention has been focused on quantum computation following a sequence of results [Bernstein and Vazirani, in Proc. 25th Annual ACM Symposium Theory Comput., 1993, pp. 11--20, SIAM J. Comput., 26 (1997), pp. 1277--1339], [Simon, in Proc. 35th Annual IEEE Symposium Foundations Comput. Sci., 1994, pp. 116--123, SIAM J. Comput., 26 (1997), pp. 1340--1349], [Shor, in Proc. 35th Annual IEEE Symposium Foundations Comput. Sci., 1994, pp. 124--134] suggesting that quantum computers are more powerful than classical probabilistic computers. Following Shor's result that factoring and the extraction of discrete logarithms are both solvable in quantum polynomial time, it is natural to ask whether all of @math can be efficiently solved in quantum polynomial time. In this paper, we address this question by proving that relative to an oracle chosen uniformly at random with probability 1 the class @math cannot be solved on a quantum Turing machine (QTM) in time @math . We also show that relative to a permutation oracle chosen uniformly at random with probability 1 the class @math cannot be solved on a QTM in time @math . The former bound is tight since recent work of Grover [in Proc. @math th Annual ACM Symposium Theory Comput. , 1996] shows how to accept the class @math relative to any oracle on a quantum computer in time @math . Given a linear code @math , one can define the @math -th power of @math as the span of all componentwise products of @math elements of @math . A power of @math may quickly fill the whole space. Our purpose is to answer the following question: does the square of a code "typically" fill the whole space? We give a positive answer, for codes of dimension @math and length roughly @math or smaller. Moreover, the convergence speed is exponential if the difference @math is at least linear in @math . The proof uses random coding and combinatorial arguments, together with algebraic tools involving the precise computation of the number of quadratic forms of a given rank, and the number of their zeros. We consider two-person zero-sum stochastic mean payoff games with perfect information, or BWR-games, given by a digraph G=(V, E), with local rewards r: E→ℝ, and three types of vertices: black VB, white VW, and random VR forming a partition of V. It is a long-standing open question whether a polynomial time algorithm for BWR-games exists, or not. In fact, a pseudo-polynomial algorithm for these games would already imply their polynomial solvability. In this paper, we show that BWR-games with a constant number of random nodes can be solved in pseudo-polynomial time. That is, for any such game with a few random nodes |VR|=O(1), a saddle point in pure stationary strategies can be found in time polynomial in |VW|+|VB|, the maximum absolute local reward R, and the common denominator of the transition probabilities. We develop an extension of recently developed methods for obtaining time-space tradeoff lower bounds for problems of learning from random test samples to handle the situation where the space of tests is signficantly smaller than the space of inputs, a class of learning problems that is not handled by prior work. This extension is based on a measure of how matrices amplify the 2-norms of probability distributions that is more refined than the 2-norms of these matrices. As applications that follow from our new technique, we show that any algorithm that learns @math -variate homogeneous polynomial functions of degree at most @math over @math from evaluations on randomly chosen inputs either requires space @math or @math time where @math is the dimension of the space of such functions. These bounds are asymptotically optimal since they match the tradeoffs achieved by natural learning algorithms for the problems.