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.

Improve this question
$\endgroup$
2
  • $\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
    Commented Jan 12, 2018 at 2:11
  • $\begingroup$ Any update so far? @redplum, Is there any automated way to convert a DFS algorithm to the boolean circuit? or do you have to convert the algorithm manually? Also, is there any boolean circuit generator where I can give a high-level function, and it returns the boolean circuit? Thanks $\endgroup$
    – taserghar
    Commented Nov 18, 2022 at 23:59

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.