Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher.
Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?
Some links on this page may take you to nonfederal websites. Their policies may differ from this site.

Abstract Let us fix a prime
p and a homogeneous system ofm linear equations for$$a_{j,1}x_1+\dots +a_{j,k}x_k=0$$ ${a}_{j,1}{x}_{1}+\cdots +{a}_{j,k}{x}_{k}=0$ with coefficients$$j=1,\dots ,m$$ $j=1,\cdots ,m$ . Suppose that$$a_{j,i}\in \mathbb {F}_p$$ ${a}_{j,i}\in {F}_{p}$ , that$$k\ge 3m$$ $k\ge 3m$ for$$a_{j,1}+\dots +a_{j,k}=0$$ ${a}_{j,1}+\cdots +{a}_{j,k}=0$ and that every$$j=1,\dots ,m$$ $j=1,\cdots ,m$ minor of the$$m\times m$$ $m\times m$ matrix$$m\times k$$ $m\times k$ is nonsingular. Then we prove that for any (large)$$(a_{j,i})_{j,i}$$ ${\left({a}_{j,i}\right)}_{j,i}$n , any subset of size$$A\subseteq \mathbb {F}_p^n$$ $A\subseteq {F}_{p}^{n}$ contains a solution$$A> C\cdot \Gamma ^n$$ $\leftA\right>C\xb7{\Gamma}^{n}$ to the given system of equations such that the vectors$$(x_1,\dots ,x_k)\in A^k$$ $({x}_{1},\cdots ,{x}_{k})\in {A}^{k}$ are all distinct. Here,$$x_1,\dots ,x_k\in A$$ ${x}_{1},\cdots ,{x}_{k}\in A$C and are constants only depending on$$\Gamma $$ $\Gamma $p ,m andk such that . The crucial point here is the condition for the vectors$$\Gamma $\Gamma <p$
in the solution$$x_1,\dots ,x_k$$ ${x}_{1},\cdots ,{x}_{k}$ to be distinct. If we relax this condition and only demand that$$(x_1,\dots ,x_k)\in A^k$$ $({x}_{1},\cdots ,{x}_{k})\in {A}^{k}$ are not all equal, then the statement would follow easily from Tao’s slice rank polynomial method. However, handling the distinctness condition is much harder, and requires a new approach. While all previous combinatorial applications of the slice rank polynomial method have relied on the slice rank of diagonal tensors, we use a slice rank argument for a nondiagonal tensor in combination with combinatorial and probabilistic arguments.$$x_1,\dots ,x_k$$ ${x}_{1},\cdots ,{x}_{k}$ 
Listdecodability of ReedSolomon codes has received a lot of attention, but the bestpossible dependence between the parameters is still not wellunderstood. In this work, we focus on the case where the listdecoding radius is of the form r=1−ε for ε tending to zero. Our main result states that there exist ReedSolomon codes with rate Ω(ε) which are (1−ε,O(1/ε)) listdecodable, meaning that any Hamming ball of radius 1−ε contains at most O(1/ε) codewords. This tradeoff between rate and listdecoding radius is bestpossible for any code with list size less than exponential in the block length. By achieving this tradeoff between rate and listdecoding radius we improve a recent result of Guo, Li, Shangguan, Tamo, and Wootters, and resolve the main motivating question of their work. Moreover, while their result requires the field to be exponentially large in the block length, we only need the field size to be polynomially large (and in fact, almostlinear suffices). We deduce our main result from a more general theorem, in which we prove good listdecodability properties of random puncturings of any given code with very large distance.more » « less

Abstract We prove several different anticoncentration inequalities for functions of independent Bernoullidistributed random variables. First, motivated by a conjecture of Alon, Hefetz, Krivelevich and Tyomkyn, we prove some “Poissontype” anticoncentration theorems that give bounds of the form 1/ e + o (1) for the point probabilities of certain polynomials. Second, we prove an anticoncentration inequality for polynomials with nonnegative coefficients which extends the classical Erdős–Littlewood–Offord theorem and improves a theorem of Meka, Nguyen and Vu for polynomials of this type. As an application, we prove some new anticoncentration bounds for subgraph counts in random graphs.more » « less