(Revised) Program:

Time and Place: February 27, 2015 (12:00-4:00)

Location: Star Conference Room, MIT 32-D463

• 12:00-12:30: Lunch
• 12:30-1:10: Sergey Gorbunov: Cryptographic Tools for the Cloud
  For centuries, cryptography played a crucial role in establishing secure communication between people, institutions and governments. The security of Internet relies on strong foundations of standard cryptographic tools, such as encryption and signature schemes. However, these tools are insufficient to secure the cloud-based world, where large data and programs are stored, processed and shared with many users through the cloud.

  In this talk, I will describe a new set of cryptographic tools that I developed enabling new possibilities for securing data and programs in the cloud. I built solutions that allow users to efficiently share data (or partial information about the data) with multiple receivers (a.k.a. functional encryption), protocols for verifiable computation and schemes for obfuscating programs. The security of my constructions relies on hard lattice problems, believe to be intractable even for quantum adversaries. This talk will primarily focus on the functional encryption.

• 1:15-1:55: Alan Guo: Do you even lift? The lifted Reed-Solomon code
  Error correcting codes have been widely used for protecting information from noise. The theory of error correcting codes studies the range of parameters achievable by such codes, as well as the efficiency of algorithms for encoding and decoding them. In recent years, attention has focused on the study of sublinear-time algorithms for various classical problems, such as decoding and membership verification.

  We present a new code, the "lifted Reed-Solomon code", a natural supercode of the well-known Reed-Muller code with the same distance and vastly greater rate. Our code naturally supports local algorithms such as local correction and testing. In fact, it is the first high-rate code known to be simultaneously locally decodable (up to half the minimum distance) and locally testable. Moreover, it is locally list-decodable up to the Johnson bound.

• 2:00-2:30: Coffee break
• 2:30-3:10: Aaron Sidford: Linear Programming Beyond the Universal Barrier and Faster Algorithms for the Maximum Flow Problem
  In this talk I will present a new algorithm for solving linear programs. Given a linear program with n variables, m > n constraints, and bit complexity L, our algorithm runs in Õ(sqrt(n) L) iterations each consisting of solving Õ(1) linear systems and additional nearly linear time computation. Our method improves upon the convergence rate of previous state-of-the-art linear programming methods which required solving either Õ(sqrt(m)L) linear systems [R88] or consisted of Õ(mn)^(1/4)) steps of more expensive linear algebra [VA93].

  Interestingly, our algorithm not only nearly matches the convergence rate of the universal barrier of Nesterov and Nemirovskii [NN94], but in the special case of the linear programming formulation of various flow problems our methods converge at a rate faster than that predicted by any self-concordantbarrier. In particular, we achieve a running time of Õ(E| sqrt(|V| log^2 U) for solving the maximum flow problem on a directed graph with |E| edges, |V| vertices, and capacity ratio U, thereby improving upon the previous fastest running time for solving this problem when |E| > Omega(|V|^1+epsilon) for any constant epsilon.

• 3:15-3:55: Break.
• 4:00 : Adjourn, to the CookieFest.