- talks - lists.cs.princeton.edu

[alg-ml-reading-group] Alg-ML Talk by Akshay Krishnamurthy on May 12, Monday, from 3pm - 4pm ET
by Emily C. Lawrence 09 May '25

09 May '25

Dr. Akshay Krishnamurthy from Microsoft Research will present his recent work on Understanding Inference Time Compute: Self-Improvement and Scaling . The talk is scheduled on on May 12, Monday. Bio: Akshay Krishnamurthy is a senior principal research manager at Microsoft Research, New York City. He previously spent two years as an assistant professor in the College of Information and Computer Sciences at the University of Massachusetts, Amherst and a year as a postdoctoral researcher at Microsoft Research, NYC. He completed my PhD in the Computer Science Department at Carnegie Mellon University, advised by Aarti Singh and received his undergraduate degree in EECS at UC Berkeley. His research interests are broadly in the areas of machine learning and statistics. He is most excited about interactive learning and decision making, including reinforcement learning, and recently has been thinking about how reinforcement learning can be used to improve modern generative AI systems. Feel free to grab a slot [ https://docs.google.com/spreadsheets/d/10LQsvqhbxw36MDLcxpnDPcG12nsrDl33yG0… | here ] to meet with our speaker! The talk will start at 3.00 pm ET. ____________________________________________________________________________ Time: 3 .00 PM ET on May 12 , Monday Physical Location: COS 402 ____________________________________________________________________________ Title: Understanding Inference Time Compute: Self-Improvement and Scaling Abstract: Inference-time compute has emerged as a new axis for scaling large language models, leading to breakthroughs in AI reasoning. Broadly speaking, inference-time compute methods involve allowing the language model to interact with a verifier to search for desirable, high-quality, or correct responses. While recent breakthroughs involve using a ground-truth verifier of correctness, it is also possible to invoke the language model itself or an otherwise learned model as verifiers. These latter protocols raise the possibility of self-improvement, whereby the AI system evaluates and refines its own generations to achieve higher performance. This talk presents new understanding of and new algorithms for language model self-improvement. The first part of the talk focuses on a new perspective on self-improvement that we refer to as sharpening, whereby we "sharpen" the model toward one placing large probability mass on high-quality sequence, as measured by the language model itself. We show how the sharpening process can be done purely at inference time or amortized into the model via post-training, thereby avoiding expensive inference-time computation. In the second part of the talk, we consider the more general setting of a learned reward model, show that the performance of naive-but-widely-used inference-time compute strategies does not improve monotonically with compute, and develop a new compute-monotone algorithm with optimal statistical performance. Based on joint works with Audrey Huang, Dhruv Rohatgi, Adam Block, Qinghua Liu, Jordan T. Ash, Cyril Zhang, Max Simchowitz, Dylan J. Foster and Nan Jiang. We hope to see you there! ____________________________________________________________________________ (Useful links: [ https://princeton-alg-ml.github.io/ | alg-ml-website ] , [ https://calendar.google.com/calendar/u/1?cid=Y185ZWQxMzVmOGMxN2JjZmNhYjAyOT… | alg-ml-calendar ] , [ https://lists.cs.princeton.edu/mailman/listinfo/alg-ml-reading-group | alg-ml-mailing-list ] ) Best, Zixuan , Gon, and Catherine _______________________________________________ alg-ml-reading-group mailing list [ mailto:alg-ml-reading-group@lists.cs.princeton.edu | alg-ml-reading-group(a)lists.cs.princeton.edu ] [ https://lists.cs.princeton.edu/mailman/listinfo/alg-ml-reading-group | https://lists.cs.princeton.edu/mailman/listinfo/alg-ml-reading-group ]

1 0

CS Colloquium speakers: week of February 26
by Emily C. Lawrence 09 May '25

09 May '25

CS Colloquium speakers Speaker: Jialin Ding, Amazon Web Services Date: Monday, February 26 Time: 12:30pm EST Location: CS 105 Host: Wyatt Lloyd Event page: https://www.cs.princeton.edu/events/26578 Register for live-stream online here: https://princeton.zoom.us/webinar/register/WN_10z_l8MYRr21ZOuPqA8Odw Title: Instance-Optimization: Rethinking Database Design for the Next 1000X Abstract: Modern database systems aim to support a large class of different use cases while simultaneously achieving high performance. However, as a result of their generality, databases often achieve adequate performance for the average use case but do not achieve the best performance for any individual use case. In this talk, I will describe my work on designing databases that use machine learning and optimization techniques to automatically achieve performance much closer to the optimal for each individual use case. In particular, I will present my work on instance-optimized database storage layouts, in which the co-design of data structures and optimization policies improves query performance in analytic databases by orders of magnitude. I will highlight how these instance-optimized data layouts address various challenges posed by real-world database workloads and how I implemented and deployed them in production within Amazon Redshift, a widely-used commercial database system. Bio: Jialin Ding is an Applied Scientist at AWS. Before that, he received his PhD in computer science from MIT, advised by Tim Kraska. He works broadly on applying machine learning and optimization techniques to improve data management systems, with a focus on building databases that automatically self-optimize to achieve high performance for any specific application. His work has appeared in top conferences such as SIGMOD, VLDB, and CIDR, and has been recognized by a Meta Research PhD Fellowship. To learn more about Jialin’s work, please visit [ https://jialinding.github.io/ | https://jialinding.github.io/ ] . CSML/CS/PSY Colloquium Speaker: Brenden Lake, New York University Date: Tuesday, February 27 Time: 12:30pm EST Location: CS 105 Host: Tom Griffiths Event page: https://csml.princeton.edu/events/csmlpsycs-seminar Register for live-stream online here: https://princeton.zoom.us/webinar/register/WN_aUfLfVQFSIqV2RDSYu4big Title: Towards more human-like learning in machines: Bridging the data and generalization gaps Abstract: There is an enormous data gap between how AI systems and children learn: The best LLMs now learn language from text with a word count in the trillions, whereas it would take a child roughly 100K years to reach those numbers through speech (Frank, 2023, "Bridging the data gap"). There is also a clear generalization gap: whereas machines struggle with systematic generalization, children can excel. For instance, once a child learns how to "skip," they immediately know how to "skip twice" or "skip around the room with their hands up" due to their compositional skills. In this talk, I'll describe two case studies in addressing these gaps. 1) The data gap: We train deep neural networks from scratch (using DINO, CLIP, etc.), not on large-scale data from the web, but through the eyes and ears of a single child. Using head-mounted video recordings from a child as training data (<200 hours of video slices over 26 months), we show how deep neural networks can perform challenging visual tasks, acquire many word-referent mappings, generalize to novel visual referents, and achieve multi-modal alignment. Our results demonstrate how today's AI models are capable of learning key aspects of children's early knowledge from realistic input. 2) The generalization gap: Can neural networks capture human-like systematic generalization? We address a 35-year-old debate catalyzed by Fodor and Pylyshyn's classic article, which argued that standard neural networks are not viable models of the mind because they lack systematic compositionality -- the algebraic ability to understand and produce novel combinations from known components. We'll show how neural networks can achieve human-like systematic generalization when trained through meta-learning for compositionality (MLC), a new method for optimizing the compositional skills of neural networks through practice. With MLC, neural networks can match human performance and solve several machine learning benchmarks. Given these findings, we'll discuss the paths forward for building machines that learn, generalize, and interact in more human-like ways based on more natural input. Related articles: Vong, W. K., Wang, W., Orhan, A. E., and Lake, B. M (2024). Grounded language acquisition through the eyes and ears of a single child. Science, 383, 504-511. Orhan, A. E., and Lake, B. M. (in press). Learning high-level visual representations from a child’s perspective without strong inductive biases. Nature Machine Intelligence. Lake, B. M. and Baroni, M. (2023). Human-like systematic generalization through a meta-learning neural network. Nature, 623, 115-121. Bio: Brenden M. Lake is an Assistant Professor of Data Science and Psychology at New York University. He received his M.S. and B.S. in Symbolic Systems from Stanford University in 2009, and his Ph.D. in Cognitive Science from MIT in 2014. He was a postdoctoral Data Science Fellow at NYU from 2014-2017. Brenden is a recipient of the Robert J. Glushko Prize for Outstanding Doctoral Dissertation in Cognitive Science and the MIT Technology Review 35 Innovators Under 35. His research was also selected by Scientific American as one of the 10 most important advances of 2016. Brenden's research focuses on computational problems that are easier for people than they are for machines, such as learning new concepts from just a few examples, learning by asking questions, learning by generating new goals, and learning by producing novel combinations of known components. CS Colloquium Speaker: Eric Mitchell, Stanford University Date: Thursday, February 29 Time: 12:30pm EST Location: CS 105 Host: Karthik Narasimhan Event page: https://www.cs.princeton.edu/events/26587 Register for live-stream online here: TBA Talk info TBA

1 23

Elizabeth Mieczkowski will present her General Exam "Quantifying Collaborative Trade-offs with Insights from Distributed Systems" on Tuesday, May 13, 2025 at 12:00 PM in FC 008.
by CS Grad Department 08 May '25

08 May '25

Elizabeth Mieczkowski will present her General Exam "Quantifying Collaborative Trade-offs with Insights from Distributed Systems" on Tuesday, May 13, 2025 at 12:00 PM in FC 008. Zoom Link: https://princeton.zoom.us/j/6756891992 Committee Members: Tom Griffiths (advisor), Benjamin Eysenbach, Wyatt Lloyd, Natalia Velez Abstract: Collaboration enables multi-agent systems to achieve goals beyond the capabilities of any single agent. However, coordination is inherently complex and dynamic. How can we identify the underlying principles that should guide the division of labor and resources in multi-agent teams, and formalize the trade-offs that emerge during collaboration? I argue that research from distributed computing systems provides a powerful interpretability framework for multi-agent collaboration. This literature focuses on building efficient, scalable, and fault-tolerant systems, while exposing fundamental constraints—such as communication overhead and consistency—when computation is shared across machines. I first extend Amdahl’s Law, which predicts how serial bottlenecks constrain parallel speedup, to naturalistic multi-agent tasks and confirm its validity in a set of human experiments. I then apply this model to large-scale MARL simulations in Overcooked, SMAC, and MPE, demonstrating that specialized policies emerge as a function of task parallelizability. Finally, I demonstrate how the model can benchmark existing algorithms and human collaborative strategies. Reading List: https://docs.google.com/document/d/12GKMv_n99TcUJvj8iua44eHGkUbQAz2hwX_zUYj… Everyone is invited to attend the talk, and those faculty wishing to remain for the oral exam following are welcome to do so.

1 0

[Machine Learning Seminar] May 9: Virtual Talk by Prof. Yitao Liang on Minecraft and Vision-Language-Action Models
by Emily C. Lawrence 07 May '25

07 May '25

This Friday, Prof. Yitao Liang from Peking University will give a virtual talk about his research on Vision-Language-Action Models and their applications to open-world games (e.g., Minecraft). Time : May 9, from 10:00 to 11:00 a.m. ET at [ https://princeton.zoom.us/j/97152277086 | https://princeton.zoom.us/j/97152277086 ] We will also stream the talk together at Friend Center 008 . Title: Instruction-Following Control in an Open World: Vision-Language-Action Models and Beyond Abstract: With the emergence of large language models, the debate about whether an instruction-following long-horizon control agent will appear has resurfaced. However, GPT's emerging abilities seem difficult to reproduce in domains that require sequential control. In this talk, we will introduce various efforts by our group and other well-known research labs to develop such a model in open-world game domains (e.g., Minecraft). Due to its extremely high degree of freedom, traditional multi-task data-driven methods are unsustainable (we cannot afford to train on thousands of tasks simultaneously, it is too expensive). One possible direction is to leverage LLMs to achieve flexible task planning. In this talk, we present latest research in this direction, and how to obtain a universal prompt-based generic policy learning. Due to models’s increasingly impressive data fitting capability, how to properly evaluate in open-ended domains has also become a new frontier. We will also discuss how generative evaluation could facilitate a more principled evaluation. Bio: Yitao Liang ( [ mailto:yitaol@pku.edu.cn | yitaol(a)pku.edu.cn ] ) is an assistant professor and Boya Fellow at Peking University. He obtained his Ph.D. degree in Computer Science from UCLA, advised by Prof. Guy Van den Broeck. His research interests span reasoning, machine learning and AI agents. His work has received recognition from top AI conferences; for example, the best-paper honorable mention from AAMAS 2016, the best paper from RL for Real Life workshop in ICML 2019, a best paper runner-up from the LLD workshop in NeurIPS 2017, a best paper from the TEACH workshop in ICML2023. He regularly serves as area chairs and senior area chairs in top venues e.g., NeurIPS, ICML. Best, Wenzhe Li & Chi Jin

1 0

Ruyu Yan will present her General Exam "Nonlinear Perspective Photography via Geometry-aware Scene Completion" on Friday, May 9, 2025 at 1:00 PM in CS 402.
by CS Grad Department 06 May '25

06 May '25

Ruyu Yan will present her General Exam "Nonlinear Perspective Photography via Geometry-aware Scene Completion" on Friday, May 9, 2025 at 1:00 PM in CS 402. Committee Members: Adam Finkelstein (advisor), Felix Heide, Szymon Rusinkiewicz Abstract: Designers of modern mobile cameras aim to capture high-quality images using linear perspective projection. However, this projection often fails to align with users' natural perception, which is influenced by nonlinear phenomena; it also does not support creative composition needs, such as depth compression along a long street or tilt-shift effects. We introduce a computational photography system that enables nonlinear perspective projection as a composition process during capture on mobile devices. Our system reconstructs a low-resolution 3D scene representation using signed distance field fusion, allowing users to explore perspective transformations with interactive preview in the camera viewfinder. During capture, the system guides users to capture additional data to overcome challenges such as occlusions and the limited field of view of the physical lens. We then employ a 2D Gaussian splatting method to reconstruct a geometry proxy of the scene, which we use for warping the captured photos and exporting high-fidelity photos with nonlinear perspective. Reading List: https://docs.google.com/document/d/1yaZAtQX7YuhOO9343ITD-ieHEApp8teCrU9aQCq… Everyone is invited to attend the talk, and those faculty wishing to remain for the oral exam following are welcome to do so.

1 0

David Braun will present his General Exam "EASY-AS-PIE: Evolutionary Algorithm SYnthesizer Architecture Search via Pre-trained Instrument Embeddings" on Thursday, May 8, 2025 at 10:00 AM in CS 402.
by gradinfo＠cs.princeton.edu 06 May '25

06 May '25

David Braun will present his General Exam "EASY-AS-PIE: Evolutionary Algorithm SYnthesizer Architecture Search via Pre-trained Instrument Embeddings" on Thursday, May 8, 2025 at 10:00 AM in CS 402. Committee Members: Adam Finkelstein (advisor), Tri Dao, Mae Milano Abstract: Software synthesizers offer immense creative possibilities for sound design, but navigation of their high-dimensional parameter spaces poses a challenge for musicians. This has motivated efforts toward automatic synthesizer programming-systems that generate parameter settings given a target sound or description. However, such systems require an automated means of comparing the similarity of sounds, which is complicated due to psychoacoustic factors. Existing methods often address synthesizer programming using gradient descent or genetic algorithms. Gradient-based optimization faces challenges because synthesizer signal processing is highly recurrent and can involve gradient discontinuities. Conversely, evolutionary methods handle such discontinuities but typically operate with fixed synthesizer architectures, limiting creative potential. Allowing dynamic architectural changes exponentially increases search complexity due to the combinatorial explosion in connecting synthesizer modules. Neither approach is well-suited for automatic programming of a large corpus of target sounds. Nonetheless, automatic synthesizer programming remains a valuable research direction because synthesizers offer greater interpretability compared to black-box neural audio synthesis models, enabling musicians and sound designers to intuitively understand and manipulate generated sounds. Motivated by these considerations, we propose a novel framework that uniquely combines two established concepts: evolutionary algorithms for synthesizer architecture search and pre-trained instrument embeddings (specifically CLAP) for perceptual comparison of sound similarity. Crucially, our method efficiently optimizes synthesizer presets for thousands of distinct target sounds simultaneously. Our evolutionary framework involves a hierarchical genetic representation comprising distinct gene classes for oscillator settings, envelopes, various audio effects, and more. Each parameter is modeled with dedicated numeric genes, either continuous (e.g., an oscillator's sustain level) or discrete (e.g., filter type), and mutations are performed by sampling from precomputed parameter distributions extracted from real synthesizer presets. Since the genome includes information about modulation routings (e.g., "Envelope 1 modulating Reverb Size with a Depth of 40%"), the genetic mutation and crossover operations explore the synthesizer architecture space in addition to a purely numeric parameter space. Our evolutionary framework also incorporates two complementary archive structures to balance exploration and exploitation. A grid-based archive inspired by MAP-Elites uses dimensionality reduction on CLAP embeddings, enabling structured diversity-driven exploration of the preset space, untethered to target sounds. Concurrently, a second archive maintains champion presets for each target sound, ranked using cosine distance metrics in the embedding space, facilitating exploitation. Through ablation studies, we demonstrate that this dual-archive approach effectively improves alignment with a held-out audio dataset measured by Kernel Audio Distance (KAD). Moreover, when optimizing for a single target sound, our approach can flexibly use a different loss signal such as a multi-scale spectrogram loss while still benefiting from pre-existing archives. We show that the addition of architecture search in such a scenario results in superior reconstruction of query sounds compared to only modifying numeric parameters. This research demonstrates that embedding-driven evolutionary strategies combined with flexible synthesizer representations enable automated and diverse exploration of sounds.

1 1

Haoran Wan will present his General Exam "Facilitating the Co-Design of Applications and Cellular Network both Internally and Externally" on May 12, 2025 at 12pm in CS 302.
by Gradinfo 05 May '25

05 May '25

Haoran Wan will present his General Exam "Facilitating the Co-Design of Applications and Cellular Network both Internally and Externally" on May 12, 2025 at 12pm in CS 302. Committee: Kyle Jamieson (adviser), Maria Apostolaki, Wyatt Lloyd Title: Facilitating the Co-Design of Applications and Cellular Network both Internally and Externally Abstract: 5G has emerged as the dominant cellular Radio Access Network (RAN) technology, serving as a critical last-mile solution for modern connectivity. Building on significant innovations in the physical (PHY) and medium access control (MAC) layers over LTE, 5G promises substantially higher throughput and lower latency. However, wireless networks suffer from highly variable end-to-end throughput due to user movement, channel fading and interference. Compounding this issue, the base station keeps deep packet buffers for retransmissions to mitigate packet loss caused by the varying channels, which paradoxically causes the high end-to-end latency. The variable throughput and hidden buffer pose performance challenges for many applications, ranging from congestion control for bulk downloading to interactive videos. And the closed nature of the RAN inhibits co-design of applications and the cellular network. To bridge the gap and facilitate the co-design of applications and the cellular network, we worked from two perspectives: 1) Externally, we developed a non-intrusive telemetry tool called NR-Scope to decode the control information passively from the raw radio signals, providing the MAC/PHY throughput of the base station in sub-millisecond level granularity; 2) Internally, we designed a base station module called L4Span that predicts the egress rate of the hidden queue and exposes this information through explicit congestion notification (ECN) bits in the IP header. Our work paves the way for co-designing future cellular systems and applications to fully leverage 5G’s capabilities.

1 0

Viola Chen will present her General Exam "Inferring Ancestral Cell States Using Transcriptome Geometry and Lineage Trees" on Thursday, May 8, 2025 at 10:30 AM in CS 302.
by CS Grad Department 05 May '25

05 May '25

Viola Chen will present her General Exam " Inferring Ancestral Cell States Using Transcriptome Geometry and Lineage Trees " on Thursday, May 8, 2025 at 10:30 AM in CS 302 . Committee Members: Benjamin Raphael (advisor), Mona Singh , Yuri Pritykin Abstract: Understanding how transcriptomic states evolve along a developmental lineage is a fundamental question in single-cell biology. While CRISPR-based lineage tracing technologies now enable high-resolution reconstruction of cell lineage trees, the transcriptomic states of internal (ancestral) nodes remain unobserved due to the destructive nature of sequencing. Existing methods for inferring these states either rely on strong parametric assumptions (e.g., Gaussian random walks in treeVAE) or discard true lineage information altogether (e.g., pseudotime methods). We present a geometry-aware parsimony framework for inferring ancestral transcriptomic states in cell lineage trees. Our approach leverages the principle of minimal transcriptomic change along a known tree structure, using either discrete or continuous representations of cell states. In the continuous case, we extend squared-change parsimony to non-Euclidean manifolds by computing Fréchet means under biologically meaningful distance metrics, such as graph geodesics derived from k-nearest neighbor (kNN) transcriptomic similarity graphs. We develop an efficient iterative optimization scheme, applicable to Euclidean, manifold, or graph-structured spaces, and benchmark our method on synthetic manifolds and real lineage-resolved datasets (e.g., C. elegans). Our results show improved recovery of internal cell states and differentiation trajectories compared to baseline methods. This framework provides a general and interpretable tool for reconstructing unobserved developmental states from lineage-traced single-cell data. Reading List: https://docs.google.com/document/d/1CtluDXuGFs2Z6IOfPlQg8gYGnNjemOPkjpYyuZZ… Everyone is invited to attend the talk, and those faculty wishing to remain for the oral exam following are welcome to do so.

1 0

Kart Kandula will present his General Exam "Competition by Design: Experimental Evidence on Search Engine Use and Choice Architecture Interventions" on May 6, 2025 at 2:30pm in 306 Sherrerd Hall.
by Gradinfo 02 May '25

02 May '25

Kart Kandula will present his General Exam "Competition by Design: Experimental Evidence on Search Engine Use and Choice Architecture Interventions" on May 6, 2025 at 2:30pm in 306 Sherrerd Hall. Committee: Jonathan Mayer (adviser), Peter Henderson, Andrés Monroy-Hernández All are welcome to attend the talk. Abstract: On both sides of the Atlantic, regulators have intensified scrutiny of Google’s dominance in the market for general search services, concerned that the company has engaged in exclusionary practices to maintain its position as the default gateway to the internet. In the United States, this culminated in a landmark ruling on August 5, 2024, in which a federal court found Google in violation of § 2 of the Sherman Act for unlawfully monopolizing the online search market. Now in the remedies phase, the U.S. Department of Justice has proposed a suite of interventions, including the use of “choice screens” to prompt users to select a default search engine. Yet critics argue that such measures, introduced too late and with limited enforcement mechanisms, fall short of meaningfully disrupting Google's entrenchment—an argument bolstered by the European Union’s tepid results following a similar Android-based remedy in 2019. To assess the real-world effectiveness of such interventions, this study aims to examine how default search engine settings shape user choices and how a variety of design interventions—modeled on plausible remedial frameworks available to regulators and courts —influence search behavior. We employ a two-phase experimental design targeting both desktop and mobile platforms, with participants recruited via Prolific. The first phase establishes a behavioral baseline while administering the intervention across the experimental conditions. The second phase, conducted after a delay, assesses the durability of observed behavioral shifts, enabling us to evaluate the long-term efficacy of choice architecture interventions. For mobile participants, we target iPhone users and implement choice architecture interventions using iOS Shortcuts, collecting behavioral data through Safari history exports. These methods, made possible by recent iOS updates, enable a novel and scalable approach to studying user behavior in naturalistic settings and open new possibilities for field experiments in digital platform research. Our findings will provide empirical insight into the real-world potency of behavioral remedies in digital platform markets—an area where policymaking has outpaced empirical evidence and measurement. Reading List 1. Dark Patterns and Privacy Choice 1. Jamie Luguri and Lior Jacob Strahilevitz. 2021. Shining a light on dark patterns. Journal of Legal Analysis 13, 1 (2021), 43–109. 2. Arunesh Mathur, Mihir Kshirsagar, and Jonathan Mayer. 2021. What makes a dark pattern . . . dark? Design attributes, normative considerations, and measurement methods. In Proceedings of the 2021 CHI Conference on Human Factors in Computing Systems . ACM, New York, NY, USA, 1–18. 3. Christine Utz, Martin Degeling, Sascha Fahl, Florian Schaub, and Thorsten Holz. 2019. (Un)informed consent: Studying GDPR consent notices in the field. In Proceedings of the ACM SIGSAC Conference on Computer and Communications Security (CCS’19) . ACM, 973–990. 4. Midas Nouwens, Ilaria Liccardi, Michael Veale, David Karger, and Lalana Kagal. 2020. Dark patterns after the GDPR: Scraping consent pop-ups and demonstrating their influence. In Proceedings of the 2020 CHI Conference on Human Factors in Computing Systems . 1–13. 2. Field Experiments Involving Online Activity 1. Hunt Allcott, Juan Camilo Castillo, Matthew Gentzkow, Leon Musolff, and Tobias Salz. 2024. Sources of Market Power in Web Search: Evidence from a Field Experiment. Working Paper (2024). 2. Andrew M Guess, Neil Malhotra, Jennifer Pan, Pablo Barberá, Hunt Allcott, Taylor Brown, Adriana Crespo-Tenorio, Drew Dimmery, Deen Freelon, Matthew Gentzkow, et al. 2023. How do social media feed algorithms affect attitudes and behavior in an election campaign? Science 381, 6656 (2023), 398–404. 3. Erik Brynjolfsson, Avinash Collis, and Felix Eggers. 2019. Using massive online choice experiments to measure changes in well-being. Proceedings of the National Academy of Sciences 116, 15 (2019), 7250–7255. 3. Human-Computer Interaction 1. Alma Whitten and J. Doug Tygar. 1999. Why Johnny can’t encrypt: A usability evaluation of PGP 5.0. In Proceedings of the USENIX Security Symposium . USENIX Association, Berkeley, CA, 1–16. Alan Dix, Janet Finlay, Gregory D. Abowd, and Russel Beale. 2004. Human-Computer Interaction (3rd ed.). Pearson Education Limited.

1 0

Kaya Alpturer will present his General Exam "Optimal RANDAO Manipulation" on May 12, 2025 at 12:30pm in CS 301.
by Gradinfo 02 May '25

02 May '25

Kaya Alpturer will present his General Exam "Optimal RANDAO Manipulation" on May 12, 2025 at 12:30pm in CS 301. Committee: Matt Weinberg (adviser), Mark Braverman, Pramod Viswanath All are welcome to attend the talk. Abstract: It is well-known that RANDAO manipulation is possible in Ethereum if an adversary controls the proposers assigned to the last slots in an epoch. We provide a methodology to compute, for any fraction α of stake owned by an adversary, the maximum fraction f(α) of rounds that a strategic adversary can propose. We further implement our methodology and compute f(⋅) for all α. For example, we conclude that an optimal strategic participant with 5% of the stake can propose a 5.048% fraction of rounds, 10% of the stake can propose a 10.19% fraction of rounds, and 20% of the stake can propose a 20.68% fraction of rounds. * Roughgarden, Tim. Twenty lectures on algorithmic game theory . Cambridge University Press, 2016. * Dwork, Cynthia, Nancy Lynch, and Larry Stockmeyer. "Consensus in the presence of partial synchrony." Journal of the ACM (JACM) 35.2 (1988): 288-323. * Fischer, Michael J., Nancy A. Lynch, and Michael S. Paterson. "Impossibility of distributed consensus with one faulty process." Journal of the ACM (JACM) 32.2 (1985): 374-382. * Yin, Maofan, et al. "HotStuff: BFT consensus with linearity and responsiveness." Proceedings of the 2019 ACM symposium on principles of distributed computing . 2019. * Cleve, Richard. "Limits on the security of coin flips when half the processors are faulty." Proceedings of the eighteenth annual ACM symposium on Theory of computing . 1986. * Eyal, Ittay, and Emin Gün Sirer. "Majority Is Not Enough: Bitcoin Mining Is Vulnerable." International Conference on Financial Cryptography and Data Security . Berlin, Heidelberg: Springer Berlin Heidelberg, 2014. * Sapirshtein, Ayelet, Yonatan Sompolinsky, and Aviv Zohar. "Optimal selfish mining strategies in bitcoin." Financial Cryptography and Data Security: 20th International Conference, FC 2016, Christ Church, Barbados, February 22–26, 2016, Revised Selected Papers 20 . Springer Berlin Heidelberg, 2017. * Cai, Yang, Nikhil R. Devanur, and S. Matthew Weinberg. "A duality based unified approach to bayesian mechanism design." Proceedings of the forty-eighth annual ACM symposium on Theory of Computing . 2016. * Beyhaghi, Hedyeh, and S. Matthew Weinberg. "Optimal (and benchmark-optimal) competition complexity for additive buyers over independent items." Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing . 2019. * Roughgarden, Tim. "Transaction Fee Mechanism Design." Journal of the ACM 71.4 (2024): 1-25. * Heilman, Ethan, et al. "Eclipse attacks on {Bitcoin’s}{peer-to-peer} network." 24th USENIX security symposium (USENIX security 15) . 2015. * Matheus V. X. Ferreira, S. Matthew Weinberg. “Proof-of-Stake Mining Games with Perfect Randomness” EC 2021.

1 0