Showing that BPP can do some surprising problems. read-once Branching program evaluation

trick:

“arithmetize” the boolean circuit. This means extend it to be a function over the integers. \[x\land y = x\cdot y, x\lor y = x+y-xy\]

lit

“while two boolean functions might only disagree in a single place, if you arithmetize different boolean functions they are gonna disagree in a lot of places. That’s because Polynomials aren’t too bouncy.”