Is there a relation between BBH (black box hypothesis) and SETH (strong exponential time hypothesis)?
2
-
8$\begingroup$ What is the black box hypothesis? I haven't heard of it. $\endgroup$– Sasho NikolovCommented Apr 19, 2019 at 18:30
-
5$\begingroup$ @SashoNikolov, I think they mean Conjecture 5.1 from "On the (Im)possibility of Obfuscating Programs" by Barak, Goldreich, Impagliazzo, Rudich, Sahai, Vadhan, and Yang. See also "Does Looking Inside a Circuit Help?" by Impagliazzo, Kabanets, Kolokolova, McKenzie, and Romani for some connections between versions of BBH and ETH. $\endgroup$– Alex GolovnevCommented Apr 20, 2019 at 17:47
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Adding to Sasha's answer. Roughly speaking, BBH posits that every property of functions that is hard to decide with only query access to the function (black box access) is also hard to decide when you're given a circuit for the function.
The paper:
https://eccc.weizmann.ac.il/report/2017/109/
shows that certain counterexamples to BBH would refute a non-uniform version of ETH (Circuit SAT has $2^{o(n)}$ size circuits). They conjecture something like that "non-uniform ETH for Circuit SAT <=> BBH is true".
Note in the other direction, if SETH is false for circuits, this would refute some version of BBH: we cannot possibly solve SAT for black boxes in $o(2^n)$ time.
answered Apr 20, 2019 at 20:35