Theory Seminar

We solve the problem of automatically computing a new class
of environment assumptions in two-player turn-based finite graph games
which characterize an “adequate cooperation” needed from the environment
to allow the system player to win. Given an ω-regular winning
condition Φ for the system player, we compute an ω-regular assumption
Ψ for the environment player, such that (i) every environment strategy
compliant with Ψ allows the system to fulfill Φ (sufficiency), (ii) Ψ can
be fulfilled by the environment for every strategy of the system (implementability),
and (iii) Ψ does not prevent any cooperative strategy choice (permissiveness).

For parity games, which are canonical representations of ω-regular games,
we present a polynomial-time algorithm for the symbolic computation of
adequately permissive assumptions and show that our algorithm runs
faster and produces better assumptions than existing approaches—both
theoretically and empirically. To the best of our knowledge, for ω-regular
games, we provide the first algorithm to compute sufficient and implementable
environment assumptions that are also permissive.

In the second part of the talk, we apply the lessons learned to strategies
computation, and negotiations between multiple agents. This is joint work with
Kaushik Mallik, Satya Prakash Nayak, and Anne-Kathrin Schmuck.

Ashwani Anand is a 3rd year PhD student at the Max Planck Institute for Software Systems, Germany, advised by Rupak Majumdar and Anne-Kathrin Schmuck. His research focuses on the verification and synthesis of distributed systems.

An extremely fruitful line of algorithms research over the past decade has been the application of interior point methods alongside data structure design to classical problems in combinatorial optimization.

Most prominently, this approach led to an almost-linear time algorithm for the max-flow problem [CKL+, FOCS23].

In this talk, we consider linear programs of the form min cᵀ x subjected to Ax = b, x ≥ 0, where the constraint matrix A has suitable structural properties. We present a general framework for solving these structured linear programs that ties together interior point methods and tools across theoretical computer science including graph decomposition, sampling, parameterized complexity, and numerical linear algebra.

Our framework in turn yields the fastest-known algorithms for min-cost flow and k-commodity flow on planar graphs, and for min-cost flow and general linear programs on graphs with bounded treewidth.

Based on joint work with Yu Gao, Gramoz Goranci, Yin Tat Lee, Lawrence Li, Richard Peng, Sushant Sachdeva, and Guanghao Ye.

Sally Dong is a PhD candidate in theoretical computer science at the University of Washington advised by Yin Tat Lee and Thomas Rothvoss. Her research currently focuses on the design and analysis of provably-fast algorithms for foundational problems in combinatorial optimization, such as the max flow problem and linear programming. She completed her bachelor’s degree at the University of Waterloo in Canada, where she also worked in structural combinatorics. She is supported in part by an NSERC grant from the government of Canada.

The emergence of internet-based markets, automated decision-making tools, and the consideration of societal factors in algorithms have led to new standards and criteria for algorithm design. These applications have inspired the study and development of algorithms that go beyond classical settings and can adapt to uncertain decision-making and strategic behavior. In this talk, I will provide an overview of my research and contributions in this field and demonstrate how techniques from mechanism design, online optimization, and machine learning can help us solve these problems. I will focus on applications in search problems and the classification of strategic entities.

Hedyeh Beyhaghi is a postdoctoral research associate in the School of Computer Science at Carnegie Mellon University, hosted by Maria-Florina Balcan. Her research interests lie in algorithmic game theory and mechanism design, machine learning theory, and algorithms under uncertainty. Hedyeh received her Ph.D. in Computer Science from Cornell University, advised by Eva Tardos. Before joining CMU, Hedyeh was a postdoctoral research fellow at Toyota Technological Institute at Chicago (TTIC) and Northwestern University, where she was hosted by Avrim Blum, Jason Hartline, and Samir Khuller.

We establish new results on the Fiat-Shamir (FS) security of several protocols that are widely used in practice, and we provide general tools for establishing similar results for others. More precisely, we: (1) prove the FS security of the FRI and batched FRI protocols; (2) analyze a general class of protocols, which we call delta-correlated, that use low-degree proximity testing as a subroutine (this includes many “Plonk-like” protocols (e.g., Plonky2 and Redshift), ethSTARK, RISC Zero, etc.); and (3) prove FS security of the aforementioned “Plonk-like” protocols, and sketch how to prove the same for the others.

We obtain our first result by analyzing the round-by-round (RBR) soundness and RBR knowledge soundness of FRI. For the second result, we prove that if a -correlated protocol is RBR (knowledge) sound under the assumption that adversaries always send low-degree polynomials, then it is RBR (knowledge) sound in general. Equipped with this tool, we prove our third result by formally showing that “Plonk-like” protocols are RBR (knowledge) sound under the assumption that adversaries always send low-degree polynomials. We then outline analogous arguments for the remainder of the aforementioned protocols.

To the best of our knowledge, ours is the first formal analysis of the Fiat-Shamir security of FRI and widely deployed protocols that invoke it.

Alex Block is a joint Postdoctoral Researcher at Georgetown University and the University of Maryland, under the guidance of Prof. Justin Thaler and Prof. Jonathan Katz. Prior to that, he received his Ph.D. from Purdue University, advised by Prof. Jeremiah Blocki. Alex’s research interests lie at the intersection of cryptography and coding theory and how tools and techniques from each area can be used together to yield new insights and results in both areas. More recently, his focus has turned towards constructing practically efficient codes for cryptographic applications. His work spans several areas, including SNARKs, concrete security, secure multi-party computation, and locally decodable codes. Today, he will talk about recent results on Fiat-Shamir security published at ASIACRYPT 2023 this past December.

An n-vertex graph with maximum degree D is (D+1)-colorable: an almost trivial
combinatorial result, with an equally simple greedy algorithm to produce a
(D+1)-coloring. However, given a stream of edges of such a graph, can we
maintain a valid (D+1)-coloring as the edges arrive, while using not much more
than O(n) space? What if the edges are chosen by an adversary who can look at
our current coloring and add additional edges to try to confound us? This is
the setting of **adversarially robust** streaming algorithms and this talk is
about the coloring problem in this setting.

We obtain upper and lower bound results for this problem. In O(n polylog n)
space, we can maintain an O(D^(5/2))-coloring of such an adversarial graph. On
the other hand, every adversarially robust coloring algorithm under the same
space limitation must spend Omega(D^2) colors. We in fact prove more general
results that trade off the space usage against the color budget. As a
by-product of our work, we obtain (i) a nuanced understanding of the power of
randomness in streaming algorithms and (ii) more concretely, the first
randomized-vs-deterministic separation for the (ordinary, non-robust)
streaming graph coloring problem.

Based on joint works [C.-Ghosh-Stoeckl] and [Assadi-C.-Ghosh-Stoeckl].

Amit Chakrabarti is a Professor in the Department of Computer Science at
Dartmouth College. He holds a Ph.D. in Computer Science from Princeton
University and a B.Tech. in Computer Science from the Indian Institute of
Technology, Bombay, where he was the President of India Gold Medalist.

Professor Chakrabarti’s research is in the broad area of theoretical computer
science. Specific interests are (1) complexity theory, especially communication
complexity and applications of information theory, and (2) algorithms,
including space-efficient algorithms for massive data streams.  He is
particularly known as a pioneer of the concept of “information complexity”. His
research has been funded by several awards from the National Science Foundation,
including a CAREER award.

Ensuring successful content moderation is vital for a healthy online social platform where it is necessary to responsively remove harmful posts without jeopardizing non-harmful content. Due to the high-volume nature of online posts, human-only moderation is operationally challenging, and platforms often employ a human-AI collaboration approach. A typical machine-learning heuristic estimates the expected harmfulness of incoming posts and uses fixed thresholds to decide whether to remove the post (classification decision) and whether to send it for human review (admission decision). This can be inefficient as it disregards the uncertainty in the machine learning estimation, the time-varying element of human review capacity and post arrivals, and the selective sampling in the dataset (humans only review posts filtered by the admission algorithm). 

In this paper, we introduce a model to capture the human-AI interplay in content moderation. The algorithm observes contextual information for incoming posts, makes classification and admission decisions, and schedules posts for human review. Non-admitted posts do not receive reviews (selective sampling) and admitted posts receive human reviews on their harmfulness. These reviews help educate the machine-learning algorithms but are delayed due to congestion in the human review system. The classical learning-theoretic way to capture this human-AI interplay is via the framework of learning to defer, where the algorithm has the option to defer a classification task to humans for a fixed cost and immediately receive feedback. Our model contributes to this literature by introducing congestion in the human review system. Moreover, unlike work on online learning with delayed feedback where the delay in the feedback is exogenous to the algorithm’s decisions, the delay in our model is endogenous to both the admission and the scheduling decisions. 

We propose a near-optimal learning algorithm that carefully balances the classification loss from a selectively sampled dataset, the idiosyncratic loss of non-reviewed posts, and the delay loss of having congestion in the human review system. To the best of our knowledge, this is the first result for contextual online learning in queueing systems and hence our analytical framework may be of independent interest.

Thodoris Lykouris is the Mitsui Career Development Assistant Professor and an Assistant Professor of Operations Management at the MIT Sloan School of Management. 

His research focuses on data-driven sequential decision-making and spans across the areas of machine learning, dynamic optimization, and economics. Prior to his current position, he was a postdoctoral researcher at Microsoft Research NYC where he was part of the machine learning group. 

His dissertation was selected as a finalist in the Dantzig dissertation award competition. His papers have also been selected as finalists in the INFORMS Nicholson and Applied Probability Society best student paper competitions. He is also the recipient of a Google Ph.D. Fellowship and a Cornell University Fellowship.

Thodoris holds a Diploma in electrical and computer engineering from National Technical University of Athens (Greece) and a PhD in computer science from Cornell University, where he was advised by Éva Tardos. 

The talk is based on joint work with Wentao Weng (PhD student at MIT); the paper is available here: https://arxiv.org/pdf/2402.12237.pdf.

The high level problem addressed by this talk is how to find a Markov chain with minimal cost (“gain”) in a large implicitly defined collection of Markov chains with rewards.

This problem was originally motivated by the construction of  binary AIFV-m codes, a relatively new method for lossless compression. They encode using an m-tuple of coding trees rather than the single tree used by Huffman coding. Their advantage is better proven redundancy than Huffman codes; their disadvantage is a slight decoding delay. The compression rate of a binary AIFV-m code is the steady-state average-gain of an associated m-state Markov chain with rewards. 

Finding a best compression rate AIFV-m code is the problem of finding a minimum-gain Markov chain within an implicitly defined (exponentially large) collection of such Markov chains. Previous algorithms for solving this problem ran in exponential time. We show how to transform it  into a Linear Programming one (with an exponential number of constraints). This LP  can then be solved in polynomial time using binary search (for m=2) or the Ellipsoid method (for m >2). The technique maps all possible Markov chain states to hyperplanes that are then used to define the polytope for the LP problem. Since this polytope is only a function of the Markov chain structure, with almost no reliance on the original coding problem, the techniques developed can be of use  in other similar problems.

Mordecai Golin is a senior teaching faculty member  at UMass Amherst. Until recently he was professor of Computer Science at HKUST. After receiving his doctorate from Princeton University in 1990, Prof Golin worked as a researcher in the Projet Algorithmes of the Institut National de Recherche en Informatique et en Automatique (INRIA) in Rocquencourt, France before arriving at HKUST in 1993. Since then, he has also been a visiting researcher at the University of Waterloo, the MADALGO Center for Massive Data Algorithms, the Max-Planck-Institut fur Informatik, INRIA-Sophia, AT&T Labs-Research, and DIMACS. He served as the HKUST Associate Vice-President for Postgraduate Studies from 2011-2014. In addition, he was the 2008 recipient of the HKUST Michael G. Gale Award for Distinguished Teaching.

In this talk, we discuss the first improvement in approximation for nearest neighbor search under the Earth Mover’s Distance (EMD) in over a decade. Given two sets of s vectors A,B in high dimensional space (ℝᵈ), the EMD between A and B is the minimum cost of a perfect matching between the vectors in A and B where the edge weights are given by the distances in Euclidean space. EMD is a classic metric in computer science (dating back over 100 years to the Hungarian algorithm of Jacobi), and a standard distance between two sets of points. In nearest neighbor search, one has a collection of n such sets A₁,…,Aₙ, which one pre-processes so that given a query set Q, one can quickly return a set Aᵢ whose distance (under EMD) is within a C-factor of the nearest neighbor to Q. 

To date, the only algorithm with sublinear O(n^ε) query time was given by Andoni, Indyk, and Krauthgamer ([AIK, SODA 08]), who designed a (data-independent) locality sensitive hash function (LSH) for EMD with approximation O(log² s).  In this work, we improve this approximation to Õ(log s) in the same runtime by designing the first data-dependent LSH functions for EMD. The talk will discuss the main techniques behind sublinear algorithms for EMD, including the tree embeddings techniques of [AIK’08] and [Chen, Jayaram, Levi, Waingarten STOC ‘22], as well as the key insights needed to glue them together into a improved LSH for EMD. 

Joint work with Erik Waingarten and Tian Zhang (STOC ‘24, https://arxiv.org/abs/2403.05041).

Rajesh is a Research Scientist at Google NYC, where he is part of the NYC Algorithms and Optimization team. He received his PhD in Computer Science from Carnegie Mellon University in 2021, where he was advised by David P. Woodruff. Prior to that, in 2017 he received his B.S. in Mathematics and Computer Science from Brown University. His research focuses primarily on sublinear algorithms, especially randomized sketching and streaming algorithms for problems in big-data. In general, he enjoys thinking about dimensionality reduction: namely, to what extent can we compress the significant components of an enormous, noisy data-set? His work also spans property testing, machine learning, and optimization.

Prior work demonstrates that diffusion- and flow-based generative models are effective for generating high dimensional objects, such as high-resolution images. Furthermore, specific models, such as score-based generative models, have shown to produce high-quality samples when the model is trained in the latent space of the data distribution. Learning in the latent space has a few obvious advantages. First, we get to work with smaller matrices and neural networks, reducing the computational cost of forward and backpropagation, and leading to faster training and faster sampling. Second, the target function we are learning has less components that we need to learn, further reducing training time. The downside is that, in general, the dimension reduction is lossy, in the case that dimensions we remove are not just noise. However, it is observed that, even when the score is learned in the original data dimension for significantly longer (to account for additional complexity), the latent space models produce strictly better samples.

Our work utilizes connections between score-based generative models and mean-field games to derive novel justification showing that latent score still learns the true score of the data distribution. We use the PDEs from the mean-field game to mathematically justify why learning a score in the latent space greatly outperforms scores learned in the original data dimension.

Ben Burns is an undergraduate math and CS student at UMass Amherst, advised by Markos Katsoulakis and Benjamin Zhang. His research interests include mathematical machine learning, applications of probability, and computational complexity.

Networks can be conducive to the spread of undesirable phenomena from false information to bankruptcy of financial institutions and contagious disease. How can we leverage algorithms to stop or slow down contagious processes? I will survey algorithmic problems related to minimum contagious sets, social distancing and vaccination. Many open questions will be discussed.

Daniel Reichman is an assistant professor in the department of computer science at Worcester Polytechnic Institute. He received his PhD at the Weizmann institute and was a postdoc at Cornell University, UC Berkeley and Princeton University. His research interests include neural networks, computational complexity and algorithmic approaches that go beyond worst-case analysis.

Abstract TBA

Bio TBA

Abstract TBA

Bio TBA