2 papers
cs.CC2026
Constructive Separations from Gate Elimination
Marco Carmosino, Ngu Dang, Tim Jackman
Gate elimination is the primary technique for proving explicit lower bounds against general Boolean circuits, including Li and Yang's state-of-the-art bound for affin…
cs.CC2026
Convergent Gate Elimination and Constructive Circuit Lower Bounds
Marco Carmosino, Ngu Dang, Tim Jackman
Towards better understanding of gate elimination, the only method known that can prove complexity lower bounds for explicit functions against unrestricted Boolean circuits, this wo…