We study problems in randomized communication complexity when the protocol is only required to attain some small advantage over purely random guessing, i.e., it produces the correct output with probability at least $\epsilon$ greater than one over the codomain size of the function. Previously, Braverman and Moitra (STOC 2013) showed ... more >>>

We present two results in structural complexity theory concerned with the following interrelated
topics: computation with postselection/restarting, closed timelike curves (CTCs), and
approximate counting. The first result is a new characterization of the lesser known complexity
class BPP_path in terms of more familiar concepts. Precisely, BPP_path is the class of ... more >>>

We ask, and answer, the question of what's computable by Turing machines equipped with time travel into the past: that is, closed timelike curves or CTCs (with no bound on their size). We focus on a model for CTCs due to Deutsch, which imposes a probabilistic consistency condition to avoid ... more >>>