Research memo

Witness-Seeded Preconditioning for the ANPS Bound

Translating the Alman--Nadimpalli--Patel--Servedio exact DNF learner into posterior-cut language suggests a concrete preconditioning step: certify and peel isolated positive witnesses before invoking the augmented-PTF learner. This changes the square-root parameter from \(k\) to the residual term count \(s=k-q\).

1. The ANPS Algorithm in Cut Language

The ANPS learner has running time \(\mathrm{poly}(n)\,2^{\widetilde O(\sqrt{k})}\). In the language of posterior cuts, it is not merely searching for good Boolean-cube split points. It builds an induced feature geometry in which equivalence counterexamples become useful online mistakes.

Positive cuts: stems

A positive counterexample \(y\) is used to find a candidate stem \(T'\). ANPS repeatedly performs a random positive walk and applies the local one-bit procedure

\[ \mathrm{GenTerm}(f,y)= \bigwedge_{i:f(y\oplus e_i)=0}\lambda_i^y. \]

This is exactly the positive-witness kill-set operation from the posterior-collapse papers.

Negative cuts: growing \(R_{T'}\)

A false positive from Winnow exposes that a current stem is missing variables. The noised line-search procedure adds a morally relevant variable to \(R_{T'}\), while preventing long terms from polluting \(R_{T'}\).

\[ |R_{T'}|\le R_{\max}=O(k^2\log k). \]

Once the feature set is fully expressive, each term \(T_i\) has a stem \(T'_i\) and all missing literals lie in \(R_{T'_i}\). Chebyshev polynomials then express the DNF as an augmented PTF of degree and weight

\[ d_{\max}=O(\sqrt{k\log k}),\qquad W_{\max}=2^{O(\sqrt{k}\log^2 k)}. \]

Winnow2 over augmented monomials supplies the equivalence-query sequence. Thus the \(\sqrt{k}\) term is driven by two linked facts: a Chebyshev PTF for \(k\) residual terms, and stem-finding whose worst-case success is \(2^{-\widetilde O(\sqrt{k})}\).

2. Certified Peeling Before ANPS

If a positive witness is isolated for a term, the one-bit star recovers that term deterministically:

\[ x^+\text{ isolated for }T \quad\Longrightarrow\quad T=\bigwedge_{i:f(x^+\oplus e_i)=0}\lambda_i^{x^+}. \]

After peeling \(q\) certified terms, the remaining target is an \(s\)-term DNF with \(s=k-q\). The ANPS machinery can then be run with \(s\), not \(k\), in every parameter that depends on the number of terms:

\[ Q(f) \le q(n+1)+\mathrm{poly}(n)\,2^{\widetilde O(\sqrt{k-q})}. \]

This is a data-dependent improvement, not a new arbitrary worst-case theorem. Its value is that it identifies a certified transcript prefix that genuinely lowers the parameter driving the ANPS bound.

In ANPS terms, a peeled term does not merely contribute a candidate stem. It is removed from the residual DNF, lowering the Chebyshev degree, Winnow weight bound, stem-search parameter, and auxiliary-variable budget.

3. Numerical Probe: Sequential Local Peeling

Random fixed-width syntactic DNFs were sampled. For each instance, an exhaustive finite-cube routine repeatedly removed any term with a locally isolated private witness, then measured the residual overlap. This is not presented as an efficient learner; it measures how much certified peeling could reduce the ANPS parameter if the witnesses are found.

\(n,k,w\)	Mean peeled \(q\)	Median \(q\)	Mean residual \(s\)	Median \(s\)	\(\sqrt{k}-E\sqrt{s}\)	Feature-log gain	Rescue rate
10,16,4	15.57	16.0	0.42	0.0	2.903	62.7	0.041
10,32,4	26.22	30.0	5.78	2.0	3.655	104.9	0.214
12,32,4	31.27	32.0	0.73	0.0	4.489	125.0	0.067
12,48,4	32.86	45.0	15.14	3.0	3.859	126.2	0.315
12,64,4	2.31	0.0	61.69	64.0	0.213	7.1	0.755
14,64,5	63.68	64.0	0.32	0.0	6.930	229.0	0.027

120 trials per row. The feature-log gain is a proxy: \(\log_2 {k^2\log k \choose \le d(k)}-\mathbb E[\log_2 {s^2\log s \choose \le d(s)}]\), with \(d(u)=\sqrt{u\log_2 u}\). It measures the drop in the ANPS augmented feature combinatorics, not the full theorem constant.

10,16,4

15.6

10,32,4

26.2

12,32,4

31.3

12,48,4

32.9

12,64,4

2.3

14,64,5

63.7

Bars show mean peeled terms \(q\) as a fraction of \(k\).

4. The Density Cliff

A phase curve at \(n=12,w=4\) shows the transition between the peelable regime and the overlap-heavy regime.

\(k\)	Mean peeled	Median residual	Full peel rate	Stuck-at-start rate	Residual rescue rate
16	15.85	0.0	92.5%	0.0%	0.019
24	23.64	0.0	83.8%	0.0%	0.043
32	30.99	0.0	72.5%	0.0%	0.078
40	39.01	0.0	68.8%	0.0%	0.087
48	32.59	2.0	37.5%	2.5%	0.297
56	7.50	55.0	3.8%	35.0%	0.666
64	1.00	64.0	0.0%	62.5%	0.758

80 trials per row. When peeling collapses, residual boundary rescue rises sharply. This matches the peel-or-overlap dichotomy: the obstruction to peeling is not structureless hardness, but rescued one-bit boundaries.

5. Mechanism-Level Takeaway

The ANPS algorithm reaches \(2^{\widetilde O(\sqrt{k})}\) by making the target compact in an adaptive feature space. The posterior-cut language explains how its counterexamples are used:

\[ \text{positive counterexample} \to \text{candidate stem},\qquad \text{negative counterexample} \to \text{grow }R_{T'},\qquad \text{Winnow mistake} \to \text{feature-space cut}. \]

The proposed preconditioning step adds a prior transcript phase:

\[ \text{positive witness star} \to \begin{cases} \text{certified peel, lowering }k\text{ to }s,\\ \text{or boundary-rescue certificate for overlap compression.} \end{cases} \]

The first branch gives a direct data-dependent improvement to the ANPS parameter. The second branch identifies the remaining route to a true worst-case improvement: prove that high rescue-rate residuals admit compact overlap modules or central surrogates.

In short: peeling lowers the residual parameter immediately; overlap rescue identifies the next source of compression.

Reproducibility

The experiments in this memo were generated by anps_witness_preconditioning_experiments.py. The ANPS source was read from arXiv:2507.20336, whose abstract states the \(\mathrm{poly}(n)2^{\widetilde O(\sqrt{k})}\) exact learner using Winnow2 over an adaptively constructed enhanced feature space.