Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userFactors of Sparse Polynomials are Sparse
202
0
0.0
(
0
)
Added by
Rafael Mendes de Oliveira
Publication date
2014
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
This paper was removed due to an error in the proof (Claim 4.12 as stated is not true). The authors would like to thank Ilya Volkovich for pointing out a counterexample to this papers main result in positive characteristic: If $F$ is a field with prime characteristic $p$, then the polynomial $x_1^p + x_2^p + ldots + x^n^p$ has the following factor: $(x_1+x_2+ ldots + x_n)^{p-1}$, which has sparsity $n^p$.
rate research
Read More
Random subspaces $X$ of $mathbb{R}^n$ of dimension proportional to $n$ are, with high probability, well-spread with respect to the $ell_p$-norm (for $p in [1,2]$). Namely, every nonzero $x in X$ is robustly non-sparse in the following sense: $x$ is $varepsilon |x|_p$-far in $ell_p$-distance from all $delta n$-sparse vectors, for positive constants $varepsilon, delta$ bounded away from $0$. This $ell_p$-spread property is the natural counterpart, for subspaces over the reals, of the minimum distance of linear codes over finite fields, and, for $p = 2$, corresponds to $X$ being a Euclidean section of the $ell_1$ unit ball. Explicit $ell_p$-spread subspaces of dimension $Omega(n)$, however, are not known except for $p=1$. The construction for $p=1$, as well as the best known constructions for $p in (1,2]$ (which achieve weaker spread properties), are analogs of low density parity check (LDPC) codes over the reals, i.e., they are kernels of sparse matrices. We study the spread properties of the kernels of sparse random matrices. Rather surprisingly, we prove that with high probability such subspaces contain vectors $x$ that are $o(1)cdot |x|_2$-close to $o(n)$-sparse with respect to the $ell_2$-norm, and in particular are not $ell_2$-spread. On the other hand, for $p < 2$ we prove that such subspaces are $ell_p$-spread with high probability. Moreover, we show that a random sparse matrix has the stronger restricted isometry property (RIP) with respect to the $ell_p$ norm, and this follows solely from the unique expansion of a random biregular graph, yielding a somewhat unexpected generalization of a similar result for the $ell_1$ norm [BGI+08]. Instantiating this with explicit expanders, we obtain the first explicit constructions of $ell_p$-spread subspaces and $ell_p$-RIP matrices for $1 leq p < p_0$, where $1 < p_0 < 2$ is an absolute constant.
In analogy with the regularity lemma of Szemeredi, regularity lemmas for polynomials shown by Green and Tao (Contrib. Discrete Math. 2009) and by Kaufman and Lovett (FOCS 2008) modify a given collection of polynomials calF = {P_1,...,P_m} to a new collection calF so that the polynomials in calF are pseudorandom. These lemmas have various applications, such as (special cases) of Reed-Muller testing and worst-case to average-case reductions for polynomials. However, the transformation from calF to calF is not algorithmic for either regularity lemma. We define new notions of regularity for polynomials, which are analogous to the above, but which allow for an efficient algorithm to compute the pseudorandom collection calF. In particular, when the field is of high characteristic, in polynomial time, we can refine calF into calF where every nonzero linear combination of polynomials in calF has desirably small Gowers norm. Using the algorithmic regularity lemmas, we show that if a polynomial P of degree d is within (normalized) Hamming distance 1-1/|F| -eps of some unknown polynomial of degree k over a prime field F (for k < d < |F|), then there is an efficient algorithm for finding a degree-k polynomial Q, which is within distance 1-1/|F| -eta of P, for some eta depending on eps. This can be thought of as decoding the Reed-Muller code of order k beyond the list decoding radius (finding one close codeword), when the received word P itself is a polynomial of degree d (with k < d < |F|). We also obtain an algorithmic version of the worst-case to average-case reductions by Kaufman and Lovett. They show that if a polynomial of degree d can be weakly approximated by a polynomial of lower degree, then it can be computed exactly using a collection of polynomials of degree at most d-1. We give an efficient (randomized) algorithm to find this collection.
Mahaneys Theorem states that, assuming $mathsf{P} eq mathsf{NP}$, no NP-hard set can have a polynomially bounded number of yes-instances at each input length. We give an exposition of a very simple unpublished proof of Manindra Agrawal whose ideas appear in Agrawal-Arvind (Geometric sets of low information content, Theoret. Comp. Sci., 1996). This proof is so simple that it can easily be taught to undergraduates or a general graduate CS audience - not just theorists! - in about 10 minutes, which the author has done successfully several times. We also include applications of Mahaneys Theorem to fundamental questions that bright undergraduates would ask which could be used to fill the remaining hour of a lecture, as well as an application (due to Ikenmeyer, Mulmuley, and Walter, arXiv:1507.02955) to the representation theory of the symmetric group and the Geometric Complexity Theory Program. To this author, the fact that sparsity results on NP-complete sets have an application to classical questions in representation theory says that they are not only a gem of classical theoretical computer science, but indeed a gem of mathematics.
We determine the rank of a random matrix over an arbitrary field with prescribed numbers of non-zero entries in each row and column. As an application we obtain a formula for the rate of low-density parity check codes. This formula vindicates a conjecture of Lelarge (2013). The proofs are based on coupling arguments and a novel random perturbation, applicable to any matrix, that diminishes the number of short linear relations.
A star $k$-coloring is a proper $k$-coloring where the union of two color classes induces a star forest. While every planar graph is 4-colorable, not every planar graph is star 4-colorable. One method to produce a star 4-coloring is to partition the vertex set into a 2-independent set and a forest; such a partition is called an I,F-partition. We use a combination of potential functions and discharging to prove that every graph with maximum average degree less than $frac{5}{2}$ has an I,F-partition, which is sharp and answers a question of Cranston and West [A guide to the discharging method, arXiv:1306.4434]. This result implies that planar graphs of girth at least 10 are star 4-colorable, improving upon previous results of Bu, Cranston, Montassier, Raspaud, and Wang [Star coloring of sparse graphs, J. Graph Theory 62 (2009), 201-219].
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
