- talks - lists.cs.princeton.edu

Jennifer Gossels will present her Pre FPO "Joint Optimization for Robust Network Design and Operation" on Thursday, May 23, 2019 at 1pm in CS 401
by Nicki Mahler 17 May '19

17 May '19

Jennifer Gossels will present her Pre FPO "Joint Optimization for Robust Network Design and Operation" on Thursday, May 23, 2019 at 1pm in CS 401. The members of her committee are as follows: Jennifer Rexford (adviser), Mike Freedman (non reader), Wyatt Lloyd (non reader), Kai Li (reader), and Gagan Choudhury (AT&T; reader). Her abstract follows below. All are welcome to attend. Abstract: The Internet is an integral part of nearly all aspects of modern life, and Internet Service Provider (ISP) backbone networks play an integral part in our Internet experience. Therefore, ISPs must design their networks to limit congestion and also to limit the disruptions caused by component failures. One obvious way to ensure that there's no congestion, even when switches or links fail, is to dramatically over provision the network. If the ISP builds, e.g., two redundant links for every link it actually needs, that network will probably not get too congested or disturbed by failures. But, buying all this equipment is prohibitively costly for the ISP. In this talk we explore how the ISP can optimally balance its objective of carrying all offered traffic with minimal congestion, even in the presence of failures, with its objective of minimizing costs. The question is complicated because the ISP makes some decisions, like purchasing and placing equipment, on long timescales (months or years), and some decisions, like exactly how to route packets from a given flow, on short timescales (seconds). We classify the long timescale decisions as network design and the short timescale decisions as network operation. These decisions interact such that the ISP must consider both of them simultaneously if it wants to make a decision about either one. Accounting for failures only complicates the situation further. In the first part of this talk, we focus on the network design problem, leveraging modern optical equipment's reconfigurability to design a minimal cost network that can still carry all traffic, even if components fail. Although this part of the talk focuses on network design, we also address network operation, since the two are interdependent. Our solution allows ISPs to save up to 29% off the cost of their network infrastructure. In the second part of this talk we shift our focus to network operation. We propose a failure recovery protocol that allows for faster responses to failures than the approaches currently employed by ISPs. Our insight here is that this improved network operation approach is possible if ISPs take into account the heterogenous nature of the switches they have deployed when designing their networks. Hence, although this part of the talk focuses on network operation, it, too, addresses network design.

1 0

Yuping Luo will present his General Exam on Thursday, May 23, 2019 at 4pm in CS 301
by Nicki Mahler 16 May '19

16 May '19

Yuping Luo will present his General Exam on Thursday, May 23, 2019 at 4pm in CS 301. The members of his committee are Sanjeev Arora (adviser), Karthik Narasimhan, and Elad Hazan. Everyone is invited to attend his talk, and those faculty wishing to remain for the oral exam following are welcome to do so. His abstract and reading list follow below. Abstract: In recent years, model-free reinforcement learning has demonstrated its significant success in many fields. However, these algorithms suffer from high sample complexity and require a massive number of interactions with the environment, which can be expensive in the physical world. Model-based reinforcement learning is considered to be a promising approach to reduce sample complexity. However, the theoretical understanding of such methods has been rather limited. In this talk, I'll present an algorithmic framework for designing and analyzing model-based RL algorithms with theoretical guarantees. We design a meta-algorithm with a theoretical guarantee of monotone improvement to a local maximum of the expected reward. The meta-algorithm iteratively builds a lower bound of the expected reward based on the estimated dynamical model and sample trajectories and then maximizes the lower bound jointly over the policy and the model. Instantiating our framework with simplification gives a variant of model-based RL algorithms Stochastic Lower Bounds Optimization. Experiments demonstrate that our algorithm achieves state-of-the-art performance when only one million or fewer samples are permitted on a range of continuous control benchmark tasks. [1] Thanard Kurutach, Ignasi Clavera, Yan Duan, Aviv Tamar, and Pieter Abbeel. Model-ensemble trust-region policy optimization. arXiv preprint arXiv:1802.10592, 2018. [2] Sutton, Richard S. "Dyna, an integrated architecture for learning, planning, and reacting." ACM SIGART Bulletin 2.4 (1991): 160-163. [3] Gu, Shixiang, et al. "Continuous deep q-learning with model-based acceleration." International Conference on Machine Learning. 2016. [4] Buckman, Jacob, et al. "Sample-efficient reinforcement learning with stochastic ensemble value expansion." Advances in Neural Information Processing Systems. 2018. [5] Feinberg, Vladimir, et al. "Model-based value estimation for efficient model-free reinforcement learning." arXiv preprint arXiv:1803.00101 (2018). [6] Pascanu, Razvan, et al. "Learning model-based planning from scratch." arXiv preprint arXiv:1707.06170 (2017). [7] Clavera, Ignasi, et al. "Model-based reinforcement learning via meta-policy optimization." arXiv preprint arXiv:1809.05214 (2018). [8] Chua, Kurtland, et al. "Deep reinforcement learning in a handful of trials using probabilistic dynamics models." Advances in Neural Information Processing Systems. 2018. [9] Asadi, Kavosh, Dipendra Misra, and Michael L. Littman. "Lipschitz continuity in model-based reinforcement learning." arXiv preprint arXiv:1804.07193 (2018). [10] Farahmand, Amir-massoud, Andre Barreto, and Daniel Nikovski. "Value-aware loss function for model-based reinforcement learning." Artificial Intelligence and Statistics. 2017.

1 0

Colloquium Speaker Yiying Zhang, Tuesday, May 21
by Emily C. Lawrence 16 May '19

16 May '19

Yiying Zhang from Purdue University Tuesday, May 21, 2019 Computer Science - Room 105 at 1:30pm Host: Amit Levy [ https://www.cs.princeton.edu/events/25862 | https://www.cs.princeton.edu/events/25862 ] Farewell to Servers: Software and Hardware Approaches towards Datacenter Resource Disaggregation Datacenters have been using the "monolithic" server model for decades, where each server hosts a set of hardware devices like CPU and DRAM on a motherboard and runs an OS on top to manage the hardware resources. This monolithic server model fundamentally restricts datacenters from achieving efficient resource packing, hardware rightsizing, and great heterogeneity. Recent hardware and application trends such as serverless computing further call for a rethinking of the long-standing server-centric model. My answer is to "disaggregate" monolithic servers into network-attached hardware components that host different hardware resources and offer different functionalities (e.g., a processor component for computation, a memory component for fast data accesses). I believe that after evolving from physical (DC-1.0) to virtual (DC-2.0), datacenters should evolve further into a disaggregated one (DC-3.0), where hardware resources can be allocated and scaled to the exact amount that applications use and can be individually managed and customized for different application needs. By not having servers, DC-3.0 disrupts designs and technologies in almost every layer in today's datacenters, from hardware and networking to OS and applications. My lab undertook pioneering efforts in building an end-to-end solution for DC-3.0 with a new OS, a new hardware platform, and a new network system. This talk will focus on two systems that are central to the design of DC-3.0: 1) LegoOS , a new distributed operating system designed for managing disaggregated resources. LegoOS splits OS functionalities into different units, each running at a hardware component and managing the component's hardware resources. LegoOS enables the disaggregation and customization of OS functionalities, a significant step towards building DC-3.0's software infrastructure. 2) LegoFPGA , a new approach of using FPGA to efficiently manage and virtualize hardware resources. LegoFPGA offers a solution to co-design application, OS, and hardware functionalities and customize them for different hardware resources and application domains, an important step towards building DC-3.0's hardware infrastructure. With LegoOS and LegoFPGA , we demonstrate that separating core OS and hardware functionalities is not only feasible but can largely improve performance per dollar over the current datacenter monolithic server model. Bio: Yiying Zhang is an assistant professor in the School of Electrical and Computer Engineering at Purdue University. Her research interests span operating systems, distributed systems, computer architecture, and datacenter networking. She also works on the intersection of systems and programming language, security, and AI/ML. She won an OSDI best paper award in 2018 and an NSF CAREER award in 2019. Yiying’s lab is among the few groups in the world now that build new OSes and full-stack, cross-layer systems. Yiying received her Ph.D. from the Department of Computer Sciences at the University of Wisconsin-Madison under the supervision of Andrea and Remzi Arpaci-Dusseau and worked as a postdoctoral scholar at the University of California, San Diego before joining Purdue.

1 0

Jiaqi Su will present her General Exam "Perceptually-motivated environment-specific speech enhancement" on Tuesday, May 21, 2019 at 3pm in CS 302.
by Nicki Mahler 14 May '19

14 May '19

Jiaqi Su will present her General Exam "Perceptually-motivated environment-specific speech enhancement" on Tuesday, May 21, 2019 at 3pm in CS 302. The members of her committee are Adam Finkelstein (adviser), Olga Russakovsky, and Szymon Rusinkiewicz. Everyone is invited to attend her talk, and those faculty wishing to remain for the oral exam following are welcome to do so. Her abstract and reading list follow below. Title: Perceptually-motivated environment-specific speech enhancement Abstract: People make "in-the-wild" recordings every day using their devices such as phones and laptops. However, many factors in a typical environment can diminish the quality of a audio recording, including noise, reverberation and undesirable equalization. We propose a deep learning approach to enhance speech recordings made in a specific environment. A single neural network that operates on waveform learns to ameliorate several types of recording artifacts. The method relies on a new perceptually-motivated loss function that combines an adversarial loss with spectrogram features. The loss function aligns better with human perception of audio quality in comparison to commonly used sample loss, and enables learning on weakly aligned recording pairs. Both subjective and objective evaluations show that the proposed approach improves on state-of-the-art baseline methods. Papers: 1. Van Den Oord A, Dieleman S, Zen H, Simonyan K, Vinyals O, Graves A, Kalchbrenner N, Senior AW, Kavukcuoglu K. WaveNet: A generative model for raw audio. SSW. 2016 Sep 13;125. 2. Goodfellow I, Pouget-Abadie J, Mirza M, Xu B, Warde-Farley D, Ozair S, Courville A, Bengio Y. Generative adversarial nets. In Advances in neural information processing systems 2014 (pp. 2672-2680). 3. Radford A, Metz L, Chintala S. Unsupervised representation learning with deep convolutional generative adversarial networks. In ICLR 2016 4. Mysore GJ. Can we automatically transform speech recorded on common consumer devices in real-world environments into professional production quality speech?—a dataset, insights, and challenges. IEEE Signal Processing Letters. 2015 Aug;22(8):1006-10. 5. Pascual S, Bonafonte A, Serrà J. SEGAN: Speech Enhancement Generative Adversarial Network. Proc. Interspeech 2017. 2017:3642-6. 6. Rethage D, Pons J, Serra X. A wavenet for speech denoising. In2018 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) 2018 Apr 15 (pp. 5069-5073). IEEE 7. Germain FG, Mysore GJ, Fujioka T. Equalization matching of speech recordings in real-world environments. In2016 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) 2016 Mar 20 (pp. 609-613). IEEE. 8. Kinoshita K, Delcroix M, Gannot S, Habets EA, Haeb-Umbach R, Kellermann W, Leutnant V, Maas R, Nakatani T, Raj B, Sehr A. A summary of the REVERB challenge: state-of-the-art and remaining challenges in reverberant speech processing research. EURASIP Journal on Advances in Signal Processing. 2016 Dec;2016(1):7. 9. Hershey JR, Chen Z, Le Roux J, Watanabe S. Deep clustering: Discriminative embeddings for segmentation and separation. In2016 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) 2016 Mar 20 (pp. 31-35). IEEE. 10. Zhang R, Isola P, Efros AA, Shechtman E, Wang O. The unreasonable effectiveness of deep features as a perceptual metric. InProceedings of the IEEE Conference on Computer Vision and Pattern Recognition 2018 (pp. 586-595). 11. Hoffer E, Ailon N. Deep metric learning using triplet network. InInternational Workshop on Similarity-Based Pattern Recognition 2015 Oct 12 (pp. 84-92). Springer, Cham. Textbook: Goodfellow I, Bengio Y, Courville A. Deep learning. MIT press; 2016 Nov 10. [ http://www.deeplearningbook.org/ | http://www.deeplearningbook.org ] [ http://www.deeplearningbook.org/ | http://www.deeplearningbook.org ]

1 0

Meryem Essaidi will present her General Exam on Tuesday, May 21, 2019 at 9:30am in CS 402.
by Nicki Mahler 14 May '19

14 May '19

Meryem Essaidi will present her General Exam on Tuesday, May 21, 2019 at 9:30am in CS 402. The members of her committee are: Matt Weinberg (adviser), Mark Braverman, Gillat Kol Everyone is invited to attend her talk, and those faculty wishing to remain for the oral exam following are welcome to do so. Her abstract and reading list follow below. Abstract: The Mechanism Design for Social Good group is a multi-institutional research group that uses different tools to solve crucial problems (e.g. US healthcare) that nowhere have near enough foundational tools, and that impact the historically under-served communities. These problems are unable to just "use Machine Learning" because every trial in trial-and-error costs billions/trillions of dollars. In this segment of work, we are trying to do foundational theory targeted at these applications aiming to improve the societal welfare of marginalized communities, starting with healthcare. We study a problem inspired by regulated health insurance markets, such as those created by the government in the Affordable Care Act Exchanges or by employers when they contract with private insurers provide plans for their employees. The market regulator (e.g. the government or employer in these examples) can choose to do nothing, running a Free Market, or can exercise her regulatory power, such as limiting the entry of the health insurance providers to create competition and decrease prices. In this paper, we investigate whether limiting entry increases or decreases the utility of the consumers who purchase from the providers, specifically in settings where the outside option of “purchasing nothing” is prohibitively undesirable (i.e. because of the Individual Mandate). We focus primarily on the case where providers are symmetric, and study the existence of unique symmetric equilibria. We precisely define the condition under which limiting entry improves consumer utility. Using Myersonian theory, we also suggest a new distributional condition that ensures the existence of a unique symmetric equilibrium and further we show that under this assumption, the Limit-Entry condition is implied, thus limiting entry always improves consumer utility. However, we also show examples in which there exist unique symmetric equilibria where consumer utility in the free market setting exceeds that in the limited entry setting. Our techniques are based primarily on tools from revenue maximization. We also include small extensions to settings where providers have identical costs for providing plans, and to two providers with an asymmetric distribution. Reading list: - Textbook: Twenty Lectures on Algorithmic Game Theory (by Roughgarden) - Optimal Auction Design (by Myerson) - Algorithms, Games, and the Internet (by Papadimitriou) - Stable Matchings, Optimal Assignments, and Linear Programming (by Roth, Rothblum, and Vate) - Optimal and Robust Mechanism Design with Interdependent Values (by Roughgarden and Cohen) - College Admissions and the Stability of Marriage (by Gale and Shapley) - Auctions Versus Negotiations (by Bulow and Klemperer) - Simple versus Optimal Mechanisms (by Hartline and Roughgarden) - Playing Large Games Using Simple Strategies (by Lipton, Markakis, and Mehta) - A Simple Mechanism for a Budget-Constrained Buyer (by Cheng, Gravin, Munagala, and Wang) - The Economics of Matching: Stability and Incentives (by Roth)

1 0

Logan Stafman will present his FPO, "Utility Scheduling for Multi-Tenant Clusters" on Tuesday, 5/21/2019 at 11:00 AM in CS 105.
by Nicki Mahler 14 May '19

14 May '19

Logan Stafman will present his FPO, "Utility Scheduling for Multi-Tenant Clusters" on Tuesday, 5/21/2019 at 11:00 AM in CS 105. The members of his committee are as follows: Michael Freedman (adviser), Readers: Wyatt Lloyd and Kyle Jamieson; Examiners: Jennifer Rexford and Amit Levy. A copy of his thesis, is available upon request. Everyone is invited to attend his talk. The talk abstract follows below. The rapid increase in data size along with the complex patterns of data usage amongst data scientists presents new challenges for large-scale data analytics systems. Modern distributed computing frameworks must support complex applications that range from answering database queries to training machine learning models. As data centers have grown, managing their resources has become an increasingly important task. New applications have become popular that make traditional scheduling systems inadequate. In this thesis, we present distributed scheduling systems aimed at increasing cluster resource utilization by taking advantage of specific characteristics of data processing applications. First, we identify a set of applications whose characteristics make them prime targets for utility-based scheduling. We then focus on two specific types of these applications in the following systems: (i) SLAQ: a cluster scheduling system for machine learning (ML) training jobs that aims to maximize the qualities of all models trained. In exploratory model training, models can be improved more quickly by redirecting resources to jobs with the highest potential for improvement. SLAQ reduces latency and maximizes the quality of models being trained by a distributed ML cluster. (ii) ReLAQS: a cluster scheduling system for incremental approximate query processing (AQP) systems that aims to minimize the error of all approximate results. In AQP, queries compute approximate results by sampling data. In AQP, error can be reduced more quickly by allocating resources to queries with higher error. ReLAQS reduces the latency required to reach a query result with a given level of error in a shared AQP environment. These works demonstrate a novel set of methods that can be used in fine-grained scheduling to build responsive, efficient distributed systems. We have evaluated these systems on standard benchmark workloads and datasets, as well as popular ML algorithms, and show both reduced latency and increased accuracy of intermediary results.

1 0

Stephen Beard will present his FPO, "TRUSTGUARD: A MODEL FOR PRACTICAL TRUST IN REAL SYSTEMS" on Tuesday, 5/21/2019 at 1:30pm in CS 301.
by Nicki Mahler 14 May '19

14 May '19

Stephen Beard will present his FPO, "TRUSTGUARD: A MODEL FOR PRACTICAL TRUST IN REAL SYSTEMS" on Tuesday, 5/21/2019 at 1:30pm in CS 301. The members of his committee are as follows: David August (adviser); Readers: Andrew Appel and Jothy Rosenberg (CEO Dover Systems); Examiners: Aarti Gupta and Arvind Narayanan. A copy of his thesis, is available upon request. Everyone is invited to attend his talk. The talk abstract follows below. All layers of today’s computing systems, from hardware to software, are vulnerable to attack. Market and economic pressure push companies to focus on performance and features, leaving security and correctness as secondary concerns. As a consequence, systems must frequently be patched after deployment to fix security vulnerabilities. While this nonvirtuous exploit-patch-exploit cycle is insecure, it is practical enough for companies to use. Formal methods in both software and hardware can guarantee the security they provide. Ideally, modern systems would be comprised of formally verified and secure components. Unfortunately, such methods have not seen widespread adoption for a number of reasons, such as difficulty in scaling, lack of tools, and high skill requirements. Additionally, the economics involved in securing and replacing every component in all systems, both new and currently deployed, result in clean slate solutions being impractical. A practical solution should rely on a few, simple components and should be adoptable incrementally. TrustGuard, the first implementation of the Containment Architecture with Verified Output (CAVO) model developed at Princeton, showed how a simple, trusted Sentry could protect against malicious or buggy hardware components to ensure integrity of external communications. This was accomplished by ensuring the correct execution of signed software, with support from a modified CPU and system architecture. However, TrustGuards practicality was limited due to its reliance on modified host hardware and its requirement to trust entire application stacks, including the operating system. The work presented in this dissertation seeks to make the CAVO model a practical solution for ensuring the integrity of data communicated externally in an untrusted commodity system. This work extends CAVO in two ways. First, it makes the Sentry compatible with a wide range of devices without requiring hardware modifications to the host system, thus increasing its flexibility and ease of integration into existing environments. Second, it gives developers the option to use trusted code to verify the execution of untrusted code, thus reducing the size of the trusted code base. This is analogous to the small, trusted Sentry ensuring correctness of execution of a large amount of complex, untrusted hardware.

1 0

Matthew Myers will present his General Exam on Tuesday, May 21, 2019 at 2pm in CS 401.
by Nicki Mahler 14 May '19

14 May '19

Matthew Myers will present his General Exam on Tuesday, May 21, 2019 at 2pm in CS 401. The members of his committee are as follows: Ben Raphael (adviser), Mona Singh, and Olga Troyanskaya. Everyone is invited to attend his talk, and those faculty wishing to remain for the oral exam following are welcome to do so. His abstract and reading list follow below. Abstract: Cancer is a complex disease, and treatment of cancer is complicated by its heterogeneity: mutations and other characteristics vary greatly not just between cancer types, but also between cancers, and even between cells within the same individual. Longitudinal DNA sequencing of cancer patients yields insight into how tumors evolve over time or in response to treatment. However, sequencing data from bulk tumor samples often has considerable ambiguity in clonal composition, complicating the inference of ancestral relationships between clones. We introduce CALDER (Cancer Analysis of Longitudinal Data through Evolutionary Reconstruction), an algorithm to infer phylogenetic trees from longitudinal bulk DNA sequencing data. CALDER explicitly models a longitudinally-observed phylogeny incorporating constraints that longitudinal sampling imposes on phylogeny reconstruction. We show on simulated bulk tumor data that longitudinal constraints substantially reduce ambiguity in phylogeny reconstruction and that CALDER outperforms existing methods that do not leverage longitudinal information. On real data from two chronic lymphocytic leukemia patients, we find that CALDER reconstructs more plausible and parsimonious phylogenies than existing methods, with CALDER phylogenies containing fewer tumor clones per sample. CALDER’s use of longitudinal information will be advantageous in further studies of tumor heterogeneity and evolution. Reading list: Main textbook: Compeau & Pevzner - Bioinformatics Algorithms: an Active Learning Approach (2nd edition vol. I-II) Papers: El-Kebir et al., 2015, “Reconstruction of clonal trees and tumor composition from multi-sample sequencing data” (AncesTree) Popic et al., 2015, “Fast and scalable inference of multi-sample cancer lineages” (LICHeE) El-Kebir et al., 2018, “Inferring parsimonious migration histories for metastatic cancers” (MACHINA) Deshwar et al., 2015, “PhyloWGS: Reconstructing subclonal composition and evolution from whole-genome sequencing of tumors” Caravagna et al, 2018, “Detecting repeated cancer evolution from multi-region tumor sequencing data” (REVOLVER) Jahn et al., 2016, “Tree inference for single-cell data” (SCITE) Turajlic et al., 2019, Resolving genetic heterogeneity in cancer Schwartz et al, 2017, “The evolution of tumour phylogenetics: principles and practice“ Chapter 2 from Gusfield - ReCombinatorics: The Algorithmics of Ancestral Recombination Graphs and Explicit Phylogenetic Networks Gabow and Myers, 1978, “Finding all spanning trees of directed and undirected graphs.”

1 0

Jishen Zhao TODAY at 12:30
by Emily C. Lawrence 14 May '19

14 May '19

Prof. Jishen Zhao from University of California, San Diego Tuesday, May 14 at 12:30pm Computer Science - Room 105 [ https://www.cs.princeton.edu/events/25852 | https://www.cs.princeton.edu/events/25852 ] System and Architecture Design for Safe and Reliable Autonomous Robotic Applications The rapid development of smart technology in edge computing systems has paved the way for us to embrace the technology movement of self-driving cars and autonomous service robots. To enable the wide adoption of these autonomous robotic applications, reliability is one of fundamental goals of computing system and architecture design. In this talk, I will present our recent exploration of safe and reliable system and architecture design for autonomous robotic applications. I will start by presenting an architecture design of supporting fast system recovery with persistent memory at low performance cost. To evaluate and guide our system design, I will introduce our safety model and architecture design strategies for self-driving cars, based on our field study of running real industrial Level-4 autonomous driving fleets. Finally, I will describe a Linux-container-based resource management framework design to improve reliability and safety of self-driving cars and service robots. Bio: Jishen Zhao is an Assistant Professor in the Computer Science and Engineering Department at University of California, San Diego. Her research spans and stretches the boundary between computer architecture and system software, with a particular emphasis on memory and storage systems, domain-specific acceleration, and system reliability. Her research is driven by both emerging technologies (e.g., nonvolatile memories, 3D-stacked memory) and modern applications (e.g., smart home and autonomous robotic systems, deep learning, and big-data analytics). Before joining UCSD, she was an Assistant Professor at UC Santa Cruz, and a research scientist at HP Labs before joining UCSC. She is a recipient of NSF CAREER award and a MICRO best paper honorable mention award.

1 0

Caleb Levy will present his FPO "New Paths from Splay to Dynamic Optimality" on Wednesday, May 15, 2019 at 2pm in Fine Hall 224
by Nicki Mahler 13 May '19

13 May '19

Caleb Levy will present his FPO "New Paths from Splay to Dynamic Optimality" on Wednesday, May 15, 2019 at 2pm in Fine Hall 224. The members of his committee are as follows: Advisor: Robert Tarjan Non-Readers: Bernard Chazelle and Robert Sedgewick Readers: Kurt Mehlhorn ( Max-Planck-Institut fur Informatik) Abstract: Consider the task of performing a sequence of searches in a binary search tree. After each search, an algorithm is allowed to arbitrarily restructure the tree, at a cost proportional to the amount of restructuring performed. The cost of an execution is the sum of the time spent searching and the time spent optimizing those searches with restructuring operations. This notion was introduced by Sleator and Tarjan in 1985, along with an algorithm and a conjecture. The algorithm, Splay, is an elegant procedure for performing adjustments while moving searched items to the top of the tree. The conjecture, called dynamic optimality, is that the cost of splaying is always within a constant factor of the optimal algorithm for performing searches. The conjecture stands to this day. We make the following contributions to this problem: 1. We introduce simulation embeddings: mappings from executions to lists of keys that induce target algorithms to simulate the executions. We build a simulation embedding for Splay by inducing Splay to perform arbitrary subtree transformations, and show that if the cost of splaying a sequence of items is an upper bound on the cost of splaying every subsequence thereof to within a constant factor, then Splay is dynamically optimal. We call this property approximate monotonicity. We also show that approximate monotonicity is a necessary condition for dynamic optimality. 2. We show that if Splay is dynamically optimal, then with respect to optimal costs, its additive overhead is at most linear in the sum of initial tree size and number of requests. 3. We prove that Wilber’s lower bound on optimal execution cost is approximately monotone. 4. Drawing on extensive empirical and heuristic observations, we speculate about how one might establish dynamic optimality by adapting the proof of monotonicity from the crossing lower bound to Splay. 5. We show that several related conjectures also follow if Splay is approximately monotone, and demonstrate that most of the results in this paper extend to a broader class of “path-based” algorithms. It is hoped that this work lays the foundations for a final proof of the dynamic optimality conjecture. A copy of this thesis is available upon request.

1 0