We prove a new equivalence between the non-uniform and uniform complexity of exponential time. We show that EXP in NP/log if and only if EXP = P^NP|| (polynomial time with non-adaptive queries to SAT). Our equivalence makes use of a recent result due to Shaltiel and Umans showing EXP in ... more >>>

Assume that Alice and Bob, given an authentic channel, have a protocol where they end up with a bit S_A and S_B, respectively, such that with probability (1+eps)/2 these bits are equal. Further assume that conditioned on the event S_A = S_B no polynomial time bounded algorithm can predict the ... more >>>

more >>>