A carbon-free dissemination of ideas across the globe.

### The Spring season of TCS+ is behind us!

With John Wright‘s talk last week, the Spring ’19 season of TCS+ concluded. Thanks to all our followers who tuned in, everyone who suggested a talk or spread the word, and, of course, thanks to all our speakers!

For those who missed a talk, or would like to watch them again in the comfort of your home, institution, or on the seaside: all past talks are now uploaded and available, along with the speakers’ slides.

Have a great summer, and see you in the Fall!

### TCS+ talk: Wednesday, June 12th — John Wright, MIT

The next TCS+ talk—and last of the season!—will take place this coming Wednesday, June 12th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 18:00 Central European Time, 19:00 Central European Summer Time, 17:00 UTC). John Wright from MIT will speak about “NEEXP in MIP*” (abstract below).

Please make sure you reserve a spot for your group to join us live by signing up on the online form. As usual, for more information about the TCS+ online seminar series and the upcoming talks, or to suggest a possible topic or speaker, please see the website.

Abstract: A long-standing puzzle in quantum complexity theory is to understand the power of the class $\textsf{MIP*}$ of multiprover interactive proofs with shared entanglement. This question is closely related to the study of entanglement through non-local games, which dates back to the pioneering work of Bell. In this work we show that $\textsf{MIP*}$ contains $\textsf{NEEXP}$ (non-deterministic doubly-exponential time), exponentially improving the prior lower bound of $\textsf{NEXP}$ due to Ito and Vidick. Our result shows that shared entanglement exponentially increases the power of these proof systems, as the class $\textsf{MIP}$ of multiprover interactive proofs without shared entanglement is known to be equal to $\textsf{NEXP}$.

### TCS+ talk: Wednesday, May 29th — Lior Kamma, Aarhus University

The next TCS+ talk will take place this coming Wednesday, May 29th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 18:00 Central European Time, 19:00 Central European Summer Time, 17:00 UTC). Lior Kamma from Aarhus University will speak about “Lower Bounds for Multiplication via Network Coding” (abstract below).

Please make sure you reserve a spot for your group to join us live by signing up on the online form. As usual, for more information about the TCS+ online seminar series and the upcoming talks, or to suggest a possible topic or speaker, please see the website.

Abstract: Multiplication is one of the most fundamental computational problems, yet its true complexity remains elusive. The best known upper bound, very recently proved by Harvey and Van Der Hoven shows that two $n$-bit numbers can be multiplied via a boolean circuit of size $O(n \lg n)$.

We prove that if a central conjecture in the area of network coding is true, then any constant degree Boolean circuit for multiplication must have size $\Omega(n \lg n)$, thus (conditioned on the conjecture) completely settling the complexity of multiplication circuits. We additionally revisit classic conjectures in circuit complexity, due to Valiant, and show that the network coding conjecture also implies one of Valiant’s conjectures.

Joint work with Peyman Afshani, Casper Freksen and Kasper Green Larsen

### TCS+ talk: Wednesday, May 15th — Ewin Tang, University of Washington

The next TCS+ talk will take place this coming Wednesday, May 15th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 18:00 Central European Time, 17:00 UTC). Ewin Tang from University of Washington will tell us about “Quantum-inspired classical linear algebra algorithms: why and how?” (abstract below).

Please make sure you reserve a spot for your group to join us live by signing up on the online form. As usual, for more information about the TCS+ online seminar series and the upcoming talks, or to suggest a possible topic or speaker, please see the website.

Abstract: Over the past ten years, the field of quantum machine learning (QML) has produced many polylogarithmic-time procedures for linear algebra routines, assuming certain “state preparation” assumptions. Though such algorithms are formally incomparable with classical computing, a recent line of work uses an analogous classical model of computation as an effective point of comparison to reveal speedups (or lack thereof) gained by QML. The resulting “dequantized” algorithms assume sampling access to input to speed up runtimes to polylogarithmic in input size.

In this talk, we will discuss the motivation behind this model and its relation to existing randomized linear algebra literature. Then, we will delve into an example quantum-inspired algorithm: Gilyen, Lloyd, and Tang’s algorithm for low-rank matrix inversion. This dequantizes a variant of Harrow, Hassidim, and Lloyd’s matrix inversion algorithm, a seminal work in QML. Finally, we will consider the implications of this work on exponential speedups in QML. No background of quantum computing is assumed for this talk.

### TCS+ talk: Wednesday, May 1st — Chris Peikert, University of Michigan

The next TCS+ talk will take place this coming Wednesday, May 1st at 1:00 PM Eastern Time (10:00 AM Pacific Time, 18:00 Central European Time, 17:00 UTC). Chris Peikert from University of Michigan will speak about “Noninteractive Zero Knowledge for NP from Learning With Errors” (abstract below).

Please make sure you reserve a spot for your group to join us live by signing up on the online form. As usual, for more information about the TCS+ online seminar series and the upcoming talks, or to suggest a possible topic or speaker, please see the website.

Abstract: We finally close the long-standing problem of constructing a noninteractive zero-knowledge (NIZK) proof system for any NP language with security based on the Learning With Errors (LWE) problem, and thereby on worst-case lattice problems. Our proof system instantiates a framework developed in a series of recent works for soundly applying the Fiat—Shamir transform using a hash function family that is correlation intractable for a suitable class of relations. Previously, such hash families were based either on “exotic” assumptions (e.g., indistinguishability obfuscation or optimal hardness of ad-hoc LWE variants) or, more recently, on the existence of circularly secure fully homomorphic encryption. However, none of these assumptions are known to be implied by LWE or worst-case hardness.

Our main technical contribution is a hash family that is correlation intractable for arbitrary size-$S$ circuits, for any polynomially bounded $S$, based on LWE (with small polynomial approximation factors). Our construction can be instantiated in two possible “modes,” yielding a NIZK that is either computationally sound and statistically zero knowledge in the common random string model, or vice-versa in the common reference string model.

(This is joint work with Sina Shiehian. Paper: https://eprint.iacr.org/2019/158)

### TCS+ talk: Wednesday, April 17th — Thatchaphol Saranurak, TTIC

The next TCS+ talk will take place this coming Wednesday, April 17th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 18:00 Central European Time, 17:00 UTC). Thatchaphol Saranurak from TTI Chicago will speak about “Breaking Quadratic Time for Small Vertex Connectivity ” (abstract below).

Please make sure you reserve a spot for your group to join us live by signing up on the online form. As usual, for more information about the TCS+ online seminar series and the upcoming talks, or to suggest a possible topic or speaker, please see the website.

Abstract: Vertex connectivity is a classic extensively-studied problem. Given an integer k, its goal is to decide if an $n$-node $m$-edge graph can be disconnected by removing $k$ vertices. Although a $O(m)$-time algorithm was postulated since 1974 [Aho, Hopcroft, and Ullman], and despite its sibling problem of edge connectivity being resolved over two decades ago [Karger STOC’96], so far no vertex connectivity algorithms are faster than $O(n^2)$ time even for $k = 4$ and $m = O(n)$. In the simplest case where $m = O(n)$ and $k = O(1)$, the $O(n^2)$ bound dates five decades back to [Kleitman IEEE Trans. Circuit Theory’69]. For the general case, the best bound is $\tilde{O}( \min{ kn^2, n^\omega + nk^\omega } )$ [Henzinger, Rao, Gabow FOCS’96; Linial, Lovász, Wigderson FOCS’86].

In this talk, I will present a randomized Monte Carlo algorithm with $\tilde{O}(m + k^3 n)$ time. This algorithm proves the conjecture by Aho, Hopcroft, and Ullman when $k=O(1)$ up to a polylog factor, breaks the 50-year-old bound by Kleitman, is fastest for $4 < k < n^{0.456}$. The story is similar for the directed graphs where we obtain an algorithm running time at most $\tilde{O}(k^2 m)$.

The key to our results is to avoid computing single-source connectivity, which was needed by all previous exact algorithms and is not known to admit $o(n^2)$ time. Instead, we design the first local algorithm for computing vertex connectivity; without reading the whole graph, our algorithm can find a separator of size at most $k$ or certify that there is no separator of size at most $k$ “near” a given seed node.

This talk is based on joint works with Danupon Nanongkai and Sorrachai Yingchareonthawornchai.

### TCS+ talk: Wednesday, April 3rd — Richard Peng, Georgia Tech

The next TCS+ talk will take place this coming Wednesday, April 3rd at 1:00 PM Eastern Time (10:00 AM Pacific Time, 18:00 Central European Time, 17:00 UTC). Richard Peng from Georgia Tech will speak about “Fully Dynamic Spectral Vertex Sparsifiers and Applications” (abstract below).

Please make sure you reserve a spot for your group to join us live by signing up on the online form. As usual, for more information about the TCS+ online seminar series and the upcoming talks, or to suggest a possible topic or speaker, please see the website.

Abstract: Problems arising from analyzing and understanding graph structures have motivated the development of many powerful tools for storing and compressing graphs and networks. Many, if not most, of these massive graphs are accumulations of updates over time. Maintaining updates and queries on dynamically changing graphs more efficiently than recomputing from scratch is a well-studied topic, with several important open problems related to global, optimization related queries.

We study dynamic graph algorithms for maintaining spectral vertex sparsifiers with respect to a subset of terminal vertices. Such sparsifiers preserve key structures in spectral algorithms, including effective resistances (which can be viewed as a numerical generalization of connectivity), solutions to systems of Laplacian linear equations, and energy of electrical flows between terminal vertices. We give data structures that maintain, in sublinear time, these sparsifiers under insertions/deletions of edges, as well as terminal additions.

This primitive in turn leads to sublinear time data structures for key primitives in spectral graph algorithms, including ones at the core of the “Laplacian paradigm” for designing graph optimization algorithms. In particular, we obtain $O(m^{4/3}\epsilon^{-4})$ time per query/update for effective resistances on unweighted graphs, and $O(n^{11/12}\epsilon^{-5})$ time per query/update for implicit access to linear system solutions, where $\epsilon$ is the relative approximation accuracy.

The majority of the talk will focus on key components of this data structure: (1) an interpretation of vertex sparsifiers as a sum of random walks, (2) a suitable choice of terminals to keep these walks local, and (3) maintenance of local walks and numerical solutions. Potential avenues in generalizing these techniques to provide new building blocks for dynamic graph algorithms will also be discussed.