Communication complexity towards lower bounds on circuit depth

DOI10.1007/S00037-001-8195-XMaRDI QIDQ1601024zbMATH OpenOpenAlexFDO

Authors Jeff Edmonds, Russell Impagliazzo, Steven Rudich, Jiří Sgall

Publication date 17 June 2002

Published in Computational Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00037-001-8195-x

zbMATH Keywords

circuit depth complexityuniversal composition relation

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Toward Better Formula Lower Bounds: The Composition of a Function and a Universal Relation
• Super-logarithmic depth lower bounds via the direct sum in communication complexity
• Toward better formula lower bounds: an information complexity approach to the KRW composition conjecture
• scientific article; zbMATH DE number 4068270
• On the depth complexity of the counting functions

Cited in

(27)

• Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity
• The direct sum of universal relations
• Super-logarithmic depth lower bounds via the direct sum in communication complexity
• On derandomized composition of Boolean functions
• Prediction from partial information and hindsight, with application to circuit lower bounds
• Dag-like communication and its applications
• Toward Better Formula Lower Bounds: The Composition of a Function and a Universal Relation
• Boolean Circuits, Tensor Ranks, and Communication Complexity
• Deterministic communication vs. partition number
• Depth reduction for composites
• scientific article; zbMATH DE number 2134904 (Why is no real title available?)
• Improved composition theorems for functions and relations
• Lifting Theorems for Equality
• Half-duplex communication complexity
• scientific article; zbMATH DE number 7250155 (Why is no real title available?)
• Toward better formula lower bounds: an information complexity approach to the KRW composition conjecture
• Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity
• Query-to-communication lifting using low-discrepancy gadgets
• Lower bound on SNARGs in the random oracle model
• A nearly-4 n depth lower bound for formulas with restriction on top
• Pebbles and branching programs for tree evaluation
• Toward better depth lower bounds: strong composition of XOR and a random function
• On the complexity of hazard-free formulas
• On the complexity of hazard-free formulas
• Choosing, agreeing, and eliminating in communication complexity
• Toward better depth lower bounds: two results on the multiplexor relation
• On the depth complexity of the counting functions

This page was built for publication: Communication complexity towards lower bounds on circuit depth

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