We study which functions can be computed by efficient circuits whose gate connections are very easy to compute. We give quasilinear-size circuits for sorting whose connections can be computed by decision trees with depth logarithmic in the length of the gate description. We also show that NL has NC$^2$ circuits ... more >>>

We reduce non-deterministic time $T \ge 2^n$ to a 3SAT
instance $\phi$ of size $|\phi| = T \cdot \log^{O(1)} T$
such that there is an explicit circuit $C$ that on input
an index $i$ of $\log |\phi|$ bits outputs the $i$th
clause, and each output bit of $C$ depends on ... more >>>

Common presentations of the NP-completeness of SAT suffer
from two drawbacks which hinder the scope of this
flagship result. First, they do not apply to machines
equipped with random-access memory, also known as
direct-access memory, even though this feature is
critical in basic algorithms. Second, they incur a
quadratic blow-up ... more >>>