6 citations · 6 across the 2 of their papers we have counts for
3 papers
Computability Theory of Closed Timelike Curves
Scott Aaronson, Mohammad Bavarian, Toby Cubitt +4
We study the question of what is computable by Turing machines equipped with time travel into the past; i.e., with Deutschian closed timelike curves (CTCs) having no bound on their…
Tighter Relations Between Sensitivity and Other Complexity Measures
Andris Ambainis, Mohammad Bavarian, Yihan Gao +3
Sensitivity conjecture is a longstanding and fundamental open problem in the area of complexity measures of Boolean functions and decision tree complexity. The conjecture postulate…
Weak Parity
Scott Aaronson, Andris Ambainis, Kaspars Balodis +1
We study the query complexity of Weak Parity: the problem of computing the parity of an n-bit input string, where one only has to succeed on a 1/2+eps fraction of input strings, bu…