A generalized polymorphism of a predicate $P \subseteq \{0,1\}^m$ is a tuple of functions $f_1,\dots,f_m\colon \{0,1\}^n \to \{0,1\}$ satisfying the following property: If $x^{(1)},\dots,x^{(m)} \in \{0,1\}^n$ are such that $(x^{(1)}_i,\dots,x^{(m)}_i) \in P$ for all $i$, then also $(f_1(x^{(1)}),\dots,f_m(x^{(m)})) \in P$.

We show that if $f_1,\dots,f_m$ satisfy this property for most ... more >>>

Lifting theorems are one of the most powerful tools for proving communication complexity lower bounds, with numerous downstream applications in proof complexity, monotone circuit lower bounds, data structures, and combinatorial optimization. However, to the best of our knowledge, prior lifting theorems have primarily focused on the two-party communication.

In this ... more >>>

We study several problems in the intersection of cryptography and complexity theory based on the following high-level thesis.

1) Obfuscation can serve as a general-purpose *worst-case to average-case reduction*, reducing the existence of various forms of cryptography to corresponding worst-case assumptions.
2) We can therefore hope to overcome ... more >>>