We consider indistinguishability obfuscation (iO) for multi-output circuits $C:\{0,1\}^n\to\{0,1\}^n$ of size s, where s is the number of AND/OR/NOT gates in C. Under the worst-case assumption that NP $\nsubseteq$ BPP, we establish that there is no efficient indistinguishability obfuscation scheme that outputs circuits of size $s + o(s/ \log s)$. ... more >>>

The Circuit Size Hierarchy CSH$^a_b$ states that if $a > b \geq 1$ then the set of functions on $n$ variables computed by Boolean circuits of size $n^a$ is strictly larger than the set of functions computed by circuits of size $n^b$. This result, which is a cornerstone of circuit ... more >>>

Classical data can be copied and re-used for computation, with adverse consequences economically and in terms of data privacy. Motivated by this, we formulate problems in one-way communication complexity where Alice holds some data and Bob holds $m$ inputs, and he wants to compute $m$ instances of a bipartite relation ... more >>>