- talks - lists.cs.princeton.edu

Decentralization of Power Through Blockchain Technology: Happening TODAY
by Emily C. Lawrence 06 Oct '22

06 Oct '22

Join us for the first seminar series event for Princeton's new Center for the [ https://decenter.princeton.edu/ | Decentralization of Power Through Blockchain Technology ] , also known as DeCenter. Lunch will be available beginning at noon. This first event will have two parts: first, the DeCenter co-directors, Dean Andrea Goldsmith and Professor Jaswinder Singh will speak about the goals for the new center. Then, a panel will discuss some of the technology and applications aspirations around blockchains along with their implications for society. Introduction to DeCenter: Andrea J. Goldsmith, Dean of the School of Engineering and Applied Science, Arthur LeGrand Doty Professor of Electrical Engineering, and co-director of DeCenter Jaswinder Singh, Professor of Computer Science, Technology, and Societal Change, co-director of DeCenter Technology, Applications, and Society, a panel discussion moderated by Professor Singh, featuring: Maria Apostolaki, Assistant Professor of Electrical and Computer Engineering Nolan McCarty, Susan Dod Brown Professor of Politics and Public Affairs and Director of the Center for Data-Driven Social Science Andrés Monroy-Hernández, Assistant Professor of Computer Science Pramod Viswanath, Forrest G. Hamrick Professor in Engineering Members of the public (without Princeton affiliation) who wish to attend must register. PUID holders do not need to register. And stay tuned for future DeCenter seminars! Monthly seminars will take place fully in-person on the first Thursday of the month from 12:30 p.m. - 1:20 p.m. in Computer Science Room 105. Videos of seminars will be made available after the event. The next seminar will take place on November 3. [ https://www.cs.princeton.edu/events/26262 | Click here for talk event info. ]

1 0

Arvind Narayanan - The Limits Of The Quantitative Approach To Discrimination: Oct 11
by Emily C. Lawrence 05 Oct '22

05 Oct '22

James Baldwin Lecture Series: Arvind Narayanan – The Limits Of The Quantitative Approach To Discrimination Date: Tuesday, October 11, 2022 Time: 5:00 pm - 6:30 pm Website: [ https://aas.princeton.edu/events/2022/james-baldwin-lecture-series-limits-q… | https://aas.princeton.edu/events/2022/james-baldwin-lecture-series-limits-q… ] Location East Pyne 010 [ https://www.eventbrite.com/e/james-baldwin-lecture-series-tickets-417929748… | REGISTER to attend. ] The annual James Baldwin Lecture series was launched on March 29, 2006, aiming to celebrate the work of Princeton faculty and to provide an occasion for the intellectual community to reflect on the issue of race and American democracy. The lectures also honor the work of the late essayist James Baldwin, one of America’s most powerful cultural critics. Discrimination is obvious to the people facing discrimination. Given this, do we even need quantitative studies to test if it exists? Regardless of the answer, quantitative studies such as ProPublica’s “Machine Bias” have had a galvanizing effect on racial justice, especially in the context of automated decision-making. In this talk, I will discuss what the quantitative approach can reveal, but, more importantly, situations where it cannot tell us what we need to know. Both because of the inherent limits of quantification and because of the way knowledge is socially constructed in quantitative communities, such studies tend to drastically underestimate discrimination, oppression, and algorithmic harms. In the end, quantification is no substitute for centering the experiences of those harmed. Bio: Arvind Narayanan is a professor of computer science at Princeton. His work was among the first to show how machine learning reflects cultural stereotypes including racial and gender biases. He is co-authoring a [ https://fairmlbook.org/ | textbook in fairness and machine learning ] . Narayanan co-created an online course and textbook on bitcoin and cryptocurrency technologies which has been used in over 150 courses worldwide. He is a recipient of the Presidential Early Career Award for Scientists and Engineers (PECASE), twice recipient of the Privacy Enhancing Technologies Award, and thrice recipient of the Privacy Papers for Policy Makers Award.

1 0

Neil Agarwal will present his General Exam on Tuesday, October 4th, 2022 at 1pm in CS 105.
by Nicki Mahler 30 Sep '22

30 Sep '22

Neil Agarwal will present his General Exam on Tuesday, October 4th, 2022 at 1pm in CS 105. Zoom link: https://princeton.zoom.us/j/95202734109 The members of his committee are as follows: Ravi Netravali (adviser), Jennifer Rexford, and Amit Levy Abstract: https://docs.google.com/document/d/1QRnVxlcKWewGSNBl19IARoH4gCg2YvISSeqJ1oj… Machine learning-based video analytics pipelines have become the de facto solution for automated and accurate video processing. However, deploying video analytics pipelines has become increasingly prohibitive due to the growing number of camera feeds, more complex and specialized vision models, and the broadening range of applications and use cases. Practically supporting this rising demand necessitates the efficient utilization of underlying resources (e.g., heterogeneous hardware, storage, network bandwidth). My research focuses on designing automated and general resource optimization techniques and building systems to practically incorporate these techniques into existing video analytics pipelines. My work has targeted 3 key operational scenarios: querying large-scale video datasets in the cloud, real-time analytics in resource-constrained edge settings, and privacy-preserving video analytics queries. In today's talk, I will discuss one of these projects, Gemel, which aims to reduce GPU memory pressure in edge video analytics deployments. We observe that edge-box GPUs lack the memory needed to concurrently house the growing number of (increasingly complex) models for real-time inference. We present model merging, a new memory management technique that exploits architectural similarities between edge vision models by judiciously sharing their layers (including weights) to reduce workload memory costs and swapping delays. Gemel efficiently integrates merging into existing pipelines by (1) leveraging several guiding observations about per-model memory usage and inter-layer dependencies to quickly identify fruitful and accuracy-preserving merging configurations, and (2) altering edge inference schedules to maximize merging benefits. Reading List: https://docs.google.com/document/d/1QRnVxlcKWewGSNBl19IARoH4gCg2YvISSeqJ1oj…

1 1

Murali Srirangam Ramanujam will present a General Exam entitled "App-driven optimizations to boost smartphone resource efficiency" on Monday, October 3, 2022 at 3pm in CS 302.
by Nicki Mahler 29 Sep '22

29 Sep '22

Murali Srirangam Ramanujam will present a General Exam entitled "App-driven optimizations to boost smartphone resource efficiency" on Monday, October 3, 2022 at 3pm in CS 302. Zoom link: [ https://princeton.zoom.us/my/muralisr92 | https://princeton.zoom.us/my/muralisr92 ] The members of the committee are as follows: Ravi Netravali (adviser), Amit Levy, and Wyatt Lloyd Abstract: [ https://docs.google.com/document/d/1trZhu-zt9wRft6nJO5_BnOCvgQMjd2n4D7s5pbP… | https://docs.google.com/document/d/1trZhu-zt9wRft6nJO5_BnOCvgQMjd2n4D7s5pbP… ] Low interaction response times are crucial to the experience that mobile apps provide for their users. These response times are determined by both the network delays incurred during content fetches, as well as the client-side computation delays to parse/render that content and other code in the app. Unfortunately, existing strategies to alleviate the network and compute latencies that hinder app responsiveness fall short in practice. We first present Marauder, a system to address network latencies by synergizing caching and prefetching to improve speedups achieved by each technique while avoiding their inherent limitations. Key to Marauder is our observation that, like web pages, apps handle interactions by downloading and parsing structured text resources that entirely list (i.e., without needing to consult app binaries) the set of other resources to load. Next, we present Floo, a system that aims to automatically reuse (or memoize) computation results during app operation in an effort to reduce the amount of computation needed to handle user interactions. In designing Floo, our primary insight is that app computations exhibit substantial stability over time in that they are entirely performed in rarely-updated codebases within app binaries and the OS. Across a wide range of apps, live networks, phones, and interaction traces, Marauder and Floo reduce median interaction response times by 27.4% and 32.7% respectively. Reading List: https://docs.google.com/document/d/1N_2e1CevxdQVyqnMYqi79TzcnpS5p3R64ybmMdk…

1 0

Dan Friedman will present his General Exam "Finding Dataset Shortcuts with Grammar Induction" on Monday, October 3, 2022 at 3:00 PM in CS 301 and via zoom.
by Louis W. Riehl 29 Sep '22

29 Sep '22

Dan Friedman will present his General Exam " Finding Dataset Shortcuts with Grammar Induction " on Monday, October 3, 2022 at 3:00 PM in CS 301 and via zoom. Zoom link: [ https://princeton.zoom.us/j/8636741030 | https://princeton.zoom.us/j/8636741030 ] Committee Members: Danqi Chen (advisor), Tom Griffiths , Karthik Narasimhan Abstract: Many NLP datasets have been found to contain “shortcuts”, simple decision rules that achieve surprisingly high accuracy. However, it is difficult to automatically discover whether a dataset contains shortcuts. Prior work has used simple classifiers, which can find only simple patterns, or qualitative heuristics like saliency maps, which lack a clear statistical interpretation. In this work, we use probabilistic grammars to characterize and discover NLP shortcuts. We describe an approach for inducing expressive grammars from text, and show how the resulting grammars can reveal interesting shortcut features in a number of single-sentence and sentence pair classification datasets. We explore applications to other settings where it is useful to have a formal characterization of a distribution of text, including domain generalization and transfer learning. Reading List: [ https://docs.google.com/document/d/1vboaALDbdh4B3AVmVna73vTB8cO7LmbQRzrixEy… | https://docs.google.com/document/d/1vboaALDbdh4B3AVmVna73vTB8cO7LmbQRzrixEy… ] Everyone is invited to attend the talk, and those faculty wishing to remain for the oral exam following are welcome to do so. Louis Riehl Graduate Administrator Computer Science Department, CS213 Princeton University (609) 258-8014

1 0

CS Colloquium Series: week of April 11-15
by Emily C. Lawrence 19 Sep '22

19 Sep '22

Here is the full list of CS Colloquium talks for next week. All talks will be recorded. ~~~~~ CS Colloquium Speaker Speaker: Parastoo Abtahi, Stanford University Date: Monday, April 11, 2022 Time: 12:30pm EST Location: CS 105 Hosts: Andrés Monroy-Hernández & Adam Finkelstein Event page: [ https://www.cs.princeton.edu/events/26186 | https://www.cs.princeton.edu/events/26186 ] This talk will be live-streamed at [ https://mediacentrallive.princeton.edu/ | https://mediacentrallive.princeton.edu/ ] Title: From Haptic Illusions in Virtual Reality to Beyond-Real Interactions Abstract: Advances in audiovisual rendering have led to the commercialization of virtual reality (VR) hardware; however, haptic technology has not kept up with these advances. While haptic devices aim to bridge this gap by simulating the sensation of touch, there are many hardware limitations that make realistic touch interactions in VR challenging. In my research, I explore how by understanding human perception, we can design VR interactions that not only overcome the current limitations of VR hardware, but also extend our abilities beyond what is possible in the real world. In this talk, I will present my work on redirection illusions that leverage the limits of human perception to improve the perceived performance of encountered-type haptic devices, such as improving the position accuracy of drones, the speed of tabletop robots, and the resolution of shape displays when used for haptics in VR. I will then present a framework I have developed through the lens of sensorimotor control theory to argue for the exploration and evaluation of VR interactions that go beyond mimicking reality. Bio: Parastoo Abtahi is a final year computer science PhD candidate and a Gerald J. Lieberman fellow at Stanford University, where she is co-advised by Prof. James Landay and Prof. Sean Follmer. Her research area is human-computer interaction (HCI) and she works broadly on virtual reality interactions and spatial computing. Her research has been published at top HCI venues, such as the ACM Conference on Human Factors in Computing Systems (CHI) and the ACM User Interface Software and Technology Symposium (UIST), and has received two honorable mention paper awards. Her work has been supported by the Stanford Institute for Human-Centered Artificial Intelligence, the Hasso Plattner Design Thinking Research Program, and the VMware fellowship. Prior to Stanford, Parastoo received her bachelor’s degree in Electrical and Computer Engineering from the University of Toronto as part of the Engineering Science program. ~~~~~ CS Colloquium Speaker Speaker: Ferran Alet, Massachusetts Institute of Technology Date: Tuesday, April 12, 2022 Time: 12:30pm EST Location: CS 105 Host: Olga Russakovsky Event page: https://www.cs.princeton.edu/events/26187 This talk will be live-streamed at https://mediacentrallive.princeton.edu/ Title: A flexible framework for machine learning Abstract: In this last decade, we have seen a lot of progress in AI and machine learning using a single recipe: given a task, we train a single neural network to map inputs to outputs. In this talk, I will show that this one-neural-network-per-task framework can be extended to improve generalization. First, I will describe modular meta-learning, which achieves language-like generalization by training a set of composable neural modules. By having multiple neural networks per task, and multiple tasks per neural network, we are able to reuse information and achieve bigger data and computational efficiency. In the second part of my talk, I will describe tailoring, a general way of encoding inductive biases in neural networks by optimizing unsupervised objectives inside the prediction function, essentially having one neural network per input. Finally, I will describe my vision for creating a flexible ML framework that will enable training reinforcement learning policies within minutes rather than days, solving complex search and discovery problems, and improving our understanding of generalization in deep learning. Bio: Ferran Alet is a PhD candidate at MIT CSAIL advised by Leslie Kaelbling, Tomas Lozano-Perez, and Joshua Tenenbaum. His research is on machine learning and leverages techniques from meta-learning, learning to search, program synthesis, and insights from mathematics and the physical sciences. During his PhD, he created the MIT Embodied Intelligence Seminar, mentored 17 students, and won the MIT Outstanding Mentor award 2021. Ferran studied mathematics and physics in Barcelona thanks to CFIS, a program for doing two degrees, where he was the valedictorian of his promotion. In college, he participated in the ACM-ICPC programming contest, being the most decorated in the history of his regional phase (South Western Europe). In grad school, he earned a “La Caixa” fellowship and was responsible for the high-level planner of the MIT-Princeton team for the Amazon Robotics Challenge, which won the stowing task in 2017. You can find more information and papers at www.alet-et.al ~~~~~ CS Colloquium Speaker Speaker: Benedikt Bünz, Stanford University Date: Thursday, April 14, 2022 Time: 12:30pm EST Location: CS 105 Hosts: Jonathan Mayer & Arvind Narayanan Event page: https://www.cs.princeton.edu/events/26188 This talk will be live-streamed at https://mediacentrallive.princeton.edu/ Title: Improving the privacy, scalability, and ecological impact of blockchains Abstract: Blockchains are an exciting area of research that touches on many areas of Computer Science and beyond. This technology has the potential to enable a fast, cheap, and private financial system based on distributed consensus and cryptography, instead of trusted parties. Despite this potential, the reality still shows severe limitations of blockchains: (i) transactions can cost hundreds of dollars and take minutes to confirm, (ii) some blockchains offer little privacy, and (iii) proof-of-work consensus consumes too much energy. In this talk, I will discuss powerful techniques that follow a prover paradigm and can mitigate these limitations. The first technique, called Bulletproofs, is a general-purpose zero-knowledge proof system that is specifically designed to enable confidential blockchain transactions. Bulletproofs requires minimal trust assumptions and gives the shortest zero-knowledge proofs without trusted setup. The system is widely deployed and powers tens of thousands of private blockchain transactions per day. The second technique, called inner pairing products, is a way to aggregate many zero-knowledge proofs into a single short proof. This can significantly reduce on-chain data, leading to a significant increase in transactions per second that the chain can process. The third technique is a new concept called a verifiable delay function (VDF) that is vital for permission-less and eco-friendly consensus. VDFs are already deployed in Filecoin and Chia, and are planned for Ethereum 2.0, the upcoming upgrade to Ethereum. Bio: Benedikt Bünz is a PhD candidate at Stanford University, a member of Dan Boneh’s applied cryptography lab, and a recipient of the Microsoft Research Fellowship at the Simons Institute. His work on the science of Blockchains uses tools from applied cryptography, distributed systems, and algorithmic game theory. His research focuses on building new proof protocols for improving the privacy, scalability, and ecological impact of blockchains. Several of his research results have had a significant industry impact. His work on Bulletproofs, secures tens of thousands of private transactions on Blockchains like Monero or Signal’s Mobilecoin. His seminal work on Verifiable Delay Functions (VDFs) sparked the VDF Alliance, a multi-million dollar initiative composed of academic, non-profit, and corporate collaborators.

1 11

CS departmental talk: Michael Figurnov, Thursday, 9/22 at 3pm
by Emily C. Lawrence 15 Sep '22

15 Sep '22

Date: Thursday, September 22nd, 3pm ET Speaker: Dr. Michael Figurnov (DeepMind) Host: Ellen Zhong Location: Zoom: [ https://princeton.zoom.us/j/96893116773 | https://princeton.zoom.us/j/96893116773 ] Event page: [ https://www.cs.princeton.edu/events/26247 | https://www.cs.princeton.edu/events/26247 ] Title: Highly accurate protein structure prediction with AlphaFold Abstract: Predicting a protein’s structure from its primary sequence has been a grand challenge in biology for the past 50 years, holding the promise to bridge the gap between the pace of genomics discovery and resulting structural characterization. In this talk, we will describe work at DeepMind to develop AlphaFold, a new deep learning-based system for structure prediction that achieves high accuracy across a wide range of targets. We demonstrated our system in the 14th biennial Critical Assessment of Protein Structure Prediction (CASP14) across a wide range of difficult targets, where the assessors judged our predictions to be at an accuracy “competitive with experiment” for approximately 2/3rds of proteins. The talk will focus on the underlying machine learning ideas, while also touching on the implications for biological research. Bio: Michael Figurnov is a Staff Research Scientist at DeepMind. He has been working with the AlphaFold team for the past four years. Before joining DeepMind, he did his Ph.D. in Computer Science at the Bayesian Methods Research Group under the supervision of Dmitry Vetrov. His research interests include deep learning, Bayesian methods, and machine learning for biology.

1 0

Reminder: Princeton AI Club Kick-Off Event with Special Guest Speaker: Prof. Yann LeCun (Meta-FAIR & New York University)
by Emily C. Lawrence 30 Aug '22

30 Aug '22

Reminder: Happening this week! The Princeton AI Club is thrilled to announce its kick-off event for the coming academic year, and we have a special guest speaker for you – [ http://yann.lecun.com/ | Prof. Yann LeCun ] from Meta-FAIR & New York University! When? September 1 st at 11:30 am Eastern Time (ET) ! Where? Computer Science Building, Room 105, Princeton University, and virtually. Sign up [ https://forms.gle/BonERMY1GNbS1vaM6 | here ] ! An in-person brunch and social event will start at 11:00 am [ https://calendar.google.com/event?action=TEMPLATE&tmeid=MW04ZDliYzc2NWE2aDM… | add brunch event to calendar ] ! Hurry up, in person attendance has limited availability. Speaker: Prof. Yann LeCun (Meta-FAIR & New York University) Title: From Machine Learning to Autonomous Intelligence Date: September 1 st at 11:30 am Eastern Time (ET). Our brunch and social event will start at 11:00 am. Abstract: How could machines learn as efficiently as humans and animals? How could machines learn to reason and plan? How could machines learn representations of percepts and action plans at multiple levels of abstraction, enabling them to reason, predict, and plan at multiple time horizons? I will propose a possible path towards autonomous intelligent agents, based on a new modular cognitive architecture and a somewhat new self-supervised training paradigm. The centerpiece of the proposed architecture is a configurable predictive world model that allows the agent to plan. Behavior and learning are driven by a set of differentiable intrinsic cost functions. The world model uses a new type of energy-based model architecture called H-JEPA (Hierarchical Joint Embedding Predictive Architecture). H-JEPA learns hierarchical abstract representations of the world that are simultaneously maximally informative and maximally predictable. The corresponding working paper is available here: [ https://openreview.net/forum?id=BZ5a1r-kVsf | https://openreview.net/forum?id=BZ5a1r-kVsf ] Bio: Yann LeCun is VP & Chief AI Scientist at Meta and Silver Professor at NYU affiliated with the Courant Institute of Mathematical Sciences & the Center for Data Science. He was the founding Director of FAIR and of the NYU Center for Data Science. He received an Engineering Diploma from ESIEE (Paris) and a PhD from Sorbonne Université. After a postdoc in Toronto he joined AT&T Bell Labs in 1988, and AT&T Labs in 1996 as Head of Image Processing Research. He joined NYU as a professor in 2003 and Meta/Facebook in 2013. His interests include AI machine learning, computer perception, robotics and computational neuroscience. He is the recipient of the 2018 ACM Turing Award (with Geoffrey Hinton and Yoshua Bengio) for "conceptual and engineering breakthroughs that have made deep neural networks a critical component of computing", a member of the National Academy of Sciences, the National Academy of Engineering, the French Académie des Sciences.

1 0

Princeton AI Club Kick-Off Event with Special Guest Speaker: Prof. Yann LeCun (Meta-FAIR & New York University)
by Emily C. Lawrence 26 Aug '22

26 Aug '22

The Princeton AI Club is thrilled to announce its kick-off event for the coming academic year, and we have a special guest speaker for you – [ http://yann.lecun.com/ | Prof. Yann LeCun ] from Meta-FAIR & New York University! When? September 1 st at 11:30 am Eastern Time (ET) ! Where? Computer Science Building, Room 105, Princeton University, and virtually. Sign up [ https://forms.gle/BonERMY1GNbS1vaM6 | here ] ! An in-person brunch and social event will start at 11:00 am [ https://calendar.google.com/event?action=TEMPLATE&tmeid=MW04ZDliYzc2NWE2aDM… | add brunch event to calendar ] ! Hurry up, in person attendance has limited availability. Speaker: Prof. Yann LeCun (Meta-FAIR & New York University) Title: From Machine Learning to Autonomous Intelligence Date: September 1 st at 11:30 am Eastern Time (ET). Our brunch and social event will start at 11:00 am. Abstract: How could machines learn as efficiently as humans and animals? How could machines learn to reason and plan? How could machines learn representations of percepts and action plans at multiple levels of abstraction, enabling them to reason, predict, and plan at multiple time horizons? I will propose a possible path towards autonomous intelligent agents, based on a new modular cognitive architecture and a somewhat new self-supervised training paradigm. The centerpiece of the proposed architecture is a configurable predictive world model that allows the agent to plan. Behavior and learning are driven by a set of differentiable intrinsic cost functions. The world model uses a new type of energy-based model architecture called H-JEPA (Hierarchical Joint Embedding Predictive Architecture). H-JEPA learns hierarchical abstract representations of the world that are simultaneously maximally informative and maximally predictable. The corresponding working paper is available here: [ https://openreview.net/forum?id=BZ5a1r-kVsf | https://openreview.net/forum?id=BZ5a1r-kVsf ] Bio: Yann LeCun is VP & Chief AI Scientist at Meta and Silver Professor at NYU affiliated with the Courant Institute of Mathematical Sciences & the Center for Data Science. He was the founding Director of FAIR and of the NYU Center for Data Science. He received an Engineering Diploma from ESIEE (Paris) and a PhD from Sorbonne Université. After a postdoc in Toronto he joined AT&T Bell Labs in 1988, and AT&T Labs in 1996 as Head of Image Processing Research. He joined NYU as a professor in 2003 and Meta/Facebook in 2013. His interests include AI machine learning, computer perception, robotics and computational neuroscience. He is the recipient of the 2018 ACM Turing Award (with Geoffrey Hinton and Yoshua Bengio) for "conceptual and engineering breakthroughs that have made deep neural networks a critical component of computing", a member of the National Academy of Sciences, the National Academy of Engineering, the French Académie des Sciences.

1 0

Corey Sinnamon will present his FPO "Analysis of self-adjusting heaps" on Tuesday, 8/30/2022 at 3PM via Zoom.
by Gradinfo 24 Aug '22

24 Aug '22

Corey Sinnamon will present his FPO " Analysis of self-adjusting heaps" on Tuesday, 8/30/2022 at 3PM via Zoom. Zoom Link: [ https://princeton.zoom.us/my/sinnamon | https://princeton.zoom.us/my/sinnamon ] 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. The members of Corey's committee are as follows: Examiners: Robert Tarjan (Advisor), Bernard Chazelle, and Maria Chudnovsky. Readers: Huacheng Yu and László Kozma (Freie Universität Berlin). Abstract: We study the amortized efficiency of self-adjusting heap data structures. Heaps (also called priority queues) are fundamental data structures, and a great deal of work has been devoted to inventing efficient heaps and analyzing them. We prove new amortized bounds for pairing heaps, multipass pairing heaps, slim heaps, and smooth heaps. The pairing heap is a classic self-adjusting heap, known to be simple, robust, and efficient in practice. Despite decades of study, its exact efficiency is still unresolved. We prove new amortized bounds on the time per operation of the pairing heap: O(log n) amortized time for delete-min and delete; O( √ log log N2 √ 2 log2 log2 N ) amortized time for insert, meld, and decrease-key; and O(1) time for make-heap and find-min. Here n is the current number of items in the heap, and N is an upper bound on n across all operations. The multipass pairing heap is a well-known variant of the pairing heap. We prove it satisfies amortized time bounds of O(log n) for delete-min and delete; O(log log n·log log log n) for decreasekey; and O(1) for insert, meld, make-heap, and find-min. This is the first analysis in which both insert and delete-min take O(log n) amortized time. It matches the known lower bounds for all operations except decrease-key, and the bound for decrease-key comes close to the lower bound. We prove the same bounds for the lazy version of multipass pairing heaps, in which insert, meld, and decrease-key operations are done lazily. Again, these bounds are tight for all operations except decrease-key. The smooth heap and the closely related slim heap are much newer self-adjusting heaps. For these two heaps, we give a tight analysis of the amortized time per operation: O(log n) for deletemin and delete; O(log log n) for decrease-key; and O(1) for make-heap, find-min, insert, and meld. These bounds are tight not only for smooth and slim heaps, but for any heap in Iacono and Ozkan’s ¨ pure heap model, intended to capture all self-adjusting heaps. Slim and smooth heaps are the first known data structures to match Iacono and Ozkan’s lower bounds and to satisfy the constraints of ¨ their model. We prove tight bounds for both eager and lazy versions of slim and smooth heaps.

1 0