Generalized lower bounds derived from Hastad's main lemma

DOI10.1016/0020-0190(87)90216-XMaRDI QIDQ1107987zbMATH OpenOpenAlexWikidataFDO

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

zbMATH Keywords

symmetric functionsconstant-depth circuits

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

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

Cites work

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

Cited in

(2)

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

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)