1
$\begingroup$

How can Barrington's Theorem be used to obtain faster programs ? Assuming, I want to evaluate function greater than gt between two bits x and y, defined as $gt(x,y)=xy+x$, equal with $1$ when $x$ is greater than $y$. Now, let's say I have two numbers on $N$ bits and the problem expands.

Can Barrington theorem be applied to speed up computation ? Or not necessary speed the computation, but reduce the number of multiplications of the boolean circuit implementing the greater than function for two numbers on $N$ bits ?

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ It seems pretty much impossible to practically speed up much of anything using Barrington's theorem. $\endgroup$ – pg1989 Mar 8 '16 at 2:02
2
$\begingroup$

Barrington's theorem probably isn't going to be useful to speed up computation. Rather, it's a useful way to understand the power of different computing models. For instance, it has been used to prove facts about what can be computed with log-depth circuits. It has also been used as a tool in building fully homomorphic cryptosystems.

|cite|improve this answer
$\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.