Toward better depth lower bounds: two results on the multiplexor relation

DOI10.1007/S00037-020-00194-8zbMath1452.68085OpenAlexW3033309051MaRDI QIDQ777911

Or Meir

Publication date: 8 July 2020

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00037-020-00194-8

zbMATH Keywords

multiplexercircuit complexitycommunication complexitycircuit lower boundsaddress functiondepth complexitydepth lower boundsKarchmer-Wigderson relationsKRW conjecturemultiplexor

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Networks and circuits as models of computation; circuit complexity (68Q06) Communication complexity, information complexity (68Q11)

Cites Work

• Unnamed Item
• Unnamed Item
• Communication complexity towards lower bounds on circuit depth
• Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity
• Super-logarithmic depth lower bounds via the direct sum in communication complexity
• A combinatorial problem; stability and order for models and theories in infinitary languages
• On the density of families of sets
• Toward Better Formula Lower Bounds: The Composition of a Function and a Universal Relation
• Monotone Circuits for Connectivity Require Super-Logarithmic Depth
• The Shrinkage Exponent of de Morgan Formulas is 2
• Communication Complexity
• Interactive channel capacity
• On a problem of K. Zarankiewicz

This page was built for publication: Toward better depth lower bounds: two results on the multiplexor relation