The direct sum of universal relations

DOI10.1016/j.ipl.2018.04.009zbMath1476.68102OpenAlexW2800573032WikidataQ129940558 ScholiaQ129940558MaRDI QIDQ1751432

Or Meir

Publication date: 25 May 2018

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2018.04.009

zbMATH Keywords

computational complexitycommunication complexityuniversal relationdirect sumKarchmer-Wigderson relations

Mathematics Subject Classification ID

Communication complexity, information complexity (68Q11)

Related Items

Lifting Theorems for Equality

Cites Work

• Unnamed Item
• On the complexity of 2-output Boolean networks
• On the synthesis of self-correcting schemes from functional elements with a small number of reliable elements
• Realizing Boolean functions on disjoint sets of variables
• On the direct sum conjecture in the straight line model
• Communication complexity towards lower bounds on circuit depth
• Super-logarithmic depth lower bounds via the direct sum in communication complexity
• Separation of the monotone NC hierarchy
• How to compress interactive communication
• Monotone Circuits for Connectivity Require Super-Logarithmic Depth
• Monotone circuits for matching require linear depth
• Amortized Communication Complexity
• Communication Complexity
• Exponential separation of communication and external information