skip to main content

Search for: All records

Creators/Authors contains: "Sauermann, Lisa"

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 non-federal websites. Their policies may differ from this site.

  1. Abstract

    Let us fix a primepand a homogeneous system ofmlinear equations$$a_{j,1}x_1+\dots +a_{j,k}x_k=0$$aj,1x1++aj,kxk=0for$$j=1,\dots ,m$$j=1,,mwith coefficients$$a_{j,i}\in \mathbb {F}_p$$aj,iFp. Suppose that$$k\ge 3m$$k3m, that$$a_{j,1}+\dots +a_{j,k}=0$$aj,1++aj,k=0for$$j=1,\dots ,m$$j=1,,mand that every$$m\times m$$m×mminor of the$$m\times k$$m×kmatrix$$(a_{j,i})_{j,i}$$(aj,i)j,iis non-singular. Then we prove that for any (large)n, any subset$$A\subseteq \mathbb {F}_p^n$$AFpnof size$$|A|> C\cdot \Gamma ^n$$|A|>C·Γncontains a solution$$(x_1,\dots ,x_k)\in A^k$$(x1,,xk)Akto the given system of equations such that the vectors$$x_1,\dots ,x_k\in A$$x1,,xkAare all distinct. Here,Cand$$\Gamma $$Γare constants only depending onp,mandksuch that$$\Gamma Γ<p. The crucial point here is the condition for the vectors$$x_1,\dots ,x_k$$x1,,xkin the solution$$(x_1,\dots ,x_k)\in A^k$$(x1,,xk)Akto be distinct. If we relax this condition and only demand that$$x_1,\dots ,x_k$$x1,,xkare 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 non-diagonal tensor in combination with combinatorial and probabilistic arguments.

    more » « less
  2. List-decodability of Reed-Solomon codes has received a lot of attention, but the best-possible dependence between the parameters is still not well-understood. In this work, we focus on the case where the list-decoding radius is of the form r=1−ε for ε tending to zero. Our main result states that there exist Reed-Solomon codes with rate Ω(ε) which are (1−ε,O(1/ε)) -list-decodable, meaning that any Hamming ball of radius 1−ε contains at most O(1/ε) codewords. This trade-off between rate and list-decoding radius is best-possible for any code with list size less than exponential in the block length. By achieving this trade-off between rate and list-decoding 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, almost-linear suffices). We deduce our main result from a more general theorem, in which we prove good list-decodability properties of random puncturings of any given code with very large distance. 
    more » « less
  3. Abstract We prove several different anti-concentration inequalities for functions of independent Bernoulli-distributed random variables. First, motivated by a conjecture of Alon, Hefetz, Krivelevich and Tyomkyn, we prove some “Poisson-type” anti-concentration theorems that give bounds of the form 1/ e + o (1) for the point probabilities of certain polynomials. Second, we prove an anti-concentration 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 anti-concentration bounds for subgraph counts in random graphs. 
    more » « less
  4. null (Ed.)