Non-adaptive simulation impossibility conjecture for irregular communication orders

Let PiPi be an interactive protocol with a sufficiently non-regular, for example pseudo-random, communication order, and let PiPi' be a non-adaptive protocol whose communication order is fixed in advance. Let RR denote the simulation rate. Non-adaptive simulation impossibility conjecture. Such a protocol PiPi cannot be robustly simulated by any non-adaptive protocol PiPi' with rate

R=1o(1).R=1-o(1).

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

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.