Generalizations of the Gate Elimination Method
summary
Proves a circuit lower bound route: starting from the classic gate elimination idea, constructs a XOR-layered and sometimes cyclic circuit normal form, then uses linear and quadratic substitutions plus a tailored measure-and-conquer complexity measure to show affine dispersers force about 3n gates (actually 3n minus o(n)), pushes that to roughly 3.01n, and reduces a further 3.1n target to an explicit construction problem about functions nonconstant on large sets defined by degree-≤2 polynomials.
AI-written summary · about