Monday June 20, 2022
8:45am-10:15am CET: Rising Stars talks:
8:45 am: Sami Davies (virtual)
9:00 am: Tamalika Mukherjee (virtual)
9:15 am: Aditi Dudeja (virtual)
9:30 am: Charlie Carlson (in person)
9:45am: Yasamin Nazari (in person)
10:00 am: Jessica Sorrell (in person)
10:15am- 10:45: Break
10:45am-11:45 am: Inspirational talk by Irit Dinur
Tuesday June 21, 2022
—-
- Lunchtime: Women’s Lunch and Panel (held in separate room off of main STOC lunch)
- Important: Please RSVP here, as seating is limited: https://form.jotform.com/221605845337053
- Confirmed panelists:
- Sumegha Garg (Harvard)
- Noga Ron-Zewi (Haifa University)
- Sandy Irani (UC Irvine)
- Shubhangi Saraf (University of Toronto)
- Sepideh Mahabadi (Microsoft Research)
Talks and speakers info
Inspirational Talk:
Speaker: Irit Dinur (Weizmann)
Title: Expansion, PCPs, and high dimensional expansion
Abstract: I will talk about my 2005 re-proof of the PCP theorem via expander graphs, and how the recent notion of high dimensional expansion is a new way to view it.
Bio: Irit Dveer Dinur is a full professor at the Weizmann Institute of Science. Her research is in the intersection of mathematics and theoretical computer science, with a particular focus on computational complexity and probabilistically checkable proofs. She was a plenary speaker at the 2010 ICM in Hyderabad, and has received several awards for her research including the Gödel Prize for her novel proof of the PCP theorem, the Erdos prize, and the ACM Paris Kanellakis Theory and Practice Award.
Rising Stars Talks:
Speaker: Sami Davies (Northwestern University)
Title: On Robust Factorizations of Tensor Graphs
Abstract: Given a tensor graph $T$ with mild assumptions on its factors, one can factor $T$ efficiently. In other words, one can find graphs $F$ and $G$ such that $T \simeq F \times G$. However, these algorithms are very brittle, in that they are no longer guaranteed to work if even a single edge is deleted from $T$. On the other hand, graphs that are close to a tensor with a triangle, i.e. graphs close to $K_3 \times G$, are interesting in the 3-coloring problem. While it is easy to 3-color $K_3 \times G$ for any graph $G$, if too many edges are deleted from the graph, it is no longer clear if such a graph is 3-colorable in polynomial time. In this work, we consider graphs $H$ that are constructed by taking $K_3 \times G$ and removing at most an $\epsilon$-fraction of each node’s edges. We show that without any assumptions on $G$, it is \textsf{NP}-hard to 3-color $H$. On the other hand, one can construct $\widetilde{H} \simeq K_3 \times \widetilde{G}$ that is close to $H$; for some permutation of the vertices in $\widetilde{H}$, at most an $\epsilon$-fraction of the total edges in $H$ are different from $\widetilde{H}$. Additionally, if one assumes $G$ is an expander, then one can 3-color $H$ is polynomial time.
Bio: Sami is a post-doc at Northwestern University. She is a CI Fellow, mentored by Samir Khuller. Broadly, her current research goes beyond worst-case analysis for combinatorial optimization problems. Sami graduated last June from the University of Washington, where she was advised by Thomas Rothvoss.
Speaker: Tamalika Mukherjee (Purdue University)
Title: Differentially Private Sublinear Algorithms
Abstract: Differential privacy is a desirable feature of algorithms manipulating individuals’ private data and has become a standard requirement in public data analysis. Modern algorithms often work with large data sets, and therefore, another desirable feature is that they are super-efficient, meaning that they run in time that is sublinear in the size of the input. In this talk, I will present our recent work on differentially-private algorithms that run in sublinear time for several combinatorial problems, such as clustering and estimation of graph parameters. I will conclude with several broad open problems.
Bio: Tamalika Mukherjee is a final-year Ph.D. candidate at Purdue University, advised by Jeremiah Blocki and Elena Grigorescu. Her research interests lie broadly in differential privacy, sublinear algorithms, and cryptography. She is a recipient of a Bilsland Dissertation fellowship and a Teaching Academy Graduate Teaching Award from Purdue University.
Speaker: Aditi Dudeja (Rutgers University)
Title: Dynamic Matching in Weighted Graphs
Abstract: In dynamic graph algorithms, the goal is to maintain a key property of the graph while an adversary makes changes to the graph in the form of edge deletions or insertions. The goal is to minimize the update time of the algorithm, which is the time taken by the algorithm to adapt to a single adversarial edge insertion or deletion and output accordingly. I will briefly talk about some algorithms that maintain a good approximation to the maximum matching in a dynamic unweighted graph. Then, I will describe a framework that extends these results to the more general case of weighted graphs.
Bio: I am a final-year graduate student at Rutgers University advised by Aaron Bernstein. My research interests are mainly in graph algorithms including dynamic algorithms and streaming algorithms.
Speaker: Charlie Carlson (University of Colorado)
Title: Approximate Counting: The Potts and Isling Models
Abstract: We introduce the Potts and Isling models along with several related approximate counting problems. We then discuss hardness of these problems and review some algorithmic results for special variants.
Bio: Charlie Carlson is a PhD student at the University of Colorado Boulder working with Alexandra Kolla. She will finish her PhD this Fall and is currently seeking postdoc positions. Her main research focus includes approximate counting, graph theory and combinatorial optimization.
Speaker: Yasamin Nazari (University of Salzburg)
Title: Deterministic Dynamic Distance Approximation
Abstract: We develop deterministic fully dynamic algorithms for computing approximate distances in a graph. Specifically, we are given an unweighted and undirected graph G = (V, E) undergoing edge insertions and deletions, and a parameter 0 < eps ≤ 1, and our goal is to maintain (1 + eps)-approximation distances between a single pair (st distance), a single source to all nodes (SSSP), or all pairs (APSP). We describe how combinatorial tools such as emulators can be combined with algebraic data structures to obtain deterministic algorithms with improved worst-case guarantees for these problems. Joint work with Jan van den Brand and Sebastian Forster.
Bio: Yasamin is a postdoc at University of Salzburg, Austria working with Dr. Sebastian Forster. She received her PhD in Computer Science from Johns Hopkins University, where she was advised by Dr. Michael Dinitz. Her research focuses on graph algorithms with an emphasis on distributed and dynamic algorithms.
Speaker: Jessica Sorrell (UC San Diego)
Title: Reproducibility in Learning
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 only the combinations producing the most significant results are reported. Such practices can lead to erroneous findings that appear to be significant, but 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 will introduce these problems and the techniques used to design reproducible algorithms for them.
This talk is based on joint work with Russell Impagliazzo (UCSD), Rex Lei (UCSD), and Toniann Pitassi (Columbia University).
Bio: Jessica Sorrell is a PhD student at UC San Diego advised by Russell Impagliazzo and Daniele Micciancio. She is broadly interested in responsible computing, particularly questions related to fairness, privacy, robustness, and reproducibility. In the fall she will be joining the University of Pennsylvania as a postdoc with Aaron Roth.