Recognition: unknown
A note on the sign degree of formulas
read the original abstract
Recent breakthroughs in quantum query complexity have shown that any formula of size n can be evaluated with O(sqrt(n)log(n)/log log(n)) many quantum queries in the bounded-error setting [FGG08, ACRSZ07, RS08b, Rei09]. In particular, this gives an upper bound on the approximate polynomial degree of formulas of the same magnitude, as approximate polynomial degree is a lower bound on quantum query complexity [BBCMW01]. These results essentially answer in the affirmative a conjecture of O'Donnell and Servedio [O'DS03] that the sign degree--the minimal degree of a polynomial that agrees in sign with a function on the Boolean cube--of every formula of size n is O(sqrt(n)). In this note, we show that sign degree is super-multiplicative under function composition. Combining this result with the above mentioned upper bounds on the quantum query complexity of formulas allows the removal of logarithmic factors to show that the sign degree of every size n formula is at most sqrt(n).
This paper has not been read by Pith yet.
Forward citations
Cited by 2 Pith papers
-
Tight Bounds for Learning Polyhedra with a Margin
A new PAC learning algorithm for k-halfspace intersections with ρ-margin achieves runtime poly(k, ε^{-1}, ρ^{-1}) exp(O(√(n log(1/ρ) log k))), improving prior work and matching lower bounds up to logs.
-
Quantum Property Testing for Bounded-Degree Directed Graphs
Properties constant-query testable classically in the bidirectional bounded-degree directed graph model admit n^{1/2 - Ω(1)} quantum query testers in the unidirectional model, with an almost-matching lower bound.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.