Size-depth tradeoffs for Boolean formulae

DOI10.1016/0020-0190(94)90093-0zbMath0802.68067OpenAlexW2069796292WikidataQ60512317 ScholiaQ60512317MaRDI QIDQ1318766

Samuel R. Buss, Maria Luisa Bonet

Publication date: 5 April 1994

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(94)90093-0

zbMATH Keywords

formula complexityBoolean formulassize-depth tradeoff

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items

A note on the size of prenex normal forms ⋮ Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity ⋮ A Generalization of Spira’s Theorem and Circuits with Small Segregators or Separators ⋮ Span-Program-Based Quantum Algorithm for Evaluating Unbalanced Formulas ⋮ A generalization of Spira's theorem and circuits with small segregators or separators ⋮ Constructing small tree grammars and small circuits for formulas ⋮ Unnamed Item ⋮ Unnamed Item ⋮ \texttt{MOTIF}: (almost) free branching in GMW. Via vector-scalar multiplication ⋮ Toward Better Formula Lower Bounds: The Composition of a Function and a Universal Relation ⋮ On the applicability of Post's lattice ⋮ A Quadratic Size-Hierarchy Theorem for Small-Depth Multilinear Formulas ⋮ On the efficiency of normal form systems for representing Boolean functions ⋮ Branching program size is almost linear in formula size ⋮ Span-program-based quantum algorithm for evaluating formulas ⋮ Unnamed Item

Cites Work

• Unnamed Item
• The Parallel Evaluation of General Arithmetic Expressions