In Spring 2025 the seminar was organized by Yu Cheng.

All talks were held from noon to 1PM on Wednesdays in CIT 241 unless otherwise stated.

Spring 2025 Schedule

Date	Speaker	Title	Abstract	Recording
Feb 12 (Wed)	Stefano Leonardi	The Role of Transparency in Repeated First-Price Auctions with Unknown Valuations	We study the problem of regret minimization for a single bidder in a sequence of first-price auctions where the bidder discovers the item’s value only if the auction is won. Our main contribution is a complete characterization, up to logarithmic factors, of the minimax regret in terms of the auction’s transparency, which controls the amount of information on competing bids disclosed by the auctioneer at the end of each auction. Our results hold under different assumptions (stochastic, adversarial, and their smoothed variants) on the environment generating the bidder’s valuations and competing bids. These minimax rates reveal how the interplay between transparency and the nature of the environment affects how fast one can learn to bid optimally in first-price auctions.	Talk
Feb 14 (Fri)	Euiwoong Lee	Theory and Applications of Complete Min-CSPs: A Case Study in Correlation Clustering	We will discuss recent algorithmic results on fundamental problems in data science and clustering, including Correlation Clustering, Low-Rank Approximation, and Metric Distance Violation. A unifying theme will be their connections to Minimum Constraint Satisfaction Problems (CSPs) in complete instances. Starting from the rich theory of dense Max CSPs with several algorithmic tools (e.g., convex hierarchy, random sampling, regularity lemma), we show how this theory can be augmented to handle minimization objectives in applied domains. These efforts also inspired a systematic study on Min-CSPs in complete instances.	Talk
Feb 19 (Wed)	Haifeng Xu	Rethinking Online Content Ecosystems in the Era of Generative AIs	Online contents not only are important to our life but also underlie the recent success of generative AIs (GenAIs) technology. In turn, GenAI is also revolutionizing the way contents are now created, which is much less costly, possibly even more creative, though depending on availability of human-created contents to sustainably refine GenAI’s model training. Such human-AI mutual dependence is fundamentally transforming existing content ecosystems. If not addressed properly, it may distort human creators’ incentives and even drive humans out of the ecosystem. In this talk, I will present our recent works on understanding such human-vs-GenAI competition through the lens of computational economics, and how to design creator reward mechanisms to incentivize desirable distribution of human content creation. Our designed mechanism not only has nice theoretical properties, but also achieved success during live tests with ~10 millions of users on a leading industrial content platform.	Talk
Feb 26 (Wed)	Kishen Gowda	Optimal Parallel Algorithms for Dendrogram Computation and Single-Linkage Clustering	Computing a Single-Linkage Dendrogram (SLD) is a key step in the classic single-linkage hierarchical clustering algorithm. Given an input edge-weighted tree T, the SLD of T is a binary dendrogram that summarizes the (n - 1) clusterings obtained by contracting the edges of T in order of weight. Existing algorithms for computing the SLD all require Ω(n log n) work where n = \|T\|. Furthermore, to the best of our knowledge, no prior work provides a parallel algorithm obtaining non-trivial speedup for this problem. In this paper, we design faster parallel algorithms for computing SLDs both in theory and in practice, based on new structural results about SLDs. In particular, we obtain a deterministic output-sensitive parallel algorithm based on parallel tree contraction that requires O(n log h) work and O(log² n log² h) depth, where h is the height of the output SLD. We then show that a lazy implementation of this algorithm, that requires O(n log n) work and O(log² n) depth, achieves significant speedups in practice. We also give a deterministic bottom-up algorithm for the problem inspired by the nearest-neighbor chain algorithm for hierarchical agglomerative clustering, and show that it achieves O(n log h) work and O(h log n) depth. Our results are based on a novel divide-and-conquer framework for building SLDs, inspired by divide-and-conquer algorithms for Cartesian trees. Our new algorithms can quickly compute the SLD on billion-scale trees, and obtain up to 150x speedup over the highly efficient Union-Find algorithm typically used to compute SLDs in practice.	Talk
Mar 5 (Wed)	Yibin Yang	Gold OPRF: Post-Quantum Oblivious Power Residue PRF	Pseudorandom functions (PRFs) are essential tools in cryptography. Modern applications often require the evaluation of PRFs in a distributed and privacy-preserving manner, leading to the notion of oblivious pseudorandom functions (OPRFs). Despite its significance, current OPRF constructions either fail to ensure post-quantum security or tend to be inefficient. We propose plausible and efficient post-quantum (PQ) oblivious pseudorandom functions (OPRFs) based on the Power Residue PRF (Damgård CRYPTO’88) called Gold, a generalization of the Legendre PRF. At the core of our constructions are efficient novel methods for evaluating Gold within two-party computation, achieving different security requirements. Our constructions support additional features and extensions, e.g., batched evolutions, different forms of verifiability, and strong UC security. All the protocols are efficient in practice. This research was conducted jointly with Fabrice Benhamouda, Shai Halevi, Hugo Krawczyk, and Tal Rabin at AWS.	Talk
Mar 12 (Wed)	Gabriele Farina	Towards Optimal Rates for Multiagent Learning	Uncoupled learning dynamics for multiagent interactions (“games”) define iterative update rules that each agent can apply repeatedly to improve their strategy. A celebrated result establishes that for several choices of learning dynamics, global notions of equilibrium in the system will arise. This connection runs deep and is far from trivial: equilibrium emerges even despite formally chaotic behavior. Today, learning dynamics are the most scalable technique for equilibrium computation in large-scale, general games. In this talk, I will focus on the following question: how fast can equilibrium emerge in general games, and how can we design learning dynamics that enable such fast rates? After retracing the history of the problem and recent progress, I will discuss new results that achieve state-of-the-art guarantees. Our algorithm is obtained by combining the classic no-regret algorithms with an adaptive, non-monotonic learning rate that paces the learning process of the players. Perhaps counterintuitively, the learning rate control aims to temporarily slow down the learning of players with low regret, preventing runaway behavior and provably leading to equilibrium faster. The resulting dynamics are uncoupled (that is, do not require knowledge of anything other than each player’s own utility), and guarantee near-constant regret per player with a polylogarithmic dependence on the number of actions. They apply both in sequential and non-sequential games, no matter the number of players, and no matter the presence of imperfect information.	Talk
Mar 19 (Wed)	Jiapeng Zhang	Sublinear Proofs over Polynomial Rings	Lattice assumptions are among the most promising foundations for building post-quantum cryptographic schemes. The majority of lattice-based constructions rely on arithmetic over polynomial rings of the form Z_Q[X]/(X^N+1). However, the efficiency of lattice-based constructions for advanced cryptographic functionalities—such as aggregate signatures, group signatures, threshold signatures, and verifiable random functions—still lags behind that of group-based approaches. These advanced functionalities are typically achieved by integrating (zero-knowledge) proof systems with simpler lattice-based building blocks. As a result, designing efficient proof systems for polynomial rings can make lattice constructions more useful in practice. However, designing efficient proof systems for such arithmetic presents two key challenges: (1) These rings are not field-like under practical choices of Q and N, making standard tools like the Schwartz–Zippel lemma inapplicable; and (2) When N is large—a common scenario in lattice-based cryptosystems—the size of the ring results in suboptimal proof sizes. In this talk, I will present a new sublinear-sized proof system for arithmetic over these rings. At the core of our approach is a novel ring switching technique, which transforms arithmetic over Z_Q[X]/(X^N+1) into equivalent instances over Galois rings—structures that are both field-like and significantly smaller (with size independent of N). This transformation enables more efficient proofs, particularly when Q is a lattice-friendly modulus, such as those supporting fast NTT computation or power-of-two moduli. Given the broad cryptographic applications of (zero-knowledge) proofs, our techniques could enhance the efficiency of lattice-based primitives, including aggregate signatures, group signatures, verifiable random functions, and verifiable fully homomorphic encryption.	Talk
Mar 26 (Wed)	No seminar (Spring Break)
Apr 2 (Wed)	Sally Dong	Fast Algorithm Design for Structured Linear Programs	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. 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, dynamic algorithms, 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.	Talk
Apr 9 (Wed)	Chris Kapulkin	An Invitation to Discrete Homotopy Theory	Discrete homotopy theory, introduced around 20 years ago by Barcelo and collaborators building on the work of Atkin from the mid-seventies, is a homotopy theory of (simple) graphs. As such, it applies techniques previously employed in the “continuous” context to study discrete objects. It has found applications both within and outside mathematics, including: matroid theory, hyperplane arrangements, topological data analysis, time series analysis, and quite concretely in understanding how social interactions between preschoolers impact their academic performance. Recently, discrete homotopy theory has seen remarkable progress leading to proofs of several longstanding conjectures and new applications in analyzing stock market data. This talk will be an introduction to discrete homotopy theory and will report on a proof, joint with Carranza (Compos. Math. 2024), of the conjecture of Babson, Barcelo, de Longueville, and Laubenbacher from 2006. No prior knowledge of either homotopy theory or combinatorics will be assumed.	Talk
Apr 16 (Wed)	Yiping Ma	Private Information Retrieval in the Shuffle Model	Private information retrieval (PIR) is a powerful cryptographic tool for building many interesting applications, like private search engines, private group chats and more. Although in recent years we have witnessed great strides towards efficient PIR both in theory (e.g., LMW23) and in practice (e.g., SimplePIR), the inherent lower bound of PIR prevents us from going further. We consider PIR under “the shuffle model”, where queries can be made anonymously by multiple clients. This model can also be viewed as a hybrid between the single-server and the two-server settings: one server holds the database and another server holds a secret permutation. On the theory side, we present the first PIR scheme in this model that has information-theoretic security and sublinear per-client communication. In particular, for every γ > 0, the protocol has O(n^γ) communication and computation costs per (stateless) client, with 1/poly(n) statistical security, assuming that a size-n database is simultaneously accessed by poly(n) clients. On the practice side, we construct concretely efficient PIR in the shuffle model based on computational assumption LPN; even better efficiency follows from conjectured hardness of Multi-Disjoint Syndrome Decoding. In the batched query setting, this PIR scheme has ~20x improvement of throughput over the state-of-the-art single-server PIR schemes. Finally, I will discuss a few interesting use cases of the shuffle model in other secure computation tasks. This talk is based on joint works with Adrià Gascón, Yuval Ishai, Mahimna Kelkar, Daniel Lee, Baiyu Li, and Mariana Raykova.	Talk
Apr 23 (Wed)	Rico Zenklusen	Random-Assignment Matroid Secretary Without Knowing the Matroid	The Matroid Secretary Problem (MSP) is a well-known online selection problem about selecting a heavy independent set among elements revealing their weights online in random order. The existence of an O(1)-competitive MSP algorithm is a notorious open problem known as the Matroid Secretary Conjecture. Intense research since MSP’s inception led to progress and O(1)-competitive algorithms for various special cases and variants. Unfortunately, these algorithms heavily rely on knowing the matroid upfront, which is arguably a very undesirable property for trying to approach the general MSP conjecture. I will talk about how one can get an O(1)-competitive algorithm without knowing the matroid for Random-Assignment MSP, where weights are assigned uniformly at random to the elements. This settles an open question raised by both Soto [SIAM Journal on Computing 2013] and Oveis Gharan & Vondrák [Algorithmica 2013], and leads to the first well-known MSP variant with an O(1)-competitive algorithm that does not need to know the matroid upfront. Our approach is based on first approximately learning the rank-density curve of the matroid, which we then exploit algorithmically. This is joint work with Richard Santiago and Ivan Sergeev.	Talk