Non-Malleable Affine Extractors with Small Error and Complexity Lower BoundsResearch Paper
Linear branching programs generalize ordinary branching programs by letting each step query a parity of the input bits rather than a single bit. They capture computations that, at every step, learn one linear fact about a hidden vector in , and lower bounds for them sit between lower bounds for ordinary read-once branching programs and for…