Smallest Formulas for Parity of 2 k Variables Are Essentially Unique

DOI10.1007/978-3-540-69733-6_10MaRDI QIDQ3511317zbMATH OpenOpenAlexFDO

Authors Jun Tarui

Publication date 10 July 2008

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-69733-6_10

Mathematics Subject Classification ID

Recommendations

• Smallest formulas for the parity of \(2^k\) variables are essentially unique
• An extension of Khrapchenko's theorem
• A note on the formula size of the ``mod k functions
• Constructing $O(n\log n)$ Size Monotone Formulae for the kth Threshold Function of n Boolean Variables
• Subspace-invariant \(\mathrm{AC}^0\) formulas

Cites work

• An extension of Khrapchenko's theorem
• Communication Complexity
• Computational Complexity
• scientific article; zbMATH DE number 4012495 (Why is no real title available?)
• scientific article; zbMATH DE number 47903 (Why is no real title available?)
• scientific article; zbMATH DE number 1178976 (Why is no real title available?)
• scientific article; zbMATH DE number 3354614 (Why is no real title available?)
• scientific article; zbMATH DE number 3420624 (Why is no real title available?)
• Improvements on Khrapchenko's theorem
• Monotone Circuits for Connectivity Require Super-Logarithmic Depth
• The quantum adversary method and classical formula size power bounds
• The Shrinkage Exponent of de Morgan Formulas is 2

Cited in

(1)

• Smallest formulas for the parity of \(2^k\) variables are essentially unique

This page was built for publication: Smallest Formulas for Parity of 2 k Variables Are Essentially Unique

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