TCS+

A carbon-free dissemination of ideas across the globe.

TCS+ talk: Wednesday, December 4 — Nihar Shah, CMU

The next TCS+ talk, and last of the Fall season, will take place this coming Wednesday, December 4th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 18:00 UTC). Nihar Shah from CMU will speak about “Battling Demons in Peer Review” (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: Peer review is the backbone of scholarly research. It is however faced with a number of challenges (or “demons”) which cause unfairness to authors, and degrade the overall quality of the process. This talk will present principled and practical approaches to battle these demons in peer review:

  1. Subjectivity: How to ensure that all papers are judged by the same yardstick?
  2. Mis-calibration: How to use ratings in presence of arbitrary or adversarial mis-calibration?
  3. Bias: How to rigorously test for existence of (gender/fame/race/…) biases in peer review?
  4. Strategic behavior: How to insulate peer review from strategic behavior of author-reviewers?
  5. Noise: How to assign reviewers to papers to simultaneously ensure fair and accurate evaluations in the presence of review noise?

The work uses tools from social choice theory, statistics and learning theory, information theory, game theory and decision theory. No prior knowledge on these topics will be assumed.

Bio:
Nihar B. Shah is an Assistant Professor in the Machine Learning and Computer Science departments at Carnegie Mellon University (CMU). His research interests include statistics, machine learning, information theory, and game theory, with a focus on applications to learning from people. He is a recipient of the the 2017 David J. Sakrison memorial prize from EECS Berkeley for a “truly outstanding and innovative PhD thesis”, the Microsoft Research PhD Fellowship 2014-16, the Berkeley Fellowship 2011-13, the IEEE Data Storage Best Paper and Best Student Paper Awards for the years 2011/2012, and the SVC Aiya Medal 2010, and has supervised the Best Student Paper at AAMAS 2019.

TCS+ talk: Wednesday, November 20 — Jason Li, CMU

The next TCS+ talk will take place this coming Wednesday, November 20th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 18:00 UTC). Jason Li from CMU will speak about “The Karger-Stein Algorithm is Optimal for k-cut” (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 k-cut problem, we are given an edge-weighted graph and want to find the least-weight set of edges whose deletion breaks the graph into k connected components. Algorithms due to Karger-Stein and Thorup showed how to find such a minimum k-cut in time approximately O(n^{2k-2}). The best lower bounds come from conjectures about the solvability of the k-clique problem and a reduction from k-clique to k-cut, and show that solving k-cut is likely to require time \Omega(n^k). Our recent results have given special-purpose algorithms that solve the problem in time n^{1.98k + O(1)}, and ones that have better performance for special classes of graphs (e.g., for small integer weights).

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!