Let X be a d-dimensional simplicial complex. A function F\colon X(k)\to \{0,1\}^k is said to be a direct product function if there exists a function f\colon X(1)\to \{0,1\} such that F(\sigma) = (f(\sigma_1), \ldots, f(\sigma_k)) for each k-face \sigma. In an effort to simplify components of the PCP theorem, Goldreich ... more >>>

We study the one-clean-qubit model of quantum communication where one qubit is in a pure state and all other qubits are maximally mixed. We demonstrate a partial function that has a quantum protocol of cost O(\log N) in this model, however, every interactive randomized protocol has cost \Omega(\sqrt{N}), settling a ... more >>>

If G is a group, we say a subset S of G is product-free if the equation xy=z has no solutions with x,y,z \in S. For D \in \mathbb{N}, a group G is said to be D-quasirandom if the minimal dimension of a nontrivial complex irreducible representation of G is ... more >>>