Invited Tutorial Speakers

STOC 2018 will have three invited tutorial speakers:

Monika Henzinger

Monika Henzinger is Professor at the University of Vienna, Austria, heading the research group of Theory and Applications of Algorithms.

Time and Location: Monday, June 25, 9:00-11:00 am, Bunker Hill/Watercourt.

Title: The State of the Art in Dynamic Graph Algorithms

Overview: A dynamic graph algorithm is a data structure that maintains a property of the graph such as its dense subgraphs as the graph is modified through a sequence of edge insertions and deletions. Dynamic graph algorithms are useful (1) on their own, for example to maintain clusters in huge graphs, such as social networks, and (2) as a data structure in a static graph algorithm, for example to maintain an s-t shortest path in the residual graph while a (static) s-t maximum flow algorithm modifies the residual graph. Designing efficient dynamic graph algorithms has been an active research area since the 80s, with a sequence of breakthrough upper and lower bounds in recent years. We give a survey of these results.

Vinod Vaikuntanathan

Vinod Vaikuntanathan is an Associate Professor in the EECS department at MIT.

Time and Location: Monday, June 25, 9:00-11:00 am, Museum A/B.

Title: The Last Five Years of Program Obfuscation

Overview: Program obfuscation is the task of compiling a machine (a circuit, Turing machine or RAM machine) into one that (a) has the same input/output functionality and yet (b) “hides the inner workings” of the original machine. A particular formalization of what it means to “hide the inner workings”, called indistinguishability obfuscation (henceforth IO) has recently become quite popular because it does not suffer from impossibility results that plague other definitions, has some candidate constructions, and has a huge number of applications both in and out of cryptography. In this talk, I will outline the most important developments in program obfuscation in the last five plus years including:

• Constructing Obfuscation: do obfuscating compilers (IO schemes) exist, and under what computational hardness assumptions? This is a (perhaps the) big open question in cryptography, although much progress has been made.

• Using Obfuscation: what applications (cryptographic or otherwise) does IO enable? We now have a rich toolkit to use IO to realize “essentially any conceivable” cryptographic application, and some outside crypto, e.g., in demonstrating (even average case) hard PPAD problems.

• Removing the need for Obfuscation: We now have a steady stream of results de-IO-izing applications that were originally built assuming IO, in particular constructing them from standard hardness assumptions. Thus, regardless of the answer to the first question (“does IO exist”), I will argue that the “obfuscation lens” teaches us much that is valuable about cryptography and complexity theory.

Umesh Vazirani

Umesh Vazirani is the Roger A. Strauch Professor of EECS at UC Berkeley and the Director of the Berkeley Quantum Computation Center.

Time and Location: Monday, June 25, 9:00-11:00 am; Hershey/Crocker.

Title: The Quantum Wave in Complexity and Cryptography

Overview: The rapid progress in the experimental realization of quantum computers comes with major algorithmic challenges for theoretical computer science --- what are the computational problems that can be solved on near term quantum computers and how can we even test such computers. There have been recent breakthroughs that have led to protocols for certified random numbers, quantum fully homomorphic encryption schemes and a proof of the games version of the quantum PCP theorem. There are deep new connections to cryptography and complexity theory, and in this tutorial I will talk about the basic building blocks and concepts underlying these results.