The choice and agreement problems of a random function

DOI10.1016/J.IPL.2017.12.007MaRDI QIDQ1705694zbMATH OpenOpenAlexFDO

Authors 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

agreechoosecomputational complexitydirect sumKRW composition conjecture

Mathematics Subject Classification ID

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

Recommendations

• A problem of random choice and its deterministic structure
• On a Choquet theorem for random upper semicontinuous functions
• On Choquet theorem for random upper semicontinuous functions
• scientific article; zbMATH DE number 4169777
• The iterated random function problem
• scientific article; zbMATH DE number 3242950
• Choquet random sup-measures with aggregations
• scientific article; zbMATH DE number 3860067
• Measurable selections:in random approximations and fixed point theory

Cites work

• Amortized Communication Complexity
• Choosing, agreeing, and eliminating in communication complexity
• How to compress interactive communication
• scientific article; zbMATH DE number 4012495 (Why is no real title available?)
• Lower bounds for elimination via weak regularity
• Monotone Circuits for Connectivity Require Super-Logarithmic Depth
• On the complexity of 2-output Boolean networks
• On the direct sum conjecture in the straight line model
• On the synthesis of self-correcting schemes from functional elements with a small number of reliable elements
• Optimal direct sum results for deterministic and randomized decision tree complexity
• Realizing Boolean functions on disjoint sets of variables
• Super-logarithmic depth lower bounds via the direct sum in communication complexity
• The communication complexity of enumeration, elimination, and selection
• Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity

Cited in

(2)

• Choosing, agreeing, and eliminating in communication complexity
• Choosing, agreeing, and eliminating in communication complexity

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

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