Open Problems:79 - Revision history

Krzysztof Onak: Formatting

2017-04-28T03:32:55Z

Formatting

Krzysztof Onak: Formatting

2017-04-28T03:16:18Z

Formatting

Joshuabrody at 16:04, 3 April 2017

2017-04-03T16:04:57Z

Blackc4 at 22:43, 1 April 2017

2017-04-01T22:43:51Z

Blackc4 at 21:45, 31 March 2017

2017-03-31T21:45:37Z

Blackc4 at 21:38, 31 March 2017

2017-03-31T21:38:06Z

Blackc4: Created page with "{{Header |source=banff17 |who=Joshua Brody }} "

2017-03-31T20:13:50Z

Created page with "{{Header |source=banff17 |who=Joshua Brody }} <references />"

New page

{{Header
|source=banff17
|who=Joshua Brody
}}

<references />

@@ Line 10: / Line 10: @@
 We are interested in maximizing the probability that players win (maximum success probability). For $k=2$, the following trivial protocol has success probability $0.25$.  Just output $1$.  It can be shown easily that maximum success probability is at most $0.5$.  The bounds can be improved to $0.3384 \le $ maximum success probability $\le 0.361$.  Here is a protocol that achieves success probability $1/3$.
-'''First round:'''
+; <span>First round:</span>
-If Alice has the secret,
+: If Alice has the secret,
-* with probability $2/3$ she asks Bob to speak second
+; <span>Second round:</span>
-* with probability $1/3$ she speaks second.
+: If the speaker has the secret, announce it. Otherwise, announce a random bit.
-Else (vice-versa)
+For large $k$, the following bounds can be shown:  $0.5644 \le $ maximum success probability $\le 0.75$. Can we improve these bounds? For more information, including the state of the art bounds, see the papers of Jakobsen {{cite|Jakobsen-14}} and Doerr and Kunnemann {{cite|DoerrK-16}}.

@@ Line 3: / Line 3: @@
 |who=Joshua Brody
 }}
+Cryptogenography, introduced by Brody et al. {{cite|BrodyJSW-14}}, is concerned with the following question: &ldquo;How to share a secret without revealing the secret owner?&rdquo;
-Cryptogenography is concerned with the following question.  "How to share a secret without revealing the secret owner?"  Please see Brody et al. {{cite|BrodyJSW-14}}.
+In this problem, there are $k$ players and an eavesdropper.  Input is a random bit $X \in \{0,1\}$, also called &ldquo;the secret.&rdquo;  The secret owner $J$ is chosen uniformly at random from $[k]$.  Players have private randomness and they can communicate publicly on a shared blackboard visible to everyone.  Players are said to win if
 * everyone learns the secret, and
 * eavesdropper does not guess the secret owner correctly.
-We are interested in maximizing the probability that players win (maximum success probability).
+We are interested in maximizing the probability that players win (maximum success probability). For $k=2$, the following trivial protocol has success probability $0.25$.  Just output $1$.  It can be shown easily that maximum success probability is at most $0.5$.  The bounds can be improved to $0.3384 \le $ maximum success probability $\le 0.361$.  Here is a protocol that achieves success probability $1/3$.
 '''First round:'''
@@ Line 27: / Line 23: @@
 If the speaker has the secret, announce it, else announce a random bit.
 For large $k$, the following bounds can be shown:  $0.5644 \le $ maximum success probability $\le 0.75$. Can we improve these bounds? For more information, including state of the art bounds, see: {{cite|Jakobsen-14|DoerrK-16}}

@@ Line 34: / Line 34: @@
 Can we improve these bounds?
+For more information, including state of the art bounds, see: {{cite|Jakobsen-14|DoerrK-16}}
 <references />

@@ Line 4: / Line 4: @@
 }}
-Cryptogenography is concerned with the following question.  "How to share a secret without revealing the secret owner?"  Please see Brody et al. {{cite|BJSW-14}} and Jakobsen {{cite|J-16}}.
+Cryptogenography is concerned with the following question.  "How to share a secret without revealing the secret owner?"  Please see Brody et al. {{cite|BrodyJSW-14}}.
 In this problem, there are $k$ players and an eavesdropper.  Input is a random bit $X \in \{0,1\}$, also called "the secret."  The secret owner $J$ is chosen uniformly at random from $[k]$.  Players have private randomness and they can communicate publicly on a shared blackboard visible to everyone.  Players are said to win if

@@ Line 7: / Line 7: @@
 In this problem, there are $k$ players and an eavesdropper.  Input is a random bit $X \in \{0,1\}$, also called "the secret."  The secret owner $J$ is chosen uniformly at random from $[k]$.  Players have private randomness and they can communicate publicly on a shared blackboard visible to everyone.  Players are said to win if
 * everyone learns the secret, and
 * eavesdropper does not guess the secret owner correctly.
@@ Line 13: / Line 12: @@
 We are interested in maximizing the probability that players win (maximum success probability).
-For $k=2$, the following trivial protocol has success probability $0.25$.  Just output $1$.  It can be shown easily that maximum success probability is at most $0.5$.  The bounds can be improved to $0.3384 \le $ maximum success probability $\le 0.361$.
+For $k=2$, the following trivial protocol has success probability $0.25$.  Just output $1$.  It can be shown easily that maximum success probability is at most $0.5$.  The bounds can be improved to $0.3384 \le $ maximum success probability $\le 0.361$.  Here is a protocol that achieves success probability $1/3$.
 For large $k$, the following bounds can be shown:  $0.5644 \le $ maximum success probability $\le 0.75$.
 Can we improve these bounds?

← Older revision		Revision as of 21:38, 31 March 2017
Line 4:		Line 4:
	}}		}}

		+	Cryptogenography is concerned with the following question. "How to share a secret without revealing the secret owner?" Please see Brody et al. {{cite\|BJSW-14}} and Jakobsen {{cite\|J-16}}.
		+
		+	In this problem, there are $k$ players and an eavesdropper. Input is a random bit $X \in \{0,1\}$, also called "the secret." The secret owner $J$ is chosen uniformly at random from $[k]$. Players have private randomness and they can communicate publicly on a shared blackboard visible to everyone. Players are said to win if
		+
		+	* everyone learns the secret, and
		+	* eavesdropper does not guess the secret owner correctly.
		+
		+	We are interested in maximizing the probability that players win (maximum success probability).
		+
		+	For $k=2$, the following trivial protocol has success probability $0.25$. Just output $1$. It can be shown easily that maximum success probability is at most $0.5$. The bounds can be improved to $0.3384 \le $ maximum success probability $\le 0.361$.
		+
		+	For large $k$, the following bounds can be shown: $0.5644 \le $ maximum success probability $\le 0.75$.
		+
		+	Can we improve these bounds?


	<references />		<references />