Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR26-115 | 7th July 2026 09:30

A Lower Bound for Read-Once Parity Branching Programs

RSS-Feed




TR26-115
Authors: Ben Lee Volk
Publication: 7th July 2026 10:21
Downloads: 38
Keywords: 


Abstract:

We prove an $\tilde{\Omega}(n^2)$ lower bound for read-once parity branching programs computing an explicit boolean function on $n$ variables. The previous best lower bound was $\tilde{\Omega}(n^{1.5})$. Our lower bound is proved by reducing the problem to a lower bound in algebraic circuit complexity.



ISSN 1433-8092 | Imprint