Monotonicity conjecture for communication complexity under user-set changes
Monotonicity conjecture for communication complexity under user-set changes
Let be the minimum communication rate required to achieve the secrecy capacity in the secret-key agreement model. A trusted helper is a user whose source is trusted and who is not initially active, a vocal active user communicates at strictly positive rate, and a source determines a source when . Monotonicity conjecture. does not increase under either of the following changes: (i) making a trusted helper active, provided that the helper's private source determines the private source of another active user; or (ii) forcing a vocal active user to be silent, provided that its private source is determined by that of another vocal user. These conjectures are proposed as possible improvements to the lower bound on communication complexity. The source says they would follow from the stronger MKS16 conjecture that private randomization does not decrease , but does not establish them independently.
Sources & referencesView supporting material
Primary source
Chung Chan, Manuj Mukherjee, Navin Kashyap and Qiaoqiao Zhou, “On the Optimality of Secret Key Agreement via Omniscience”, arXiv:1702.07429 (2018).
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.