Paper 2026/1896

A size/fan-in trade-off for circuits

Abstract

We consider (boolean or arithmetic) circuits in which every gate may compute an arbitrary function of its input gates. We show a novel tradeoff between a circuit's size and its fan-in: \begin{quote} Any function which may be computed using $s$ fan-in $2$ gates can alternatively be computed using $s/3\ (1+O(1/\sqrt{k}))$ fan-in $k$ gates. \end{quote} This asymptotically improves the previous bound of $2s/5\ (1+O(1/k))$ by Charbit, Couteau, Meyer, and Naserasr [TCC'24]. Among other applications, this improves the communication complexity of secure multiparty computation in the correlated randomness model. \emph{Any} $n$-input $m$-output circuit with $s$ internal gates (over arbitrary binary gates) can be securely computed in the correlated randomness model with per party communication $s/3 + n + m$ and computation $\widetilde{O}(s)$. Our paper stands at the intersection of cryptography, complexity theory, and graph theory, but our main technical contribution is one to extremal combinatorics: we establish that every order-$n$ $2$-degenerate graph admits a planarising set of size at most $\lfloor n/3 \rfloor$. Our main conceptual contribution is to relate the existence of sublinear-size (directed) $k$-path transversals to well-studied graph parameters. Along the way, we uncover a recurringly overstated lemma throughout the literature on sublinear-size vertex-separators and hyperfinite graphs. According to this lemma, any monotone graph class admitting sublinear-size balanced vertex separators should be weakly hyperfinite. However, this is contradicted by a graph class put forward by [Moshkovitz and Shapira, Random Structures \& Algorithms'15]. Unfortunately, the lemma appears in highly influencial works such as [Henzinger, Klein, Rao, and Subramanian, STOC'94 \& JCSS'97], or the textbook of Nešetřil and Ossona de Mendez [\emph{Sparsity}, Springer'12], and in turn it is used in a significant number of papers. Thankfully a slightly weaker version of this lemma is true, with a caveat on how sublinear the vertex separators needs to be, and we provide the correction as a service to the community.