Application down time is one of the major reasons for revenue loss in the modern enterprise. While aggressive release schedules cause frail software to be released, application failures occurring in the field cost millions to the technical support organizations in personnel time. Since developers usually don't have direct access to the field environment for a variety of privacy and security reasons, problems are reproduced, analyzed and fixed in very different lab environments. However, the complexity and diversity of application environments make it difficult to accurately replicate the production environment. The indiscriminate collection of data provided by the bug reports often overwhelm or even mislead the developer. A typical issue requires time consuming rounds of clarifications and interactions with the end user, even after which the issue may not manifest. This dissertation introduces vPlay, a software problem determination system which captures software bugs as they occur in the field into small and self-contained recordings, and allows them to be deterministically reproduced across different operating systems and heterogeneous environments. vPlay makes two key advances over the state of the art. First, the recorded bug can be reproduced in a completely different operating system environment without any kind of dependency on the source. vPlay packages up every piece of data necessary to correctly reproduce the bug on any stateless target machine in the developer environment, without the application, its binaries, and other support data. Second, the data captured by vPlay is small, typically amounting to a few megabytes. vPlay achieves this without requiring changes to the applications, base kernel or hardware. vPlay employs a recording mechanism which provides data level independence between the application and its source environment by adopting a state machine model of the application to capture every piece of state accessed by the application. vPlay minimizes the size of the recording through a new technique called partial checkpointing, to efficiently capture the partial intermediate state of the application required to replay just the last few moments of its execution prior to the failure. The recorded state is saved as a partial checkpoint along with metadata representing the information specific to the source environment, such as call- ing convention used for the system calls on the source system, to make it portable across operating systems. A partial checkpoint is loaded by a partial checkpoint loader, which itself is designed to be portable across different operating systems. Partial checkpointing is combined with a logging mechanism, which monitors the application to identify and record relevant accessed state for root cause analysis and to record application's nondeterministic events. vPlay introduces a new type of virtualization abstraction called vPlay Container, to natively replay an application built for one operating system on another. vPlay Container relies on the self-contained recording produced by vPlay to decouple the application from the target operating system environment in three key areas. The application is decoupled from (1) the address space and its content by transparently fulfilling its memory accesses, (2) the instructions and the processor MMU structures such as segment descriptor tables through a binary translation technique designed specifically for user application code, (3) the operating system interface and its services by abstracting the system call interface through emulation and replay. To facilitate root cause analysis, vPlay Container integrates with a standard debugger to enable the user to set breakpoints and single step the replayed execution of the application to examine the contents of variables and other program state at each source line. We have implemented a vPlay prototype which can record unmodified Linux applications and natively replay them on different versions of Linux as well as Windows. Experiments with several applications including Apache and MySQL show that vPlay can reproduce real bugs and be used in production with modest recording overhead.

In modern network measurement research, there exists a clear and demonstrable need for open sharing of large-scale network traffic datasets between organizations. Beyond network measurement, many security-related fields, such as those focused on detecting new exploits or worm outbreaks, stand to benefit given the ability to easily correlate information between several different sources. Currently, the primary factor limiting such sharing is the risk of disclosing private information. While prior anonymization work has focused on traffic content, analysis based on statistical behavior patterns within network traffic has, so far, been under-explored. This thesis proposes a new behavior-based approach towards network trace source-anonymization, motivated by the concept of anonymity-by-crowds, and conditioned on the statistical similarity in host behavior. Novel time-series models for network traffic and kernel metrics for similarity are derived, and the problem is framed such that anonymity and statistics-preservation are congruent objectives in an unsupervised-learning problem. Source-anonymity is connected directly to the group size and homogeneity under this approach, and metrics for these properties are derived. Optimal segmentation of the population into anonymized groups is approximated with a graph-partitioning problem where maximization of this anonymity metric is an intrinsic property of the solution. Algorithms that guarantee a minimum anonymity-set size are presented, as well as novel techniques for behavior visualization and compression. Empirical evaluations on a range of network traffic datasets show significant advantages in both accuracy and runtime over similar solutions.

Graphs are commonly represented as points in space connected by lines. The points in space are the vertices of the graph, and the lines joining them are the edges of the graph. A general definition of a graph is considered here, where multiple edges are allowed between two vertices and an edge is permitted to connect a vertex to itself. It is assumed that graphs are connected, i.e., any vertex in the graph is reachable from another distinct vertex either directly through an edge connecting them or by a path consisting of intermediate vertices and connecting edges. Under this visual representation, graphs can be drawn on various surfaces. The focus of my research is restricted to a class of surfaces that are characterized as compact connected orientable 2-manifolds. The drawings of graphs on surfaces that are of primary interest follow certain prescribed rules. These are called 2-cellular graph embeddings, or simply embeddings. A well-known closed formula makes it easy to enumerate the total number of 2-cellular embeddings for a given graph over all surfaces. A much harder task is to give a surface-wise breakdown of this number as a sequence of numbers that count the number of 2-cellular embeddings of a graph for each orientable surface. This sequence of numbers for a graph is known as the genus distribution of a graph. Prior research on genus distributions of graphs has primarily focused on making calculations of genus distributions for specific families of graphs. These families of graphs have often been contrived, and the methods used for finding their genus distributions have not been general enough to extend to other graph families. The research I have undertaken aims at developing and using a general method that frames the problem of calculating genus distributions of large graphs in terms of a partitioning of the genus distributions of smaller graphs. To this end, I use various operations such as edge-amalgamation, self-edge-amalgamation, and vertex-amalgamation to construct large graphs out of smaller graphs, by coupling their vertices and edges together in certain consistent ways. This method assumes that the partitioned genus distribution of the smaller graphs is known or is easily calculable by computer, for instance, by using the famous Heffter-Edmonds algorithm. As an outcome of the techniques used, I obtain general recurrences and closed-formulas that give genus distributions for infinitely many recursively specifiable graph families. I also give an easily understood method for finding non-trivial examples of distinct graphs having the same genus distribution. In addition to this, I describe an algorithm that computes the genus distributions for a family of graphs known as the 4-regular outerplanar graphs.

Millions of people worldwide use voice over IP (VoIP) services not only as cost-effective alternatives to long distance and international calls but also as unified communication tools, such as video conferencing. Owing to the low cost of new user accounts, each person can easily obtain multiple accounts for various purposes. Rich VoIP functions combined with the low cost of new accounts and connections attract many people, resulting in a dramatic increase in the number of active user accounts. Internet telephony service providers (ITSPs), therefore, need to deploy VoIP systems to accommodate this growing demand for VoIP user accounts. Attracted people also include bad actors who make calls that are unwanted to callees. Once ITSPs openly connect with each other, unwanted bulk calls will be at least as serious a problem as email spam. This dissertation studies how we can reduce load both on ITSPs and end users to ensure continuing the success of VoIP services. From ITSPs' perspective, the scalability of VoIP servers is of importance and concern. Scalability depends on server implementation and the transport protocol for SIP, VoIP signaling. We conduct experiments to understand the impact of connection-oriented transport protocols, namely, TCP and SCTP, because of the additional costs of handling connections. Contradicting the negative perception of connection-oriented transport protocols, our experimental results demonstrate that the TCP implementation in Linux can maintain comparable capacity to UDP, which is a lightweight connection-less transport protocol. The use of SCTP, on the other hand, requires improving the Linux implementation since the not-well-tested implementation makes a server less scalable. We establish the maximum number of concurrent TCP or SCTP connections as baseline data and suggest better server configurations to minimize the negative impact of handling a large number of connections. Thus, our experimental analysis will also contribute to the design of other servers with a very large number of TCP or SCTP connections. From the perspective of end users, controlling unwanted calls is vital to preserving the VoIP service utility and value. Prior work on preventing unwanted email or calls has mainly focused on detecting unwanted communication requests, leaving many messages or calls unlabeled since false positives during filtering are unacceptable. Unlike prior work, we explore approaches to identifying a "good" call based on signaling messages rather than content. This is because content-based filtering cannot prevent call spam from disturbing callees since a ringing tone interrupts them before content is sent. Our first approach uses "cross-media relations.'' Calls are unlikely to be unwanted if two parties have been previously communicated with each other through other communication means. Specifically, we propose two mechanisms using cross-media relations. For the first mechanism, a potential caller offers her contact addresses which might be used in future calls to the callee. For the second mechanism, a callee provides a potential caller with weak secret for future use. When the caller makes a call, she conveys the information to be identified as someone the callee contacted before through other means. Our prototype illustrates how these mechanisms work in web-then-call and email-then-call scenarios. In addition, our user study of received email messages, calls, SMS messages demonstrates the potential effectiveness of this idea. Another approach uses caller's attributes, such as organizational affiliation, in the case where two parties have had no prior contact. We introduce a lightweight mechanism for validating user attributes with privacy-awareness and moderate security. Unlike existing mechanisms of asserting user attributes, we design to allow the caller to claim her attributes to callees without needing to prove her identity or her public key. To strike the proper balance between the ease of service deployment and security, our proposed mechanism relies on transitive trust, through an attribute validation server, established over transport layer security. This mechanism uses an attribute reference ID, which limits the lifetime and restricts relying parties. Our prototype demonstrates the simplicity of our concept and the possibility of practical use.

The architectural simplicity of the core Internet is a double-edged sword. On the one hand, its agnostic nature paved the way for endless innovations of end-to-end applications. On the other hand, the inherent limitation of this simplicity makes it difficult to add new functions to the network core itself. This is exacerbated by the conservative tendency of commercial entities to "leave well-enough alone", leading to the current situation often referred to as the ossification of the Internet. For decades, there has been practically no new functionality that has been added to the core Internet on a large scale. This thesis explores the possibility of enabling in-network services towards the goal of overcoming the ossification of the Internet. Our ultimate goal is to provide a common run-time environment supported by all Internet nodes and a wide-area deployment mechanism, so that network services can be freely installed, removed, and migrated among Internet nodes of all kinds–from a backbone router to a set-top box at home. In that vision of a future Internet, there is little difference between servers and routers for the purpose of running network services. Services can run anywhere on the Internet. Application service providers will have the freedom to choose the best place to run their code. This thesis presents NetServ, our first step to realize the vision of network services running anywhere on the Internet. NetServ is a node architecture for dynamically deploying in-network services on edge routers. Network functions and applications are implemented as software modules which can be deployed at any NetServ-enabled node on the Internet, subject to policy restrictions. The NetServ framework provides a common execution environment for service modules and the ability to dynamically install and remove the services without restarting the nodes. There are many challenges in designing such a system. The main contribution of this thesis lies in meeting those challenges. First, we recognize that the primary impetus for adopting new technologies is economics. To address the challenge of providing economic incentives for enabling in-network services, we demonstrate how NetServ can facilitate an economic alliance between content providers and ISPs. Using NetServ, content providers and the ISPs operating at the network edge (aka eyeball ISPs) can enter into a mutually beneficial economic relationship. ISPs make their NetServ-enabled edge routers available for hosting content providers' applications and contents. Content providers can operate closer to end users by deploying code modules on NetServ-enabled edge routers. We make our case by presenting NetServ applications which represent four concrete use cases. Second, our node architecture must support both traditional server applications and in-network packet processing applications since content providers' applications running on ISPs' routers will combine the traits of both. To address this challenge, NetServ framework can host a packet processing module that sits in the data path, a server module that uses the TCP/IP stack in the traditional way, or a combined module that does both. NetServ provides a unified runtime environment between routers and servers, taking us a step closer to the vision of the unified runtime available on all Internet nodes. Third, we must provide a fast and streamlined deployment mechanism. Content providers should be able to deploy their applications at any NetServ-enabled edge router on the Inter- net, given that they have proper authorizations. Moreover, in some application scenarios, content providers may not know the exact locations of the target routers. Content providers need a way to send a message to install or remove an application module towards a network destination, and have the NetServ-enabled routers located in the path catch and act on the message. To address this challenge, we adopted on-path signaling as the deployment mechanism for NetServ. A NetServ signaling message is sent in an IP packet towards a destination. The packet gets forwarded by IP routers as usual, but when it transits a NetServ-enabled router, the message gets intercepted and passed to the NetServ control layer. Fourth, a NetServ-enabled router must support the concurrent executions of multiple without restarting the nodes. There are many challenges in designing such a system. The main contribution of this thesis lies in meeting those challenges. First, we recognize that the primary impetus for adopting new technologies is economics. To address the challenge of providing economic incentives for enabling in-network services, we demonstrate how NetServ can facilitate an economic alliance between content providers and ISPs. Using NetServ, content providers and the ISPs operating at the network edge (aka eyeball ISPs) can enter into a mutually beneficial economic relationship. ISPs make their NetServ-enabled edge routers available for hosting content providers' applications and contents. Content providers can operate closer to end users by deploying code modules on NetServ-enabled edge routers. We make our case by presenting NetServ applications which represent four concrete use cases. Second, our node architecture must support both traditional server applications and in-network packet processing applications since content providers' applications running on ISPs' routers will combine the traits of both. To address this challenge, NetServ framework can host a packet processing module that sits in the data path, a server module that uses the TCP/IP stack in the traditional way, or a combined module that does both. NetServ provides a unified runtime environment between routers and servers, taking us a step closer to the vision of the unified runtime available on all Internet nodes. Third, we must provide a fast and streamlined deployment mechanism. Content providers should be able to deploy their applications at any NetServ-enabled edge router on the Internet, given that they have proper authorizations. Moreover, in some application scenarios, content providers may not know the exact locations of the target routers. Content providers need a way to send a message to install or remove an application module towards a network destination, and have the NetServ-enabled routers located in the path catch and act on the message. To address this challenge, we adopted on-path signaling as the deployment mechanism for NetServ. A NetServ signaling message is sent in an IP packet towards a destination. The packet gets forwarded by IP routers as usual, but when it transits a NetServ-enabled router, the message gets intercepted and passed to the NetServ control layer. Fourth, a NetServ-enabled router must support the concurrent executions of multiple content providers' applications. Each content provider's execution environment must be isolated from one another, and the resource usage of each must be controlled. To address the challenge of providing a robust multi-user execution environment, we chose to run NetServ modules in user space. This is in stark contrast to most programmable routers, which run service modules in kernel space for fast packet processing. Furthermore, NetServ modules are written in Java and run in Java Virtual Machines (JVMs). Our choice of user space execution and JVM allows us to leverage the decades of technology advances in operating systems, virtualization, and Java. Lastly, in order to host the services of a large number of content providers, NetServ must be able to scale beyond the single-box architecture. We address this challenge with the multi-box lateral expansion of NetServ using the OpenFlow forwarding engine. In this extended architecture, multiple NetServ nodes are attached to an OpenFlow switch, which provides a physically separate forwarding plane. The scalability of user services is no longer limited to a single NetServ box. Additionally, this thesis presents our prior work on improving service discovery in local and global networks. The service discovery work makes indirect contribution because the limitations of local and overlay networks encountered during those studies eventually led us to investigate in-network services, which resulted in NetServ. Specifically, we investigate the issues involved in bootstrapping large-scale structured overlay networks, present a tool to merge service announcements from multiple local networks, and propose an enhancement to structured overlay networks using link-local multicast.

Security in computer systems is concerned with protecting resources from unauthorized access while ensuring legitimate requests can be satisfied all the time. The recent growth of computer systems both in scale and complexity poses tremendous management challenges. Policy-based systems management is a very promising solution in this scenario. It allows the separation of the rules that govern the behavior choices of a system from the provided functionality, and can be adapted to handle a large number of system elements. In the past two decades there have been many advances in the field of policy research. Although existing solutions in centralized systems are well-established, they do not work nearly as well in distributed environments because of scalability, network partitions, and the heterogeneity of the endpoints. This dissertation contributes to this endeavor by proposing three novel techniques to address the problem of security policy definition and enforcement in large-scale distributed systems. To correctly enforce service and security requirements from users who have no intimate knowledge of the underlying systems, we introduce the first distributed policy refinement solution that translates high-level policies into low-level implementable rules, for which the syntax and semantics can be fully interpreted by individual enforcement points. Taking advantage of both the centralized and end-to-end enforcement approaches, we propose a novel policy algebra framework for policy delegation, composition and analysis. As a concrete instantiation of policy delegation enabled by the algebraic framework, we invent a novel firewall system, called ROFL (routing as the firewall layer), that implements packet filtering using the underlying routing techniques. ROFL implements a form of ubiquitous enforcement, and is able to drop malicious packets closer to their origins to save transmission bandwidth and battery power, especially for resource-limited devices in mobile ad hoc networks (MANET). The correctness and consistency of ROFL can be verified using policy algebra. It provides formalisms to address the complexity of distributed environments, increase assurance and show how to tune tradeoffs and improve security with ubiquitous enforcement. To demonstrate the effectiveness and efficiency of ROFL as a high-performance firewall mechanism, we analyze its performance quantitatively and conduct experiments in a simulated environment with two ad-hoc routing protocols. Empirical study shows that the increase in traffic for handling ROFL routing messages is more than outweighed by the savings by early drops of unwanted traffic.

Using cross-lingual question answering (CLQA), users can find information in languages that they do not know. In this thesis, we consider the broader problem of CLQA with result translation, where answers retrieved by a CLQA system must be translated back to the user's language by a machine translation (MT) system. This task is challenging because answers must be both relevant to the question and adequately translated in order to be correct. In this work, we show that integrating the MT closely with cross-lingual retrieval can improve result relevance and we further demonstrate that automatically correcting errors in the MT output can improve the adequacy of translated results. To understand the task better, we undertake detailed error analyses examining the impact of MT errors on CLQA with result translation. We identify which MT errors are most detrimental to the task and how different cross-lingual information retrieval (CLIR) systems respond to different kinds of MT errors. We describe two main types of CLQA errors caused by MT errors: lost in retrieval errors, where relevant results are not returned, and lost in translation errors, where relevant results are perceived irrelevant due to inadequate MT. To address the lost in retrieval errors, we introduce two novel models for cross-lingual information retrieval that combine complementary source-language and target-language information from MT. We show empirically that these hybrid, bilingual models outperform both monolingual models and a prior hybrid model. Even once relevant results are retrieved, if they are not translated adequately, users will not understand that they are relevant. Rather than improving a specific MT system, we take a more general approach that can be applied to the output of any MT system. Our adequacy-oriented automatic post-editors (APEs) use resources from the CLQA context and information from the MT system to automatically detect and correct phrase-level errors in MT at query time, focusing on the errors that are most likely to impact CLQA: deleted or missing content words and mistranslated named entities. Human evaluations show that these adequacy-oriented APEs can successfully adapt task-agnostic MT systems to the needs of the CLQA task. Since there is no existing test data for translingual QA or IR tasks, we create a translingual information retrieval (TLIR) evaluation corpus. Furthermore, we develop an analysis framework for isolating the impact of MT errors on CLIR and on result understanding, as well as evaluating the whole TLIR task. We use the TLIR corpus to carry out a task-embedded MT evaluation, which shows that our CLIR models address lost in retrieval errors, resulting in higher TLIR recall; and that the APEs successfully correct many lost in translation errors, leading to more adequately translated results.

A computational camera uses a combination of optics and processing to produce images that cannot be captured with traditional cameras. Over the last decade, a range of computational cameras have been proposed, which use various optics designs to encode and use computation to decode useful visual information. What is often missing, however, is the quantitative analysis of the relation between camera design and the captured visual information, and little systematic work has been done to evaluate and optimize these computational camera designs. While the optics of computational cameras may be quite complicated, many of them can be effectively characterized by their point spread functions (PSFs): the intensity distribution on an image sensor as a response to a point light source in a scene. This thesis explores the techniques to characterize, evaluate and optimize computational cameras via PSF engineering for computer vision tasks, including image recovery, 3D reconstruction, and image refocusing. I first explore PSF engineering techniques to recover image details from blurry images. Image blur is a problem commonly seen in photography due to a number of reasons, including defocus, lens aberration, diffraction, atmospheric turbulence, object motion, and etc. Image blur is often formulated as a convolution of the latent blur-free image and a PSF, and deconvolution (or deblurring) techniques have to be used to recover image details from a blurry region. Here, I propose a comprehensive framework of PSF evaluation for the purpose of image deblurring, in which the effects of image noise, deblurring algorithm, and the structure of natural images are all taken into account. In defocus blur, the shape of defocus PSF is largely determined by the aperture pattern of the camera lens. By using an evaluation criterion derived from the comprehensive framework, I optimize the aperture pattern to preserve many more image details when defocus occurs. Both through simulations and experiments, I demonstrate the significant improvement gained by using optimized aperture patterns. While defocus blur causes a loss in image detail, it also encodes depth information of scenes in images. A typical depth from defocus (DFD) technique computes depth from two or more images that are captured with circular aperture lenses of different focus settings. Circular apertures produce circular defocus PSFs. In this thesis, I show that the use of a circular aperture severely restricts the accuracy of DFD, and propose a comprehensive framework of PSF evaluation for depth recovery. With this framework, we can derive a criterion for evaluating a pair of apertures with respect to the precision of depth recovery. This criterion is optimized using a genetic algorithm and gradient descent search to arrive at a pair of high resolution apertures. The two coded apertures are found to complement each other in the scene frequencies they preserve. With this property it becomes possible to not only recover depth with greater fidelity but also to obtain a high quality all-focused image from the two defocused images. While depth recovery can significantly benefit from optimized aperture patterns, its overall performance is rigidly limited by the lens aperture's physical size. To transcend this limitation, I propose a novel depth recovery technique using an optical diffuser - referred to as depth from diffusion (DFDiff). I show that DFDiff is analogous to conventional DFD, in which the scatter angle of the diffuser determines the system's effective aperture. High precision depth estimation can be achieved by choosing a proper diffuser and no longer requires the large lenses that DFD requires. Even a consumer camera with a low-end small lens can be used to do high-precision depth estimation when coupled with an optical diffuser. In my detailed analysis of the image formation properties of a DFDiff system, I show a number of examples demonstrating greater precision in depth estimation when using DFDiff. While the finite depth of field (DOF) of a lens camera leads to defocus blur, it also produces artistic visual experience. Many of today's displays are interactive in nature, which opens up a possibility for new kind of visual representations. Users could, for example, interactively refocus images to different depths, so that they can experience the artistic narrow DOF images while simultaneously making available the image detail for the entire image. To enable image refocusing, one typical approach is to capture the entire light field. But this method has the drawback of a significant sacrifice in spatial resolution due to the dimensionality gap: the captured information (light field) is 4D, while the required information (focal stack) is only 3D.In this thesis, I present an imaging system that directly captures focal stacks by a sweeping focal plane. First, I describe how to synchronize focus sweeping with image capturing so that the summed DOF of a focal stack efficiently covers the entire depth range. Then, I take a customized algorithm to enable a seamless refocusing experience, even in textureless regions or with moving objects. Prototype cameras are presented to capture real space-time focal stacks. There is also an interactive refocusing viewer available online at www.focalsweep.com.

Multivariate continuous problems are widely encountered in physics, chemistry, finance and in computational sciences. Unfortunately, interesting real world multivariate continuous problems can almost never be solved analytically. As a result, they are typically solved numerically and therefore approximately. In this thesis we deal with the approximate solution of multivariate problems. The complexity of such problems in the classical setting has been extensively studied in the literature. On the other hand the quantum computational model presents a promising alternative for dealing with multivariate problems. The idea of using quantum mechanics to simulate quantum physics was initially proposed by Feynman in 1982. Its potential was demonstrated by Shor's integer factorization algorithm, which exponentially improves the cost of the best classical algorithm known. In the first part of this thesis we study the tractability of multivariate problems in the worst and average case settings using the real number model with oracles. We derive necessary and sufficient conditions for weak tractability for linear multivariate tensor product problems in those settings. More specifically, we initially study necessary and sufficient conditions for weak tractability on linear multivariate tensor product problems in the worst case setting under the absolute error criterion. The complexity of such problems depends on the rate of decay of the squares of the singular values of the solution operator for the univariate problem. We show a condition on the singular values that is sufficient for weak tractability. The same condition is known to be necessary for weak tractability. Then, we study linear multivariate tensor product problems in the average case setting under the absolute error criterion. The complexity of such problems depends on the rate of decay of the eigenvalues of the covariance operator of the induced measure of the one dimensional problem. We derive a necessary and sufficient condition on the eigenvalues for such problems to be weakly tractable but not polynomially tractable. In the second part of this thesis we study quantum algorithms for certain eigenvalue problems and the implementation and design of quantum circuits for a modification of the quantum NAND evaluation algorithm on k-ary trees, where k is a constant. First, we study quantum algorithms for the estimation of the ground state energy of the multivariate time-independent Schrodinger equation corresponding to a multiparticle system in a box. The dimension d of the problem depends linearly to the number of particles of the system. We design a quantum algorithm that approximates the lowest eigenvalue with relative error ε for a non-negative potential V, where V as well as its first order partial derivatives are continuous and uniformly bounded by one. The algorithm requires a number of quantum operations that depends polynomially on the inverse of the accuracy and linearly on the number of the particles of the system. We note that the cost of any classical deterministic algorithm grows exponentially in the number of particles. Thus we have an exponential speedup with respect to the dimension of the problem d, when compared to the classical deterministic case. We extend our results to convex non-negative potentials V, where V as well as its first order partial derivatives are continuous and uniformly bounded by constants C and C' respectively. The algorithm solves the eigenvalue problem for a sequence of convex potentials in order to obtain its final result. More specifically, the quantum algorithm estimates the ground state energy with relative error ε a number of quantum operations that depends polynomially on the inverse of the accuracy, the uniform bound C on the potential and the dimension d of the problem. In addition, we present a modification of the algorithm that produces a quantum state which approximates the ground state eigenvector of the discretized Hamiltonian within Δ. This algorithm requires a number of quantum operations that depends pollynomially on the inverse of ε, the inverse of Δ, the uniform bound C on the potential and the dimension d of the problem. Finally, we consider the algorithm by Ambainis et.al. that evaluates balanced binary NAND formulas. We design a quantum circuit that implements a modification of the algorithm for k-ary trees, where k is a constant. Furthermore, we design another quantum circuit that consists exclusively of Clifford and T gates. This circuit approximates the previous one with error ε using the Solovay-Kitaev algorithm.

We study optimization problems with multiple objectives. Such problems are pervasive across many diverse disciplines -- in economics, engineering, healthcare, biology, to name but a few -- and heuristic approaches to solve them have already been deployed in several areas, in both academia and industry. Hence, there is a real need for a rigorous investigation of the relevant questions. In such problems we are interested not in a single optimal solution, but in the tradeoff between the different objectives. This is captured by the tradeoff or Pareto curve, the set of all feasible solutions whose vector of the various objectives is not dominated by any other solution. Typically, we have a small number of objectives and we wish to plot the tradeoff curve to get a sense of the design space. Unfortunately, typically the tradeoff curve has exponential size for discrete optimization problems even for two objectives (and is typically infinite for continuous problems). Hence, a natural goal in this setting is, given an instance of a multiobjective problem, to efficiently obtain a ``good'' approximation to the entire solution space with ``few'' solutions. This has been the underlying goal in much of the research in the multiobjective area, with many heuristics proposed for this purpose, typically however without any performance guarantees or complexity analysis. We develop efficient algorithms for the succinct approximation of the Pareto set for a large class of multiobjective problems. First, we investigate the problem of computing a minimum set of solutions that approximates within a specified accuracy the Pareto curve of a multiobjective optimization problem. We provide approximation algorithms with tight performance guarantees for bi-objective problems and make progress for the more challenging case of three and more objectives. Subsequently, we propose and study the notion of the approximate convex Pareto set; a novel notion of approximation to the Pareto set, as the appropriate one for the convex setting. We characterize when such an approximation can be efficiently constructed and investigate the problem of computing minimum size approximate convex Pareto sets, both for discrete and convex problems. Next, we turn to the problem of approximating the Pareto set as efficiently as possible. To this end, we analyze the Chord algorithm, a popular, simple method for the succinct approximation of curves, which is widely used, under different names, in a variety of areas, such as, multiobjective and parametric optimization, computational geometry, and graphics.