Improvements on Khrapchenko's theorem

DOI10.1016/0304-3975(93)90330-VzbMath0777.94022OpenAlexW2044982302MaRDI QIDQ685364

Elias Koutsoupias

Publication date: 1993

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(93)90330-v

zbMATH Keywords

Khrapchenko's theoremlower bounds for Boolean formulae

Mathematics Subject Classification ID

Related Items (6)

Smallest Formulas for Parity of 2 k Variables Are Essentially Unique ⋮ A stronger LP bound for formula size lower bounds via clique constraints ⋮ Exploring the Limits of Subadditive Approaches: Parallels between Optimization and Complexity Theory ⋮ BREAKING THE RECTANGLE BOUND BARRIER AGAINST FORMULA SIZE LOWER BOUNDS ⋮ On convex complexity measures ⋮ Smallest formulas for the parity of \(2^k\) variables are essentially unique

Cites Work

• An extension of Khrapchenko's theorem
• Method of determining lower bounds for the complexity of \(\Pi\)-circuits
• Unnamed Item
• Unnamed Item

This page was built for publication: Improvements on Khrapchenko's theorem