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

DOI10.1007/S00037-020-00194-8MaRDI QIDQ777911zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

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

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)