6
$\begingroup$

Is there a relation between BBH (black box hypothesis) and SETH (strong exponential time hypothesis)?

$\endgroup$
  • 8
    $\begingroup$ What is the black box hypothesis? I haven't heard of it. $\endgroup$ – Sasho Nikolov Apr 19 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 Golovnev Apr 20 at 17:47
8
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.