Lower Bounds for Nondeterministic Semantic Read-Once Branching Programs
From MaRDI portal
Publication:4598173
DOI10.4230/LIPIcs.ICALP.2016.36zbMath1388.68028OpenAlexW2533991449MaRDI QIDQ4598173
Toniann Pitassi, Jeff Edmonds, Venkatesh Medabalimi, Stephen A. Cook
Publication date: 19 December 2017
Full work available at URL: https://dblp.uni-trier.de/db/conf/icalp/icalp2016.html#CookEMP16
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Data structures (68P05)
Related Items (3)
Satisfiability algorithm for syntactic read-\(k\)-times branching programs ⋮ Unnamed Item ⋮ Satisfiable Tseitin Formulas Are Hard for Nondeterministic Read-Once Branching Programs.
This page was built for publication: Lower Bounds for Nondeterministic Semantic Read-Once Branching Programs