MCSP is hard for read-once nondeterministic branching programs

DOI10.1007/978-3-031-20624-5_38MaRDI QIDQ6164002zbMATH OpenFDO

Authors Ludmila Glinskih, Artur Riazanov

Publication date 26 July 2023

Published in LATIN 2022: Theoretical Informatics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-031-20624-5_38

Mathematics Subject Classification ID

Theory of computing (68Qxx) Discrete mathematics in relation to computer science (68Rxx) Algorithms in computer science (68Wxx)

Cites work

• \(\mathrm{AC}^0[p]\) lower bounds against MCSP via the coin problem
• Circuit lower bounds for MCSP from local pseudorandom generators
• Circuit minimization problem
• scientific article; zbMATH DE number 7650416 (Why is no real title available?)
• On lower bounds for read-\(k\)-times branching programs
• On the (non) \(\mathsf{NP}\)-hardness of computing circuit complexity
• Satisfiable Tseitin formulas are hard for nondeterministic read-once branching programs
• Slightly superexponential parameterized problems
• The complexity of minimizing and learning OBDDs and FBDDs
• Weak lower bounds on resource-bounded compression imply strong separations of complexity classes

Cited in

(1)

• SAT reduces to the minimum circuit size problem with a random oracle

This page was built for publication: MCSP is hard for read-once nondeterministic branching programs

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