Efficient oblivious branching programs for threshold and mod functions

DOI10.1006/JCSS.1997.1530MaRDI QIDQ1384527zbMATH OpenOpenAlexFDO

Authors 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)

Cites work

• Approximate formulas for some functions of prime numbers
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Computing Algebraic Formulas Using a Constant Number of Registers
• scientific article; zbMATH DE number 3913677 (Why is no real title available?)
• scientific article; zbMATH DE number 4012495 (Why is no real title available?)
• scientific article; zbMATH DE number 3657869 (Why is no real title available?)
• scientific article; zbMATH DE number 3257409 (Why is no real title available?)
• scientific article; zbMATH DE number 3404149 (Why is no real title available?)
• Lower bounds to the complexity of symmetric Boolean functions
• Meanders and their applications in lower bounds arguments
• Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
• On lower bounds for read-\(k\)-times branching programs
• Subquadratic Simulations of Balanced Formulae by Branching Programs
• Superlinear lower bounds for bounded-width branching programs
• Towards optimal simulations of formulas by bounded-width programs

Cited in

(5)

• Complexity and depth of formulas for symmetric Boolean functions
• scientific article; zbMATH DE number 17548 (Why is no real title available?)
• Tight Bounds on Oblivious Chaining
• Catalytic branching programs from groups and general protocols
• Communication memento: memoryless communication complexity

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

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