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

Fangyin Wei will present her FPO "Learning to Edit 3D Objects and Scenes" on Monday, April 22, 2024 at 1:30 PM in CS 302
by gradinfo＠cs.princeton.edu 10 Apr '24

10 Apr '24

Fangyin Wei will present her FPO "Learning to Edit 3D Objects and Scenes" on Monday, April 22, 2024 at 1:30 PM in CS 302 Location: CS 302 The members of Fangyin's committee are as follows: Examiners: Szymon Rusinkiewicz (Adviser), Thomas Funkhouser (Adviser), Jia Deng Readers: Felix Heide, Olga Russakovsky A copy of her thesis is available upon request. Please email gradinfo(a)cs.princeton.edu <mailto:gradinfo@cs.princeton.edu> if you would like a copy of the thesis. Everyone is invited to attend her talk. Abstract follows below: 3D editing plays a key role in many fields ranging from AR/VR, industrial and art design, to robotics. However, existing 3D editing tools either (i) demand labor-intensive manual efforts and struggle to scale to many examples, or (ii) use optimization and machine learning but produce unsatisfactory results (e.g., losing details, supporting only coarse editing, etc.). These shortcomings often arise from editing in geometric space rather than structure-aware semantic space, where the latter is the key to automatic 3D editing at scale. While learning a structure-aware space will result in significantly improved efficiency and accuracy, labeled datasets to train 3D editing models don't exist. In this dissertation, we present novel approaches for learning to edit 3D objects and scenes in structure-aware semantic space with noisy or no supervision. We first address how to extract the underlying structure to edit 3D objects, with a focus on editing two critical properties: semantic shape parts and articulations. Our semantic editing method enables specific edits to an object's semantic parameters (e.g., the pose of a person's arm or the length of an airplane's wing), leading to better preservation of input details and improved accuracy compared to previous work. Next, we introduce a 3D annotation-free method that learns to model geometry, articulation, and appearance of articulated objects from color images. The model works on an entire category (as opposed to typical NeRF extensions that only overfit on a single scene) and enables various applications such as few-shot reconstruction and static object animation. It also generalizes to real-world captures. Then, we tackle how to extract structure for scene editing. We present an automatic system that removes clutter (frequently moving objects such as clothes or chairs) from 3D scenes and inpaints the resulting holes with coherent geometry and texture. We address challenges including the lack of well-defined clutter annotations, entangled semantics and geometry, and multi-view inconsistency. In summary, this dissertation demonstrates techniques to exploit the underlying structure of 3D data for editing. Our work opens up new research directions such as leveraging structures from other modalities (e.g., text, images) to empower 3D editing models with stronger semantic understanding.

1 0

Upcoming Princeton Precision Health talks: bioethics, neuroscience, computer vision, environmental effects on disease
by Emily C. Lawrence 10 Apr '24

10 Apr '24

The Princeton Precision Health team has three great seminars coming up in the next two weeks: On Friday, April 12, at 12 pm , we have two bioethicists, Aurelia Sauerbrei from Oxford and Ian Peebles from Princeton University Center for Human Values, presenting talks titled: "A.I. and the Doctor-Patient Relationship: a Bioethics Perspective” and “What’s Wrong With Decision Procedures in Medical Ethics?” Lunch will be provided. On Thursday, April 18, at 10:00 am , Uri Hasson from Psychology and PNI will give a talk, “The First 1000 Days Project: A Novel Framework for Modeling Language Development,” and Olga Russakovsky from Computer Science will present, “The Role of Computer Vision in Understanding Neurodivergence.” Breakfast will be provided. On Friday, April 19, at 12 pm , Jane Burns, MD, the Director of the Kawasaki Disease Clinic and Research Center at UCSD will give a talk about the climate and environmental effects on Kawasaki Disease. Her work has recently been featured in the [ https://www.nytimes.com/2024/02/27/health/kawasaki-disease-cause.html | NY Times ] . Lunch will be provided. We hope to see you at our upcoming seminars! The PPH Team 252 Nassau Street is between Tiger Noodles and the Small World Coffee on Nassau Street. We do not yet have a functional elevator, and getting to our space requires that you climb a flight of stairs. If an accommodation is needed, please do not hesitate to let us know in advance of the event. ************************************ Princeton Precision Health [ http://pph.princeton.edu/ | pph.princeton.edu ] [ mailto:princetonpph@princeton.edu | princetonpph(a)princeton.edu ]

1 0

Kritkorn Karntikoon will present his FPO "Dynamics of Averaging Systems: Convergence and Cyclical Trends" on May 9th, 2024 at 10:30am in CS 402 (and Zoom)
by Gradinfo 10 Apr '24

10 Apr '24

Kritkorn Karntikoon will present his FPO "Handling Data Too Large To Handle: On Multi-pass Streaming and Interactive Coding" on May 9th, 2024 at 10:30am in CS 402 (and Zoom). Title: Dynamics of Averaging Systems: Convergence and Cyclical Trends Examiners: Bernard Chazelle (advisor), Mark Braverman, Matt Weinberg Readers: Robert Tarjan, Huacheng Yu Date and Time: May 9, 2024 at 10.30 AM ET Zoom link: https://princeton.zoom.us/j/98534246633 All are welcome to attend. Abstract: Averaging dynamics drives countless processes in biology, social science, physics, and engineering. Notable examples include opinion dynamics, bird flocking, and synchronization processes. These processes involve agents interacting across a dynamic network by averaging their state variables with those of their neighbors. The dynamics of averaging systems therefore depend on the structure of the underlying network sequences. Under mild conditions, such systems are known to converge to fixed-point attractors but are hard to analyze because of the time-varying nature of networks. The s-energy, a generating function over inter-agent distances, has emerged as a powerful tool to deal with this issue. In this thesis, we refine the analysis of the s-energy by highlighting the impact of network connectivity. This allows us to address an intriguing exponential gap in the convergence rate of averaging systems. We also apply this new s-energy bound to resolve open questions in several areas including bird flocking, where we establish sufficient conditions for the first polynomial bound in bird flocking convergence. Additionally, we investigate the emergence of cyclical trends in opinion dynamics. Modifying the model with a separation rule reveals that the systems either converge to a nonconsensual equilibrium or are attracted to periodic or quasi-periodic orbits. Our analysis includes exploring geometric properties such as dimensionality, periodicity, and conditions for various behaviors.

1 1

Ben Burgess will present his FPO " Reverse Engineering Real World Trusted Systems" on Tuesday, May 7th, 2024 at 2:15pm in CS 105.
by Gradinfo 09 Apr '24

09 Apr '24

Ben Burgess will present his FPO " Reverse Engineering Real World Trusted Systems" on Tuesday, May 7th, 2024 at 2:15pm in CS 105. The members of his committee are as follows: Examiners: Ed Felten (adviser), Arvind Narayanan, and Roya Ensafi (University of Michigan) Readers: Ed Felten, Prateek Mittal, Danny Huang (New York University) All are welcome to attend. Please see below for abstract. In recent years, the adoption of remote proctoring solutions for law schools and bar examshassurged. Yet, the integrity and fairness of these systems have come under scrutiny. Concurrently, post the September 11th attacks, the security of police radio systems, notably Motorola P25 and Harris OpenSky, has emerged as a significant concern. This thesis delves into the issues plaguing these real-world systems and forwards potential remedies. The initial segment of the thesis appraises the integrity and equitability of remote proctoring solutions. An extensive literature review on remote proctoring’s application in law schools and bar exams sets the stage, elucidating both the advantages and limitations of these platforms. The narrative then transitions to the inherent security challenges: threats to exam sanctity posed by students, and the overarching issues of unfairness and systemic discrimination at the institutional level. The subsequent section casts a spotlight on the security dimensions of police radio systems, with an emphasis on Motorola P25 and Harris OpenSky. A meticulous breakdown of these systems’ features, capabilities, and security vulnerabilities ensues. The discourse deepens by investigating real-world deployments of these platforms, capturing the authentic security tribulations encountered by police departments across the United States. Additionally, the repercussions of these security concerns on police efficacy and overall public safety are explored. Drawing from the insights garnered, this thesis recommends a suite of measures to enhance the security and fairness of remote proctoring platforms and fortify the security infrastructure of police radio systems. These encompass the incorporation of advanced encryption methodologies and other security protocols to shield sensitive information. Moreover, the formulation of ethnically diverse datasets and strategies to curtail bias and discrimination in remote proctoring systems are elaborated upon. In essence, this thesis offers a holistic examination of the security and fairness facets of remote proctoring tools and the robustness of police radio systems, culminating in actionable recommendations to ameliorate the identified challenges.

1 0

Mary Hogan will present her FPO "Language Expressiveness Under Extreme Scarcity in Programmable Data Planes" on Thursday, May 9th at 1pm in Friend 125 (and zoom).
by Gradinfo 09 Apr '24

09 Apr '24

Mary Hogan will present her FPO "Language Expressiveness Under Extreme Scarcity in Programmable Data Planes" on Thursday, May 9th at 1pm in Friend 125 (and zoom). [ https://princeton.zoom.us/j/3627976305 | https://princeton.zoom.us/j/3627976305 ] Committee: Jen Rexford (advisor), Maria Apostolaki (examiner), Ravi Netravali (examiner), Dave Walker (reader), Shir Landau Feibish (reader) Title: Language Expressiveness Under Extreme Scarcity in Programmable Data Planes Abstract: Today's networks must run a vast array of sophisticated applications, and the network devices that implement these applications need to operate at high speeds (100+Gbps) and be flexible enough to adapt applications to changing requirements. Programmable network devices have emerged as a way to customize network functionality, while guaranteeing high-speed processing. Writing applications for programmable devices, however, is notoriously difficult. Deploying these applications often requires tedious optimization of their layout, with programmers manually writing, compiling, and testing an implementation, adjusting the design, and repeating. In my research, I aim to simplify the development process with high-level frameworks that allow programmers to define general, parameterized network algorithms and automatically optimize their various parameters. I will first discuss P4All, an extension of an existing programming language that allows programmers to define elastic data structures that stretch automatically to optimally use available resources. These data structures are defined using symbolic primitives (that parameterize the size and shape of the structure) and objective functions (that quantify the value gained or lost as that shape changes). I will then present Parasol, which extends the ideas of P4All by allowing for much more general parameters, whose optimization is tailored to particular network conditions using a representative traffic trace.

1 0

CS Colloquium Speakers: week of March 4
by Emily C. Lawrence 09 Apr '24

09 Apr '24

CS Colloquium Speakers Speaker: Sewon Min, University of Washington Date: Monday, March 4 Time: 12:30pm EST Location: CS 105 Host: Danqi Chen Event page: https://www.cs.princeton.edu/events/26579 Register for live-stream online here: https://princeton.zoom.us/webinar/register/WN_5uVGEpXNTVe8eBNSLpxKtg Title: Rethinking Data Use in Large Language Models Abstract: Large language models (LMs) such as ChatGPT have revolutionized natural language processing and artificial intelligence more broadly. In this talk, I will discuss my research on understanding and advancing these models, centered around how they use the very large text corpora they are trained on. First, I will describe our efforts to understand how these models learn to perform new tasks after training, demonstrating that their so-called in context learning capabilities are almost entirely determined by what they learn from the training data. Next, I will introduce a new class of LMs—nonparametric LMs—that repurpose this training data as a data store from which they retrieve information for improved accuracy and updatability. I will describe my work on establishing the foundations of such models, including one of the first broadly used neural retrieval models and an approach that simplifies a traditional, two-stage pipeline into one. I will also discuss how nonparametric models open up new avenues for responsible data use, e.g., by segregating permissive and copyrighted text and using them differently. Finally, I will envision the next generation of LMs we should build, focusing on efficient scaling, improved factuality, and decentralization. Bio: Sewon Min is a Ph.D. candidate in the Paul G. Allen School of Computer Science & Engineering at the University of Washington. Her research focuses on language models (LMs): studying the science of LMs, and designing new model classes and learning methods that make LMs more performant and flexible. She also studies LMs in information-seeking, legal, and privacy contexts. She is a co-organizer of multiple tutorials and workshops, including most recently at ACL 2023 on Retrieval-based Language Models and Applications and upcoming at ICLR 2024 on Mathematical and Empirical Understanding of Foundation Models. She won a paper award at ACL 2023, received a J.P. Morgan Fellowship, and was named an EECS rising star in 2022. Speaker: Lianmin Zheng, University of California, Berkeley Date: Tuesday, March 5 Time: 12:30pm EST Location: CS 105 Host: Ravi Netravali Event page: https://www.cs.princeton.edu/events/26593 Register for live-stream online here: https://princeton.zoom.us/webinar/register/WN_ghiT2HbhSPqKBouJ-VwzFg Title: Scalable and Efficient Systems for Large Language Models Abstract: Large Language Models (LLMs) have been driving recent breakthroughs in AI. These advancements would not have been possible without the support of scalable and efficient infrastructure systems. In this talk, I will introduce several underlying systems I have designed and built to support the entire model lifecycle, from training to deployment to evaluation. First, I will present Alpa, a system for large-scale model-parallel training that automatically generates execution plans unifying data, operator, and pipeline parallelism. Next, I will discuss efficient deployment systems, covering the frontend programming interface and backend runtime optimizations for high-performance inference. Finally, I will complete the model lifecycle by presenting our model evaluation efforts, including the crowdsourced live benchmark platform, Chatbot Arena, and the automatic evaluation pipeline, LLM-as-a-Judge. These projects have collectively laid a solid foundation for large language model systems, being widely adopted by leading LLM developers and companies. I will conclude by outlining some future directions of machine learning systems, such as co-optimizing across the full stack for building AI-centric applications. Bio: Lianmin Zheng is a Ph.D. student in the EECS department at UC Berkeley, advised by Ion Stoica and Joseph E. Gonzalez. His research interests include machine learning systems, large language models, compilers, and distributed systems. He builds full-stack, scalable, and efficient systems to advance the development of AI. He co-founded LMSYS.org, where he leads impactful open-source large language model projects such as Vicuna and Chatbot Arena, which have received millions of downloads and served millions of users. He also co-organized the Big Model Tutorial at ICML 2022. He has received a Meta Ph.D. Fellowship, an IEEE Micro Best Paper Award, and an a16z open-source AI grant. Speaker: Emma Dauterman, University of California, Berkeley Date: Thursday, March 7 Time: 12:30pm EST Location: CS 105 Host: Amit Levy Event page: https://www.cs.princeton.edu/events/26585 Register for live-stream online here: https://princeton.zoom.us/webinar/register/WN_soNesOKXSFml9MPaTx_1iw Title: Secure systems from insecure components Abstract: In many computer systems today, an attacker that breaks one system component can steal data from millions of users. In this talk, I will present two systems that can withstand component compromise. I will describe (1) a single sign-on system that protects user security and privacy from a compromised single sign-on server, and (2) a secure-hardware-based backup service that protects user backups from compromised secure hardware devices. These systems provide strong security and privacy properties while taking into account practical constraints such as compatibility requirements, hardware limitations, and user expectations. Each splits user secrets across different system components, using new cryptographic tools to provide necessary functionality while protecting user data. Bio: Emma Dauterman is a Ph.D. candidate at UC Berkeley where she is advised by Raluca Ada Popa and Ion Stoica. Her research interests include computer security, systems, and applied cryptography. She has received the Microsoft Research Ada Lovelace fellowship, the NSF graduate research fellowship, and a UC Berkeley EECS excellence award.

1 16

Marcelo Orenes Vera will present his FPO "Navigating Heterogeneity and Scalability in Modern Chip Design" on Friday, May 3rd, 2024 at 11am in CS 105.
by Gradinfo 08 Apr '24

08 Apr '24

Marcelo Orenes Vera will present his FPO "Navigating Heterogeneity and Scalability in Modern Chip Design" on Friday, May 3rd, 2024 at 11am in CS 105. The members of his committee are as follows: Examiners: Margaret Martonosi (adviser), David Wentzlaff, and Aarti Gupta Readers: Kai Li and Jonathan Balkind (University of California Santa Barbara) All are welcome to attend. Please see below for the talk abstract. Computing systems have become ubiquitous in the modern world but their design is far from one-size-fits-all. From battery-powered devices to supercomputers, deployment requirements are a primary driver of heterogeneity in computer design. As modern systems rely on parallelism and specialization to achieve their performance and power goals, new challenges arise. The system's complexity grows with the number of distinct hardware modules, complicating the verification of correct and secure behavior. Moreover, expanding parallelization across more processing units (PUs) increases the pressure on the memory hierarchy and inter-PU network, which results in severe bottlenecks for applications traversing graph-like data structures with indirect memory accesses (IMAs). These challenges call for re-thinking software abstractions and hardware designs to achieve scalable and efficient systems, as well as introducing robust methodologies to ensure their correctness. My dissertation aims to tackle these challenges with three main thrusts. First, to facilitate hardware designers applying formal verification to their modules, this dissertation introduces AutoSVA, a toolflow that generates formal verification testbenches from module interface annotations. Testbenches generated with AutoSVA have uncovered bugs in open-source projects, including a widely used RISC-V CPU. Second, to alleviate IMA latency without increasing verification complexity, this dissertation introduces MAPLE, a network-connected memory-access engine that supports data pipelining and prefetching without requiring PU modifications. As such, off-the-shelf PUs can offload IMAs to MAPLE, and consume data via software-managed queues. Using MAPLE effectively mitigates memory latency, providing 2x speedups over software- and hardware-only prefetching. Third, to further the scalability of graph and sparse workloads, this dissertation co-designs scale-out architectures with a data-centric execution model, Dalorex, where IMAs are split into tasks that only access a confined address range and execute at the PU with dedicated access to that memory range. The parallelization of breadth-first-search on a billion-edge graph across a million PUs results in nearly an order of magnitude faster runtimes than Graph500's top entries. By introducing novel hardware designs, execution models, and verification tools, this dissertation contributes towards addressing the challenges posed by the increasing demand for high-performance, energy-efficient, and cost-effective computing systems.

1 0

Mike He will present his General Exam "Equality Saturation: Term Extraction and an Application to Network Synthesis" on April 16th, 2024 at 10:30am in CS 401 and Zoom.
by Nicki Mahler 08 Apr '24

08 Apr '24

Mike He will present his General Exam "Equality Saturation: Term Extraction and an Application to Network Synthesis" on April 16th, 2024 at 10:30am in CS 401 and Zoom. Zoom link: https://princeton.zoom.us/my/deyuan Committee Members: Aarti Gupta (adviser), Andrew Appel, and Mae Milano Link to Abstract and Reading List: [ https://docs.google.com/document/d/1hiZgxT9Jj0U_V83oK9eTD9siDWR0wdVKXE3BSkn… | https://docs.google.com/document/d/1hiZgxT9Jj0U_V83oK9eTD9siDWR0wdVKXE3BSkn… ] [ https://docs.google.com/document/d/1hiZgxT9Jj0U_V83oK9eTD9siDWR0wdVKXE3BSkn… | Abst ] [ https://docs.google.com/document/d/1hiZgxT9Jj0U_V83oK9eTD9siDWR0wdVKXE3BSkn… | ract ] Equality saturation is a recent technique that mitigates the phase ordering problem in compilers. Instead of performing destructive rewrite rules over the input program, equality saturation memorizes all the equivalent representations compactly in a data structure called e-graph (equality graphs) and executes multiple rewrite rules simultaneously over e-graphs. Designing an efficient algorithm for term extraction from e-graphs is challenging because the candidate space can be exponentially large and candidate terms can be cyclic. We present a Weighted Partial MaxSAT encoding of the extraction problem by identifying cycles in the e-graph and encoding acyclic constraints with Tseitin transformation to avoid extracting cyclic terms. Our evaluation of real-world workload shows a ~3x speed-up in comparison with extraction with the ILP encoding. Next, we present a case study of applying equality saturation to resource synthesis for packet programs. We propose CatsTail, a packet program compilation pipeline that leverages equality saturation to find feasible ALU mappings to reconfigurable switches. We benchmarked CatsTail using real-world switch programs and compared its synthesis performance with a previous work CaT. CatsTail shows comparable stage utilization optimality while being up to two orders of magnitude faster than CaT in resource synthesis for real-world P4 programs. Finally, if time permits, we will talk about an ongoing project of automated invariant synthesis for distributed systems. [ https://docs.google.com/document/d/1hiZgxT9Jj0U_V83oK9eTD9siDWR0wdVKXE3BSkn… | Reading List ] Textbooks Software Foundations, [ https://softwarefoundations.cis.upenn.edu/lf-current/index.html | Vol 1 ] , [ https://softwarefoundations.cis.upenn.edu/plf-current/index.html | Vol 2 ] Chapters 1~11 Logic in Computer Science, Chapters 1, 2, 3.1-3.5, 4, 6.1 Papers Equality Saturation and its Applications 1. [ https://dl.acm.org/doi/10.1145/3434304 | egg: Fast and extensible equality saturation ] (POPL’21) 2. [ https://arxiv.org/abs/2105.09377 | Pure Tensor Program Rewriting via Access Patterns ] (MAPS’21) 3. [ https://dl.acm.org/doi/abs/10.1145/3582016.3582036 | CaT: A Solver-Aided Compiler for Packet-Processing Pipelines ] (ASPLOS’23) 4. [ https://www.usenix.org/conference/nsdi22/presentation/li-yifan | Cetus: Releasing P4 Programmers from the Chore of Trial and Error Compiling ] (NSDI’22) Verification for Distributed Systems 1. [ https://www.cis.upenn.edu/~alur/SyGuS13.pdf | Syntax-guided Synthesis ] (FMCAD’13) 2. [ https://www.usenix.org/conference/osdi22/presentation/yao | DuoAI: Fast, Automated Inference of Inductive Invariants for Verifying Distributed Protocols ] (OSDI’22) 3. [ https://dl.acm.org/doi/pdf/10.1145/3622876 | Message Chain Invariant for Distributed System Verification ] (OOPSLA’23) 4. [ https://homes.cs.washington.edu/~ztatlock/pubs/verdi-wilcox-pldi15.pdf | Verdi: A Framework for Implementing and Formally Verifying Distributed Systems ] (PLDI’15) Formal Methods Background 1. [ https://dl.acm.org/doi/10.1145/1592434.1592438 | Software model checking ] (ACM Computing Survey) [ https://people.eecs.berkeley.edu/~sseshia/pubdir/SMT-BookChapter.pdf | Satisfiability Modulo Theories. Handbook of Model Checking ] (2018)

1 0

Angelina Wang will present her FPO "Operationalizing Responsible Machine Learning: From Equality Towards Equity" on Monday, May 6, 2024 at 2:30 PM in CS 402.
by CS Grad Department 06 Apr '24

06 Apr '24

Angelina Wang will present her FPO " Operationalizing Responsible Machine Learning: From Equality Towards Equity " on Monday, May 6, 2024 at 2:30 PM in CS 402 . Location: CS 402 The members of Angelina ’s committee are as follows: Examiners: Olga Russakovsky (Adviser), Arvind Narayanan , Solon Barocas (Cornell) Readers: Aleksandra Korolova , Janet Vertesi A copy of her 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 her talk. Abstract follows below: With the widespread proliferation of machine learning, there arises both the opportunity for societal benefit as well as the risk of harm. Approaching responsible machine learning is challenging because technical approaches may prioritize a mathematical definition of fairness that correlates poorly to real-world constructs of fairness due to too many layers of abstraction. Conversely, social approaches that engage with prescriptive theories may produce findings that are too abstract to effectively translate into practice. In my research, I bridge these approaches and utilize social implications to guide technical work. I will discuss three research directions that show how, despite the technically convenient approach of considering equality acontextually, a stronger engagement with societal context allows us to operationalize a more equitable formulation. First, I will introduce a dataset tool that we developed to analyze complex, socially-grounded forms of visual bias. Then, I will provide empirical evidence to support how we should incorporate societal context in bringing intersectionality into machine learning. Finally, I will discuss how in the excitement of using LLMs for tasks like human participant replacement, we have neglected to consider the importance of human positionality. Overall, I will explore how we can expand a narrow focus on equality in responsible machine learning to encompass a broader understanding of equity that substantively engages with societal context.

1 0

Uma Girish will present her FPO "Quantum versus Classical Communication and Query Complexity" on Thursday, May 2nd, 2024 at 11am in CS 201.
by Gradinfo 05 Apr '24

05 Apr '24

Uma Girish will present her FPO "Quantum versus Classical Communication and Query Complexity" on Thursday, May 2nd, 2024 at 11am in CS 201. The members of her committee are as follows: Examiners: Ran Raz (adviser), Mark Braverman and Gillat Kol Readers: Matt Weinberg and Huacheng Yu All are welcome to attend. Please see abstract below. Understanding the relative power of quantum versus classical computation is a fascinating and important problem in modern science on which there is likely to be much research and progress in the next few decades. While quantum algorithms are widely believed to exponentially outperform classical algorithms, there are very few settings in which this has been unconditionally proved. Communication complexity and query complexity are striking examples of such settings, where we can mathematically prove that quantum algorithms exponentially outperform classical algorithms. In this thesis we study the advantages of quantum over classical in these settings and present new and improved quantum speedups over classical. Among several results, we achieve state-of-the-art quantum speedups in communication complexity, using quantum protocols that are efficiently implementable, and using noisy quantum protocols where all qubits except for one are maximally noisy. We also study the power of entanglement and demonstrate in various ways that a slight increase in the entanglement can provide exponential savings in the communication complexity. We also study the power of adaptive queries in quantum query complexity and show that each successive round of quantum queries can yield super-exponential speedups in the number of quantum queries.

1 0