A three-decade-old open problem of mine just got solved! Matt Kovacs-Deak, Daochen Wang and Rain Zimin Yang showed that if a Boolean function f is exactly computed by a low-degree rational function, the quotient of two polynomials, then f has low decision-tree complexity.
1/2
29 days ago