MCSP is hard for read-once nondeterministic branching programs

DOI10.1007/978-3-031-20624-5_38MaRDI QIDQ6164002FDOQ6164002

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

• On lower bounds for read-\(k\)-times branching programs
• Circuit minimization problem
• Slightly superexponential parameterized problems
• On the (non) \(\mathsf{NP}\)-hardness of computing circuit complexity
• Title not available (Why is that?)
• The complexity of minimizing and learning OBDDs and FBDDs
• Satisfiable Tseitin formulas are hard for nondeterministic read-once branching programs
• Weak lower bounds on resource-bounded compression imply strong separations of complexity classes
• Title not available (Why is that?)
• Circuit lower bounds for MCSP from local pseudorandom generators

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)