Pabbaraju’s quartic approximate-degree function
$\mathrm{C}\ge\Omega(\widetilde{\deg}^{\,4}/\log^6 n)$; settles the exponent at four.
total arity: $O(n^3\log n)$ bits
Description
The function $G(x,p,K)$ of Section 5. Its input comprises the $n^2$ DNF bits from Pabbaraju’s optimal unambiguous DNF, a cell pointer attached to each bit, and $n^2$ cells of $O(n\log n)$-bit certificate descriptions. A cell validates the selected DNF term via $O(n)$ local checks of depth $O(\log n)$ and requires the pointer of its first positive literal to designate that cell. At most one cell can be valid. Accept iff a valid cell exists.
Formal definition
Fix Pabbaraju’s optimal unambiguous DNF and its bijections. An input is $(x,p,K)$: DNF bits $x$, pointers $p_u\in[n^2]$ (invalid encodings fail any check using them), and cells $K_z$, $z\in[n^2]$, in the fixed-size encoding of [Pabbaraju26, Section 5]. Each cell contains a block index $i$, sorted lists $a_1,\ldots,a_k$ and $b_1,\ldots,b_{n-k}$, witnesses $t_j$, and a padded list $\Gamma$ of cross-block positions. The verifier $V(x,K_z)$ checks: the two sorted lists partition $B_i$, with $x_{a_h}=1$ and $x_{b_h}=0$; for $j\ne i$, $t_j\in B_i$ and $x_{t_j}=1$; writing $\ell_j=\pi_i^{ij}(t_j)$, $\Gamma$ lists exactly the pairs $(j,1),\ldots,(j,\ell_j)$ for $j\ne i$ in increasing order, followed by at least one padding entry; and $x_{(\pi_j^{ij})^{-1}(h)}=0$ for every listed $(j,h)$. The list has fixed length one greater than the uniform maximum term width; malformed checks reject. $$G(x,p,K)=\bigvee_{z\in[n^2]}\big(V(x,K_z)\wedge[p_{a_1}=z]\big).$$
Measure values
| Measure | Value | Notes |
|---|---|---|
| \(\mathrm{C}(f)\) Certificate complexity | \(\Omega(n^2)\) | Theorem 4; equation (42). Pabbaraju26 |
| \(\mathrm{C}^0(f)\) 0-certificate complexity | \(\Omega(n^2)\) | All-zero input, equation (42). Pabbaraju26 |
| \(\widetilde{\deg}_{\varepsilon}(f)\) Approximate degree | \(O(\sqrt n\log^{3/2}n)\) | Section 5, equation (43); approximate each cell to error 1/(3n²) and sum its polynomial. Pabbaraju26 |
Separations its values prove — computed, not recorded
Read straight off the table above by comparing two values: no relation record states these, and where one does and says more, the record wins and the pair is not listed here. 1 in total.
-
\(\mathrm{C}^0(f_n) = \Omega\big(\widetilde{\deg}_{\varepsilon}(f_n)^{4}\big)\)from \(\mathrm{C}^0(f) = \Omega(n^2)\) against \(\widetilde{\deg}_{\varepsilon}(f) = O(\sqrt n\log^{3/2}n)\)
Cited as a witness by
-
\(\mathrm{C}(G_n)=\Omega(\widetilde{\deg}(G_n)^4/\log^6\widetilde{\deg}(G_n))\)
Notes
This source proves a low-degree approximation. It does not give a quantum algorithm of the same complexity; [AIK26] supplies the subsequent quantum result for a modified construction.