The choice and agreement problems of a random function
type: Item
instance of: scholarly article
title: The choice and agreement problems of a random function
zbMATH Open document ID: 1427.68081
author: Or Meir
author: Avishay Tal
published in: Information Processing Letters
publication date: 2018-03-16T00:00:00Z
Mathematics Subject Classification ID: 68Q10
Mathematics Subject Classification ID: 68Q11
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 6851033
zbMATH Keywords: computational complexity
zbMATH Keywords: agree
zbMATH Keywords: choose
zbMATH Keywords: direct sum
zbMATH Keywords: KRW composition conjecture
MaRDI profile type: Publication
full work available at URL: j.ipl.2017.12.007
OpenAlex ID: W2784149224
cites work: The communication complexity of enumeration, elimination, and selection
cites work: How to compress interactive communication
cites work: Choosing, agreeing, and eliminating in communication complexity
cites work: On the direct sum conjecture in the straight line model
cites work: Lower Bounds for Elimination via Weak Regularity
cites work: Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity
cites work: Amortized Communication Complexity
cites work: On the complexity of 2-output Boolean networks
cites work: Optimal direct sum results for deterministic and randomized decision tree complexity
cites work: Super-logarithmic depth lower bounds via the direct sum in communication complexity
cites work: Monotone Circuits for Connectivity Require Super-Logarithmic Depth
cites work: Realizing Boolean functions on disjoint sets of variables
cites work: On the synthesis of self-correcting schemes from functional elements with a small number of reliable elements
cites work: Q3762226
DOI: 10.1016/J.IPL.2017.12.007
Recommended article: A problem of random choice and its deterministic structure
Recommended article: Q3416148
Recommended article: On Choquet theorem for random upper semicontinuous functions
Recommended article: Q3496983
Recommended article: The iterated random function problem
Recommended article: Q5530192
Recommended article: Choquet random sup-measures with aggregations
Recommended article: Q3327412
Recommended article: Measurable selections:in random approximations and fixed point theory
description: scientific article; zbMATH DE number 6851033