Vanishing sums of roots of unity can be seen as a natural generalization of knapsack from Boolean variables to variables taking values over the roots of unity. We show that these sums are hard to prove for polynomial calculus and for sum-of-squares, both in terms of degree and size.

more >>>

We study the query complexity of one-sided $\epsilon$-testing the class of Boolean functions $f:F^n\to \{0,1\}$ that describe affine subspaces and Boolean functions that describe axis-parallel affine subspaces, where $F$ is any finite field. We give a polynomial-time $\epsilon$-testers that ask $\tilde O(1/\epsilon)$ queries. This improves the query complexity $\tilde O(|F|/\epsilon)$ ... more >>>

A Chor--Goldreich (CG) source [CG88] is a sequence of random variables $X = X_1 \circ \ldots \circ X_t$, each $X_i \sim \{0,1 \{^d$, such that each $X_i$ has $\delta d$ min-entropy for some constant $\delta > 0$, even conditioned on any fixing of $X_1 \circ \ldots \circ X_{i-1}$. We typically ... more >>>