3 papers
cs.CC2026
Rational degree is polynomially related to degree
Robin Kothari, Matt Kovacs-Deak, Daochen Wang +1
We prove that for every Boolean function , where is the degree of and is the ra…
quant-ph2025
Translation-Invariant Quantum Algorithms for Ordered Search are Optimal
Joseph Carolan, Andrew M. Childs, Matt Kovacs-Deak +1
Ordered search is the task of finding an item in an ordered list using comparison queries. The best exact classical algorithm for this fundamental problem uses $\lceil \log_{2}{n}\…
cs.CC2025
On the Rational Degree of Boolean Functions and Applications
Vishnu Iyer, Siddhartha Jain, Robin Kothari +5
We study a natural complexity measure of Boolean functions known as the rational degree. Denoted , it is the minimal degree of a rational function that is equal t…