Hardness against linear branching programs and more

DOI10.4230/LIPICS.CCC.2023.9MaRDI QIDQ6640344zbMATH OpenFDO

Authors Eshan Chattopadhyay, Jyun-Jie Liao

Publication date 19 November 2024

Full work available at URL https://doi.org/10.4230/LIPICS.CCC.2023.9

zbMATH Keywords

circuit lower boundhitting setslinear branching programssumset extractors

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cited in

(5)

• Exponential separation between powers of regular and general resolution over parities
• Explicit directional affine extractors and improved hardness for linear branching programs
• Two-source and affine non-malleable extractors for small entropy
• Lower bounds for regular resolution over parities
• Low-degree polynomials are good extractors

This page was built for publication: Hardness against linear branching programs and more

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6640344)