TCS+

A carbon-free dissemination of ideas across the globe.

TCS+ talk: Wednesday, September 28 — Joakim Blikstad, KTH Stockholm

The next TCS+ talk will take place this coming Wednesday, September 28th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). Joakim Blikstad from KTH Stockholm will speak about “Nearly Optimal Communication and Query Complexity of Bipartite Matching” (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: With a simple application of the cutting planes method, we settle the complexities of the bipartite maximum matching problem (BMM) up to poly-logarithmic factors in five models of computation: the two-party communication, AND query, OR query, XOR query, and quantum edge query models. Our results answer open problems that have been raised repeatedly since at least three decades ago [Hajnal, Maass, and Turan STOC’88; Ivanyos, Klauck, Lee, Santha, and de Wolf FSTTCS’12; Dobzinski, Nisan, and Oren STOC’14; Nisan SODA’21] and tighten the lower bounds shown by Beniamini and Nisan [STOC’21] and Zhang [ICALP’04]. Our communication protocols also work for some generalizations of BMM, such as maximum-cost bipartite b-matching and transshipment, using only Õ(|V|) bits of communications.

To appear in FOCS’22. Joint work with Jan van den Brand, Yuval Efron, Danupon Nanongkai, and Sagnik Mukhopadhyay. preprint: https://arxiv.org/abs/2208.02526

TCS+ talk: Wednesday, September 14 — Moses Charikar, Stanford University

The Fall’22 season of TCS+ is about to start (next week!), with our very first “Test of Time” talk! This coming Wednesday, September 14th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC), Moses Charikar from Stanford University will speak about “A Retrospective on Locality Sensitive Hashing” (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.

The seminar will include some time for questions and discussions after the talk, off the record.

Abstract: In this talk, I will look back at the development of locality sensitive hashing — a twist on classical hashing, where similar items are more likely to map to the same hash bucket. This is an integral part of the algorithmic toolkit for big data algorithms. We will review the evolution of these ideas from 25 years ago to the present.

Guest Post: TCS Women Travel Scholarships for FOCS’22

Below is an announcement on behalf of TCS Women regarding the upcoming FOCS’22.

TCS Women is offering travel scholarships to attend FOCS 2022 in Denver, Colorado, USA. TCS Women Travel Scholarships are intended for researchers at the beginning of their career. This scholarship is being made available for women and minorities, and anyone who identifies as such is welcome to apply; this scholarship is open to both US and international students. Preference will be given to students at the beginning of their studies. If we have sufficient funding, we will give awards to more senior students and possibly even postdocs.

To apply, you will need to fill out the following form by Sept 2nd, 2022 (11:59 pm PDT) in which you provide basic information about yourself, an estimate of your expenses, and a brief statement:

Apply for a travel grant here.

In addition, you will need to have your advisor (or department head or other faculty mentor if you do not yet have an advisor) send a letter of support to tcswomen@gmail.com by Sept 2nd, 2022. Your advisor’s letter should also describe the availability of other travel funds.  Note for advisors: Specifics about alternative funding are very helpful.  Statements like “funding is tight” are not very helpful. This letter should be sent with the subject line “support letter for [your name]”. This is very important. Your application is not complete without this letter.

For more information, check out the website: https://sigact.org/tcswomen/5th-tcs-women-meeting/travel-scholarship/

TCS+: We want YOU(R feedback)

For the new season of TCS+, the organizers’ team has been discussing a range of suggestions to improve our general format, and adapt it to the all-Zoom, COVID/post-COVID world. We would love your feedback on some of these ideas — if you could take a few minutes to answer the following survey (4-5 questions), this would be greatly appreciated!

📋 Link to the survey

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.