Better lower bounds for monotone threshold formulas

DOI10.1006/jcss.1997.1287zbMath0877.68062OpenAlexW2007620922MaRDI QIDQ1356879

Jaikumar Radhakrishnan

Publication date: 16 June 1997

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/01b5cd67571019bc7b6bfb9637f52d1de64028d6

zbMATH Keywords

monotone formulamonotone directed contact networks model

Mathematics Subject Classification ID

Parallel algorithms in computer science (68W10)

Related Items (2)

A stronger LP bound for formula size lower bounds via clique constraints ⋮ Exploring the Limits of Subadditive Approaches: Parallels between Optimization and Complexity Theory

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Sorting in \(c \log n\) parallel steps
• Lower bounds of the complexity of symmetric Boolean functions of contact- rectifier circuits
• Improved bounds for covering complete uniform hypergraphs
• An information-theoretic method in combinatorial theory
• The covering problem of complete uniform hypergraphs
• Directed monotone contact networks for threshold functions
• Method of determining lower bounds for the complexity of \(\Pi\)-circuits
• On the Size of Separating Systems and Families of Perfect Hash Functions
• Short monotone formulae for the majority function
• $\Omega (n\log n)$ Lower Bounds on Length of Boolean Formulas
• Amplification and percolation (probabilistic Boolean functions)

This page was built for publication: Better lower bounds for monotone threshold formulas