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