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

DOI10.1016/j.tcs.2010.03.022zbMath1344.68081OpenAlexW2051174588MaRDI QIDQ974758

Jun Tarui

Publication date: 7 June 2010

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2010.03.022

zbMATH Keywords

combinatorial complexitycommunication complexityformula complexityKarchmer-Wigderson protocoluniqueness of optimal algorithms

Mathematics Subject Classification ID

General topics in the theory of algorithms (68W01)

Related Items (1)

Unnamed Item

Cites Work

• Improvements on Khrapchenko's theorem
• An extension of Khrapchenko's theorem
• The quantum adversary method and classical formula size power bounds
• Monotone Circuits for Connectivity Require Super-Logarithmic Depth
• Smallest Formulas for Parity of 2 k Variables Are Essentially Unique
• The Shrinkage Exponent of de Morgan Formulas is 2
• Communication Complexity
• Computational Complexity
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Smallest formulas for the parity of \(2^k\) variables are essentially unique