Superlinear lower bounds for bounded-width branching programs
type: Item
instance of: scholarly article
title: Superlinear lower bounds for bounded-width branching programs
zbMATH Open document ID: 0837.68056
author: David A. Mix Barrington
author: Howard Straubing
published in: Journal of Computer and System Sciences
publication date: 1995-08-21T00:00:00Z
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 777959
zbMATH Keywords: bounded-width branching program
zbMATH Keywords: threshold functions
zbMATH Keywords: circuit complexity
MaRDI profile type: Publication
full work available at URL: jcss.1995.1029
OpenAlex ID: W2025481592
DOI: 10.1006/JCSS.1995.1029
Recommended article: Q4318222
Recommended article: A superpolynomial lower bound for (1,+k(n))-branching programs
Recommended article: Q3690219
Recommended article: Bounds for Width Two Branching Programs
Recommended article: Q3991212
Recommended article: Q3002761
Recommended article: Stochastic Algorithms: Foundations and Applications
Recommended article: Lower Bounds for Syntactically Multilinear Algebraic Branching Programs
Recommended article: Q4736860
Recommended article: New lower bounds and hierarchy results for restricted branching programs
description: scientific article; zbMATH DE number 777959