3 citations · 3 across the 4 of their papers we have counts for
4 papers
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…
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}\…
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…
Quantum divide and conquer
Andrew M. Childs, Robin Kothari, Matt Kovacs-Deak +2
The divide-and-conquer framework, used extensively in classical algorithm design, recursively breaks a problem of size into smaller subproblems (say, copies of size e…