Catálogo de publicaciones - libros

Advances in data acquisition technology, together with the imminent demise of Moore’s Law, are prompting a rethink of basic algorithm design principles. Computing with massive data sets, data streaming, coping with uncertainty, priced computation, property testing, and sublinear algorithms are all parts of the story. So is the growing trend toward using algorithms as modeling tools for natural phenomena. I will discuss some of these developments; in particular, dimension reduction, sublinear algorithms, online reconstruction, and self-improving algorithms.

In this paper, we identify some issues in the interplay between practice and theory in cryptography, issues that have repeatedly appeared in different incarnations over the years. These issues are related to fundamental concepts in the field, e.g., to what extent we can prove that a system is secure and what theoretic results on security mean for practical applications. We argue that several such issues are often overlooked or misunderstood, and that it may be very productive if both theoreticians and practitioners think more consciously about these issues and act accordingly.

Nexus is a new operating system that runs on computers equipped with tamperproof secure co-processors; it is designed to support the construction of where actions can be attributed with some measure of confidence and where trust assumptions are explicit.

We present a series of techniques for the design of subexponential parameterized algorithms for graph problems. The design of such algorithms usually consists of two main steps: first find a branch- (or tree-) decomposition of the input graph whose width is bounded by a sublinear function of the parameter and, second, use this decomposition to solve the problem in time that is single exponential to this bound. The main tool for the first step is Bidimensionality Theory. Here we present the potential, but also the boundaries, of this theory. For the second step, we describe recent techniques, associating the analysis of sub-exponential algorithms to combinatorial bounds related to Catalan numbers. As a result, we have time algorithms for a wide variety of parameterized problems on graphs, where is the size of the graph and is the parameter.

We consider several online scheduling problems that arise when customers request make-to-order products from a company. At the time of the order, the company must quote a due date to the customer. To satisfy the customer, the company must produce the good by the due date. The company must have an online algorithm with two components: The first component sets the due dates, and the second component schedules the resulting jobs with the goal of meeting the due dates.

The most basic quality of service measure for a job is the , which is the difference between the due date and the release time. We first consider the basic problem of minimizing the average quoted lead time. We show that there is a (1 + )-speed -competitive algorithm for this problem (here is the ratio of the maximum work of a job to the minimum work of a job), and that this algorithm is essentially optimally competitive. This result extends to the case that each job has a weight and the objective is weighted quoted lead time.

We then introduce the following general setting: there is a non- increasing profit function () associated with each job . If the customer for job is quoted a due date of , then the profit obtained from completing this job by its due date is (). We consider the objective of maximizing profits. We show that if the company must finish each job by its due date, then there is no (1)-speed poly-log-competitive algorithm. However, if the company can miss the due date of a job, at the cost of forgoing the profits from that job, then we show that there is a (1 + )-speed (1 + 1/)-competitive algorithm, and that this algorithm is essentially optimally competitive.

In this paper, we consider the mechanism design version of the fractional variant of the scheduling problem on unrelated machines. We give a lower bound of 2 − 1/ for any fractional truthful mechanism, while we propose a truthful mechanism that achieves approximation of 1 + ( − 1)/2, for machines. We also focus on an interesting family of allocation algorithms, the algorithms. We give a lower bound of 1 + ( − 1)/2, that holds for every (not only monotone) allocation algorithm of this class. Under this consideration, our truthful independent mechanism is the best that we can hope from this family of algorithms.

We study the classic problem of estimating the sum of variables. The traditional uniform sampling approach requires a linear number of samples to provide any non-trivial guarantees on the estimated sum. In this paper we consider various sampling methods besides uniform sampling, in particular sampling a variable with probability proportional to its value, referred to as . If only linear weighted sampling is allowed, we show an algorithm for estimating sum with samples, and it is almost optimal in the sense that samples are necessary for any reasonable sum estimator. If both uniform sampling and linear weighted sampling are allowed, we show a sum estimator with samples. More generally, we may allow general weighted sampling where the probability of sampling a variable is proportional to any function of its value. We prove a lower bound of samples for any reasonable sum estimator using general weighted sampling, which implies that our algorithm combining uniform and linear weighted sampling is an almost optimal sum estimator.

In this paper we introduce a new lattice problem, the (). We describe a probabilistic single exponential time algorithm for for arbitrary ℓ norms. We also describe polynomial time reductions for four classical problems from the geometry of numbers, the , the , the , and the to , establishing probabilistic single exponential time algorithms for them. The result generalize and extend previous results of Ajtai, Kumar and Sivakumar. The results on and are new for all norms. The results on and generalize previous results of Ajtai et al. for the ℓ norm to arbitrary ℓ norms.

A of an undirected unweighted graph is a subgraph that approximates the distance metric of the original graph with some specified accuracy. Specifically, we say  ⊆  is an -spanner of if any two vertices , at distance in are at distance at most () in . There is clearly some tradeoff between the sparsity of and the distortion function , though the nature of this tradeoff is still poorly understood.

In this paper we present a simple, modular framework for constructing sparse spanners that is based on interchangable components called . By assembling connection schemes in different ways we can recreate the additive 2- and 6-spanners of Aingworth et al. and Baswana et al. and improve on the (1 + ,)-spanners of Elkin and Peleg, the sublinear additive spanners of Thorup and Zwick, and the (non constant) additive spanners of Baswana et al. Our constructions rival the simplicity of all comparable algorithms and provide substantially better spanners, in some cases reducing the density exponentially.

We present a linear time algorithm exactly solving the in a graph of bounded treewidth. Using this with Klein’s diameter reduction technique [15], we find a linear time PTAS for the problem in unweighted planar graphs, and the first PTAS for the problem in weighted planar graphs.