Efficient oblivious branching programs for threshold and mod functions
type: Item
instance of: scholarly article
title: Efficient oblivious branching programs for threshold and mod functions
zbMATH Open document ID: 0897.68033
author: Rakesh Kumar Sinha
author: Jayram S. Thathachar
published in: Journal of Computer and System Sciences
publication date: 1998-08-04T00:00:00Z
Mathematics Subject Classification ID: 68N99
zbMATH DE Number: 1140551
zbMATH Keywords: branching programs
MaRDI profile type: Publication
OpenAlex ID: W1996519664
cites work: Meanders and their applications in lower bounds arguments
cites work: Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
cites work: Lower bounds to the complexity of symmetric Boolean functions
cites work: On lower bounds for read-\(k\)-times branching programs
cites work: Computing Algebraic Formulas Using a Constant Number of Registers
cites work: Superlinear lower bounds for bounded-width branching programs
cites work: Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
cites work: Subquadratic Simulations of Balanced Formulae by Branching Programs
cites work: Towards optimal simulations of formulas by bounded-width programs
cites work: Q3856819
cites work: Q5670543
cites work: Q5545524
cites work: Q3690219
cites work: Approximate formulas for some functions of prime numbers
cites work: Q3762226
DOI: 10.1006/JCSS.1997.1530
description: scientific article; zbMATH DE number 1140551