Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userLocal decoding and testing of polynomials over grids
91
0
0.0
(
0
)
Added by
Mitali Bafna
Publication date
2017
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
The well-known DeMillo-Lipton-Schwartz-Zippel lemma says that $n$-variate polynomials of total degree at most $d$ over grids, i.e. sets of the form $A_1 times A_2 times cdots times A_n$, form error-correcting codes (of distance at least $2^{-d}$ provided $min_i{|A_i|}geq 2$). In this work we explore their local decodability and (tolerant) local testability. While these aspects have been studied extensively when $A_1 = cdots = A_n = mathbb{F}_q$ are the same finite field, the setting when $A_i$s are not the full field does not seem to have been explored before. In this work we focus on the case $A_i = {0,1}$ for every $i$. We show that for every field (finite or otherwise) there is a test whose query complexity depends only on the degree (and not on the number of variables). In contrast we show that decodability is possible over fields of positive characteristic (with query complexity growing with the degree of the polynomial and the characteristic), but not over the reals, where the query complexity must grow with $n$. As a consequence we get a natural example of a code (one with a transitive group of symmetries) that is locally testable but not locally decodable. Classical results on local decoding and testing of polynomials have relied on the 2-transitive symmetries of the space of low-degree polynomials (under affine transformations). Grids do not possess this symmetry: So we introduce some new techniques to overcome this handicap and in particular use the hypercontractivity of the (constant weight) noise operator on the Hamming cube.
rate research
Read More
Two polynomials $f, g in mathbb{F}[x_1, ldots, x_n]$ are called shift-equivalent if there exists a vector $(a_1, ldots, a_n) in mathbb{F}^n$ such that the polynomial identity $f(x_1+a_1, ldots, x_n+a_n) equiv g(x_1,ldots,x_n)$ holds. Our main result is a new randomized algorithm that tests whether two given polynomials are shift equivalent. Our algorithm runs in time polynomial in the circuit size of the polynomials, to which it is given black box access. This complements a previous work of Grigoriev (Theoretical Computer Science, 1997) who gave a deterministic algorithm running in time $n^{O(d)}$ for degree $d$ polynomials. Our algorithm uses randomness only to solve instances of the Polynomial Identity Testing (PIT) problem. Hence, if one could de-randomize PIT (a long-standing open problem in complexity) a de-randomization of our algorithm would follow. This establishes an equivalence between de-randomizing shift-equivalence testing and de-randomizing PIT (both in the black-box and the white-box setting). For certain restricted models, such as Read Once Branching Programs, we already obtain a deterministic algorithm using existing PIT results.
We give a polynomial time algorithm to decode multivariate polynomial codes of degree $d$ up to half their minimum distance, when the evaluation points are an arbitrary product set $S^m$, for every $d < |S|$. Previously known algorithms can achieve this only if the set $S$ has some very special algebraic structure, or if the degree $d$ is significantly smaller than $|S|$. We also give a near-linear time randomized algorithm, which is based on tools from list-decoding, to decode these codes from nearly half their minimum distance, provided $d < (1-epsilon)|S|$ for constant $epsilon > 0$. Our result gives an $m$-dimensional generalization of the well known decoding algorithms for Reed-Solomon codes, and can be viewed as giving an algorithmic version of the Schwartz-Zippel lemma.
We establish new upper and lower bounds on the number of queries required to test convexity of functions over various discrete domains. 1. We provide a simplified version of the non-adaptive convexity tester on the line. We re-prove the upper bound $O(frac{log(epsilon n)}{epsilon})$ in the usual uniform model, and prove an $O(frac{log n}{epsilon})$ upper bound in the distribution-free setting. 2. We show a tight lower bound of $Omega(frac{log(epsilon n)}{epsilon})$ queries for testing convexity of functions $f: [n] rightarrow mathbb{R}$ on the line. This lower bound applies to both adaptive and non-adaptive algorithms, and matches the upper bound from item 1, showing that adaptivity does not help in this setting. 3. Moving to higher dimensions, we consider the case of a stripe $[3] times [n]$. We construct an emph{adaptive} tester for convexity of functions $fcolon [3] times [n] to mathbb R$ with query complexity $O(log^2 n)$. We also show that any emph{non-adaptive} tester must use $Omega(sqrt{n})$ queries in this setting. Thus, adaptivity yields an exponential improvement for this problem. 4. For functions $fcolon [n]^d to mathbb R$ over domains of dimension $d geq 2$, we show a non-adaptive query lower bound $Omega((frac{n}{d})^{frac{d}{2}})$.
In this paper we study arithmetic computations in the nonassociative, and noncommutative free polynomial ring $mathbb{F}{x_1,x_2,ldots,x_n}$. Prior to this work, nonassociative arithmetic computation was considered by Hrubes, Wigderson, and Yehudayoff [HWY10], and they showed lower bounds and proved completeness results. We consider Polynomial Identity Testing (PIT) and polynomial factorization over $mathbb{F}{x_1,x_2,ldots,x_n}$ and show the following results. (1) Given an arithmetic circuit $C$ of size $s$ computing a polynomial $fin mathbb{F} {x_1,x_2,ldots,x_n}$ of degree $d$, we give a deterministic $poly(n,s,d)$ algorithm to decide if $f$ is identically zero polynomial or not. Our result is obtained by a suitable adaptation of the PIT algorithm of Raz-Shpilka [RS05] for noncommutative ABPs. (2) Given an arithmetic circuit $C$ of size $s$ computing a polynomial $fin mathbb{F} {x_1,x_2,ldots,x_n}$ of degree $d$, we give an efficient deterministic algorithm to compute circuits for the irreducible factors of $f$ in time $poly(n,s,d)$ when $mathbb{F}=mathbb{Q}$. Over finite fields of characteristic $p$, our algorithm runs in time $poly(n,s,d,p)$.
This paper deals with the partition function of the Ising model from statistical mechanics, which is used to study phase transitions in physical systems. A special case of interest is that of the Ising model with constant energies and external field. One may consider such an Ising system as a simple graph together with vertex and edge weights. When these weights are considered indeterminates, the partition function for the constant case is a trivariate polynomial Z(G;x,y,z). This polynomial was studied with respect to its approximability by L. A. Goldberg, M. Jerrum and M. Paterson in 2003. Z(G;x,y,z) generalizes a bivariate polynomial Z(G;t,y), which was studied by D. Andr{e}n and K. Markstr{o}m in 2009. We consider the complexity of Z(G;t,y) and Z(G;x,y,z) in comparison to that of the Tutte polynomial, which is well-known to be closely related to the Potts model in the absence of an external field. We show that Z(G;x,y,z) is #P-hard to evaluate at all points in $mathbb{Q}^3$, except those in an exception set of low dimension, even when restricted to simple graphs which are bipartite and planar. A counting version of the Exponential Time Hypothesis, #ETH, was introduced by H. Dell, T. Husfeldt and M. Wahl{e}n in 2010 in order to study the complexity of the Tutte polynomial. In analogy to their results, we give a dichotomy theorem stating that evaluations of Z(G;t,y) either take exponential time in the number of vertices of $G$ to compute, or can be done in polynomial time. Finally, we give an algorithm for computing Z(G;x,y,z) in polynomial time on graphs of bounded clique-width, which is not known in the case of the Tutte polynomial.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
