<html>
<head>
<meta http-equiv="content-type" content="text/html; charset=UTF-8">
</head>
<body bgcolor="#FFFFFF" text="#000000">
11:15 IAS - Michael Rabin<br>
4:30 PACM, PU - Dan Spielman<br>
<br>
-------------------<br>
<pre><span>Cryptography and Preventing Collusion in Second Price (Vickery) Auctions</span></pre>
<pre><span> Michael Rabin</span></pre>
<pre><span> </span></pre>
<pre><span>We present practically efficient methods for proving correctness of announced results of a</span></pre>
<pre><span>computation while keeping input and intermediate values information theoretically secret. These</span></pre>
<pre><span>methods are applied to solve the long standing problem of preventing collusion in second-price</span></pre>
<pre><span>auctions.</span></pre>
<pre><span> </span></pre>
<pre><span>Second Price auctions, where the highest bidder gets the item and pays the second highest bid value,</span></pre>
<pre><span>are theoretically advantageous to the Seller. Namely, absent collusion between bidders, a</span></pre>
<pre><span>participant's best strategy is to bid his true private value for the item. In practice, however,</span></pre>
<pre><span>Vickery auctions are rarely used because of possibility of collusion amongst bidders. The above</span></pre>
<pre><span>secrecy preserving proofs of correctness are enhanced to enable uncontrollable and deniable</span></pre>
<pre><span>submission of bids in our collusion prevention mechanism. Joint work with Silvio Micali.
-------------
</span></pre>
<pre><span>
</span><meta charset="utf-8"></pre>
<table style="color: rgb(0, 0, 0); font-family: Geneva, Arial,
Helvetica, sans-serif; font-size: 12px; font-style: normal;
font-variant: normal; font-weight: normal; letter-spacing: normal;
line-height: normal; orphans: auto; text-align: left; text-indent:
0px; text-transform: none; white-space: normal; widows: auto;
word-spacing: 0px; -webkit-text-size-adjust: auto;
-webkit-text-stroke-width: 0px;" border="0" cellpadding="0"
cellspacing="0" width="100%">
<tbody>
<tr>
<td class="colloq" style="font-size: 12px; padding-top: 5px;
padding-bottom: 5px;"><strong>Speaker:</strong><span
class="Apple-converted-space"> </span>Daniel Spielman,
Yale University</td>
</tr>
<tr>
<td class="colloq" style="font-size: 12px; padding-top: 5px;
padding-bottom: 5px;"><strong>Title:<span
class="Apple-converted-space"> </span></strong>A good
lift: bipartite Ramanujan graphs of all degrees</td>
</tr>
<tr>
<td class="colloq" style="font-size: 12px; padding-top: 5px;
padding-bottom: 5px;"><strong>Abstract:</strong><span
class="Apple-converted-space"> </span>We prove that there
exist infinite families of bipartite Ramanujan graphs of
every degree bigger than 2. We do this by proving a variant
of a conjecture of Bilu and Linial about the existence of
good 2-lifts of every graph. We also construct infinite
families of `irregular Ramanujan' graphs, whose eigenvalues
are bounded by the spectral radius of their universal cover.
In particular, we construct infinite families of
(c,d)-biregular bipartite Ramanujan graphs for all c and d
greater than 2. Our proof exploits a new technique for
demonstrating the existence of useful combinatorial objects
that we call the ``Method of Interlacing Polynomials''. The
proofs are elementary, and the talk should be accessible to
a broad audience. Joint work with Adam Marcus and Nikhil
Srivastava.</td>
</tr>
</tbody>
</table>
<pre>
</pre>
<pre><span> </span></pre>
<pre><span> </span></pre>
<pre><span> </span></pre>
<pre><span> </span></pre>
<br>
</body>
</html>