Iterated group products and leakage resilience against NC1
Iterated group products and leakage resilience against NC1
We show that if NC1 ≠ L, then for every element α of the alternating group At, circuits of depth O(log t) cannot distinguish between a uniform vector over (At)t with product = α and one with product = identity. Combined with a recent construction by the author and Viola …