Better lower bounds for monotone threshold formulas
From MaRDI portal
Publication:1356879
DOI10.1006/jcss.1997.1287zbMath0877.68062OpenAlexW2007620922MaRDI QIDQ1356879
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
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