153 citations · 237 across the 10 of their papers we have counts for
Showing cs.CCShow all
3 papers · 1 filter
cs.CC2005
Oracles Are Subtle But Not Malicious
Scott Aaronson
Theoretical computer scientists have been debating the role of oracles since the 1970's. This paper illustrates both that oracles can give us nontrivial insights about the barrier…
cs.CC2004
The Complexity of Agreement
Scott Aaronson
A celebrated 1976 theorem of Aumann asserts that honest, rational Bayesian agents with common priors will never "agree to disagree": if their opinions about any topic are common kn…
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…