The slice rank method gives exponential bounds for sets with no three-term arithmetic progression in finite vector spaces of odd characteristic and for three-sunflower-free families of subsets of a fixed ground set. We show that for $k\ge4$, every tensor that is nonzero exactly on the $k$-term arithmetic progression relation or ... more >>>

We give an elementary proof of the Komlos conjecture by simplifying the recent proof of Guo, Fang, and Lu. We show that any vectors $v_1,\ldots,v_n\in\mathbb{R}^d$ with $\|v_i\|_2\le1$ admit signs $\varepsilon_i\in\{-1,1\}$ such that $\|\sum_{i=1}^n\varepsilon_i v_i\|_\infty\le36$. The proof uses only elementary combinatorial and probabilistic arguments and basic calculus.

The prototypical construction of error correcting codes is based on linear codes over finite fields. In this work, we make first steps in the study of codes defined over integers. We focus on Maximum Distance Separable (MDS) codes, and show that MDS codes with linear rate and distance can be ... more >>>

We propose an algebraic approach to proving circuit lower bounds for ACC0 by defining and studying the notion of torus polynomials. We show how currently known polynomial-based approximation results for AC0 and ACC0 can be reformulated in this framework, implying that ACC0 can be approximated by low-degree torus polynomials. Furthermore, ... more >>>

A new probabilistic technique for establishing the existence of certain regular combinatorial structures has been introduced by Kuperberg, Lovett, and Peled (STOC 2012). Using this technique, it can be shown that under certain conditions, a randomly chosen structure has the required properties of a $t-(n,k,?)$ combinatorial design with tiny, yet ... more >>>

Assume that the edges of the complete bipartite graph $K_{n,n}$ are labeled with elements of $\mathbb{F}_2^d$, such that the sum over
any simple cycle is nonzero. What is the smallest possible value of $d$? This problem was raised by Gopalan et al. [SODA 2017] as it characterizes the alphabet size ... more >>>