April 2025 - talks - lists.cs.princeton.edu

Haichen Dong will present his masters' thesis "Optimal Strategy in Longest-Chain Proof-of-Stake Mining with External Randomness" on April 25, 2025 at 10:15am in the CS 402.
by CS Grad Department 23 Apr '25

23 Apr '25

Haichen Dong will present his masters' thesis "Optimal Strategy in Longest-Chain Proof-of-Stake Mining with External Randomness" on April 25, 2025 at 10:15am in the CS 402. The members of his committee are as follows: Matt Weinberg (Adviser) and Mark Braverman(reader). All are welcome to attend. Please see the title and abstract below. Title: Optimal Strategy in Longest-Chain Proof-of-Stake Mining with External Randomness The longest-chain Proof-of-Stake(PoS) mining protocol is an attractive energy-friendly alternative to the popular and successful Proof-of-Work(PoW) diagram. One foundational property of a blockchain protocol is its robustness against strategic manipulation, that all miners are incentivized to follow the honest mining strategy because no miners can defect from using the honest strategy and earn greater revenue. A mining protocol is robust against strategic manipulation when and only when it is a Nash equilibrium for all miners to play the honest mining strategy. Let ⍺^protocol denote the supremum ⍺ such that whenever no miner is selected to create a new block with probability greater than ⍺, it is a Nash equilibrium for all miners to play the honest mining strategy. Sapirshtein et al. (2019) estimates that ⍺^PoW ≈ 0.329. For the Proof-of-Stake framework, it is known that without access to external randomness, the PoS mining protocol will suffer greatly from strategic manipulation, with ⍺^”PoS w/o External Randomness” = 0. Even with external randomness, Ferreira and Weinberg (2021) showed that 0.3080 ≤ ⍺^PoS ≤ 0.3247, which was later improved by Hein (2022) to 0.3189 ≤ ⍺^PoS ≤ 0.3235. In this work, we closed the profit threshold gap by showing that ⍺^PoS ≈ 0.3234. We presented the optimal strategy for the PoS mining game with external randomness assuming a mining power of ⍺^PoS. We also proposed a computer-assisted algorithm that helps bound the possible future profit for each state in the mining game, the result of which matches the optimal profit threshold implied by the optimal strategy.

1 0

Emma Farkash will present her MSE talk "Studying the Role of CPU Overheads in Modern Vision AI" on Thursday, April 24, 2025 at 12:40pm in CS 302.
by Gradinfo 22 Apr '25

22 Apr '25

Emma Farkash will present her MSE talk "Studying the Role of CPU Overheads in Modern Vision AI" on Thursday, April 24, 2025 at 12:40pm in CS 302. Thesis adviser: Ravi Netravali and Kevin Wayne (Reader) Abstract: GPUs are at the center of AI's rise to prominence and have seen massive improvements in the past years. Though less in the spotlight, CPUs remain an important player in AI pipelines; data processing tasks that run on the CPU are a necessary part of every inference call. As AI workloads are shifting towards incorporating more modalities and growing in complexity, heavy vision data processing tasks are increasingly common. This work explores various Vision AI pipelines and their CPU overheads, specifically CPU time and utilization, under diverse configurations, image resolutions, request rates and serving systems. We find that the CPU is increasingly oversubscribed for multimodal and multi-model pipelines, higher resolution images and request rates. Additionally, evaluations on newer hardware point to a widening gap between GPU inference and CPU data processing efficiencies, supporting the conjecture that the CPU may become increasingly congested in the future, impacting service level objectives.

1 0

DeCenter Seminar Series: Wed April 30 at 3:30pm
by Emily C. Lawrence 22 Apr '25

22 Apr '25

Dear all, Next Wednesday, April 30th, at 3:30 PM, the DeCenter Seminar Series continues with Ciamac Moallemi, a professor of Business in the Decision, Risk, and Operations Division at the Graduate School of Business at Columbia University. He will present a seminar titled "The Economics of Automated Market Making and Decentralized Exchanges.” The event will take place in the Computer Science Building Room (105). Abstract: Automated market making (AMM) protocols such as Uniswap have recently emerged as an alternative to the most common market structure for electronic trading, the limit order book. Relative to limit order books, AMMs are both more computationally efficient and do not require the participation of active market making intermediaries such as high frequency traders. As such, AMMs have emerged as the dominant market mechanism for trust-less decentralized exchanges (DEXs) implemented through smart contracts on programmable blockchain platforms such as Ethereum. In cryptocurrency markets, the aggregate trading volume on the Uniswap DEX exceeds that of the much better known Coinbase centralized exchange. We develop a model the underlying economics of AMMs from the perspective of their passive liquidity providers (LPs). Our central contribution is a “Black-Scholes formula for AMMs”. Like the Black-Scholes formula, we consider the return to LPs once market risk has been hedged. We identify the main adverse selection cost incurred by LPs, which we call “loss-versus-rebalancing” (LVR, pronounced “lever”). LVR captures costs incurred by AMM LPs due to stale prices that are picked off by better informed arbitrageurs. In a continuous time Black-Scholes setting, we are able to derive closed-form expressions for this adverse selection cost. Qualitatively, we highlight the main forces that drive AMM LP returns, including asset characteristics (volatility), AMM characteristics (curvature / marginal liquidity, fee structure), and blockchain characteristics (block rate). Quantitatively, we illustrate how our model’s expressions for LP returns match actual LP returns for the Uniswap v2 WETH-USDC trading pair. Our model provides tradable insight into both the ex-ante and ex post assessment of AMM LP investment decisions. LVR can also inform the design of the next generation of DEX market mechanisms and “LVR mitigation” has already emerged as an important challenge among practitioners in the AMM protocol designer community. We present the auction-managed AMM (am-AMM), a novel DEX design utilizing an auction mechanism to mitigate LVR losses to informed orderflow while maximizing fee revenue from uninformed orderflow. This talk includes joint work with Jason Milionis (Columbia CS), Tim Roughgarden (Columbia CS / a16z crypto), Anthony Zhang (Chicago Booth), Austin Adams (Uniswap Labs), Sara Reynolds (Uniswap Labs), and Dan Robinson (Paradigm). It is based on the following three papers: [ https://moallemi.com/ciamac/papers/lvr-2022.pdf | https://moallemi.com/ciamac/papers/lvr-2022.pdf ] [ https://moallemi.com/ciamac/papers/lvr-fee-model-2023.pdf | https://moallemi.com/ciamac/papers/lvr-fee-model-2023.pdf ] [ https://moallemi.com/ciamac/papers/mm-amm-2024.pdf | https://moallemi.com/ciamac/papers/mm-amm-2024.pdf ] Bio: Ciamac C. Moallemi is William von Mueffling Professor of Business in the Decision, Risk, and Operations Division and the director of the Briger Family Digital Finance Lab at the Graduate School of Business at Columbia University, where he has been since 2007. A high school dropout, he received S.B. degrees in Electrical Engineering & Computer Science and in Mathematics from the Massachusetts Institute of Technology (1996). He studied at the University of Cambridge, where he earned a Master of Advanced Study degree in Mathematics (Part III of the Mathematical Tripos), with distinction (1997). He received a Ph.D. in Electrical Engineering from Stanford University (2007). Prior to his doctoral studies, he developed quantitative methods in a number of entrepreneurial ventures: as a partner in a $200 million fixed-income arbitrage hedge fund and as the director of scientific computing at an early-stage drug discovery start-up. He holds editorial positions at the journals Operations Research and Management Science. He is a past recipient of the British Marshall Scholarship (1996), the Benchmark Stanford Graduate Fellowship (2003), first place in the INFORMS Junior Faculty Paper Competition (2011), and the Best Simulation Publication Award of the INFORMS Simulation Society (2014). Aside from his academic work, he has developed high Sharpe, short-term systematic trading strategies as a quantitative portfolio manager, and he regularly consults for fintech companies. He is currently a Research Advisor at Paradigm, a research-driven technology venture capital firm, and at Uniswap Labs, a developer of decentralized exchanges. His research interests are in the development of mathematical and computational tools for optimal decision making under uncertainty, with a focus on applications areas including market microstructure, quantitative and algorithmic trading, and blockchain technology. We hope to see you there! Best, Madelyn LaBuda Administrative and Events Coordinator DeCenter Engineering Quad, C215 Princeton University E: ml2512 [ mailto:email@princeton.edu | @princeton.edu ] M: 570-599-5338

1 0

Josh Cohen will present his FPO "A Foundationally Verified Intermediate Verification Language" on Friday, 5/2/2025 at 2:30 PM in COS 302 and Zoom
by Gradinfo 22 Apr '25

22 Apr '25

Josh Cohen will present his FPO "A Foundationally Verified Intermediate Verification Language" on Friday, 5/2/2025 at 2:30 PM in COS 302 and Zoom. Committee: Examiners: Andrew Appel (Adviser), Zak Kincaid, and David Walker Readers: Aarti Gupta and Philip Johnson-Freyd (Sandia National Laboratories) Zoom link: [ https://princeton.zoom.us/j/93082391321 | https://princeton.zoom.us/j/93082391321 ] Abstract: Annotation-based deductive verifiers have emerged in recent years as practical, capable, and increasingly scalable tools for verifying programs in languages including C, Rust, Go, OCaml, and Dafny. Intermediate verification languages (IVLs) like Why3, Boogie, and Viper have made it significantly easier to build such verifiers by performing part of the translation from high-level, expressive program logics to SMT formulas once and for all. But these verifiers are difficult to fully trust: their toolchains comprise hundreds of thousands of lines of code and bugs in any part can result in unsoundness. An alternate approach to building program verifiers is the foundational one, where the language semantics, program logic, and user-supplied proofs are defined in a proof assistant, giving an end-to-end soundness theorem. These tools, including VST, CakeML, and Bedrock2, provide very strong guarantees but require manual proof and are inaccessible to non-experts. The two approaches have largely remained separate. IVL-based tools are not themselves verified, while interactive tools cannot take advantage of the automation provided by the IVL and SMT-based pipelines. In this thesis, we take steps towards bridging this gap by providing an implementation of the Why3 IVL in the Coq proof assistant, giving the first foundationally verified IVL. First, we give a novel formal semantics for a core subset of the logic implemented by Why3– polymorphic first-order logic with recursive types, functions, predicates, and pattern matching. We prove sound a compiler from this logic to first-order logic, giving the first machine-checked soundness proofs for a sophisticated pattern matching compiler and a first-order axiomatization of algebraic data types. We then develop a new framework to idiomatically implement OCaml APIs in Coq and use this to produce a Coq implementation of the Why3 logic API. Our IVL implementation is fully executable both within Coq and via extraction to OCaml. Using the latter, we demonstrate our tool’s practicality by running existing Why3-based tools and test suites against our implementation, while the former allows our tool to serve as a future back-end for foundational verifiers such as VST.

1 0

Neil Agarwal will present his FPO, "Offline Processing for Machine Learning-Based Video Systems," on Monday, May 5, 2025, at 9 AM in COS 302.
by Gradinfo 21 Apr '25

21 Apr '25

Neil Agarwal will present his FPO, "Offline Processing for Machine Learning-Based Video Systems," on Monday, May 5, 2025, at 9 AM in COS 302. Please see below for details. Committee: Adviser/Examiner: Professor Ravi Netravali Examiner: Professor Wyatt Lloyd Examiner: Professor Kai Li Reader: Professor Maria Apostolaki Reader: Professor Amit Levy Title: Offline Processing for Machine Learning-Based Video Systems Abstract: Video-based applications proliferate our society, from sophisticated video analysis pipelines to large-scale video content and delivery platforms. Machine learning algorithms are instrumental in supporting these applications, enabling fine-grained, high-quality analysis of video data and supporting highly efficient and dynamic control of underlying system processes in video applications. However, integrating machine learning techniques into existing video pipelines brings significant overheads that hinder usability and deployability. This dissertation examines how we can leverage offline processing techniques to mitigate these potential overheads. By carefully shifting computational tasks from application runtime into an offline phase, it is possible to reduce runtime latency, computational cost, and disruptive behaviors experienced by end users. We present two systems that demonstrate the potential benefits of this approach in real-world video applications. Boggart builds a conservative, model-agnostic video index ahead of time to accelerate retrospective video analytics querying pipelines. Mowgli enables practical, offline-trained learning for real-time video rate control by leveraging historical telemetry logs to learn high-quality bitrate adaptation policies without disrupting user experience during deployment.

1 0

Aadityan Ganesh will the General Exam "To Burn or Not to Burn: Hamlet Revisited for Simple Plain-Text Transaction Fee Mechanism Design" on 4/28/25 at 3:30pm in CS 302.
by Gradinfo 21 Apr '25

21 Apr '25

Aadityan Ganesh will the General Exam "To Burn or Not to Burn: Hamlet Revisited for Simple Plain-Text Transaction Fee Mechanism Design" on 4/28/25 at 3:30pm in CS 302. Committee: Matt Weinberg, Mark Braverman, Pramod Viswanath Abstract: Transaction fee mechanisms (TFMs) determine which subset of transactions are included in a block. Following Roughgarden (2020), we consider a “good” TFM to be one that is on-chain simple—that is, incentive compatible for both users and miners. We propose an additional criterion: off-chain influence proofness, meaning miners should not be able to improve their expected revenue by conducting separate, off-chain auctions. While cryptographic second-price auctions satisfy both properties, they rely on heavy cryptographic machinery. We investigate whether similarly robust guarantees can be achieved through mechanisms that are simple-to-participate in (i.e, are both on-chain simple and off-chain influence proof) and do not require cryptography. Our results are twofold. First, we establish a burn identity that precisely characterizes the portion of user payments that must be burned for a TFM to be off-chain influence proof. A TFM satisfies off-chain influence proofness if and only if its allocation rule X and burn rule B satisfy the payment identity in a multi-item single-buyer setting (Rochet, 1985) where the buyer's values for the n items correspond to the Myerson virtual values of the n users in the original TFM environment. Second, we build on the burn identity to characterize all deterministic plain-text TFMs that are simple-to-participate. These mechanisms are precisely posted-price mechanisms, where the price is set by the blockchain and each transaction has a specially tailored fixed burn. However, posted-price mechanisms require an infinite block capacity. Perhaps surprisingly, we also show the existence of simple-to-participate randomized TFMs that remain feasible even with finite block sizes. Holistically, our results show that while off-chain influence proofness is a fairly stringent requirement, families of on-chain simple and off-chain influence proof mechanisms can be found for a variety of settings.

1 1

Andrew Zhao will present "Monte Carlo for Probabilistic Programs Analysis" for the General Exam scheduled for 4/25/25 at 3pm in CS 302.
by Gradinfo 21 Apr '25

21 Apr '25

Andrew Zhao will present "Monte Carlo for Probabilistic Programs Analysis" for the General Exam scheduled for 4/25/25 at 3pm in CS 302. Committee: David Walker (adviser), Mae Milano, and Ryan Adams Abstract and Reading List: https://docs.google.com/document/d/16yOJApNC1GWVaWDK7xcO4zoK1WCXkj1dPrEAxgk…

1 0

Samuel Resendez will present his MSE talk "Online Contention Resolution against Online Adversaries" on April 21, 2025 at 2:30 pm in CS 302.
by Gradinfo 18 Apr '25

18 Apr '25

Samuel Resendez will present his MSE talk " Online Contention Resolution against Online Adversaries " on April 21, 2025 at 2:30 pm in CS 302. Committee: Matt Weinberg and Huacheng Yu Abstract: A framework called contention resolution schemes has been proposed as a way to unify algorithms for a relatively broad class of problems with similar combinatorial structures. A subset of this class comprises Bayesian online selection problems (BOSP). A BOSP describes an optimization problem that can be modeled as making an online selection of choices on a sequence of random variables, subject to some constraints. While the Bayesian online selection problem has been explored in many contexts we restrict ourselves to the k-uniform case. The k-uniform case describes settings where the only constraint on the selection of elements is the total cardinality of the set chosen. In particular, we are allowed to pick up to k elements from an arbitrarily large number of options. An online flavor of contention resolution schemes has been developed for BOSPs under k-uniform constraints. These schemes have been explored primarily in 2 settings. The first is the offline setting. In this setting, the ordering of elements is chosen before any of the elements are revealed. The other is the almighty setting. In this setting, we assume omnipotence for whoever is determining the element order - they are aware of all realizations of randomness, both of the elements and the algorithm, and are free to rearrange the order of elements shown at any moment. There is a third setting that lies between these two extremes - one that assumes that our opponent has a similar amount of power as us, in that they can rearrange elements arbitrarily after seeing what has been revealed, but do not know the realizations of any of the subsequent elements. This is known as the online setting. Our work demonstrates the hardness of online contention resolution against online adversaries. We develop tools to prove that the online case is more akin to the almighty case, and prove impossibility of restricted classes of algorithms against the online adversary.

1 0

Owen Xingjian Zhang will present his MSE talk “Enhancing Moderation in Decentralized Social Media: A Comprehensive Approach to Community-Level Blocklist Management and Customization on Mastodon” on Wednesday, April 23, 2025 at 1:30pm in CS 302.
by CS Grad Department 18 Apr '25

18 Apr '25

Owen Xingjian Zhang will present his MSE talk “Enhancing Moderation in Decentralized Social Media: A Comprehensive Approach to Community-Level Blocklist Management and Customization on Mastodon” on Wednesday, April 23, 2025 at 1:30pm in CS 302. The members of his committee are as follows: Andrés Monroy-Hernández (Adviser) and Manoel Horta Ribeiro (reader) All ae welcome to attend. Please see abstract below. Tools such as blocklists serve as crucial mechanisms for managing online interactions by preventing unwanted engagement and mitigating harassment. Most implementations of blocklists operate at the individual-level, where users can independently manage their blocklists. However, prior research suggests that blocklists at the community-level could be more effective, reliable, and particularly valuable for non-dominant groups seeking counterpublics where they can be safe from the systemic abuse they face online. At the same time, research on the use of community-level governance tools on platforms point to substantial challenges that would undermine the usefulness of community-level blocklists. In this work, we look to Mastodon, a decentralized social media network which allows independent servers hosting groups of users to enforce blocklists at the community-level / for the entire server; we aim to understand how community-level blocklists tools can be designed to maximize their expected benefits. Using a mock-up of a community-level blocklist tool interface informed by prior work, we ask: RQ1: What are the common features of community-level blocklists? RQ2: How do moderators perceive and utilize community-level blocklists? RQ3: What design features would enhance the usability and effectiveness of community-level blocklist management tools? Based on our results, we propose design implications to improve transparency, customization, and moderation flexibility in blocklist management tools for decentralized social media networks.

1 0

Kurtland Chua will present his FPO "Analyzing Meta-Learning in Supervised and Reinforcement Learning Settings" on Wednesday, April 30, 2025 at 2:00 PM in CS 401.
by CS Grad Department 16 Apr '25

16 Apr '25

Kurtland Chua will present his FPO "Analyzing Meta-Learning in Supervised and Reinforcement Learning Settings" on Wednesday, April 30, 2025 at 2:00 PM in CS 401. Location: CS 401 The members of Kurtland’s committee are as follows: Examiners: Jason Lee (Adviser), Elad Hazan, Benjamin Eysenbach Readers: Ryan Adams, Qi Lei (NYU) A copy of his thesis is available upon request. Please email gradinfo(a)cs.princeton.edu if you would like a copy of the thesis. Everyone is invited to attend his talk. Abstract follows below: Machine learning has recently seen widespread usage of large foundation models which, although highly expressive, are also prone to overfitting when trained on limited domain specific datasets. As such, training on larger but indirectly relevant datasets to extract useful representations, and more generally meta-learning, has proven to be key for using these models in data-sparse settings. This dissertation presents a theoretical study of the assumptions underlying meta-learning, focusing on two settings: Meta-Supervised Learning: Prior work has analyzed the statistical complexity of learning a fixed representation for several regression tasks. However, methods in practice, including popular gradient-based approaches like MAML, fine-tune representations for each task. As such, we performed the first theoretical study of fine-tuning-based representation learning. Firstly, we derive sample complexity bounds on a representative procedure applied to a generic class of representations. Secondly, we establish a sample complexity separation between using fine-tunable and fixed representations, illustrating when fine-tuning is preferable. Meta-Reinforcement Learning (RL): Many notions of shared task structure exist for meta-RL, including broadly useful “options” as in hierarchical RL (HRL). However, prior HRL regret bounds assume that the hierarchical structure is known a priori. To bridge this gap, we construct a notion of hierarchical structure that is provably recoverable under appropriate “coverage conditions”. Secondly, we show that the recovered hierarchy can be used to achieve downstream task regret exponentially better than minimax, under mild assumptions. These conditions encode notions such as temporal and state/action abstractions, suggesting that our analysis captures important aspects of HRL in practice.

1 0