# Can Barrington's Theorem be used to speed up computation of some function ? How?

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 ?

• It seems pretty much impossible to practically speed up much of anything using Barrington's theorem. – pg1989 Mar 8 '16 at 2:02