Improvements on Khrapchenko's theorem

DOI10.1016/0304-3975(93)90330-VzbMATH Open0777.94022OpenAlexW2044982302MaRDI QIDQ685364FDOQ685364

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

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

zbMATH Keywords

Khrapchenko's theoremlower bounds for Boolean formulae

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites Work

• Title not available (Why is that?)
• Method of determining lower bounds for the complexity of \(\Pi\)-circuits
• Title not available (Why is that?)
• An extension of Khrapchenko's theorem

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
• Title not available (Why is that?)
• On convex complexity measures
• Breaking the rectangle bound barrier against formula size lower bounds
• Title not available (Why is that?)
• 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)