Improvements on Khrapchenko's theorem

DOI10.1016/0304-3975(93)90330-VMaRDI QIDQ685364zbMATH OpenOpenAlexFDO

Authors 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

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• An extension of Khrapchenko's theorem
• scientific article; zbMATH DE number 3877162
• The effect of random restrictions on formula size
• Upper bounds for the formula size of symmetric Boolean functions
• A New Rank Technique for Formula Size Lower Bounds

Cites work

• scientific article; zbMATH DE number 3144516 (Why is no real title available?)
• scientific article; zbMATH DE number 1142303 (Why is no real title available?)
• An extension of Khrapchenko's theorem
• Method of determining lower bounds for the complexity of \(\Pi\)-circuits

Cited in

(11)

• On an improvement of the Hake theorem
• An extension of Khrapchenko's theorem
• The improvement of the Kneser theorem and its applications
• Smallest formulas for the parity of \(2^k\) variables are essentially unique
• A stronger LP bound for formula size lower bounds via clique constraints
• scientific article; zbMATH DE number 5211136 (Why is no real title available?)
• On convex complexity measures
• Breaking the rectangle bound barrier against formula size lower bounds
• scientific article; zbMATH DE number 3877162 (Why is no real title available?)
• Smallest Formulas for Parity of 2 k Variables Are Essentially Unique
• Exploring the limits of subadditive approaches: parallels between optimization and complexity theory

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

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