Incorporating Rich Social Interactions Into MDPs
Ravi Tejwani, Yen-Ling Kuo, et al.
ICRA 2022
We show that if Arthur-Merlin protocols can be derandomized, then there is a language computable in deterministic exponential-time with access to an NP oracle that requires circuits of exponential size. More formally, if every promise problem in prAM, the class of promise problems that have Arthur-Merlin protocols, can be computed by a deterministic polynomial-time algorithm with access to an NP oracle, then there is a language in ENP that requires circuits of size Ω(2n/n). The lower bound in the conclusion of our theorem suffices to construct pseudorandom generators with exponential stretch. We also show that the same conclusion holds if the following two related problems can be computed in polynomial time with access to an NP-oracle: (i) approximately counting the number of accepted inputs of a circuit, up to multiplicative factors; and (ii) recognizing an approximate lower bound on the number of accepted inputs of a circuit, up to multiplicative factors. © 2011 Springer Basel AG.
Ravi Tejwani, Yen-Ling Kuo, et al.
ICRA 2022
Ehud Aharoni, Anatoly Polnarov, et al.
ACL 2014
Dan Gutfreund, Akinori Kawachi
CCC 2010
Ehud Aharoni, Carlos Alzate, et al.
COLING 2014