Size-depth tradeoffs for Boolean formulae
From MaRDI portal
Publication:1318766
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
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
