Super-logarithmic depth lower bounds via the direct sum in communication complexity

DOI10.1007/BF01206317zbMath0851.68034MaRDI QIDQ1918946

Mauricio Karchmer, Avi Wigderson, Ran Raz

Publication date: 10 November 1996

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

zbMATH Keywords

complexitycommunication problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (28)

Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity ⋮ New bounds on the half-duplex communication complexity ⋮ The Range of Topological Effects on Communication ⋮ Branching Programs for Tree Evaluation ⋮ Communication complexity of approximate Nash equilibria ⋮ An information statistics approach to data stream and communication complexity ⋮ Super-logarithmic depth lower bounds via the direct sum in communication complexity ⋮ Communication and information complexity ⋮ Toward Better Formula Lower Bounds: The Composition of a Function and a Universal Relation ⋮ Unnamed Item ⋮ The choice and agreement problems of a random function ⋮ Information complexity and applications. ⋮ The direct sum of universal relations ⋮ Unnamed Item ⋮ Capturing one-way functions via NP-hardness of meta-complexity ⋮ Unnamed Item ⋮ The communication complexity of enumeration, elimination, and selection ⋮ On derandomized composition of Boolean functions ⋮ Lower Bounds for Number-in-Hand Multiparty Communication Complexity, Made Easy ⋮ Unnamed Item ⋮ Choosing, agreeing, and eliminating in communication complexity ⋮ Unnamed Item ⋮ Lifting Theorems for Equality ⋮ Cubic Formula Size Lower Bounds Based on Compositions with Majority ⋮ Prediction from partial information and hindsight, with application to circuit lower bounds ⋮ Toward better depth lower bounds: two results on the multiplexor relation ⋮ Query-to-Communication Lifting Using Low-Discrepancy Gadgets ⋮ Unnamed Item

Cites Work

• A method for obtaining more than quadratic effective lower estimates of complexity of \(\pi\) schemes
• On the complexity of 2-output Boolean networks
• Super-logarithmic depth lower bounds via the direct sum in communication complexity
• On incidence matrices of finite projective and affine spaces
• Method of determining lower bounds for the complexity of \(\Pi\)-circuits
• Applications of matrix methods to the theory of lower bounds in computational complexity
• Monotone Circuits for Connectivity Require Super-Logarithmic Depth

This page was built for publication: Super-logarithmic depth lower bounds via the direct sum in communication complexity