Datensatz

Zusammenfassung

We establish a lower bound on the efficiency of area--universal circuits. The area $A_u$ of every graph $H$ that can host any graph $G$ of area (at most) $A$ with dilation $d$, and congestion $c \leq \sqrt{A}/\log\log A$ satisfies the tradeoff $$ A_u = \Omega ( A \log A / (c^2 \log (2d)) ). $$ In particular, if $A_u = O(A)$ then $\max(c,d) = \Omega(\sqrt{\log A} / \log\log A)$.