4
$\begingroup$

Given $G=(V,E)$

How can i implement a DFS search in the Boolean circuit? ( The output should be to assign each node it's DFS value from a root node)

I assume the complexity should be exponential, because each move we don't know the next node to be it's consequent node).

But is there any justification to that? Can I do it better?

The above question is algorithmic, Because it's a preliminary stage to make the circuit obliviously...

Thanks.

$\endgroup$
1
  • $\begingroup$ For any program running in T steps using N memory, you can compile it to an oblivious version with ~O(T\log N) steps. An oblivious version can then be compiled to a circuit in a straightforward manner. No guarantee in terms of concrete cost. $\endgroup$ – redplum Jan 12 '18 at 2:11

Your Answer

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

Browse other questions tagged or ask your own question.