Workshop Details

Edit distance is a widely used measure of similarity of two strings based on the minimum number of character insertions, deletions, and substitutions required to transform one string into the other. The edit distance can be computed exactly using a classical dynamic programming algorithm that runs in quadratic time. No known algorithm improves on quadratic running time by more than a polylogarithmic factor, and Backurs and Indyk showed that a truly subquadratic time algorithm (running in time O(n^(2-a)) for some a>0) would violate the Strong Exponential Time Hypothesis (SETH).

Even if we ask only for an algorithm that approximates edit distance to within a constant factor, no truly subquadratic algorithm was known. In this talk I will describe recent work, joint with Diptarka Chakroborty, Debarati Das, Elazar Goldenberg, and Michal Koucky giving such an algorithm.

Linear dynamical systems, a.k.a. Kalman filtering, are a class of time-series models widely used in robotics, finance, engineering, and meteorology. In its general form (unknown system), learning LDS is a classic non-convex problem, typically tackled with heuristics like gradient descent ("backpropagation through time") or the EM algorithm. I will present our new "spectral filtering" approach to the identification and control of discrete-time general linear dynamical systems with multi-dimensional inputs, outputs, and a latent state. This approach yields a simple and efficient algorithm for low-regret prediction (i.e. asymptotically vanishing MSE) as well as finite-time control.

Based on work with Karan Singh and Cyril Zhang, and follow up works with Holden Lee, Yi Zhang and Sanjeev Arora.

In this talk, I will present new constructions of publicly verifiable non-interactive delegation schemes, under (polynomial) falsifiable assumptions over bilinear groups. These schemes are in the common reference string (CRS) model, where the CRS is long (polynomial in the running time of the computation).

The first scheme is based on a decisional assumption, and supports any deterministic polynomial time computation. It is obtained by converting the delegation scheme of Kalai, Raz and Rothblum (STOC 2014) into a publicly verifiable one by constructing a homomorphic encryption scheme with a weak zero-test, a paradigm suggested by Paneth and Rothblum (TCC 2017). The second scheme is based on a (constant size) search assumption, but only supports log-space uniform circuits of bounded depth. It is obtained by converting the interactive delegation scheme of Goldwasser, Kalai and Rothblum (J. ACM 2015) into a non-interactive one, by replacing the sum-check protocol with a publicly verifiable non-interactive one.

Prior to this work, publicly verifiable non-interactive delegation schemes were only known under knowledge assumptions (or in the Random Oracle model), or under non-standard assumptions related to obfuscation or multilinear maps.

This is joint work with Omer Paneth and Lisa Yang.

We present the first protocol allowing a classical computer to interactively verify the result of an efficient quantum computation. We achieve this by constructing a measurement protocol, which allows a classical string to serve as a commitment to a quantum state. The protocol forces the prover to behave as follows: the prover must construct an n qubit state of his choice, measure each qubit in the Hadamard or standard basis as directed by the verifier, and report the measurement results to the verifier. The soundness of this protocol is enforced based on the assumption that the learning with errors problem is computationally intractable for efficient quantum machines. This talk will not assume prior knowledge of quantum computing or cryptography.