Toward better depth lower bounds: two results on the multiplexor relation
From MaRDI portal
(Redirected from Publication:777911)
communication complexitycircuit complexitycircuit lower boundsmultiplexeraddress functiondepth complexitydepth lower boundsKarchmer-Wigderson relationsKRW conjecturemultiplexor
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)
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)