Lower bounds for nondeterministic semantic read-once branching programs

DOI10.4230/LIPICS.ICALP.2016.36MaRDI QIDQ4598173zbMATH OpenOpenAlexFDO

Authors Jeff Edmonds, Venkatesh Medabalimi, Toniann Pitassi, Stephen Cook

Publication date 19 December 2017

Full work available at URL https://dblp.uni-trier.de/db/conf/icalp/icalp2016.html#CookEMP16

zbMATH Keywords

branching programslower bounds

Mathematics Subject Classification ID

Data structures (68P05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• scientific article; zbMATH DE number 1962823
• scientific article; zbMATH DE number 1759409
• Restricted nondeterministic read-once branching programs and an exponential lower bound for integer multiplication
• scientific article; zbMATH DE number 1929932
• A lower bound technique for nondeterministic graph-driven read-once-branching programs and its applications

Cited in

(7)

• Neither reading few bits twice nor reading illegally helps much
• Satisfiability algorithm for syntactic read-\(k\)-times branching programs
• A lower bound technique for nondeterministic graph-driven read-once-branching programs and its applications
• scientific article; zbMATH DE number 549860 (Why is no real title available?)
• Satisfiable Tseitin formulas are hard for nondeterministic read-once branching programs
• scientific article; zbMATH DE number 7250155 (Why is no real title available?)
• Perspective on complexity measures targeting read-once branching programs

This page was built for publication: Lower bounds for nondeterministic semantic read-once branching programs

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