Weight Duals: Dual Certificates for the Weight–Degree Tradeoff of Threshold Circuits

A polynomial threshold function (PTF) computes a Boolean function as the sign of a polynomial with integer coefficients. Two costs matter: the degree $d$, meaning how many input bits any one term touches, and the weight $W$, meaning the sum of the absolute values of the coefficients. The two trade against each other. Lowering the degree can force the weight to grow exponentially. In circuit language, a PTF of degree $d$ and weight $W$ built from conjunctions of literals is exactly a majority gate over $W$ AND gates (counted with multiplicity), each AND gate having fan-in at most $d$. The weight–degree tradeoff is therefore a tradeoff between the fan-in of the bottom gates and the total size of a depth-two threshold circuit. It is one of the few places where threshold circuits with large weights can be analyzed at all.

The main tool for lower bounds in this area is the dual polynomial: a signed measure on the hypercube that certifies no low-degree polynomial approximates the function. That tool certifies degree. It is blind to weight once $d$ exceeds the approximate degree, because above that point a low-degree approximation exists, even though it has enormous coefficients. We propose to build weight duals instead. These are distributions $\mu$ on the inputs under which $f$ has small correlation with every term of degree at most $d$, without requiring exact orthogonality. We will construct them explicitly, first by giving a dual proof of the weight-sensitive Markov inequality of Attribute-Efficient Learning and Weight-Degree Tradeoffs for Polynomial Threshold Functions, then by composing such witnesses through the block constructions used for depth-three AC⁰. AC⁰ here means constant-depth circuits of AND, OR and NOT gates with unbounded fan-in.

Core Claim

For a Boolean function $f$ and a set of terms $\mathcal{T}_d$, which consists of monomials or conjunctions of at most $d$ literals, the minimum weight of a sign-representation with margin 1 is given by a linear program. Integer PTFs automatically have margin 1, so this program lower-bounds integer weight. Its dual reads

$$ W_d(f) \;\ge\; \max_{\mu}\; \frac{1}{\max_{T \in \mathcal{T}_d} \left|\mathbb{E}_{x\sim\mu}[f(x)\,T(x)]\right|}, $$

where $\mu$ ranges over probability distributions on $\{-1,1\}^n$. A distribution achieving a large value is a weight dual.

This characterization itself is elementary; the file cites no source for it, and we claim no novelty for it. What we claim is new is two things. The first is explicit constructions of such $\mu$ that stay informative when $d$ exceeds the approximate degree of $f$, which is exactly where degree duals give nothing. The second is a composition theorem for weight duals that yields degree-parameterized size lower bounds for majority-of-AND circuits computing depth-three AC⁰ functions. The concrete targets are two. One is narrowing the open gap for decision lists at degree $d \ge \Omega(\sqrt n)$ noted in Polynomial Threshold Functions for Decision Lists. The other is a weight-versus-bottom-fan-in curve for depth-three AC⁰ that beats both existing routes in the middle range of $d$.

Why the Gap Is Real

Two existing results frame the problem. The first is Attribute-Efficient Learning and Weight-Degree Tradeoffs for Polynomial Threshold Functions. It proves a primal Markov-type inequality: a bounded univariate polynomial of degree $d$ and integer weight $W$ has derivative $O(d\log W)$ rather than $O(d^2)$. From this it derives $W \ge 2^{\Omega(\sqrt{k/d})}$ for ODD-MAX-BIT, a canonical decision list whose output is the parity of the position of the last 1 among its $k$ relevant bits. The authors state that the argument needs features closed under restriction and that no dual characterization was given. That paper supplies our target inequality. We aim to replace its proof technique rather than its statement.

The second is Hardness Amplification and the Approximate Degree of Constant-Depth Circuits. It shows that a depth-three circuit resists degree-$d$ approximation up to error $1-\exp(-\tilde\Omega(n d^{-3/2}))$. Because a conjunction of literals has Fourier $\ell_1$ norm 1, any majority-of-$\mathrm{AND}_d$ circuit of size $W$ gives a degree-$d$ approximation with error $1-1/W$. This yields $W_d \ge \exp(\tilde\Omega(nd^{-3/2}))$, a bound that falls below $\sqrt n$ in the exponent once $d > n^{1/3}$. Above that point the best bound available is the degree-independent threshold weight $\exp(\Omega(n^{1/2-\delta}))$ from Approximate Degree and the Complexity of Depth Three Circuits. Nothing currently captures how weight grows as the bottom fan-in shrinks in this middle range. The approximate-degree route cannot, because the error-$(1-1/W)$ translation throws away all weight information once $d$ exceeds the approximate degree.

Two further results supply methods. Dual lower bounds for approximate degree and Markov-Bernstein inequalities reproves classical Markov–Bernstein inequalities by explicit LP duals. We reuse that technique for the weighted inequality. Dual Polynomials for Collision and Element Distinctness contributes two tricks: a cancellation trick that sums two leaky duals, and averaging over extensions. We expect both to transfer, because weight duals only need correlations to be small, not zero, so leakage is tolerable in a quantified way.

The papers on the upper-bound side constrain the program. Polynomial Threshold Functions for Decision Lists gives weight $2^{O(n/d^2)}$, tight for $d = O(n^{1/3})$, so no weight dual can beat that curve for decision lists. A regularity lemma, and low-weight approximators, for low-degree polynomial threshold functions shows that approximate representations need only weight $O_{\epsilon,d}(n^d)$. Any super-polynomial bound we prove must therefore come from exact representation on a vanishing fraction of inputs, and our distributions $\mu$ must concentrate on those inputs.

Research Program

The first strand is a dual proof of the weighted Markov inequality. We will extend the LP-duality proof of Markov's inequality in Dual lower bounds for approximate degree and Markov-Bernstein inequalities to the version with integer weight $W$. The output is a univariate distribution on the points $\{0,\dots,k\}$ under which the derivative-probing test function has correlation at most $2^{-\Omega(\sqrt{k/d})}$ with every term of degree at most $d$. Lifting this distribution along the ODD-MAX-BIT structure should give an explicit weight dual that reproves the bound of Attribute-Efficient Learning and Weight-Degree Tradeoffs for Polynomial Threshold Functions. Since the lift never restricts variables, it should also apply to feature families that are not closed under restriction, such as decision trees of depth $d$, which have $\ell_1$ norm at most $2^d$.

The second strand is a composition theorem for weight duals. We will prove a statement of the following form. If $\mu_1$ is a weight dual for an outer function $g$ at degree $d_1$, and $\mu_2$ is a one-sided weight dual for an inner gadget at degree $d_2$, then the natural combined distribution is a weight dual for $g \circ h$ at degree roughly $d_1 d_2$, and its correlations multiply. This mirrors the hardness amplification theorem of Hardness Amplification and the Approximate Degree of Constant-Depth Circuits, but we track the largest correlation with any single term rather than an $\ell_1$ error. We will then apply it to ODD-MAX-BIT composed with OR, and to the block-dependent variant of Approximate Degree and the Complexity of Depth Three Circuits. The target is $W_d \ge \exp(\tilde\Omega(n/d))$ for some depth-three AC⁰ function across $n^{1/3} \le d \le \sqrt n$.

The third strand is a computational instrument, which guides the conjectures and does not prove anything. We will solve the dual LP exactly for small $n$ and extract optimal distributions $\mu$ to guess their structure, much as explicit duals in the Bun–Thaler papers were designed to match known bounds.

Baselines

The naive reference point is the degree-independent threshold weight: the smallest weight at unbounded degree, which lower-bounds $W_d$ for every $d$. For depth-three AC⁰ this is $\exp(\Omega(n^{1/2-\delta}))$, reported in Approximate Degree and the Complexity of Depth Three Circuits. A result counts as beating it only if, at some $d$, the exponent exceeds $n^{1/2}$ by a polynomial factor.

The strongest degree-sensitive competitor is the route through approximation error near 1 in Hardness Amplification and the Approximate Degree of Constant-Depth Circuits, which reports error $1-\exp(-\tilde\Omega(nd^{-3/2}))$ and hence the weight bound above. Beating it means a larger exponent at the same $d$ for an AC⁰ function of depth at most three.

For decision lists, the primal baseline is $W \ge 2^{\Omega(\sqrt{k/d})}$ from Attribute-Efficient Learning and Weight-Degree Tradeoffs for Polynomial Threshold Functions, and the ceiling is the upper bound $2^{O(n/d^2)}$ from Polynomial Threshold Functions for Decision Lists. At $d \ge \sqrt n$, any improvement over the primal lower bound, or any proof that it is tight, counts as a result.

The ablation that isolates our key ingredient replaces the weight dual with a standard degree dual: a measure exactly orthogonal to all terms of degree at most $d$, applied through the $1/\delta$ translation. We will run both on the same functions, at the same $n$ and $d$, with the same LP solver and tolerance. Our claim predicts that the degree-dual bound collapses to a constant once $d$ exceeds the approximate degree, while the weight-dual bound stays exponential.

For the computational experiments, no reported numerical LP values for small-$n$ weights were found on Lacuna. The baselines there are the asymptotic formulas evaluated with unit constants, which we will fit rather than treat as ground truth.

Why not just…?

Why not just use the error-near-1 approximate degree bound? It is provably blind in the regime we target. ODD-MAX-BIT and similar lists can be approximated to constant error at degree around $\sqrt n$, so their best achievable advantage over random guessing is constant there, and the $1/\delta$ translation yields a constant. Yet Attribute-Efficient Learning and Weight-Degree Tradeoffs for Polynomial Threshold Functions shows that the true weight at that degree is at least $2^{n^{1/4}}$. The ablation above measures this collapse directly.

Why not just push the primal Markov inequality further? This is a real threat for plain decision lists, where a sharper primal inequality might close the high-degree gap faster than our dual route. The primal argument's reliance on restriction closure and on a reduction to one variable is what blocks composition with gadgets like OR and with block dependencies. The composition theorem is exactly what a primal argument lacks. If the primal route wins on decision lists, we will still claim the depth-three curve, which the primal method cannot reach as stated.

Why not just take the degree-independent threshold weight, since it already holds at every $d$? It says nothing about how weight depends on bottom fan-in. Conversely, the Bun–Thaler curve exceeds it only for $d < n^{1/3}$. The middle range is uncovered by both, and that range is where our target sits.

Why not just compute optimal weights by brute force? Exact LPs are limited to about $n \le 22$, where asymptotic exponents are hard to separate. We use computation only to guess the structure of $\mu$, never as evidence for the asymptotic claims.

Proposed Experiments

We will solve the dual LP by column generation over terms, with symmetry reduction where the function permits it. The test functions are ODD-MAX-BIT, general decision lists, ODD-MAX-BIT composed with OR, the $M\times N$ AND–OR tree whose approximate degree $\Theta(\sqrt{MN})$ is settled in Dual lower bounds for approximate degree and Markov-Bernstein inequalities, and small instances of the block-dependent depth-three function. We take $n$ up to about 22 and $d$ from 1 to $n$, under both monomial and conjunction features. For $n \le 12$ we will also solve the integer program to measure the gap between LP weight and true integer weight.

The measured quantity is $\log W_d$ as a function of $d$. We will fit exponents against the competing forms $n/d^2$, $\sqrt{n/d}$, $n d^{-3/2}$ and $n/d$ on log–log plots. We will also record, for each optimal $\mu$, its support structure: the positions of the last 1 it favors and how its mass decays.

Three checks are decisive. First, ODD-MAX-BIT must show an exponential $W_d$ at $d$ well above its approximate degree while the degree-dual ablation gives $O(1)$. If both are small, the premise fails. Second, the extracted $\mu$ for ODD-MAX-BIT must match, up to lifting, the univariate distribution predicted by our dual Markov proof. A mismatch means the proof strategy is wrong, not merely loose. Third, for ODD-MAX-BIT composed with OR in the middle range of $d$, the fitted exponent must exceed both $\sqrt n$ and $nd^{-3/2}$ at the same $n$. If it does not, the composition target of $\exp(\tilde\Omega(n/d))$ is likely false, and we would retreat to decision lists alone.