225 citations · 582 across the 52 of their papers we have counts for
3 papers · 2 filters
Separations in Query Complexity Based on Pointer Functions
Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs +3
In 1986, Saks and Wigderson conjectured that the largest separation between deterministic and zero-error randomized query complexity for a total boolean function is given by the fu…
Separating decision tree complexity from subcube partition complexity
Robin Kothari, David Racicot-Desloges, Miklos Santha
The subcube partition model of computation is at least as powerful as decision trees but no separation between these models was known. We show that there exists a function whose de…
On solving systems of diagonal polynomial equations over finite fields
Gabor Ivanyos, Miklos Santha
We present an algorithm to solve a system of diagonal polynomial equations over finite fields when the number of variables is greater than some fixed polynomial of the number of eq…