|
Algorithms & Complexity Seminar, MIT : Fall 2024
Organizers: Noah Golowich (nzg AT mit DOT edu), Rahul Ilango (rilango AT mit DOT edu)
The Algorithms & Complexity Seminar will usually (unless otherwise stated) meet on Wednesdays 4pm-5pm at MIT. The style and format of these meetings are variable. Please feel free to contact the organizers to find out more details. To receive announcements of upcoming talks, subscribe to the mailing list by either visiting the mailman page or send an empty email to compalgsem-subscribe@lists.csail.mit.edu.
Talks
-
September 4, 2024: Keegan Harris (Carnegie Melon Uniersity). [Time: 4-5pm: 32-G575]
Topic.
Towards Bridging Causal Inference and Algorithmic Decision-Making
Abstract.
The goal in causal inference is to estimate counterfactual outcomes of units (e.g. patients, customers, subpopulations) under different interventions (e.g. medical treatments, discounts, socioeconomic policies). However, the end goal in practice is often to use these counterfactual estimates to make a decision which optimizes some downstream objective (e.g., maximizing life expectancy or revenue, minimizing unemployment). To bridge counterfactual estimation and decision-making, there are additional challenges one must take into account. We study two such challenges: (i) interventions are applied adaptively using some learning algorithm, (ii) units are strategic in what data they share about themselves. Specifically, we focus on the setting of panel data, where a learner observes repeated, noisy measurements of units over time. This talk is based on the following papers: https://arxiv.org/pdf/2307.01357 (NeurIPS 2023) and https://arxiv.org/pdf/2312.16307 (preprint).
-
September 18, 2024: Esty Kelman (MIT & BU). [Time: 4-5pm: 32-G575]
Topic.
Sparse Graph Counting and Kelley--Meka Bounds for Binary Systems
Abstract.
Graph counting lemma of Chung, Graham, and Wilson (Combinatorica 1988) is a fundamental result in combinatorics, which states that if a large graph is pseudorandom, then the number of copies of any small graph $H$ in $G$ is close to what is expected from a random graph of the same density. However, this result is only nontrivial when $G$ is a dense graph. In this work, we obtain a counting lemma that works in the sparse setting, and it is well-suited for the density increment arguments in additive combinatorics. In a recent remarkable breakthrough, Kelley and Meka (FOCS 2023) obtained a strong upper bound on the density of sets of integers without nontrivial three-term arithmetic progressions. We combine our counting lemma with other ideas to establish Kelley--Meka type bounds for all linear patterns defined by translation-invariant systems of binary linear forms, i.e., each form depends on exactly two variables. In particular, we obtain strong bounds for the Turan problem in Abelian Cayley sum graphs, i.e. an upper bound on the maximum edge density of an Abelian Cayley sum graph with a clique of a given size. To prove our results, we employ some of the recent technology developed by Kelley and Meka and also the follow-up work by Kelley, Lovett, and Meka (STOC 2024). This talk is based on a joint work with Yuval Filmus, Hamed Hatami and Kaave Hosseini.
Theory Calendar
Add this calendar to yours to receive details about upcoming events in the Theory group
(includes A&C Seminars, TOC Colloquium, CIS Seminars, Theory Lunch, TOC tea and more!) :
Click on the events above to get more description about the same (title/abstract for talks, etc.)
Earlier Editions of A&C Seminar
|