Events
Fall 2013
Big Data All Hands Meeting
Tuesday, October 1st, 2013, 12:30 pm–1:30 pm
Parent Program:
Speaker:
Justin Thaler (Harvard University) and Nikhil Srivastava (Microsoft Research India)
Location:
Calvin Lab 2nd Floor Interaction Area
Justin Thaler (Harvard University)
A Crash Course on Fast Interactive Proofs
Protocols for verifiable computation enable a computationally weak verifier to offload computations to a powerful but untrusted prover, while providing the verifier with a guarantee that the prover performed the computations correctly. Asymptotically efficient
protocols for verifiable computation have been known for several
decades in the form of interactive proofs, PCPs, and their brethren.
However, it is only very recently that these protocols have grown
efficient enough for plausible use in the real world.
In this talk, I will give a crash course on interactive proofs and the
algorithmic techniques underlying their efficient implementation.
Nikhil Srivastava (Microsoft Research India)
Interlacing Families III: Sharper Restricted Invertibility Estimates
A well-known form of Bourgain and Tzafriri's restricted invertibility
principle asserts that every matrix L with unit length columns
contains a column submatrix of size proportional to n/||L||_2^2 whose
least singular value is bounded away from zero.
We give a short, elementary proof of a sharp version of this theorem
based on the 'method of interlacing polynomials. The proof is
conceptually transparent and avoids technical calculations, relying on
classical estimates for roots of Laguerre polynomials. Moreover, it
provides an improved guarantee on the size of the invertible
submatrix, depending on the Schatten 4-norm of L rather than on the
operator norm ||L||.
Joint work with A. Marcus and D. Spielman.
