TCS+ talk: Wednesday, March 22 — Christian Coester, University of Oxford

The next TCS+ talk will take place this coming March 22nd at 1:00 PM Eastern Time (10:00 AM Pacific Time, 18:00 Central European Time, 17:00 UTC: check your timezone!). Christian Coester from University of Oxford will speak about “The Randomized k-Server Conjecture is False!” (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 randomized -server conjecture, which had been open for over three decades, states that there exists an -competitive randomized algorithm for the k-server problem. In this talk, I will present our recent joint work with Sébastien Bubeck and Yuval Rabani, where we refute this conjecture by giving a lower bound of . Our work also settles the competitive ratio of metrical task systems to be on the hardest metric spaces and on the easiest metric spaces of points. In particular, this yields the first improvement over the previous “coupon collector” lower bound since the introduction of the model in 1987.

TCS+ talk: Wednesday, March 8 — Christos Tzamos, U Athens/UW Madison

The next TCS+ talk will take place this coming Wednesday, March 8th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 18:00 UTC). Christos Tzamos from University of Athens/UW Madison will speak about “A Strongly Polynomial Algorithm for Approximate Forster Transforms and its Application to Halfspace 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: The Forster transform is a method of regularizing a dataset by placing it in radial isotropic position while maintaining some of its essential properties. Forster transforms have played a key role in a diverse range of settings spanning computer science and functional analysis. Prior work had given weakly polynomial time algorithms for computing Forster transforms, when they exist. Our main result is the first strongly polynomial time algorithm to compute an approximate Forster transform of a given dataset or certify that no such transformation exists. By leveraging our strongly polynomial Forster algorithm, we obtain the first strongly polynomial time algorithm for distribution-free PAC learning of halfspaces. This learning result is surprising because proper PAC learning of halfspaces is equivalent to linear programming. Our learning approach extends to give a strongly polynomial halfspace learner in the presence of random classification noise and, more generally, Massart noise.

“

TCS+ talk: Wednesday, February 22 — Jinyoung Park, NYU/Courant Institute

The next TCS+ talk will take place this coming Wednesday, February 22th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 18:00 UTC). Jinyoung Park from NYU/Courant Institute will speak about “Thresholds” (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 a finite set , a family of subsets of is said to be increasing if any set that contains in is also in . The -biased product measure of increases as increases from 0 to 1, and often exhibits a drastic change around a specific value, which is called a “threshold.” Thresholds of increasing families have been of great historical interest and a central focus of the study of random discrete structures (e.g. random graphs and hypergraphs), with estimation of thresholds for specific properties the subject of some of the most challenging work in the area. In 2006, Jeff Kahn and Gil Kalai conjectured that a natural (and often easy to calculate) lower bound (which we refer to as the “expectation-threshold”) for the threshold is in fact never far from its actual value. A positive answer to this conjecture enables one to narrow down the location of thresholds for any increasing properties in a tiny window. In particular, this easily implies several previously very difficult results in probabilistic combinatorics such as thresholds for perfect hypergraph matchings (Johansson–Kahn–Vu) and bounded-degree spanning trees (Montgomery). In this talk, I will present recent progress on this topic.

Based on joint work with Keith Frankston, Jeff Kahn, Bhargav Narayanan, and Huy Tuan Pham.

TCS+ talk: Wednesday, February 8 — Ziv Scully, Harvard and MIT

The first TCS+ talk of 2023 will take place on Wednesday, February 8th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 18:00 UTC). Ziv Scully from Harvard and MIT will speak about “Recent Progress in Queueing and Scheduling Theory (for a TCS Audience)” (abstract below).

Ziv’s talk will also mark the ten-year anniversary of TCS+. Ten years already! For a retrospective of all the talks over the past decade, check out our YouTube channel. (Yes, YouTube: we’re tweens now, but do not have a TikTok or Instagram account.)

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: Queues are ubiquitous in computer systems. Implicit in every queue is a scheduling problem: in what order should we serve jobs in the queue? As such, scheduling has become an important area of study for theorists in multiple communities, including theoretical computer science (TCS) and applied probability (AP).

Due to differences between their usual modeling assumptions and benchmarks, TCS and AP consider different scheduling problems open or closed. For example, consider scheduling to minimize mean response time (a.k.a. flowtime) in multiserver queueing systems. TCS considers this closed, because the Shortest Remaining Processing Time (SRPT) policy is known to have the best possible competitive ratio relative to the optimal offline policy. But AP considers the problem open, because it is unclear whether this worst-case behavior of multiserver SRPT is typical when jobs arrive stochastically, and if it is, it is unclear whether another policy might do much better. Unfortunately, making progress on the AP version of the problem appears very difficult, as underlying it is a stochastic process that is well known to be intractable.

In this talk, I will describe recent developments in queueing theory that have enabled a flurry of progress on scheduling from an AP perspective. One of the key themes is, taking a leaf out of TCS’s playbook, to complement AP’s usual stochastic strategies with a strategic sprinkling of worst-case analysis. I will discuss how these developments enable the first AP solutions to multiserver scheduling—where SRPT does turn out to perform well—and other scheduling problems.

Based on joint work with Isaac Grosof, Mor Harchol-Balter, Alan Scheller-Wolf, and Michael Mitzenmacher.

TCS+ “Test of Time” talk: Wednesday, December 7 — Ronitt Rubinfeld, MIT and Tel Aviv University

The next TCS+ talk will take place this coming Wednesday, December 7th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 18:00 UTC). Ronitt Rubinfeld from MIT and Tel Aviv University will give our very first “Test of Time” talk, titled “A Comedy of Errors” (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 the late 1980s, a new model of “Program Checking” was put forth by Blum and Kannan in order to prevail over errors in programs. With that as a starting point, several lines of research developed — including one that eventually morphed into the area of sublinear time algorithms. Along the way, errors were made and others were detected. We will recount a personal view of the arbitrary nature of this process and place it in historical context.

The talk will be followed by an unrecorded “Ask Me Anything” (AMA) session.

TCS+ talk: Wednesday, November 30 — Nicole Wein, DIMACS (Reminder)

A reminder that the next TCS+ talk will take place this coming Wednesday, November 30th (tomorrow!) at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 18:00 UTC). Nicole Wein from DIMACS will speak about “Online List Labeling: Breaking the Barrier” (abstract below).

The perfect way to ease back into it, after the Thanksgiving week!

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.

More details on Nicole’s talk can be found here.

TCS+ talk: Wednesday, November 30 — Nicole Wein, DIMACS

The next TCS+ talk will take place this coming Wednesday, November 30th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 18:00 UTC). Nicole Wein from DIMACS will speak about “Online List Labeling: Breaking the 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: The online list labeling problem is a basic primitive in data structures. The goal is to store a dynamically-changing set of n items in an array of m slots, while keeping the elements in sorted order. To do so, some items may need to be moved over time, and the goal is to minimize the number of items moved per insertion/deletion. When for some constant , an upper bound of items moved per insertion/deletion has been known since 1981. There is a matching lower bound for deterministic algorithms, but for randomized algorithms, the best known lower bound is , leaving a gap between upper and lower bounds. We improve the upper bound, providing a randomized data structure with expected items moved per insertion/deletion.

Joint work with Michael Bender, Alexander Conway, Martin Farach-Colton, Hanna Komlos, and William Kuszmaul

TCS+ talk: Wednesday, November 9 — Yaonan Jin, Columbia University

The next TCS+ talk will take place this coming Wednesday, November 9th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 18:00 UTC). Yaonan Jin from Columbia University will speak about “First Price Auction is 1-1/e² Efficient” (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 prove that, for the first-price auction, the tight Price of Anarchy (PoA) and the tight Price of Stability (PoS) are both , closing the gap between the best known bounds [0.7430, 0.8689].

Based on joint works with Pinyan Lu.
https://arxiv.org/abs/2207.01761
https://arxiv.org/abs/2207.04455

TCS+ talk: Wednesday, October 26 — Shay Moran, Technion and Google Research

The next TCS+ talk will take place this coming Wednesday, October 26th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). Shay Moran from Technion and Google Research will speak about “A Characterization of Multiclass PAC 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: A seminal result in learning theory characterizes the PAC learnability of binary classes through the VC dimension. Extending this characterization to the general multiclass setting has been open since the late 1980s.

We resolve this problem by characterizing multiclass PAC learnability through the DS dimension, a combinatorial dimension defined by Daniely and Shalev-Shwartz (2014).

The classical characterization of the binary case boils down to empirical risk minimization. In contrast, our characterization of the multiclass case involves a variety of algorithmic ideas; these include a natural setting we call list PAC learning. In the list learning setting, instead of predicting the label of a given unseen input, the goal is to provide a short list of labels which contains the correct one with high probability.

Our second main result concerns the Natarajan dimension, which has been a central candidate for characterizing multiclass learnability. This dimension was introduced by Natarajan (1988) as a barrier for PAC learning. Whether the Natarajan dimension characterizes PAC learnability in general has been posed as an open question in several papers since. We provide a negative answer: we construct a non-learnable class with Natarajan dimension one.

For the construction, we identify a fundamental connection between concept classes and topology. We crucially rely on a deep and involved geometric-group-theoretic construction by Januszkiewicz and Swiatkowski. This proof provides another demonstration of the fruitful links learning theory has with different areas in mathematics.

Joint work with Nataly Brukhim, Daniel Carmon, Irit Dinur, and Amir Yehudayoff

TCS+ talk: Wednesday, October 12 — Venkatesan Guruswami, UC Berkeley

The next TCS+ talk will take place this coming Wednesday, October 12th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). Venkatesan Guruswami from UC Berkeley will speak about “A near-cubic lower bound for 3-query locally decodable codes” (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: Locally decodable codes (LDCs) allow for ultra-efficient recovery of any single message symbol by querying very few symbols of the associated codeword, even in the presence of a constant fraction of errors. In addition to their appeal for storage and cryptographic applications, locality as a concept drives many connections between coding theory and computational complexity.

An outstanding challenge concerning LDCs is their optimal encoding length for a desired number q of queries. For q=2, it is known that exponential blow-up in encoding length is necessary (and the simple Hadamard code achieves this). For q > 2, however, there are significant gaps in our understanding. For instance, for 3-query LDCs, the best known constructions have sub-exponential encoding length, whereas the best known lower bound, that has stood for two decades, was only quadratic.

In this talk, we will describe a near-cubic lower bound on the encoding length of 3-query LDCs. The approach is inspired by and borrows from recent advances in refuting semi-random instances of constraint satisfaction problems.

Joint work with Omar Alrabiah, Pravesh Kothari, and Peter Manohar.