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 >>>

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 >>>

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 >>>

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 >>>