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 >>>

We obtain new explicit pseudorandom generators for several computational models involving groups. Our main results are as follows:

1. We consider read-once group-products over a finite group $G$, i.e., tests of the form $\prod_{i=1}^n g_{i}^{x_{i}}$ where $g_{i}\in G$, a special case of read-once permutation branching programs. We give generators with ... more >>>