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 ?

  • 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

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.


Your Answer

