We introduce and study swap cosystolic expansion, a new expansion property of simplicial complexes. We prove lower bounds for swap coboundary expansion of spherical buildings and use them to lower bound swap cosystolic expansion of the LSV Ramanujan complexes. Our motivation is the recent work (in a companion paper) showing ... more >>>

We provide compelling evidence for the potential of hardness-vs.-randomness approaches to make progress on the long-standing problem of derandomizing space-bounded computation.

Our first contribution is a derandomization of bounded-space machines from hardness assumptions for classes of uniform deterministic algorithms, for which strong (but non-matching) lower bounds can be unconditionally proved. ... more >>>

Suppose you are given a function $f\colon [n] \to [n]$ via (black-box) query access to the function. You are looking to find something local, like a collision (a pair $x \neq y$ s.t.\ $f(x)=f(y)$). The question is whether knowing the `shape' of the function helps you or not (by shape ... more >>>