Swastik Kopparty

  1. Kakeya-type sets in finite vector spaces.

    Authors: Vsevolod F. Lev, Swastik Kopparty, Shubhangi Saraf, Madhu Sudan
    Subjects: Number Theory
    Abstract

    For a finite vector space $V$ and a non-negative integer $r\le\dim V$ we
    estimate the smallest possible size of a subset of $V$, containing a translate
    of every $r$-dimensional subspace. In particular, we show that if $K\subset V$
    is the smallest subset with this property, $n$ denotes the dimension of $V$,
    and $q$ is the size of the underlying field, then for $r$ bounded and $r<n\le
    rq^{r-1}$ we have $|V\setminus K|=\Theta(nq^{n-r+1})$. This improves previously
    known bounds $|V\setminus K|=\Omega(q^{n-r+1})$ and $|V\setminus
    K|=O(n^2q^{n-r+1})$.

  2. On the List-Decodability of Random Linear Codes.

    Authors: Venkatesan Guruswami, Johan Hastad, Swastik Kopparty
    Subjects: Information Theory
    Abstract

    For every fixed finite field $\F_q$, $p \in (0,1-1/q)$ and $\epsilon > 0$, we
    prove that with high probability a random subspace $C$ of $\F_q^n$ of dimension
    $(1-H_q(p)-\epsilon)n$ has the property that every Hamming ball of radius $pn$
    has at most $O(1/\epsilon)$ codewords.

RSS-материал