Computer Science & Discrete Mathematics (CSDM)

Computer Science & Discrete Mathematics (CSDM) Seminar

A weekly seminar on topics in theoretical computer science and discrete mathematics

Time: Every Monday 11:00 AM-12:00 PM, and Tuesday 10:30 AM-12:30 PM,   Place: Simonyi 101

Information about CSDM

Upcoming Talk

The Extreme Tail

Speaker: Huy Tuan Pham, Institute for Advanced Study
When: Tuesday, September 29, 2026 | 10:30 AM EDT
Where: Simonyi Hall 101 and Remote Access

Abstract

Since their inception, random graphs have been a central topic in probability and combinatorics, offering a remarkably rich landscape for studying how complex structures emerge from randomness. We will discuss the following fundamental questions: What is the probability that the random graph fails to contain certain structures? For instance, what is the probability that the random graph is triangle-free?

Studying different regimes of such containment probability leads to the heart of different subjects with rich understanding and fundamental phenomena. While the study of thresholds occupies the typical regime of the containment probability, understanding precise asymptotics in the extreme tail is a central topic in the study of large deviations. I will discuss recent progress in this regime in joint work with Matthew Kwan, and describe connections with other cornerstone ideas and developments in modern combinatorics and probability.

Add to calendar 09/29/2026 10:30 09/29/2026 12:30 America/New_York Computer Science/Discrete Mathematics Seminar II use-title Topic: The Extreme Tail Speakers: Huy Tuan Pham, Institute for Advanced Study More: https://www.ias.edu/math/events/computer-sciencediscrete-mathematics-seminar-ii-626 Since their inception, random graphs have been a central topic in probability and combinatorics, offering a remarkably rich landscape for studying how complex structures emerge from randomness. We will discuss the following fundamental questions: What is the probability that the random graph fails to contain certain structures? For instance, what is the probability that the random graph is triangle-free? Studying different regimes of such containment probability leads to the heart of different subjects with rich understanding and fundamental phenomena. While the study of thresholds occupies the typical regime of the containment probability, understanding precise asymptotics in the extreme tail is a central topic in the study of large deviations. I will discuss recent progress in this regime in joint work with Matthew Kwan, and describe connections with other cornerstone ideas and developments in modern combinatorics and probability. Simonyi Hall 101 and Remote Access a7a99c3d46944b65a08073518d638c23

Upcoming Schedule

Monday, Oct 05, 2026 | 11:00am
Eli Berger, University of Haifa
A Sharp Bound on the Integrality Gap in the 3-set
 Abstract

Given a hypergraph with edges of size at most $3$, the $3$-set cover problem asks to determine the minimum size of a family of edges that covers the vertex set. As the problem is NP-hard, it is natural to consider its fractional (linear programming) relaxation, which is the most common tool for providing a lower bound on the value of the optimal solution. The ratio between the actual value and that of the fractional relaxation is called the integrality gap. A classic bound of Lovász implies that the integrality gap in this problem is at most $11/6$. This has been improved to $5/3$ by Fujito and Okumura. In this talk, we prove that the integrality gap is at most $3/2$, which is best possible. A corollary of this result is that the vertex set of any $3$-uniform, regular hypergraph on $n$ vertices can be covered by $n/2$ (or fewer) edges. This solves the $k=3$ case of a problem of de~A.~Moreira and Kohayakawa. As another application, we derive a certain variant of the Gale-Shapley stable marriage theorem for triples.

View additional event details
Add to calendar Monday, 2026-10-05 11:00 Monday, 2026-10-05 12:00 America/New_York Computer Science/Discrete Mathematics Seminar I use-title Topic: A Sharp Bound on the Integrality Gap in the 3-set Speakers: Eli Berger, University of Haifa More: https://www.ias.edu/math/events/computer-sciencediscrete-mathematics-seminar-i-631 Given a hypergraph with edges of size at most $3$, the $3$-set cover problem asks to determine the minimum size of a family of edges that covers the vertex set. As the problem is NP-hard, it is natural to consider its fractional (linear programming) relaxation, which is the most common tool for providing a lower bound on the value of the optimal solution. The ratio between the actual value and that of the fractional relaxation is called the integrality gap. A classic bound of Lovász implies that the integrality gap in this problem is at most $11/6$. This has been improved to $5/3$ by Fujito and Okumura. In this talk, we prove that the integrality gap is at most $3/2$, which is best possible. A corollary of this result is that the vertex set of any $3$-uniform, regular hypergraph on $n$ vertices can be covered by $n/2$ (or fewer) edges. This solves the $k=3$ case of a problem of de~A.~Moreira and Kohayakawa. As another application, we derive a certain variant of the Gale-Shapley stable marriage theorem for triples. Simonyi 101 and Remote Access a7a99c3d46944b65a08073518d638c23
Tuesday, Oct 06, 2026 | 10:30am
Ehud Friedgut, Weizmann Institute of Science
The Fundamentals of Analysis of Boolean Functions; An Old Timer Reminiscing About his Graduate Studies
Abstract

The recent flurry of AI-generated mathematical activity has brought an avalanche of new results. Among them are the resolution of some conjectures that I made more than a quarter of a century ago, as a graduate student. In this talk I’ll give the context of these conjectures, and recall some the most fundamental results in the field. Being in a nostalgic mood, I will probably compare the modus operandi that was used then (meaning up to a couple of months ago) and now, to produce these questions and answers. 

View additional event details
Add to calendar Tuesday, 2026-10-06 10:30 Tuesday, 2026-10-06 12:30 America/New_York Computer Science/Discrete Mathematics Seminar II use-title Topic: The Fundamentals of Analysis of Boolean Functions; An Old Timer Reminiscing About his Graduate Studies Speakers: Ehud Friedgut, Weizmann Institute of Science More: https://www.ias.edu/math/events/computer-sciencediscrete-mathematics-seminar-ii-627 The recent flurry of AI-generated mathematical activity has brought an avalanche of new results. Among them are the resolution of some conjectures that I made more than a quarter of a century ago, as a graduate student. In this talk I’ll give the context of these conjectures, and recall some the most fundamental results in the field. Being in a nostalgic mood, I will probably compare the modus operandi that was used then (meaning up to a couple of months ago) and now, to produce these questions and answers.  Simonyi Hall 101 and Remote Access a7a99c3d46944b65a08073518d638c23
Wednesday, Oct 07, 2026 | 3:30pm
Gil Kalai, Reichman University and The Hebrew University of Jerusalem
Intersection Homology and Combinatorics
 Abstract

I will discuss the wonderful theory of intersection homology, introduced by Goresky and MacPherson, and its connections to the combinatorics of convex polytopes and cellular spaces. I will mention results and questions about "toric g-vectors", important invariants of polytopes, with particular emphasis on the combinatorially motivated search for a suitable ring structure—or a substitute.

I will then turn to the search for traces of intersection homology in Stanley–Reisner rings and exterior face rings of triangulated spaces. Inspired by the many algebraic manifestations of ordinary Betti numbers for manifolds, we seek descriptions of intersection homology that do not require a chosen stratification.

Finally, I will discuss possible extensions of intersection homology to multiperversities and the prospect of obtaining new topological invariants for singular spaces.

This lecture continues discussions from the pleasant informal 1995 seminar here at the IAS with Bob MacPherson, Mark Goresky, Tom Braden, and a few others. I will try to make it self-contained and easygoing.

View additional event details
Add to calendar Wednesday, 2026-10-07 15:30 Wednesday, 2026-10-07 16:30 America/New_York Computer Science/Discrete Mathematics Seminar use-title Topic: Intersection Homology and Combinatorics Speakers: Gil Kalai, Reichman University and The Hebrew University of Jerusalem More: https://www.ias.edu/math/events/computer-sciencediscrete-mathematics-seminar-0 I will discuss the wonderful theory of intersection homology, introduced by Goresky and MacPherson, and its connections to the combinatorics of convex polytopes and cellular spaces. I will mention results and questions about "toric g-vectors", important invariants of polytopes, with particular emphasis on the combinatorially motivated search for a suitable ring structure—or a substitute. I will then turn to the search for traces of intersection homology in Stanley–Reisner rings and exterior face rings of triangulated spaces. Inspired by the many algebraic manifestations of ordinary Betti numbers for manifolds, we seek descriptions of intersection homology that do not require a chosen stratification. Finally, I will discuss possible extensions of intersection homology to multiperversities and the prospect of obtaining new topological invariants for singular spaces. This lecture continues discussions from the pleasant informal 1995 seminar here at the IAS with Bob MacPherson, Mark Goresky, Tom Braden, and a few others. I will try to make it self-contained and easygoing. Simonyi Hall 101 and Remote Access a7a99c3d46944b65a08073518d638c23
More Events

Past Seminars Archive

Past Seminars Archive

Information About CSDM