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)

Mathematics Subject Classification ID

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

Cites work

• scientific article; zbMATH DE number 7561559 (Why is no real title available?)
• scientific article; zbMATH DE number 7650416 (Why is no real title available?)
• Circuit lower bounds for MCSP from local pseudorandom generators
• Circuit minimization problem
• 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

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)