Efficient oblivious branching programs for threshold and mod functions

DOI10.1006/jcss.1997.1530zbMath0897.68033OpenAlexW1996519664MaRDI QIDQ1384527

Rakesh Kumar Sinha, Jayram S. Thathachar

Publication date: 4 August 1998

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/c28e448a64b1abc4f931e1ee08a13ac3e7ba59ed

zbMATH Keywords

branching programs

Mathematics Subject Classification ID

Theory of software (68N99)

Related Items (1)

Complexity and depth of formulas for symmetric Boolean functions

Cites Work

• Towards optimal simulations of formulas by bounded-width programs
• Lower bounds to the complexity of symmetric Boolean functions
• Meanders and their applications in lower bounds arguments
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
• Superlinear lower bounds for bounded-width branching programs
• On lower bounds for read-\(k\)-times branching programs
• Approximate formulas for some functions of prime numbers
• Computing Algebraic Formulas Using a Constant Number of Registers
• Subquadratic Simulations of Balanced Formulae by Branching Programs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Efficient oblivious branching programs for threshold and mod functions