Christoph Behle, Andreas Krebs, Stephanie Reifferscheid

We consider the regular languages recognized by weighted threshold circuits with a linear number of wires.

We present a simple proof to show that parity cannot be computed by such circuits.

Our proofs are based on an explicit construction to restrict the input of the circuit such that the value ...
more >>>

Christoph Behle, Andreas Krebs, Klaus-Joern Lange, Pierre McKenzie

In the setting known as DLOGTIME-uniformity,

the fundamental complexity classes

$AC^0\subset ACC^0\subseteq TC^0\subseteq NC^1$ have several

robust characterizations.

In this paper we refine uniformity further and examine the impact

of these refinements on $NC^1$ and its subclasses.

When applied to the logarithmic circuit depth characterization of $NC^1$,

some refinements leave ...
more >>>

Vinayak Kumar

We initiate the study of generalized $AC^0$ circuits comprised of arbitrary unbounded fan-in gates which only need to be constant over inputs of Hamming weight $\ge k$ (up to negations of the input bits), which we denote $GC^0(k)$. The gate set of this class includes biased LTFs like the $k$-$OR$ ... more >>>

Sabee Grewal, Vinayak Kumar

Kumar (CCC, 2023) used a novel switching lemma to prove exponential-size lower bounds for a circuit class $GC^0$ that not only contains $AC^0$ but can---with a single gate---compute functions that require exponential-size $TC^0$ circuits. Their main result was that switching-lemma lower bounds for $AC^0$ lift to $GC^0$ with no loss ... more >>>