Non-adaptive simulation impossibility conjecture for irregular communication orders
Non-adaptive simulation impossibility conjecture for irregular communication orders
Let be an interactive protocol with a sufficiently non-regular, for example pseudo-random, communication order, and let be a non-adaptive protocol whose communication order is fixed in advance. Let denote the simulation rate. Non-adaptive simulation impossibility conjecture. Such a protocol cannot be robustly simulated by any non-adaptive protocol with rate
This should hold for essentially any channel introducing some error, including a channel introducing only a single random error or erasure. The conjecture concerns the strong limitation imposed by non-adaptive communication orders, in contrast with adaptive simulations.
Sources & referencesView supporting material
Primary source
Bernhard Haeupler, “Interactive Channel Capacity Revisited”, arXiv:1408.1467 (2014).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.