The choice and agreement problems of a random function

DOI10.1016/j.ipl.2017.12.007zbMath1427.68081OpenAlexW2784149224MaRDI QIDQ1705694

Or Meir, Avishay Tal

Publication date: 16 March 2018

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

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

zbMATH Keywords

computational complexitydirect sumagreechooseKRW composition conjecture

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Communication complexity, information complexity (68Q11)

Cites Work

• Unnamed Item
• Optimal direct sum results for deterministic and randomized decision tree complexity
• Choosing, agreeing, and eliminating in communication complexity
• 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
• Super-logarithmic depth lower bounds via the direct sum in communication complexity
• How to compress interactive communication
• Monotone Circuits for Connectivity Require Super-Logarithmic Depth
• Lower Bounds for Elimination via Weak Regularity
• Amortized Communication Complexity
• Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity
• The communication complexity of enumeration, elimination, and selection

This page was built for publication: The choice and agreement problems of a random function