Abstract A map $f:{0,1}^{n}\to {0,1}^{n}$ has locality t if every output bit of f depends only on t input bits. Arora, Steurer, and Wigderson (2009) ask if there exist bounded-degree expander graphs on $2^{n}$ nodes such that the neighbors of a node $x\in {0,1}^{n}$ can be computed by maps of ... more >>>

We show that if gap-3SAT has no sub-exponential time algorithms then a weak form of the sliding scale conjecture holds. Namely, for every $\alpha>0$ any algorithm for $n^\alpha$-approximating the value of label cover must run in time at least $n^{\Omega(\exp(1/\alpha))}$, where $n$ is the size of the instance.

Put differently, ... more >>>

Party $A_i$ of $k$ parties $A_1,\dots,A_k$ receives on
its forehead a $t$-tuple $(a_{i1},\dots,a_{it})$ of
elements from the group $G=\text{SL}(2,q)$. The parties
are promised that the interleaved product $a_{11}\dots
a_{k1}a_{12}\dots a_{k2}\dots a_{1t}\dots a_{kt}$ is
equal either to the identity $e$ or to some other fixed
element $g\in G$. Their goal is ... more >>>