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

DOI10.1007/S00037-020-00194-8zbMATH Open1452.68085OpenAlexW3033309051MaRDI QIDQ777911FDOQ777911

Authors: 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

Recommendations

• Toward Better Formula Lower Bounds: The Composition of a Function and a Universal Relation
• Improved composition theorems for functions and relations
• Communication complexity towards lower bounds on circuit depth
• Toward better formula lower bounds: an information complexity approach to the KRW composition conjecture
• Super-logarithmic depth lower bounds via the direct sum in communication complexity

zbMATH Keywords

communication complexitycircuit complexitycircuit lower boundsmultiplexeraddress 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

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

Cited In (2)

• On the depth of a multiplexer function with a small number of select lines
• Improved composition theorems for functions and relations

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

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