Generalized lower bounds derived from Hastad's main lemma

DOI10.1016/0020-0190(87)90216-XzbMATH Open0653.68018OpenAlexW1983993468WikidataQ124808236 ScholiaQ124808236MaRDI QIDQ1107987FDOQ1107987

Authors: 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

Recommendations

• scientific article; zbMATH DE number 2020238
• scientific article; zbMATH DE number 591277
• A generalization of Hensel's lemma
• scientific article; zbMATH DE number 1204304
• Generalized Hensel's lemma
• Generalization of H. Minc and L. Sathre's inequality
• Remarks on the generalized Hestenes's Lemma
• A generalization of a lower bound technique due to Fredman and Saks
• On the Generalization of Hörmander's Inequality
• A general Hensel's lemma

zbMATH Keywords

symmetric functionsconstant-depth circuits

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites Work

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

Cited In (2)

• Coloring k-colorable graphs in constant expected parallel time
• Bounded-depth, polynomial-size circuits for symmetric functions

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1107987)