scientific article; zbMATH DE number 1775455

zbMATH Open1006.68054MaRDI QIDQ4542589FDOQ4542589

Authors: Jayram S. Thatachar 

Publication date: 9 March 2003

Title of this publication is not available (Why is that?)

Recommendations

• A note on read-$k$ times branching programs
• A read-once lower bound and a \((1,+k)\)-hierarchy for branching programs
• On lower bounds for read-\(k\)-times branching programs
• On the hierarchies for deterministic, nondeterministic and probabilistic ordered read-\(k\)-times branching programs
• A hierarchy result for read-once branching programs with restricted parity nondeterminism
• scientific article; zbMATH DE number 1759451
• Satisfiability algorithm for syntactic read-\(k\)-times branching programs
• Satisfiability algorithm for syntactic read-\(k\)-times branching programs
• Comparing the sizes of nondeterministic branching read-k-times programs
• A lower bound for read-once-only branching programs

zbMATH Keywords

branching programs

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cited In (17)

• The hardest halfspace
• Complexity Theoretical Results on Nondeterministic Graph-driven Read-Once Branching Programs
• Polynomial-size binary decision diagrams for the exactly half-\(d\)-hyperclique problem reading each input bit twice
• Nondeterministic ordered binary decision diagrams with repeated tests and various modes of acceptance
• Approximation of boolean functions by combinatorial rectangles
• On the hierarchies for deterministic, nondeterministic and probabilistic ordered read-\(k\)-times branching programs
• Satisfiability algorithm for syntactic read-\(k\)-times branching programs
• Satisfiable Tseitin Formulas Are Hard for Nondeterministic Read-Once Branching Programs.
• Parity graph-driven read-once branching programs and an exponential lower bound for integer multiplication
• Notes on Boolean read-\(k\) and multilinear circuits
• Satisfiability Algorithm for Syntactic Read-$k$-times Branching Programs
• Time-space tradeoffs for branching programs
• Restricted nondeterministic read-once branching programs and an exponential lower bound for integer multiplication
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the hierarchy of nondeterministic branching k-programs
• Classical and Quantum Computations with Restricted Memory

This page was built for publication:

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