Approximate degree lower bounds for oracle identification problems

Mark Bun, Nadezhda Voronova

The approximate degree of a Boolean function is the minimum degree of real polynomial that approximates it pointwise. For any Boolean function, its approximate degree serves as a l…