The direct sum of universal relations
From MaRDI portal
Publication:1751432
DOI10.1016/j.ipl.2018.04.009zbMath1476.68102OpenAlexW2800573032WikidataQ129940558 ScholiaQ129940558MaRDI QIDQ1751432
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
computational complexitycommunication complexityuniversal relationdirect sumKarchmer-Wigderson relations
Related Items
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