scientific article; zbMATH DE number 1263188

zbMath0968.68516MaRDI QIDQ4234058

Stephen J. Ponzio

Publication date: 29 June 1999

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

oblivious read-once branching programs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (8)

A simple function that requires exponential size read-once branching programs ⋮ Approximating Boolean functions by OBDDs ⋮ Randomization and nondeterminism are comparable for ordered read-once branching programs ⋮ A lower bound for integer multiplication on randomized ordered read-once branching programs. ⋮ On BPP versus \(NP\cup coNP\) for ordered read-once branching programs ⋮ A read-once lower bound and a \((1,+k)\)-hierarchy for branching programs ⋮ Bounds on the OBDD-size of integer multiplication via universal hashing ⋮ A very simple function that requires exponential size read-once branching programs.

This page was built for publication: