Post

@robinkothari.bsky.social

In "On the Rational Degree of Boolean Functions and Applications" with Vishnu Iyer, Siddhartha Jain (@sidjai.bsky.social), Matt Kovacs-Deak, Vinayak Kumar, Luke Schaeffer, Daochen Wang, and Michael Whitmeyer, we prove many interesting results about rational degree. arxiv.org/pdf/2310.08004

25/4/25, 11:02 pm0 reposts11 likes

Robin Kothari

@robinkothari.bsky.social

25 Apr 2025

Rational degree is one of the rare measures that could be polynomially related to deterministic query complexity, quantum query complexity, sensitivity, and all our favorite measures (for total functions), but we just don't know! Bonus: we have an updated table of query separations!