Robust Coin Flipping
Gene Kopp and John Wiltshire-Gordon
University of Chicago
gkopp@uchicago.edu
jwiltshiregordon@uchicago.edu

August 16, 2011

G. Kopp & J. Wiltshire-Gordon (UChicago)

Robust Coin Flipping

August 16, 2011

1 / 18

The Problem

G. Kopp & J. Wiltshire-Gordon (UChicago)

Robust Coin Flipping

August 16, 20112 / 18

The Problem

G. Kopp & J. Wiltshire-Gordon (UChicago)

Robust Coin Flipping

August 16, 20112 / 18

The Problem

G. Kopp & J. Wiltshire-Gordon (UChicago)

Robust Coin Flipping

August 16, 20112 / 18

The ProblemG. Kopp & J. Wiltshire-Gordon (UChicago)

Robust Coin Flipping

August 16, 2011

3 / 18

The Problem

G. Kopp & J. Wiltshire-Gordon (UChicago)

Robust Coin Flipping

August 16, 2011

3 / 18

The Problem

G. Kopp & J. Wiltshire-Gordon (UChicago)

Robust Coin Flipping

August 16, 2011

3 / 18

The Problem

G. Kopp & J. Wiltshire-Gordon (UChicago)

Robust Coin Flipping

August 16, 2011

3 / 18

Results

G. Kopp & J. Wiltshire-Gordon (UChicago)

Robust Coin Flipping

August 16, 2011

4 / 18

Results

G. Kopp & J. Wiltshire-Gordon (UChicago)

Robust Coin Flipping

August 16, 2011

4 / 18

Results

G. Kopp & J. Wiltshire-Gordon (UChicago)

Robust Coin Flipping

August 16, 2011

4 / 18

Results

G. Kopp & J. Wiltshire-Gordon (UChicago)

Robust Coin Flipping

August 16, 2011

4 / 18

Results

G. Kopp & J. Wiltshire-Gordon (UChicago)

Robust Coin Flipping

August 16, 2011

4 / 18

Results
Theorem (KW)
Alice has access to p = q + r indistinguishable random
oracles, q unreliable and r reliable.
For r = 0, Alice can simulate only an always-heads
or always-tails coin.
For 0 < q ≤ r , any rational bias α is possible, andnothing else.
For q > r > 0, any algebraic probability α ispossible, and nothing else.
For q = 0 and r > 0, any bias is possible.
G. Kopp & J. Wiltshire-Gordon (UChicago)

Robust Coin Flipping

August 16, 2011

5 / 18

Algebraic α?
Q: Why would anyone want to choose anything withirrational probabilities?

G. Kopp & J. Wiltshire-Gordon (UChicago)

Robust Coin Flipping

August 16, 2011

6 / 18

Algebraic α?
Q: Why would anyone want to choose anything withirrational probabilities?
A: Shows up in applications (e.g. Nash equilibria).

G. Kopp & J. Wiltshire-Gordon (UChicago)

Robust Coin Flipping

August 16, 2011

6 / 18

Algebraic α?
Q: Why would anyone want to choose anything withirrational probabilities?
A: Shows up in applications (e.g. Nash equilibria).
Q: Why don’t we just approximate by rationals?

G. Kopp & J. Wiltshire-Gordon (UChicago)

Robust Coin Flipping

August 16, 2011

6 / 18

Algebraic α?
Q: Why would anyone want to choose anything withirrational probabilities?
A: Shows up in applications (e.g. Nash equilibria).
Q: Why don’t we just approximate by rationals?
A: If Alice simulates an (a/b)-biased bit, hercommunication with the oracles and her
computation of the bit will both be linear in log b.

G. Kopp & J. Wiltshire-Gordon (UChicago)

Robust Coin Flipping

August 16, 2011

6 / 18

Algebraic α?
Q: Why would anyone want to choose anything withirrational probabilities?
A: Shows up in applications (e.g. Nash equilibria).
Q: Why don’t we just approximate by rationals?
A: If Alice simulates an (a/b)-biased bit, hercommunication with the oracles and her
computation of the bit will both be linear in log b.
In our solution (without rational approximation),
Alice’s communication and computation stay
constant even as her desired accuracy increases.
G. Kopp & J. Wiltshire-Gordon (UChicago)

Robust Coin Flipping

August 16, 2011

6 / 18

A Basic Example 







⊗



G. Kopp & J. Wiltshire-Gordon (UChicago) =⊗⊗⊗⊗⊗⊗⊗⊗⊗⊗⊗⊗Robust Coin Flipping

August 16, 20117 / 18

A Basic Example 1/6

1/6 1/6
 ⊗ P(1/6 1/6 ) P( ) = 



1/6

G. Kopp & J. Wiltshire-Gordon (UChicago)

1P(61P(61P(61P(61P(61P(6))))))

Robust Coin Flipping

1P(61P(61P(61P(61P(61P(6))
)
)))August 16, 20118 / 18

A Basic Example


1P(61P(61P(61P(61P(61P(6))))))

1P(61P(61P(61P(61P(61P(6 ))
 )·) ) )G. Kopp & J. Wiltshire-Gordon (UChicago)




=


Robust Coin Flipping12



P ( )+P ( ) 
1
P ( )+P ( )2August 16, 2011+9 / 18

A Basic Example

1P(61P(61P(61P(61P(61P(6))))))

1P(61P(61P(61P(61P(61P(6 ))
 )·) ) )G. Kopp & J. Wiltshire-Gordon (UChicago)




=1
 2



Robust Coin Flipping+ 12

August 16, 201110 / 18

A Basic Example

P(P (P (P (P (P()))
⊗)
)
)

1/2

G. Kopp & J. Wiltshire-Gordon (UChicago) 1/2=

1P(21P(21P(21P(21P(21P(2))))))

Robust Coin Flipping

1P(21P(21P(21P(21P(21P(2))
)
))
)August 16, 2011






11 / 18

A Basic Example





1P(21P(21P(21P(21P(21P(2))))))

1P(21P(21P(21P(21P(21P(2 ))
 )·) ) )G. Kopp & J. Wiltshire-Gordon (UChicago)



=


Robust Coin Flipping

12(P ( )+. . .+P ( )) +(P ( )+. . .+P ( ))12

August 16, 201112 / 18

A Basic Example










1P(21P(21P(21P(21P(21P(2))))))

1P(21P(21P(21P(21P(21P(2 ))
 )·) ) )G. Kopp & J. Wiltshire-Gordon (UChicago)
=1 2

Robust Coin Flipping+ 12

August 16, 201113 / 18

Rational α Is Easy
Say α = ba .

G. Kopp & J. Wiltshire-Gordon (UChicago)

Robust Coin Flipping

August 16, 201114 / 18

Rational α Is Easy
Say α = ba .
Alice asks party i to pick uniformly a randomxi ∈ Z/bZ.

G. Kopp & J. Wiltshire-Gordon (UChicago)

Robust Coin Flipping

August 16, 201114 / 18

Rational α Is Easy
Say α = ba .
Alice asks party i to pick uniformly a randomxi ∈ Z/bZ.
p
X
Heads ifxi ∈ {0, ..., a − 1}; tails otherwise.
i=1

G. Kopp & J. Wiltshire-Gordon (UChicago)

Robust Coin Flipping

August 16, 201114 / 18

Rational α Is Easy
Say α = ba .
Alice asks party i to pick uniformly a randomxi ∈ Z/bZ.
p
X
Heads ifxi ∈ {0, ..., a − 1}; tails otherwise.
i=1

Works as long as q < p.

G. Kopp & J. Wiltshire-Gordon (UChicago)

Robust Coin Flipping

August 16, 201114 / 18Multilinear Algebra
For p = 3, q = 1, we want to find a {0, 1}-hypermatrix
A and probability vectors β (i) such that, for all
probability vectors x (i) ,A(x (1) , β (2) , β (3) ) = A(β (1) , x (2) , β (3) ) = A(β (1) , β (2) , x (3) ) = α.

G. Kopp & J. Wiltshire-Gordon (UChicago)

Robust Coin Flipping

August 16, 201115 / 18

Multilinear Algebra
For p = 3, q = 1, we want to find a {0, 1}-hypermatrix
A and probability vectors β (i) such that, for all
probability vectors x (i) ,A(x (1) , β (2) , β (3) ) = A(β (1) , x (2) , β (3) ) = A(β (1) , β (2) , x (3) ) = α.

So, αJ − A is degenerate in the sense of Gelfand,Kapranov, and Zelevinsky, and the theory of complex
projective duality and stratification shows that α lies ona zero-dimensional variety defined over Q. But positive
results are more fun. . .
G. Kopp & J. Wiltshire-Gordon (UChicago)

Robust Coin Flipping

August 16, 201115 / 18

Multilinear Algebra!

1 0 10 0 1
1 1 0
0 1 1√√ 11=5)5)(−1+(3−√22 15)
2 (3 − √=15)
2 (−1 +√√√ 
111=(5−5)(5−5)
10105 5

A =
β (1)
β (2)
β (3)

G. Kopp & J. Wiltshire-Gordon (UChicago)

Robust Coin Flipping

August 16, 201116 / 18

α= ?

G. Kopp & J. Wiltshire-Gordon (UChicago)

Robust Coin Flipping

August 16, 201117 / 18

Read our paper!
Play around with our code!
arxiv.org/abs/1009.4188

G. Kopp & J. Wiltshire-Gordon (UChicago)

Robust Coin Flipping

August 16, 201118 / 18