[CSDM] TCS lectures today

[Avi Wigderson]

11:15 IAS         - Michael Rabin
4:30 PACM, PU - Dan Spielman

-------------------

Cryptography and Preventing Collusion in Second Price (Vickery) Auctions

                Michael Rabin

  

We present practically efficient methods for proving correctness of announced results of a

computation while keeping input and intermediate values information theoretically secret. These

methods are applied to solve the long standing problem of preventing collusion in second-price

auctions.

  

Second Price auctions, where the highest bidder gets the item and pays the second highest bid value,

are theoretically advantageous to the Seller. Namely, absent collusion between bidders, a

participant's best strategy is to bid his true private value for the item. In practice, however,

Vickery auctions are rarely used because of possibility of collusion amongst bidders. The above

secrecy preserving proofs of correctness are enhanced to enable uncontrollable and deniable

submission of bids in our collusion prevention mechanism. Joint work with Silvio Micali.



-------------

  

*Speaker:*Daniel Spielman, Yale University
*Title:*A good lift: bipartite Ramanujan graphs of all degrees
*Abstract:*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.

  

  

  

  


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://imap.math.ias.edu/pipermail/csdm/attachments/20130429/908e22d2/attachment.html>