Smallest formulas for the parity of \(2^k\) variables are essentially unique
type: Item
instance of: scholarly article
title: Smallest formulas for the parity of \(2^k\) variables are essentially unique
zbMATH Open document ID: 1344.68081
author: Jun Tarui
published in: Theoretical Computer Science
publication date: 2010-06-07T00:00:00Z
Mathematics Subject Classification ID: 68Q05
Mathematics Subject Classification ID: 68W01
zbMATH DE Number: 5717745
zbMATH Keywords: combinatorial complexity
zbMATH Keywords: uniqueness of optimal algorithms
zbMATH Keywords: formula complexity
zbMATH Keywords: Karchmer-Wigderson protocol
zbMATH Keywords: communication complexity
MaRDI profile type: Publication
full work available at URL: j.tcs.2010.03.022
OpenAlex ID: W2051174588
cites work: Smallest Formulas for Parity of 2 k Variables Are Essentially Unique
cites work: The Shrinkage Exponent of de Morgan Formulas is 2
cites work: Q5629239
cites work: Monotone Circuits for Connectivity Require Super-Logarithmic Depth
cites work: Q4385519
cites work: Communication Complexity
cites work: Q3762226
cites work: Computational Complexity
cites work: An extension of Khrapchenko's theorem
cites work: Improvements on Khrapchenko's theorem
cites work: The quantum adversary method and classical formula size power bounds
cites work: Q4398780
DOI: 10.1016/J.TCS.2010.03.022
description: scientific article; zbMATH DE number 5717745