Robin KothariMatt Kovacs-DeakDaochen WangRain Zimin Yang
所有作者
Robin KothariMatt Kovacs-DeakDaochen WangRain Zimin Yang
文献摘要
We prove that deg(f)≤O(rdeg(f)3) for every Boolean function f, where deg(f) is the degree of f and rdeg(f) is the rational degree of f. This resolves the second of the three open problems stated by Nisan and Szegedy, and attributed to Fortnow, in 1994.