A carbon-free dissemination of ideas across the globe.

TCS+ talk: Wednesday, September 25 — Mark Sellke, Stanford

The next TCS+ talk will take place this coming Wednesday, September 25th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). Mark Sellke from Stanford will speak about “Chasing Convex Bodies” (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: I will explain our recent understanding of the chasing convex bodies problem posed by Friedman and Linial in 1991. In this problem, an online player receives a request sequence $K_1,\dots,K_T$ of convex sets in $d$ dimensional space and moves his position online into each requested set. The player’s movement cost is the length of the resulting path. Chasing convex bodies asks if there an online algorithm with cost competitive against the offline optimal path. This is both an challenging metrical task system and (equivalent to) a competitive analysis view on online convex optimization.

This problem was open for $d>2$ until last year but has recently been solved twice. The first solution gives a $2^{O(d)}$ competitive algorithm while the second gives a nearly optimal $\min(d,\sqrt(d\log(T)))$ competitive algorithm for $T$ requests. The latter result is based on the Steiner point, which is the exact optimal solution to a related geometric problem called Lipschitz selection and dates from 1840. In the talk, I will briefly outline the first solution and fully explain the second.

Partially based on joint works with Sébastien Bubeck, Bo’az Klartag, Yin Tat Lee, and Yuanzhi Li.

The Fall season of TCS+ is upon us!

With the summer winding down, the Fall ’19 season of TCS+ is coming fast! We’re excited to bring to you, over the next few months, great speakers and amazing results, right into the comfort of your home institution (or home home, for that matter).

As a teaser, here are the first three talks of the season:

• Mark Sellke (Stanford) will tell us, on September 25th, about his recent work on Chasing Convex Bodies.
• Shachar Lovett (UCSD) will on October 9th present his new results on the Sunflower Lemma.
• Hao Huang (Emory University) will talk on October 22nd (note: a Tuesday) about his recent proof of the Sensitivity Conjecture.

Stay tuned for those, and the following!

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)