Lower Bounds for Nondeterministic Semantic Read-Once Branching Programs

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

zbMATH Keywords

lower boundsbranching programs

Mathematics Subject Classification ID

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