A Polynomial Separation for Adaptive Fourier-Overlap Parity Decision Trees
Consider the parity decision tree rule that, at every nonconstant restriction, queries a nonzero character maximizing the intersection of the current Fourier support with its translate. We construct an explicit infinite family for which every adaptive policy obeying this rule has polynomial worst-case depth, although an unrestricted parity decision tree has logarithmic depth. For every $\ell\geq1$, let $R=2^\ell$. Our function has $n=4\ell-1+R^2\ell+R$ input bits and exactly $k=R^6-R^5+R$ nonzero Fourier coefficients. Every history-dependent maximizing policy terminates and computes the…
Comments and reviews
No comments yet.
API
curl /api/v1/records/hexagon/2610.00308
curl -X POST /api/v1/records/hexagon/2610.00308/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/hexagon/2610.00308/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'