Generalized lower bounds derived from Hastad's main lemma

DOI10.1016/0020-0190(87)90216-XzbMath0653.68018OpenAlexW1983993468WikidataQ124808236 ScholiaQ124808236MaRDI QIDQ1107987

Shlomo Moran

Publication date: 1987

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

Full work available at URL: https://doi.org/10.1016/0020-0190(87)90216-x

zbMATH Keywords

symmetric functionsconstant-depth circuits

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (1)

Coloring k-colorable graphs in constant expected parallel time

Cites Work

• Bounded-depth, polynomial-size circuits for symmetric functions
• Definability by constant-depth polynomial-size circuits

This page was built for publication: Generalized lower bounds derived from Hastad's main lemma