TCS+

A carbon-free dissemination of ideas across the globe.

TCS+ talk: Wednesday, June 1 — Inbal Talgam-Cohen, Technion – Israel Institute of Technology

The next TCS+ talk will take place this coming Wednesday, June 1st at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). Inbal Talgam-Cohen from the Technion – Israel Institute of Technology will speak about “Algorithmic contract theory” (abstract below).

You can reserve a spot as an individual or a group to join us live by signing up on the online form. Registration is not required to attend the interactive talk, and the link will be posted on the website the day prior to the talk; however, by registering in the form, you will receive a reminder, along with the link. (The recorded talk will also be posted on our website afterwards) 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: Algorithms increasingly interact with strategic, self-interested players; their design must take player incentives into account or risk being “gamed” and failing miserably. The algorithmic game theory literature traditionally focused on “mechanisms” – algorithms that incentivize players to truthfully report the input. In this talk we shift focus from mechanisms to “contracts”, which are concerned with the algorithm’s output and players’ incentives to carry it out. The goal of this talk is to describe where we’re at in forming a new algorithmic theory of contract design.

I will demonstrate how algorithmic approaches – in particular the approach of beyond worst-case analysis – can shed light on a classic economic puzzle regarding simple contracts. Within the realm of incentives and learning, I will discuss how classifiers induce incentives and show a formal relation to contracts.

Based on joint works with Tal Alon, Magdalen Dobson, Paul Duetting, Ron Lavi, Ariel Procaccia, Tim Roughgarden, Elisheva Shamash and Jamie Tucker-Foltz.

TCS+ talk: Wednesday, May 18 — Thatchaphol Saranurak, University of Michigan

The next TCS+ talk will take place this coming Wednesday, May 18th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). Thatchaphol Saranurak from University of Michigan will speak about “All-pairs minimum cuts in nearly quadratic time: a tutorial ” (abstract below).

You can reserve a spot as an individual or a group to join us live by signing up on the online form. Registration is not required to attend the interactive talk, and the link will be posted on the website the day prior to the talk; however, by registering in the form, you will receive a reminder, along with the link. (The recorded talk will also be posted on our website afterwards) 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 recently showed an algorithm for computing all-pairs minimum cuts (or, more precisely, the Gomory-Hu tree) in ~O(n^2) time in weighted graphs and even almost-linear time in unweighted graphs. For weighted graphs, this is the first improvement over the 60-year-old algorithm by Gomory and Hu. Thus, surprisingly, computing all-pairs minimum cuts seems to be strictly easier than computing all-pairs shortest paths, which is conjectured to require n^{3-o(1)} time.

I will give a tutorial on the techniques behind our new result, one of which is called “isolating cuts”. Then, I will survey recent progress in fast minimum cut algorithms and discuss open problems.

Joint work with Amir Abboud, Robert Krauthgamer, Jason Li, Debmalya Panigrahi, and Ohad Trabelsi.

TCS+ talk: Wednesday, May 4 — Vera Traub, ETH Zürich

The next TCS+ talk will take place this coming Wednesday, May 4th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). Vera Traub from ETH Zürich will speak about “Approximation Algorithms for Connectivity Augmentation Problems” (abstract below).

You can reserve a spot as an individual or a group to join us live by signing up on the online form. Registration is not required to attend the interactive talk, and the link will be posted on the website the day prior to the talk; however, by registering in the form, you will receive a reminder, along with the link. (The recorded talk will also be posted on our website afterwards) 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: Augmentation problems are a fundamental class of network design problems. They ask about the cheapest way to increase the (edge-)connectivity of a graph by adding edges among a given set of options. One of the most elementary and intensely studied augmentation problems is the (Weighted) Tree Augmentation Problem. Here, a spanning tree has to be augmented into a 2-edge-connected graph.

Classic techniques for network design yield 2-approximation algorithms for a wide class of augmentation problems. For the Unweighted Tree Augmentation Problem, better-than-2 approximations are known for more than 20 years. However, only recently the first better-than-2 approximations have been found for the more general Unweighted Connectivity Augmentation Problem and Weighted Tree Augmentation Problem. In this talk we will discuss these recent advances.

TCS+ talk: Wednesday, April 20 — Rasmus Kyng, ETH Zürich

The next TCS+ talk will take place this coming Wednesday, April 20th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). Rasmus Kyng from ETH Zürich will speak about “Almost-Linear Time Algorithms for Maximum Flow and More” (abstract below).

You can reserve a spot as an individual or a group to join us live by signing up on the online form. Registration is not required to attend the interactive talk, and the link will be posted on the website the day prior to the talk; however, by registering in the form, you will receive a reminder, along with the link. (The recorded talk will also be posted on our website afterwards) 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 give the first almost-linear time algorithm for computing exact maximum flows and minimum-cost flows on directed graphs. By well-known reductions, this implies almost-linear time algorithms for several problems including bipartite matching, optimal transport, and undirected vertex connectivity.

Our algorithm uses a new Interior Point Method (IPM) that builds the optimal flow as a sequence of an almost-linear number of approximate undirected minimum-ratio cycles, each of which is computed and processed very efficiently using a new dynamic data structure.

Our framework extends to give an almost-linear time algorithm for computing flows that minimize general edge-separable convex functions to high accuracy. This gives the first almost-linear time algorithm for several problems including entropy-regularized optimal transport, matrix scaling, p-norm flows, and Isotonic regression.

Joint work with Li Chen, Yang Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva.

TCS+ talk: Wednesday, April 6 — Jessica Sorrell, UCSD

The next TCS+ talk will take place this coming Wednesday, April 6th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). Jessica Sorrell from UCSD will speak about “Reproducibility in Learning” (abstract below).

You can reserve a spot as an individual or a group to join us live by signing up on the online form. Registration is not required to attend the interactive talk, and the link will be posted on the website the day prior to the talk; however, by registering in the form, you will receive a reminder, along with the link. (The recorded talk will also be posted on our website afterwards) 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: Reproducibility is vital to ensuring scientific conclusions are reliable, but failures of reproducibility have been a major issue in nearly all scientific areas of study in recent decades. A key issue underlying the reproducibility crisis is the explosion of methods for data generation, screening, testing, and analysis, where, crucially, only the combinations producing the most significant results are reported. Such practices (also known as p-hacking, data dredging, and researcher degrees of freedom) can lead to erroneous findings that appear to be significant, but that don’t hold up when other researchers attempt to replicate them.

In this talk, we introduce a new notion of reproducibility for randomized algorithms. This notion ensures that with high probability, an algorithm returns exactly the same output when run with two samples from the same distribution. Despite the exceedingly strong demand of reproducibility, there are efficient reproducible algorithms for several fundamental problems in statistics and learning. We show that any statistical query algorithm can be made reproducible with a modest increase in sample complexity, and we use this to construct reproducible algorithms for finding approximate heavy-hitters and medians. Using these ideas, we give the first reproducible algorithm for learning halfspaces via a reproducible weak learner and a reproducible boosting algorithm. We initiate the study of lower bounds and inherent tradeoffs for reproducible algorithms, giving nearly tight sample complexity upper and lower bounds for reproducible versus non-reproducible SQ algorithms. Finally, we discuss connections to other well-studied notions of algorithmic stability, such as differential privacy.

Joint work with Russell Impagliazzo (UCSD), Rex Lei (UCSD), and Toniann Pitassi (Columbia University), to appear in STOC 2022.

TCS+ talk: Wednesday, March 23 — Shuichi Hirahara, National Institute of Informatics, Japan

The next TCS+ talk will take place this coming Wednesday, March 23rd at 6:00 PM Eastern Time (1:00 PM Pacific Time, 13:00 Central European Time, 22:00 UTC [note the unusual time!]). Shuichi Hirahara from the National Institute of Informatics, Japan will speak about “Excluding PH Pessiland” (abstract below).

You can reserve a spot as an individual or a group to join us live by signing up on the online form. Registration is not required to attend the interactive talk, and the link will be posted on the website the day prior to the talk; however, by registering in the form, you will receive a reminder, along with the link. (The recorded talk will also be posted on our website afterwards) 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: Pessiland is the worst of Impagliazzo’s five possible worlds: it is a world where NP is hard on average and pseudorandom generators do not exist. Excluding Pessiland (i.e., showing the equivalence between average-case hardness of NP and the existence of pseudorandom generators) is one of the most important open questions in theoretical computer science. In this talk, we propose to consider PH (Polynomial Hierarchy) variants of Impagliazzo’s five possible worlds. Our main result is to unconditionally rule out PH variants of Pessiland. I will also mention recent progress on excluding PH Heuristica: average-case hardness of PH follows from exponential worst-case hardness of PH.

Based on joint works with Rahul Santhanam.

TCS+ talk: Wednesday, March 9 — Roei Tell, IAS

The next TCS+ talk will take place this coming Wednesday, March 9th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 18:00 UTC). Roei Tell from IAS will speak about “Hardness vs Randomness, Revised: Uniform, Non-Black-Box, and Instance-Wise” (abstract below).

You can reserve a spot as an individual or a group to join us live by signing up on the online form. Registration is not required to attend the interactive talk, and the link will be posted on the website the day prior to the talk; however, by registering in the form, you will receive a reminder, along with the link. (The recorded talk will also be posted on our website afterwards) 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’ll show how to revise the classical hardness-vs-randomness framework, so that it can work in a non-black-box fashion. Specifically, we will construct derandomization algorithms that don’t rely on classical PRGs, and instead “extract pseudorandomness” from the given input on which we want to simulate the probabilistic machine.

Using a non-black-box approach allows us to deduce stronger conclusions (or alternatively rely on weaker hypotheses), compared to classical approaches. In one instantiation of the new framework, we reveal a close connection between the promiseBPP = promiseP conjecture and a new type of uniform lower bounds. In another instantiation, we simulate probabilistic algorithms with essentially no observable runtime overhead, under plausible hypotheses.

Based on a joint work with Lijie Chen.

TCS+ talk: Wednesday, February 23 — Merav Parter, Weizmann Institute of Science

The first TCS+ talk of 2022 will take place on Wednesday, February 23rd at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 18:00 UTC). Merav Parter from Weizmann Institute of Science will speak about “New Diameter Reducing Shortcuts: Breaking the O(\sqrt{n}) Barrier” (abstract below).

You can reserve a spot as an individual or a group to join us live by signing up on the online form. Registration is not required to attend the interactive talk, and the link will be posted on the website the day prior to the talk; however, by registering in the form, you will receive a reminder, along with the link. (The recorded talk will also be posted on our website afterwards) 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 an n-vertex digraph G=(V,E), a shortcut set is a (small) subset of edges H taken from the transitive closure of G that, when added to G guarantees that the diameter of G \cup H is small. Shortcut sets, introduced by Thorup in 1993, have a wide range of applications in algorithm design, especially in the context of parallel, distributed and dynamic computation on directed graphs. A folklore result in this context shows that every n-vertex digraph admits a shortcut set of linear size (i.e., of O(n) edges) that reduces the diameter to \widetilde{O}(\sqrt{n}). Despite extensive research over the years, the question of whether one can reduce the diameter to o(\sqrt{n}) with \widetilde{O}(n) shortcut edges has been left open.

In this talk, I will present the first improved diameter-sparsity tradeoff for this problem, breaking the \sqrt{n} diameter barrier. Specifically, we show an O(n^{\omega})-time randomized algorithm for computing a linear shortcut set that reduces the diameter of the digraph to \widetilde{O}(n^{1/3}). We also extend our algorithms to provide improved (\beta,\epsilon) hopsets for n-vertex weighted directed graphs.

Joint work with Shimon Kogan.

TCS+ talk: Wednesday, December 8 — Guy Blanc, Stanford

The next TCS+ talk (and last of the semester!) will take place this coming Wednesday, December 8th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 18:00 UTC). Guy Blanc from Stanford will speak about “Properly learning decision trees in almost polynomial time” (abstract below).

You can reserve a spot as an individual or a group to join us live by signing up on the online form. Registration is not required to attend the interactive talk, and the link will be posted on the website the day prior to the talk; however, by registering in the form, you will receive a reminder, along with the link. (The recorded talk will also be posted on our website afterwards) 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 give an n^{O(\log\log n)}-time membership query algorithm for properly and agnostically learning decision trees under the uniform distribution over \{-1,1\}^n. Even in the realizable setting, the previous fastest runtime was n^{O(\log n)}, a consequence of a classic algorithm of Ehrenfeucht and Haussler.

Our algorithm shares similarities with practical heuristics for learning decision trees, which we augment with additional ideas to circumvent known lower bounds against these heuristics. To analyze our algorithm, we prove a new structural result for decision trees that strengthens a theorem of O’Donnell, Saks, Schramm, and Servedio. While the OSSS theorem says that every decision tree has an influential variable, we show how every decision tree can be “pruned” so that every variable in the resulting tree is influential.

Joint work with Jane Lange, Mingda Qiao, and Li-Yang Tan (arXiv:2109.00637). To appear in FOCS 2021.

TCS+ talk: Wednesday, December 1 — William Kuszmaul, MIT

The next TCS+ talk will take place this coming Wednesday, December 1th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 18:00 UTC). William Kuszmaul from MIT will speak about “Linear Probing Revisited: Tombstones Mark the Demise of Primary Clustering” (abstract below).

You can reserve a spot as an individual or a group to join us live by signing up on the online form. Registration is not required to attend the interactive talk, and the link will be posted on the website the day prior to the talk; however, by registering in the form, you will receive a reminder, along with the link. (The recorded talk will also be posted on our website afterwards) 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: The linear-probing hash table is one of the oldest and most widely used data structures in computer science. However, linear probing also famously comes with a major drawback: as soon as the hash table reaches a high memory utilization, elements within the hash table begin to cluster together, causing insertions to become slow. This phenomenon, now known as “primary clustering”, was first captured by Donald Knuth in 1963; at a load factor of 1 - 1/x, the expected time per insertion becomes \Theta(x^2), rather than the more desirable \Theta(x).

We show that there is more to the story than the classic analysis would seem to suggest. It turns out that small design decisions in how deletions are implemented have dramatic effects on the asymptotic performance of insertions. If these design decisions are made correctly, then even a hash table that is continuously at a load factor 1 - \Theta(1/x) can achieve average insertion time \tilde{O}(x). A key insight is that the tombstones left behind by deletions cause a surprisingly strong “anti-clustering” effect, and that when insertions and deletions are one-for-one, the anti-clustering effects of deletions actually overpower the clustering effects of insertions.

We also present a new variant of linear probing, which we call “graveyard hashing”, that completely eliminates primary clustering on any sequence of operations. If, when an operation is performed, the current load factor is 1 - 1/x for some x, then the expected cost of the operation is O(x). One corollary is that, in the external-memory model with a data block size of B, graveyard hashing offers the following remarkable guarantee: at any load factor 1-1/x satisfying x = o(B), graveyard hashing achieves 1 + o(1) expected block transfers per operation. Past external-memory hash tables have only been able to offer a 1+o(1) guarantee when the block size B is at least \Omega(x^2).

Based on joint work with Michael A. Bender and Bradley C. Kuszmaul (arXiv:2107.01250). To appear in FOCS 2021.