Fractional certificates for bounded functions

on YouTube ↗22m

" summary

Defines epsilon-fractional certificate complexity and proves that any bounded function f with polynomial degree D satisfies Fc_eps(f) = O(D^8 log^16 n / eps^4) (so for D ≥ log n this is polynomial in D and 1/eps). Proof uses linear-program duality and shows fractional block sensitivity = fractional certificate complexity. Gives the separating example sum(xi)/n (degree 1) with huge classical epsilon-certificates but small fractional certificates, linking these notions toward the Aaronson–Ambainis degree→query conjecture.

AI-written summary · about

" chapters (7)

1. 0:00Intro
2. 0:45Complexity measures of Boolean-valued functions
3. 4:22Complexity of bounded functions
4. 7:32Decision tree complexity v.s. polynomial degree
5. 12:32Certificate complexity v.s. fractional certification complexity
6. 13:59Fractional certificate complexity v.s. degree
7. 20:13Some facts of fractional block sensitivity