Add build system. Write most of the introduction.

[doc/wrestlers] / wr-backg.tex

diff --git a/background.tex b/wr-backg.tex
similarity index 99%
rename from background.tex
rename to wr-backg.tex
index f2a6554..d08fe6d 100644 (file)
--- a/background.tex
+++ b/wr-backg.tex
@@ -321,8 +321,8 @@
   \item Soundness: if $P^*$ convinces $V$ with probability $p > \frac{1}{2}$
     then we can, in theory, run $P^*$ with (say) $c = 0$ and get $\gamma$.
     We then \emph{rewind} $P^*$, give it $c = 1$, and get $\gamma \beta$,
-    from which we compute $\beta$.  This works with probability at least $p -
-    \frac{1}{2}$.
+    from which we compute $\beta$.  This works with probability at least $2
+    (p - \frac{1}{2})$.
   \end{itemize}
 \end{slide}
 
@@ -339,7 +339,7 @@ guaranteed to lose.
 
 On the other hand, if $n > r$, there must be a winning row, because there are
 too many ones to fit otherwise.  In fact, there must be at least $n - r$
-winning rows.  So our probability of winning must be at least $(n - r)/2r$.
+winning rows.  So our probability of winning must be at least $(n - r)/r$.
 
 Apply this to the problem of our dishonest prover.  The `table''s rows are
 indexed by all the possible inputs to the prover -- the value $\alpha$ and
@@ -347,7 +347,7 @@ its own internal coin tosses.  (We only consider provers running in bounded
 time, so these are finite.)  The columns are indexed by our coin $c$.  We
 know that $2 r p$ of the entries contain $1$.  Hence, the probability that we
 win is at least
-\[ \frac{2 r p - r}{2 r} = p - \frac{1}{2}. \]
+\[ \frac{2 r p - r}{r} = 2 \biggl( p - \frac{1}{2} \biggr). \]
 
 \begin{slide}
   \head{Zero-knowledge \seq: an example (cont.)}