TCS+

A carbon-free dissemination of ideas across the globe.

TCS+ talk: Wednesday, November 6 — Ryan O’Donnell, CMU

The next TCS+ talk will take place this coming Wednesday, November 6th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 18:00 UTC). Ryan O’Donnell from CMU will speak about “Explicit near-Ramanujan graphs of every degree” (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: For every constant d and \varepsilon, we give a deterministic \text{poly}(n)-time algorithm that outputs a d-regular graph on \approx n vertices that is \varepsilon-near-Ramanujan; i.e., its eigenvalues are bounded in magnitude by 2\sqrt(d-1) + \varepsilon (excluding the single trivial eigenvalue of d).

Joint work with Sidhanth Mohanty (Berkeley) and Pedro Paredes (CMU).

TCS+ talk: Tuesday, October 22 — Hao Huang, Emory University

The next TCS+ talk will take place this coming Tuesday, October 22th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC) (note the unusual day). Hao Huang from Emory University will speak about “A proof of the Sensitivity Conjecture” (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 the n-dimensional hypercube graph, one can easily choose half of the vertices such that they induce an empty graph. However, having even just one more vertex would cause the induced subgraph to contain a vertex of degree at least \sqrt{n}. This result is best possible, and improves a logarithmic lower bound shown by Chung, Furedi, Graham and Seymour in 1988. In this talk we will discuss a very short algebraic proof of it.

As a direct corollary of this purely combinatorial result, the sensitivity and degree of every boolean function are polynomially related. This solves an outstanding foundational problem in theoretical computer science, the Sensitivity Conjecture of Nisan and Szegedy.

 

TCS+ talk: Wednesday, October 2 — Shachar Lovett, UCSD

The next TCS+ talk will take place this coming Wednesday, October 2th (next week!) at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). Shachar Lovett from UCSD will lead us “Towards the sunflower conjecture” (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 sunflower with r petals is a collection of r sets so that the intersection of each pair is equal to the intersection of all. Erdos and Rado in 1960 proved the sunflower lemma: for any fixed r, any family of sets of size w, with at least about w^w sets, must contain a sunflower. The famous sunflower conjecture is that the bound on the number of sets can be improved to c^w for some constant c. Despite much research, the best bounds until recently were all of the order of w^{cw} for some constant c. In this work, we improve the bounds to about (\log w)^w.

There are two main ideas that underlie our result. The first is a structure vs pseudo-randomness paradigm, a commonly used paradigm in combinatorics. This allows us to either exploit structure in the given family of sets, or otherwise to assume that it is pseudo-random in a certain way. The second is a duality between families of sets and DNFs (Disjunctive Normal Forms). DNFs are widely studied in theoretical computer science. One of the central results about them is the switching lemma, which shows that DNFs simplify under random restriction. We show that when restricted to pseudo-random DNFs, much milder random restrictions are sufficient to simplify their structure.

Joint work with Ryan Alweiss, Kewen Wu and Jiapeng Zhang.

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}.