Toward better depth lower bounds: two results on the multiplexor relation
type: Item
instance of: scholarly article
title: Toward better depth lower bounds: two results on the multiplexor relation
zbMATH Open document ID: 1452.68085
author: Or Meir
published in: Computational Complexity
publication date: 2020-07-08T00:00:00Z
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68Q06
Mathematics Subject Classification ID: 68Q11
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 7218637
zbMATH Keywords: circuit complexity
zbMATH Keywords: circuit lower bounds
zbMATH Keywords: depth complexity
zbMATH Keywords: depth lower bounds
zbMATH Keywords: communication complexity
zbMATH Keywords: Karchmer-Wigderson relations
zbMATH Keywords: KRW conjecture
zbMATH Keywords: multiplexor
zbMATH Keywords: multiplexer
zbMATH Keywords: address function
MaRDI profile type: Publication
full work available at URL: s00037-020-00194-8
OpenAlex ID: W3033309051
cites work: Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity
cites work: Communication complexity towards lower bounds on circuit depth
cites work: Toward Better Formula Lower Bounds: The Composition of a Function and a Universal Relation
cites work: The Shrinkage Exponent of de Morgan Formulas is 2
cites work: Q4275381
cites work: Q5091000
cites work: Super-logarithmic depth lower bounds via the direct sum in communication complexity
cites work: Monotone Circuits for Connectivity Require Super-Logarithmic Depth
cites work: On a problem of K. Zarankiewicz
cites work: Interactive channel capacity
cites work: Communication Complexity
cites work: On the density of families of sets
cites work: A combinatorial problem; stability and order for models and theories in infinitary languages
DOI: 10.1007/S00037-020-00194-8
description: scientific article; zbMATH DE number 7218637