Q The Query Complexity Zoo
PabbarajuQuartic

Pabbaraju’s quartic approximate-degree function

$\mathrm{C}\ge\Omega(\widetilde{\deg}^{\,4}/\log^6 n)$; settles the exponent at four.

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

MeasureValueNotes
\(\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.

Cited as a witness by

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.