153 citations · 237 across the 10 of their papers we have counts for
Showing 2001Show all
2 papers · 1 filter
quant-ph2001
Quantum Lower Bound for the Collision Problem
Scott Aaronson
The collision problem is to decide whether a function X:{1,..,n}->{1,..,n} is one-to-one or two-to-one, given that one of these is the case. We show a lower bound of Theta(n^{1/5})…
cs.CC2001
Algorithms for Boolean Function Query Properties
Scott Aaronson
We present new algorithms to compute fundamental properties of a Boolean function given in truth-table form. Specifically, we give an O(N^2.322 log N) algorithm for block sensitivi…