TCS+

A carbon-free dissemination of ideas across the globe.

TCS+ talk: Wednesday, February 28th — Sanjam Garg, UC Berkeley

The next TCS+ talk will take place this coming Wednesday, February 28th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 18:00 UTC). Sanjam Garg from UC Berkeley will speak about “Identity-Based Encryption from the Diffie-Hellman Assumption” (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: In this talk, I will describe new constructions of identity-based encryption based on the hardness of the Diffie-Hellman (without using groups with pairings) Problem. Previously, constructions based on this assumption were believed to be impossible. Our construction is based on new techniques that bypass the known impossibility results using garbled circuits that make a non-black-box use of the underlying cryptographic primitives.

(Based on joint work with Nico Döttling.)

Advertisements

TCS+ talk: Wednesday, February 14th — Dor Minzer, Tel-Aviv University

The next TCS+ talk will take place this coming Wednesday, February 14th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 18:00 UTC). Dor Minzer from Tel-Aviv University will speak about “2-to-2 Games via expansion on the Grassmann Graph” (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 fundamental goal in the theory of PCPs asks whether a special type of PCP, namely 2-to-2 Games, exists. This is a variant of Khot’s well-known Unique Games conjecture.

In this talk we will discuss a recent line of study establishing the 2-to-2 games conjecture, albeit with imperfect completeness.
At the heart of the approach lies an object called the Grassmann Graph, and a certain linearity test on it.
This leads to the study of edge expansion in this graph, and in particular, the study of (small) sets of vertices in the Grassmann Graph, whose edge expansion is bounded away from 1.

Based on joint works with Irit Dinur, Subhash Khot, Guy Kindler and Muli Safra

TCS+ talk: Wednesday, January 31st — Avi Wigderson, IAS

The first TCS+ talk of the new year will take place this coming Wednesday, January 31st at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 18:00 UTC). We’re honored to have Avi Wigderson from IAS as our speaker; Avi will speak about “Optimization, Complexity and Math (through the lens of one problem and one algorithm)” (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: In this lecture, we introduce and motivate the main characters in this plot:
– Singularity of symbolic matrices: a basic problem in both computational complexity.
– Alternating Minimization: a basic heuristic in non-convex optimization.

I will explain how variants of this algorithm are applied to variants of this problem, how they are analyzed, and how the analysis gives rise to problems in and connections between a surprisingly diverse set of mathematical areas, including quantum information theory, non-commutative algebra and invariant theory, and analysis. Time permitting, we will discuss challenges this work raises in invariant theory and non-convex optimization.

Last four talks of the semester

Hi everyone,

we have posted the last four talks of the semester.

Happy holidays and make sure to stop by the next semester!

TCS+ talk: Wednesday, December 13th — Sebastien Bubeck, MSR

The last TCS+ talk of the Fall will take place this coming Wednesday, December 13th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 18:00 UTC). Sebastien Bubeck from MSR will speak about his recent breakthrough with Michael B. Cohen, James R. Lee, Yin Tat Lee, and Aleksander Madry on “k-server via multiscale entropic regularization”  (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 start by describing how mirror descent is a natural strategy for online decision making, specifically in online learning and metrical task systems. To motivate the k-server problem I will also briefly recall what we know and what we don’t know for structured state/action spaces in these models. Using the basic mirror descent calculations I will show how to easily obtain a log(k)-competitive algorithm for k-paging. I will then introduce our new parametrization of fractional k-server on a tree, and explain how to analyze the movement cost of entropy-regularized mirror descent on this parametrization. This leads to a depth*log(k)-competitive (fractional) algorithm for general trees, and log^2(k) for HSTs. I will also briefly mention dynamic embeddings to go beyond the standard log(n) loss in the reduction from general metrics to HSTs.

Joint work with Michael B. Cohen, James R. Lee, Yin Tat Lee, and Aleksander Madry.

TCS+ talk: Wednesday, November 29th — Jon Kelner, MIT

Many of you will be aware of the recent passing away of MIT graduate student Michael Cohen. At TCS+ we had asked Michael to give a talk; although he responded positively, he had also told us he’d want to wait for a really cool result to tell us all about.

The next TCS+ talk is dedicated to Michael’s memory. The talk will be given by Jon Kelner, from MIT, on work in which Michael played an important part (title and abstract below).

The talk will take place this coming Wednesday, November 29th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 18:00 UTC). Jon Kelner will speak about “Almost-Linear-Time Algorithms for Markov Chains and New Spectral Primitives for Directed Graphs“.

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: In the analysis of Markov chains, there has been a longstanding algorithmic gap between the general case, corresponding to random walks on directed graphs, and the special case of reversible chains, for which the corresponding graph can be taken to be undirected. This begins with the most basic computational task, computing the stationary distribution, and persists for many of the fundamental problems associated with random walks, such as computing hitting and commute times, escape probabilities, and personalized PageRank vectors. In the undirected case, there are algorithms for all of these problems that run in linear or nearly-linear time, whereas it was unknown in the directed case whether one could solve any of them more efficiently than an arbitrary linear system.

More broadly, this gap has its origins in a substantial discrepancy between the state of algorithmic spectral graph theory in the undirected and directed settings. While the undirected case has a richly developed theory and a powerful collection of algorithmic tools, similar results have remained elusive for directed graphs.

In this talk, I will begin to address this by giving an algorithmic framework that solves all of the problems listed above in almost-linear time. To do so, I will develop the first directed versions of several foundational primitives from undirected algorithmic spectral graph theory that had not been known to exist for directed graphs, notably including the first directed version of graph sparsification and an almost-linear-time solver for directed Laplacian systems. If time permits, I will also briefly discuss more recent work that improves the running time to be nearly linear, thereby eliminating the gap between the undirected and directed versions of these problems (up to polylogarithmic factors).

This talk is based on work with Michael Cohen, Rasmus Kyng, John Peebles, Richard Peng, Anup Rao, Aaron Sidford, and Adrian Vladu.

TCS+ talk: Wednesday, November 15th — Vinod Vaikuntanathan, MIT

The next TCS+ talk will take place this coming Wednesday, November 15th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 18:00 UTC). Vinod Vaikuntanathan from MIT will speak about “Program Obfuscation and Random CSPs: The Love-Hate Relationship” (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 recent line of work shows how to construct indistinguishability obfuscation under two assumptions: (a) that there exist k-linear maps for some constant k; and (b) that certain random O(k)-constraint satisfaction problems (CSPs) are hard in an appropriate sense. The latest of these works (by Lin and Tessaro) assumes the existence of 3-linear maps and the hardness of certain random 3-CSPs. We have 1-linear maps since the 1970s; 2-linear maps since the 1990s; but the existence of 3-linear maps is wide open. On the other hand, we do have reasonable constructions of “secure” random 3-CSPs. The first part of the talk will describe these developments.

Much more surprising was a result (from the same work of Lin and Tessaro) which showed a construction from 2-linear maps and the hardness of random 2-CSPs over a large alphabet. Overnight, the burden of existence of IO went from the question of whether 3-linear maps exist to the completely unrelated question of whether random 2-CSPs over large alphabets is hard. In a nutshell, they require the existence of pseudo-random generators G: \Sigma^n \to {0,1}^m for some poly(n)-size alphabet \Sigma where each output bit depends on at most two input alphabet symbols, and which achieve sufficiently large stretch. In the second part of the talk, we will present a polynomial-time algorithm that breaks these random CSPs.

Based on joint work with Alex Lombardi (MIT) and Rachel Lin (UCSB).