Algorithms and Complexity Theory Seminars

We study the computational geometry problems in the parallel external memory (PEM) model. PEM is a parallel version of the external memory model of Aggarwal and Vitter. We solve the problems for 2-d dominance counting, 3-d maxima, visibility from a point and 2-d convex hull using simple techniques of the PEM model. We also introduce a parallel version of the distribution sweeping technique, which we use to solve output-sensitive problems, such as orthogonal line segment intersection reporting, batched range searching and other related problems.

Joint work with Deepak Ajwani and Norbert Zeh.

Integer optimization is an important component of Operations Research, and it is used for solving many problems that arise in practice. The state-of-the-art approach for solving integer problems uses so-called cutting-planes to cut off points that have fractional coordinates. Recently a new cutting-plane theory has emerged which is based on lattice-free sets. Lattice-free sets are convex sets whose interior does not contain integer points. The interior of a lattice-free set does therefore not contain any feasible solutions to an integer optimization problem. In this talk we survey this new approach and present some of the results that have been obtained. We also consider algorithmic consequences. In particular we present a new class of cutting planes that have a number of desirable theoretical properties. We call these cutting-planes for zero-coefficient cuts. In terms of quality, zero-coefficient cuts are those cuts that are violated the most, and in terms of efficiency, zero-coefficient cuts can be identified efficiently in polynomial time. Initial computational experiments suggest that zero-coefficient cuts could be an interesting class of cutting-planes to include in practical software for mixed integer optimization.

We consider the problem of maintaining dynamically a set of points in the plane and supporting range queries of the type [a,b]x(- \infty, c]. We assume that the inserted points have their x-coordinates drawn from a class of smooth distributions, whereas the y-coordinates are arbitrarily distributed. The points to be deleted are selected uniformly at random among the inserted points.

For the RAM model, we present a linear space data structure that supports queries in O(log log n + t) expected time with high probability and updates in O(log log n) expected amortized time, where n is the number of points stored and t is the size of the output of the query.

For the I/O model we support queries in O(log log_B n + t/B) expected I/Os with high probability and updates in O(log_B log n) expected amortized I/Os using linear space, where B is the disk block size.

The data structures are deterministic and the expectation is with respect to the input distribution.

Joint work with: G.S. Brodal, A. Kaporis, S. Sioutas, K. Tsichlas

We consider the problem of approximating a set P of n points in \Re^d by a j-dimensional subspace under the l_p measure, in which we wish to minimize the sum of l_p distances from each point of P to this subspace. More generally, the F_q(l_p)-subspace approximation problem asks for a j-subspace that minimizes the sum of qth powers of l_p-distances to this subspace, up to a multiplicative factor of (1+epsilon).

We develop techniques for subspace approximation, regression, and matrix approximation that can be used to deal with massive data sets in high dimensional spaces. In particular, we develop coresets and sketches, i.e. small space representations that approximate the input point set P with respect to the subspace approximation problem. Among the results we propose a dimensionality reduction method for various clustering measures, strong coreset, ptas and streaming algorithms in bounded and unbounded precision model for F₁(l₂)-subspace approximation in high-dimensional spaces.

Joint work with: Dan Feldman, Christian Sohler, David P. Woodruff

In this talk we present a data structure to do a 3-approximation of the range mode with constant time queries and linear space. We present a data structure doing a (1+eps)-approximation of the range mode in O(log(1/eps)) time and O(n/eps) time. Finally we present some work on the related Fixed Range Frequency problem.

Joint work with: Mark Greve, Allan Grønlund Jørgensen and Kasper Dalgaard Larsen

Everyone knows the determinant of a square matrix. The permanent is less known though it is almost the same thing, one just omits all the switching of signs. Note that in characteristic 2 the permanent and determinant are the same thing. One can compute the determinant of a given matrix in polynomial time using Gaussian elimination. However this does not hold for the permanent, assuming the characteristic is not 2, since it is not multiplicative.

One might ask if there is some way to compute the permanent by "blowing up and applying the determinant". More precisely can one compute the permanent by constructing a bigger matrix with linear (affine) polynomials as entries, such that the permanent equals the determinant applied to this bigger matrix? Valiant has shown that such maps exist; in fact all polynomials can be written as the determinant of some matrix with linear entries.

The topic of this talk is to establish a lower bound of how fast these matrices grow as the original matrices grow. A result due to Mignon and Ressayre gives by use of Hessian matrices that the growth is at least quadratic, when working over a field of characteristic 0. This has been generalized by Cai, Chen and Li to hold over fields of odd characteristic. For a variety X there is a link from the rank of a Hessian matrix to the dimension of the dual variety. We will outline a translation of the work of Mignon, Ressayre, Cai, Chen and Li into the language of dual varieties.

In this talk we present an I/O-efficient version of an algorithm for simplifying contour trees of two- and three-dimensional scalar fields described by Carr et al. Our algorithm uses optimal O(sort(N)) I/Os where N is the size of the contour tree. Like the algorithm of Carr et al. our algorithm can perform the simplification based on a number of local geometric measures associated with the individual contours.

Joint work with: Lars Arge

Consider the following problem: a large data x in 0,1^k is stored on a storage device in some encoded form. A fraction of the stored information might have got corrupted. An algorithm needs the data x as input. But most likely the algorithm will only need a small fraction (say t bits) of the data for its execution. Thus decoding the whole message is not economical. Also the algorithm is adaptive and thus does not know which bits it would need beforehand. So ideally it would like to decode any bit of the x only when the need arises and would like to decode the bit by looking at a very small fraction of the encoded data. To ensure correctness of the algorithm we would hope that the algorithm manages to correctly decode all the t bits with high probability (say > 2/3).

This example motivated us to define reconstructible code. A k-query t-bit reconstructible code allows to probabilistically decode any bit of an encoded message by probing only k bits of its corrupted encoding such that any t-bits of the message is decoded correctly with high probability.

An LDC can be converted into a reconstructible code by amplification of the success probability. But the question we ask is what is the best query complexity of a t-bit reconstructible code. We will study the limitations on reconstructible codes and see how it related to other areas in computer science.

Identical products being sold at different prices in different locations is a common phenomenon. Price differences might occur due to different reasons such as shipping costs, trade restrictions and price discrimination. This is modeled in traditional market models by adding a production that transfers the goods from one location to another. However, this approach is not always satisfactory since it would have the market determine the cost of production as well, as opposed to it being exogenously specified, and it would unnecessarily blow up the number of goods in the market, which affects the computational complexity of finding an equilibrium.

We give a more direct way to model such scenarios by supplementing the classical Fisher model of a market by introducing transaction costs. For every buyer i and every good j, there is a transaction cost of c(i,j); if the price of good j is p(j) then the cost to the buyer i per unit of j is p(j) + c(i,j). This allows the same good to be sold at different (effective) prices to different buyers. We study questions regarding existence, uniqueness and computability of equilibrium in such a model.

Joint work with Chinmay Karande and Nikhil Devanur.

In this talk I will describe a new technique for proving data structure lower bounds based on statistical reasoning. I will present it in the context of new (as in submitted-5-days-ago new) lower bounds for dynamic membership in the external memory model; the general technique, however, might (and should!) have further applications.

The external memory model is just like the cell probe model, except that it has a free-to-access cache of size m, and the cell size is typically w=polylog(n). The cell-probe model for data structures counts only cell-accesses, so computation is free. One of the most interesting features of the external memory model is that it allows to achieve sub-constant update time by writing multiple items to the cache, and then writing them to memory at the same time using only one probe (just like what is done in practice when paging). This is called *buffering*.

There is a data structure called the buffer tree, which achieves update time roughly O(log2(n)/w) and query time O(logn); it works for multiple problems, among them membership, predecessor search, rank select, 1-d range counting, etc. . For w=log9(n), for example, the update time here is subconstant.

We prove that if one wants to keep the update time less than 0.999 (or any const<1), it is impossible to reduce the query time to less than logarithmic (namely, to o(log_wlogn(n/m)) ). Thus one has a choice between two sides of a dichotomy: either buffer very well but take at least logarithmic query time, or use the old data structures from the RAM model who do not buffer at all, and have a shot at sublogarithmic query time.

To restate, we prove that for membership data structures, in order to get update time 0.999, the query time has to be at least logarithmic.

This is a *threshold phenomenon for data structures*, since when the update time is allowed to be 1+o(1), then a bit vector or hash table give query time O(1).

The proof of our lower bound is based on statistical reasoning, and in particular on a new combinatorial lemma called the Lemma Of Surprising Intersections (LOSI) The LOSI allows us to use a proof methodology where we first analyze the intersection structure of the positive queries by using encoding arguments, and then use statistical arguments to deduce properties of the intersection structure of *all* queries, even the negative ones. We have not previously seen this way of arguing about the negative queries, and we suspect it might have further applications.

Joint work with: Qin Zhang, HKUST

The past fifteen years has seen an amazing burst of research in streaming algorithms, starting with the famous paper by Alon, Matias, and Szegedy. In particular, space-efficient algorithms are possible for several functions, when you allow both randomness and approximation. However, this comes at a price: most of the algorithms pay a penalty in space that is quadratic with the approximation factor.

In 2003, Woodruff and Indyk showed that this penalty was necessary in the case of one-pass data streams, using a reduction from the one-way complexity of the Gap Hamming problem. However, it has been a long standing open problem whether the same lower bound applies to multipass algorithms.

We extend this lower bound so it holds even when a constant number of rounds of communication are allowed. As a result, we show that even with O(1) passes, streaming algorithms must pay a high price for their approximation. Our main technique combines a Round Elimination Lemma with several isoperimetric inequalities.

Joint work with Amit Chakrabarti, Ishay Haviv, Oded Regev, Thomas Vidick, and Ronald de Wolf.

Computational topology is attractive for visualization tasks because it provides abstractions of scalar fields that can be exploited either directly or indirectly to extract information and knowledge from underlying data sets. The first part of this talk will provide a brief survey of the applications reported to date, while the second part will focus on unresolved questions relating to adaptive meshing, higher-order interpolation, and applications to multi-variate data.

In this talk we design data structures supporting range median queries, i.e. report the median element in a sub-range of an array. We consider static and dynamic data structures and batched queries. Our data structures support range selection queries, which are more general, and dominance queries (range rank). In the static case our data structure uses linear space and queries are supported in O(log n/loglog n) time. Our dynamic data structure uses O(nlog n/log log n) space and supports queries and updates in O((log n/loglog n)²) time.

A Boolean function f on n inputs is called a sign-function of an integer polynomial p on n variables if for all n-bit strings x it holds that p(x)>0 if f(x)=1 and p(x)<0 if f(x)=0. In this case p is called a perceptron for f. The degree of the perceptron is simply the degree of the polynomial and the weight of the perceptron is the sum of the absolute values of its coefficients.

In this talk we will be interested in the smallest possible weight of a perceptron of a given degree for a given function. We will review upper and lower bounds on this quantity and give some proof ideas.

The talk will be based on the following papers:

Vladimir V. Podolskii. Perceptrons of Large Weight. Problems of Information Transmission. 45(1):51-59, 2009.

Vladimir V. Podolskii. A Uniform Lower Bound on Weights of Perceptrons. Proc. of the Third International Computer Science Symposium in Russia (CSR), pp. 261-272, 2008.

In orthogonal range reporting we are to preprocess N points in d-dimensional space so that the points inside a d-dimensional axis-aligned query box can be reported efficiently. This is a fundamental problem in various fields, including spatial databases and computational geometry.

In this talk we show a number of improvements for three and higher dimensional orthogonal range reporting:

* In the pointer machine model, we improve all the best previous results, some of which have not seen any improvements in almost two decades.

* In the I/O-model, we improve the previously known three-dimensional structures and provide the first (nontrivial) structures for four and higher dimensions.

Joint work with: Peyman Afshani Lars Arge

e give new results on the number-on-the-forhead (NOF) communication complexity of the multiparty pointer jumping problem.

The origional motivation for this problem comes from circuit complexity. Specifically, there is no explicit function known to lie outside the complexity class ACC0. However, a long line of research in the early 90's showed that a sufficiently strong NOF communication lower bound for a function would place it outside ACC0. Pointer juming is widely considered to be a strong candidate for such a lower bound.

We give a surprising general upper bound to this problem, as well as a tight upper and lower bound for a restricted class of protocols.

Part of this talk was joint work with Amit Chakrabarti.

We reexamine what it means to compute Nash equilibria and, more generally, what it means to compute a fixed point of a given Brouwer function, and we investigate the complexity of the associated problems. Specifically, we study the complexity of the following problem: given a finite game with 3 or more players, and given epsilon > 0, approximate some actual Nash Equilibrium to within distance epsilon.

We show that for games with 3 (or more) players approximating an actual NE within any non-trivial distance is at least as hard as long standing open problems in numerical computation (the square-root-sum problem and arithmetic circuit decision problems), which are not known to be in NP nor in the polynomial time hierarchy.

Thus, approximating an actual NE for 3-player games is much harder, in our present state of knowledge, than the PPAD-complete problems of computing an epsilon-NE for 3-player games, and of computing an actual NE for 2-player game.

We define a new complexity class, FIXP, which captures search problems that can be cast as fixed point computation problems for functions represented by algebraic circuits (straight line programs) over basis +,*,max with rational coefficients. We show that the computation (approximate or otherwise) of actual Nash equilibria for 3 or more players is FIXP-complete. We show that PPAD is precisely equal to the piecewise-linear fragment of FIXP where the basis is restricted to the operators +,max.

Many other important problems in game theory, economics, and probability theory, can be formulated as fixed point problems for such algebraic functions. We discuss several such problems: computing economic market equilibria, computing the value of Shapley's stochastic games and Condon's simpler games, and computing extincition probabilities of branching processes. We show that for approximation, or even exact computation, some of these problems can be placed in PPAD, while others are at least as hard as the square-root sum and arithmetic circuit decision problems, and some are FIXP-complete.

The policy iteration algorithms is a simple family of algorithms that can be applied in many different settings, ranging from the relatively simple problem of finding a minimum mean weight cycle in a graph, the more challenging solution of Markov Decision Processes (MDPs), to the solution of 2-player full information stochastic games, also known as Simple Stochastic Games (SSGs).

It was recently shown by Fridmann that the worst case running time of a natural deterministic version of the policy iteration algorithm, when applied to Parity Games (PGs), is exponential. It is still open, however, whether deterministic policy iteration algorithm can solve Markov Decision Processes in polynomial time, and whether randomized policy iteration algorithms can solve Simple Stochastic Games in polynomial time.

The talk will survey what is known regarding policy iteration algorithms and mention many intriguing open problems.

We consider the problem of representing, in a space-efficient way, a function f: S -> Sigma such that any function value can be computed in constant time on a RAM. Specifically, our aim is to achieve space usage close to the 0th order entropy of the sequence of function values. Our technique works for any set S of machine words, without storing S, which is crucial for applications.

Our contribution consists of two new techniques, of independent interest, that we use in combination with an existing result of Dietzfelbinger and Pagh (ICALP 2008). First of all, we introduce a way to support more space efficient approximate membership queries (Bloom filter functionality) with arbitrary false positive rate. Second, we present a variation of Huffman coding using approximate membership, providing an alternative that improves the classical bounds of Gallager (IEEE Trans. Information Theory, 1978) in some cases. The end result is an entropy-compressed function supporting constant time random access to values associated with a given set S. This improves both space and time compared to a recent result by Talbot and Talbot (ANALCO 2008).

Joint work with Johannes Hreinsson and Morten Krøyer

Standard worst-case analysis of algorithms has often been criticized as overly pessimistic. As a remedy, some researchers have turned towards adaptive analysis where the cost of algorithms is measured as a function of not just the input size but other parameters, such as the output size. The ultimate in adaptive algorithms is an instance-optimal algorithm, i.e., an algorithm whose cost is at most a constant factor from the cost of any other algorithm running on the same input, for every input instance. In other words, an instance-optimal algorithm cannot be beaten by any other algorithm on any input.

For many problems, this requirement is too stringent but we show that if we ignore the order of the input elements (i.e., we assume the input is given in the worst case order), then adaptive algorithms exist for many fundamental geometric problems such as convex hull. Thus, these convex hull algorithms are optimal with respect to all the measures of difficulty that are independent of the order, such as output-size, spread of the input point set or more complicated quantities like the expected size of the convex hull of a random sample.

Joint work with: Jeremy Barbay Timothy M. Chan

Parameterized complexity aims to design exact algorithms whose running times depend on certain parameters of the input data that are naturally related to the problem at hand and in a way capture its complexity. A problem is called fixed-parameter tractable (FPT) with respect to a parameter k if there is an efficient algorithm to solve the problem for the cases where the parameter k is small. Another objective of this theory is to show that such algorithms are unlikely to exist for certain problems (and parameters).

Not many geometric problems have been studied from the parameterized complexity point of view. Most research has focused on special (combinatorial) parameters for geometric problems, like, e.g., the number of inner points (i.e., points in the interior of the convex hull) for the TSP problem or for the problem of computing minimum convex decompositions. Also, on the negative side, only few connections between geometric problems and known hard parameterized problems are known to date. We provide a brief tour of results from parameterized complexity theory for various geometric problems (e.g. hyperplane depth, clustering) with a focus on the dimension as the parameter. Our results indicate that all these problems are inherently difficult in higher dimensions.

Joint work with:

Sergio Cabello Panos Giannopoulos Günter Rote

In recent years, a number of cache-oblvious range search structures for 3-sided range reporting in the plane, 3-d dominance reporting, and 3-d halfspace range reporting with the optimal query bound of O(log_B N + K/B) I/O's have been developed. These structures use O(N log N) space, while the best cache-aware structures for these problems use (almost) linear space. This raises the question whether linear-space cache-oblivious structures with the optimal query bound exist for these problems. We give a negative answer to this question by proving that Omega(N (log log N)^epsilon) space is necessary to achieve the optimal query bound cache-obliviously. This is the first result that provides a gap between the resource consumption of a cache-oblivious algorithm or data structure and its cache-aware counterpart that grows with the input size.

Let (S, d) be a finite metric space, where each element p . S has a non-negative weight wt(p). We study t-spanners for the set S with respect to the following weighted distance function d.: d.(p, q) = 0 if p = q, dw(p,q) = wt(p) + d(p, q) + wt(q) if p <> q.

We present a general method for turning spanners with respect to the d-metric into spanners with respect to the d.-metric. For any given . > 0, we can apply our method to obtain (5+ .)-spanners with a linear number of edges for three cases: points in Euclidean space Rd, points in spaces of bounded doubling dimension, and points on the boundary of a convex body in Rd where d is the geodesic distance function. We also describe an alternative method that leads to (2+.)-spanners for points in Rd and for points on the boundary of a convex body in Rd. The number of edges in these spanners is O(n log n). This bound on the stretch factor is nearly optimal: in any finite metric space and for any . > 0, it is possible to assign weights to the elements such that any non-complete graph has stretch factor larger than 2 . ..

Model checking is a popular approach for formal verification of reactive systems. However, usage of this method is limited by so-called state space explosion. One way to cope with this problem is to represent the model and the state space symbolically by using Binary Decision Diagrams (BDDs). Unfortunately, during the computation the BDD can become too large to fit into the available main memory and it becomes essential to minimize the number of I/O operations.

In this presentation, we will first talk about model checking and related problems in general. After that we will give a short introduction to BDDs and we will discuss their usage in symbolic model checking. Finally, we will briefly mention previous work on I/O-efficient BDD manipulation and we will talk about our research in this area. We will present general idea of our new vector existential quantification algorithm which is the first I/O-efficient algorithm to solve this or similarly complex problem connected to BDDs.

The B-tree is a fundamental external index structure that is widely used for answering one-dimensional range reporting queries. Given a set of N keys, a range query can be answered in O(logB N/M + K/B) I/Os, where B is the disk block size, K the output size, and M the size of the main memory buffer. When keys are inserted or deleted, the B-tree is updated in O(logB N) I/Os, if we require the resulting changes to be committed to disk right away. Otherwise, the memory buffer can be used to buffer the recent updates, and changes can be written to disk in batches, which significantly lowers the amortized update cost. A systematic way of batching up updates is to use the logarithmic method, combined with fractional cascading, resulting in a dynamic B-tree that supports insertions in O(1/B log N/M) I/Os and queries in O(log N/M + K/B) I/Os. Such bounds have also been matched by several known dynamic B-tree variants in the database literature.

Note that, however, the query cost of these dynamic B-trees is substantially worse than the O(logB N/M + K/B) bound of the static B-tree by a factor of O(log B).

In this paper, we prove that for any dynamic one dimensional range query index structure with query cost O(q + K/B) and amortized insertion cost O(u/B), the tradeoff q log(u/q) = Omega(log B) must hold if q = O(log B). For most reasonable values of the parameters, we have N/M = B^O(1), in which case our query-insertion tradeoff implies that the bounds mentioned above are already optimal. We also prove a lower bound of u log q = Omega(log B), which is relevant for larger values of q. Our lower bounds hold in a dynamic version of the indexability model, which is of independent interests. Dynamic indexability is a clean yet powerful model for studying dynamic indexing problems, and can potentially lead to more interesting complexity results.

Real algebraic numbers are the numbers that are real solutions of a univariate polynomial with integer coefficients, and they are usually represented using the isolating interval representation, that is a square-free polynomial and an isolating interval. To construct such numbers we need to isolate the real roots of a univariate polynomial. We will present some recent complexity and algorithmic results for the problem of real root isolation, and we will sketch on going work on random polynomials.

Algebraic algorithms, and in particular computations with real algebraic numbers and (real) solving of univariate polynomials and polynomial systems, are powerful tools that could be used in many applications. We will present some recent advances in the problem of symmetric tensor decomposition, and in non-linear computational geometry. The latter includes the arrangement of conic arcs, the Voronoi diagram of convex smooth pseudo-circles. and the computation of the topology of a real plane algebraic curve. If time permits, we will also present algorithms that given a convex lattice polygon, test whether it can be decomposed into a Minkowski sum of two other such polygons and if so, find one or all such decompositions. The problem is closely related to the problem of bivariate polynomial factorization.

Abstract: Through the example of the BIG MATCH, we give a gentle invitation to the theory of two-player zero-sum stochastic games with limiting average payoffs. Such games were shown to have values in a celebrated 1981-paper by Mertens and Neyman, building on earlier work of Bewley and Kohlberg. A key ingredient of this earlier work is an elegant use of the Tarski transfer theorem. In 2009, Solan and Vielle published an algorithmic version of the theorem of Mertens and Neyman, but without any non-trivial upper bound on the computational resources used by the algorithm. Such a bound would seem to require new theorems of semi-algebraic geometry. We shall discuss as much of the above as the patience of the audience and the ability of the lecturer permits, and save the rest of the story for a later meeting.

The founders of Google introduced the PageRank algorithm that computes an estimate of the popularity of each web page based solely on the link structure of the web graph - these estimates are the so called PageRank values. A page will achieve one of the top spots of search results if it has a high PageRank value and it matches the search criteria for the actual Google search.

For a given node t in a directed graph G(V,E) and a positive integer k we study the problem of computing a set of k new links pointing to t - so called backlinks to t - producing the maximum increase in the PageRank value of t. This problem is known as "Link Building" in the www context. We present a theorem showing how the topology of the graph comes in to play when evaluating potential new backlinks. Based on the theorem we show that no FPTAS exists for Link Building under the assumption NP<>P and we also show that Link Building is W[1]-hard - strongly suggesting that Link Building is not fixed parameter tractable. We prove these results by reduction from the independent set problem on regular graphs. Finally, we use the theorem to characterize sets of backlinks producing a significant increase in the PageRank value of t.

Semi-algebraic geometry is concerned with the set of real solutions of systems of polynomial equations and inequalities, called semi-algebraic sets. In this lecture we will introduce semi-algebraic sets from basics. Next we will prove the Tarski-Seidenberg theorem, that semi-algebraic sets in (n+1)-dimensional space projects to semi- algebraic sets in n-dimensional space. Coupled with parametric versions of real root counting techniques such as Sturm sequences (that we will also cover from basics) this gives us a decision procedure for determining if the given system has a real solution. This lecture marks the beginning of a series of lectures on semi- algebraic geometry. The intent is that it will over time transform into a reading/lecture series working towards research problems.

In this talk we shall classify several group-theoretic computational problems into the classes PZK and SZK (problems with perfect/statistical zero-knowledge proofs respectively). Previously, these problems were known to be in AM and coAM. As PZK and SZK are subsets of AM as well as coAM, we have a tighter upper bound for these problems.

Specifically:

1) We will show that the permutation group problems Coset Intersection, Double Coset Membership, Group Conjugacy are in PZK. We will also show that permutation group isomorphism for solvable groups is in PZK. As an ingredient of this protocol, we design a randomized algorithm for sampling short presentations of solvable permutation groups.

2) We shall show that the above problems for black-box groups are in SZK.

This talk is based on a joint work with V. Arvind.

A terrain S is the graph of a bivariate function. We assume that S is represented as a triangulated surface with n vertices. A "contour" of S is a connected component of a level set of S. Generically, each contour is a closed polygonal curve; at "critical" levels these curves may touch each other. We present I/O-efficient algorithms for the following two problems related to computing contours of S:

Given two real parameters h and d > 0, we present an I/O-optimal algorithm that report all contours of S at heights h + kd, for every positive integer k, using O(Sort(N)+T/B) I/Os, where T is the total number edges in the output contours, B is the "block size," and Sort(N) is the number of I/Os needed to sort N elements. The algorithm uses

O(N/B) disk blocks. Each contour is generated individually with its composing segments sorted in clockwise order.

We can preprocess S, using O(Sort(N)) I/Os, into a linear-size data structure so that all contours at a given height can be reported using O(log_B N + T/B) I/Os, where T is the output size. Each contour is generated individually with its composing segments sorted in clockwise order.

Joint work with: Lars Arge, Pankaj K. Agarwal, and Bardia Sadri

The problem of estimating the pth moment F_p (p nonnegative and real) in data streams is as follows. There is a vector x which starts at 0, and many updates of the form x_i <- x_i + v come sequentially in a stream. The algorithm also receives an error parameter 0 < eps < 1. The goal is then to output an approximation with relative error at most eps to F_p = ||x||_p^p.

Previously, it was known that polylogarithmic space (in the vector length n) was achievable if and only if p <= 2. We make several new contributions in this regime, including:

(*) An optimal space algorithm for 0 < p < 2, which, unlike previous algorithms which had optimal dependence on 1/eps but sub-optimal dependence on n, does not rely on Nisan's PRG. (*) A near-optimal space algorithm for p = 0 with optimal update and query time. (*) A near-optimal space algorithm for the "distinct elements" problem (p = 0 and all updates have v = 1) with optimal update and query time. (*) Improved L_2 -> L_2 dimensionality reduction in a stream. (*) New 1-pass lower bounds to show optimality and near-optimality of our algorithms, as well as of some previous algorithms (the "AMS sketch" for p = 2, and the L_1-difference algorithm of Feigenbaum et al.).

As corollaries of our work, we also obtain a few separations in the complexity of moment estimation problems: F_0 in 1 pass vs. 2 passes, p = 0 vs. p > 0, and F_0 with strictly positive updates vs. arbitrary updates.

Joint work with Daniel Kane (Harvard) and David Woodruff (IBM Almaden).

Compressed sensing is a method for reconstructing a sparse signal from a low-rank linear sketch. This is useful because many real-world signals have sparse representations in some basis; for example, images are sparse in the wavelet basis and music is sparse in the Fourier basis.

In the past five years, a variety of sketch matrices and reconstruction techniques have emerged that can efficiently and stably recover an N-dimensional vector with K non-zero components from O(K log N/K) linear measurements.

We prove that any stable recovery scheme requires Omega(K log N/K) linear measurements, matching the upper bound. This contrasts with the Theta(K) measurements required for unstable recovery.

Given a set P of n points in d-dimensional space, a unit- disk graph is a graph built with P as the vertex set, by connecting two vertices (i.e., points) if and only if their Euclidean distance is at most one. We are interested in problems related to the maximum cliques in a unit-disk graph.

These graphs have numerous applications (for instance, they can be used to model wireless networks) and are well studied in computational geometry literature and other fields.

In this talk, after a brief introduction, we will survey a few previous results on this problem. First, we will review how the algorithmic problem of computing the maximum clique corresponds to the following non-algorithmic covering problem: for R^d, find the minimum value of k and a set S of k objects of diameter one, such that *any* shape of diameter one can be covered using k elements of S.

For d=2 the answer is two; for d=3 the best result so far is five and no non-trivial result is known for higher dimensions.

We will also examine a related problem of embedding graphs as unit- disk graphs including some embedding results.

References

* Finding k points with minimum diameter and related problems Alok Aggarwal and Hiroshi Imai and Naoki Katoh and Subhash Suri, Journal of Algorithms, volume 12, pages: 38 - 56, 1991

* Approximation algorithms for maximum cliques in 3D unit-disk graphs, Peyman Afshani and Timothy Chan, CCCG, pages 6-9, 2005

* Approximation and inapproximability results for maximum clique of disc graphs in high dimensions, Peyman Afshani and Hamed Hatami, Information Processing Letters, volume 105, pages 83-87, January 2008

* On finding a large number of 3D points with a small diameter, Minghui Jiang, Discrete Applied Mathematics, 155:2355-2361, 2007

We present a new (1+\eps)-spanner for sets of n points in \Reals^d. Our spanner has size O(n/\eps^d-1) and maximum degree O(log^d n).

The main advantage of our spanner is that it can be maintained efficiently as the points move: Assuming the trajectories of the points can be described by bounded-degree polynomials, the number of topological changes to the spanner is O(n²/\eps^d-1), and using a supporting data structure of size O(nlog^dn) we can handle events in time O(log^d+1 n). Moreover, the spanner can be updated in time O(log n) if the flight plan of a point changes.

This is the first kinetic spanner for points in \Reals^d whose performance does not depend on the spread of the point set.

The goal of coordination mechanism is to design policies in such a way that the policies reflect the social cost in the individual costs so that selfish agents' behaviors result in a socially desirable solution. In the talk, we are interested in coordination mechanism in scheduling games where every player has to choose a machine on which to execute its job. The cost of a player is the completion time of its job and the social cost is the makespan - the largest load over all machines.

Most prior studied policies depend on the processing times and need the jobs to announce their processing times. The jobs could try to influence the schedule to their advantage by misreporting their processing times. In our work, we study the so-called non-clairvoyant policies policies do not require knowledge on the processing times of jobs - in scheduling games. We introduce a non-clairvoyant policy under which the scheduling game always admits an equilibrium and the price of anarchy matches that of the best (strongly local) clairvoyant policy.

Joint work with Christoph Durr.

In this talk I will show how we improve both the upper and lower bounds for three-dimensional range search indexing, the problem of storing a set of points in three dimensions such that the points in a three-dimensional axis-parallel query hyper-rectangle can be found efficiently.

I first describe a disk based index structure for three-dimensional range searching that answers queries in optimal O(log_B N+T/B) I/Os using O(N (log N/(loglog_B N))³) space, where B is the disk block size, N the number of points, and T the query output size. The previously best known structure uses O(N (log N)³) space. I will also describe improved structures for several infinite range variants of the problem.

Next I will show how we apply the theory of indexability to show that any d-dimensional range search index answering queries in O(PolyLog N+T/B) I/Os has to use Omega(N (log N/(loglog_B N))^d-1) space. The previously best known lower bound was Omega(N (log B /(loglog_B N))^d-1) space.

Our results narrows the space gab between the lower and upper bound to a factor of \log N/loglog_B N, thus moving us closer to optimal three-dimensional range search indexing.

A Kakeya set is any set of points in n-Euclidean space which contains a unit line segment in every direction. The famous Kakeya conjecture is that such sets must have Hausdorff dimension and Minkowski dimension n. In this talk we consider the finite field version of the Kakeya question, and cover a recent optimal lower bound on the size of Kakeya sets due to Zeev Dvir.

We will next cover applications to the problem of randomness extraction studied in theoretical computer science. This problem is the following: We are given access to a source of "dirty" randomness with a guarantee that it has min-entropy k. Using a short seed of pure random bits we wish to transform the source of "dirty" randomness into a source of "pure" randomness, i.e close in statiscal distance to pure random bits.

The talk will be based on the following papers (available at http://www.math.ias.edu/ dvir/papers/lop.html).

* Z. Dvir. On the size of Kakeya sets in finite fields. J. Amer. Math. Soc. (to appear), 2008.

* Z. Dvir and A. Wigderson. Kakeya sets, new mergers and old extractors. In FOCS '08, 2008.

* Z. Dvir, S. Kopparty, S. Saraf, and M. Sudan. Extensions to the method of multiplicities, with applications to kakeya sets and mergers.

R-trees are a class of spatial index structures in which objects are arranged to enable fast window queries: report all objects that intersect a given query window. One of the most successful methods of arranging the objects in the index structure is based on sorting them along a space-filling curve.

In this talk, I will discuss how the choice of space-filling curve influences the query performance of such index structures. We take a look at two types of input objects.

For sets of points in the plane we can qualify the efficiency of two-dimensional space-filling curves using quality measures. We develop new measures and prove general lower bounds for a number of cases. I will also discuss the results of our approximation algorithm for such measures for a number of space-filling curves.

For sets of rectangles in the plane we propose new four-dimensional space-filling curves and test their performance on several real-world and synthetic data sets. The new curves combine the strengths of earlier approaches based on two- and four-dimensional curves, while avoiding their apparent weaknesses.

Joint work with Herman Haverkort.

Flash memory based solid-state disks are fast becoming the dominant form of end-user storage technology for mobile devices, partly even replacing the traditional hard disks. The I/O characteristics of the currently available solid-state disks fundamentally differ from those of the hard disks. In this talk, I will present new computation models that can capture the intricacies of the flash devices better. I will then discuss the relationship between the proposed models and the existing memory hierarchy models and show how a large body of merging-based external memory algorithms can be adapted to the flash models.

Joint work with Andreas Beckmann, Ulrich Meyer, Gabriel Moruz and Riko Jacob.

The Tutte polynomial sits in the intersection of enumerative combinatorics, graph theory, and statistical physics. Depending on who looks at it, it counts the colourings of a graph, its number of spanning forests, the reliability of a network, the topology of a knot, and many other things; perhaps most importantly, it computes the partition function of the Ising, Potts, and random cluster model. All in all, tens of thousands of research papers have been written about it in some guise or another.

In the first half of my talk I will spend some time introducing the Tutte polynomial in several ways. For the algorithmic audience this will go via the deletion-contraction algorithm. For the more algebraically inclined I will approach it via the chromatic polynomial from algebraic graph theory. I will also show the connection to statistical mechanics via the Potts model, demonstrating all the theoretical physics I know, which isn't a lot.

Then I will show how the Tutte polynomial for a given graph can be computed in time exponential in the number of vertices. (It's straightforward to do this in time exponential in the number of edges.)

Joint work with A. Björklund (Lund), P. Kaski (Helsinki), and M. Koivisto (Helsinki), FOCS 2008

Halfspace range reporting is a data structure problem in computational geometry where we are to preprocess an input set of point in a data structure that is capable of answering the following queries: report all the points inside a given halfspace.

This fundamental problem has been studied for more than 25 years, and during this time many efficient solutions were given for the problem in three dimensions, but unfortunately none of them was optimal. In this talk, after a brief introduction to the problem, we will describe a recent simple idea which allows us to obtain the first optimal data structure for this problem. We will also investigate the implications of our techniques in higher dimensions and in the I/O model.

Joint work Timothy Chan.

This work discusses extensions and results on the price of anarchy for network congestion games that in general quantify the loss of efficiency due to lack of central control. In this work, the users in the system have different aims (utility functions). In particular we discuss the impact of malicious and oblivious behavior in routing games; a malicious user attempts to increase congestion for a system, while an oblivious user acts without any knowledge of the congestion of the network.

Speaker's short bio: taso viglas is a senior lecturer at the university of sydney. taso received his PhD from Princeton University in 2002, and was a postoctoral fellow at the University of Toronto for two years, before joining the University of Sydney in 2004. taso's main research interests include computational complexity theory and algorithmic game theory.

We explore various techniques to compress a permutation pi over n integers, taking advantage of ordered subsequences in pi, while supporting its application pi(i) and the application of its inverse pi^-1(i) in small time. Our compression schemes yield several interesting byproducts, in many cases matching, improving or extending the best existing results on applications such as the encoding of a permutation in order to support iterated applications pi^k(i) of it, of integer functions, and of inverted lists and suffix arrays.

Joint work with Gonzalo Navarro

We design a new P2P data structure, called the Deterministic Distributed tree (DDtree). The DDtree compares favourably to other designs for the following reasons: a) it divides the overlay structure of the P2P environment from the actual elements stored in it and b) it provides better complexities (which are deterministic) compared to all previous solutions. Additionally, the division between elements and nodes results in a load balancing problem in which we have provided an innovative and very efficient solution.This load-balancing scheme can also be applied to any other tree structure in a P2P environment. Finally, a small discussion on models of P2P Networks is initiated.

In an array of n numbers each of the \binomn2+n contiguous subarrays define a sum. In this paper we focus on algorithms for selecting and reporting maximal sums from an array of numbers. First, we consider the problem of reporting k subarrays inducing the k largest sums among all subarrays of length at least l and at most u. For this problem we design an optimal O(n+k) time algorithm. Secondly, we consider the problem of selecting a subarray storing the k'th largest sum. For this problem we prove a time bound of Theta(n · max{1,log (k/n)}) by describing an algorithm with this running time and by proving a matching lower bound. Finally, we combine the ideas and obtain an O(n· max{1,log (k/n)}) time algorithm that selects a subarray storing the k'th largest sum among all subarrays of length at least l and at most u.

Bounded volume hierarchies (BVHs) are efficient and versatile search data structures for geometric data, which are similar to binary space partitions (BSPs). Like BSPs, they store the geometric data in the leafs of a search tree. While each non-leaf node of a BSP stores a half-plane that decides what data is stored in which sub-tree, the non-leaf nodes of a BVH stores a bounding volume of the data of each of its sub-trees.

Different BVHs differ mostly in two ways, in the shape of the bounding volumes, and in the way they are constructed. The first criterion usually determines the name of a BVH. The simplest BVH is the box tree, which stores axis-aligned boxes as bounding volumes. Its strength is its simplicity and the efficiency of intersection tests with a box. Its weakness is input data aligned to a diagonal, which may cause linear instead of the usual logarithmic query running time.

A c-DOP tree stores convex polygonal bounding volumes whose sides are parallel to a set of c pre-determined directions. c-DOP trees have better worst-case query running times than box trees, but lack the simplicity of box trees and are therefore often slower.

We introduce a new BVH, the c-rotating-box tree (c-rb tree), which is a compromise of box tree and c-DOP tree. Every bounding volume stored in a c-rb tree is a box, but they are not necessarily axis-aligned. The boxes are aligned to c pre-determined directions. The c-rb tree allows more efficient intersection operations than c-DOP trees and has the same worst-case behavior.

We prove that c-rb trees indeed have the same worst case complexity as c-DOP trees, and we compare several variants of the three data structures by experiments.

Joint work with Mark de Berg.

We consider enhancing a sealed-bid single-item auction with privacy concerns, our assumption being that bidders primarily care about monetary payoff and secondarily worry about exposing information about their type to other players and learning information about other players? types. To treat privacy explicitly within the game theoretic context, we put forward a novel hybrid utility model that considers both fiscal and privacy components in the players? payoffs. We show how to use rational cryptography to approximately implement a given ex interim indi- vidually strictly rational equilibrium of such an auction (or any game with a winner) without a trusted mediator through a cryptographic protocol that uses only point-to-point authenticated channels between the players. By ?ex interim individually strictly rational? we mean that, given its type and before making its move, each player has a strictly positive expected utility, i.e., it becomes the winner of the auction with positive probability. By ?approximately implement? we mean that, under cryptographic assump- tions, running the protocol is a computational Nash equilibrium with a payoff profile negligibly close to the original equilibrium.

In addition the protocol has the stronger property that no collusion, of any size, can obtain more by deviating in the implementation than by deviating in the ideal mediated setting which the mechanism was designed in. Also, despite the non-symmetric payoffs profile, the protocol always correctly terminates.

Joint work with Nikolaos Triandopoulos and Peter Bro Miltersen.

We study the following extension of the static one-dimensional range reporting problem. For an array A of n elements, build a data structure that supports the query: Given two indices i.j and an integer k, report the k smallest elements in the sub array A[i..j] in sorted order. We present a static data structure that uses O(n) words of space, supports queries in O(k) time, and can be constructed in O(n log n) time on the RAM model. We also extend the data structure to solve the online version of the problem where the elements in A[i..j] are reported in sorted order one-by-one, each element being reported in O(1) worst-case time. The data structure has applications to e.g. top-k queries in databases, prioritized suffix tree reporting, and three-sided planar sorted range reporting.

We revisit Washburn's deterministic graphical games, a natural generalization of the perfect information win/lose games commonly solved by retrograde analysis. We study the complexity of solving deterministic graphical games and obtain an almost-linear time comparison-based algorithm for computing an equilibrium of such a game. The existence of a linear time comparison-based algorithm remains an open problem.

Joint work with Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, and Troels Bjerre Sørensen.

I will present a simple algorithm which maintains the topological order of a directed acyclic graph with n nodes under an online edge insertion sequence in O(n^2.75) time, independent of the number of edges inserted. I will then show an average case analysis of incremental topological ordering algorithms. After discussing some recent advances in this area, I will talk about dynamic topological ordering in the external memory model.

Joint work with Tobias Friedrich, MPI and Ulrich Meyer, J.W. Goethe Universität

We study social cost losses in Facility Location games, where n selfish agents install facilities over a network and connect to them, so as to forward their local demand (expressed by a non-negative weight per agent). Agents using the same facility share fairly its installation cost, but every agent pays individually a (weighted) connection cost to the chosen location. We study the Price of Stability (PoS) of pure Nash equilibria and the Price of Anarchy of strong equilibria (SPoA), that generalize pure equilibria by being resilient to coalitional deviations. A special case of recently studied network design games, Facility Location merits separate study as a classic model with numerous applications and individual characteristics: our analysis for unweighted agents on metric networks reveals constant upper and lower bounds for the PoS, while an O(ln n) upper bound implied by previous work is tight for non-metric networks. Strong equilibria do not always exist, even for the unweighted metric case. For this case we prove existence of 2.36-approximate strong equilibria, whereas in general we show that e-approximate strong equilibria exist (e=2.718...). The SPoA is generally upper bounded by O(ln W) (W is the sum of agents' weights), which becomes tight for unweighted agents. For the unweighted metric case we prove a constant upper bound. We point out challenging open questions that arise.

Joint work with Thomas Dueholm Hansen.

Let X = x₁ x₂ ... x_n be a string over a finite, ordered alphabet S. A secondary index for X answers alphabet range queries of the form: Given a range [1,r] over S, return the set I_[1,r] = {i | x_i \in [l,r]}. Secondary indexes are heavily used in relational databases and scientific data analysis. It is well-known that the obvious solution of storing a dictionary for the position set associated with each character, does not always give optimal query time. In this paper we give the first theoretically optimal data structure for the secondary indexing problem. In the I/O model, the amount of data read when answering a query is within a constant factor of the minimum space needed to represent I_[l,r], assuming that the size of internal memory is S^Omega(1) blocks. The space usage is \O(n log |S|) bits in the worst case, and we also show how to bound the size of the data structure in terms of the 0th order entropy of X. Updates can be done in essentially the same time bound as for buffered B-trees. We also consider an approximate version of the basic secondary indexing problem, where a query reports a superset of I_[l,r] containing each element not in I_[l,r] with probability at most epsilon, where epsilon > 0 is the false positive probability. For this problem the amount of data that needs to be read by the query algorithm is reduced to |I_[l,r]| log (1/epsilon) bits.

We consider some well known families of two-player, zero-sum, turn-based, perfect information games that can be viewed as specical cases of Shapley's stochastic games.

Strengthening a theorem of Zwick and Paterson, we show that the following tasks are polynomial time equivalent:

1. Solving simple stochastic games,

2. Solving stochastic mean-payoff games with rewards and probabilities given in unary, and

3. Solving stochastic mean-payoff games with rewards and probabilities given in binary.

Joint work with Vladimir Gurvich.

Tagline: "I am a Bear of Very Little Brain, and long words bother me." - Winnie the Pooh

Abstract:

A minimal perfect hash function maps a set S of n keys into the set {0, 1, ..., n - 1 } bijectively. Classical results state that minimal perfect hashing is possible in constant time using a structure occupying space close to the lower bound of log e bits per element. Here we consider the problem of monotone minimal perfect hashing, in which the bijection is required to preserve the lexicographical ordering of the keys. A monotone minimal perfect hash function can be seen as a very weak form of index that provides just ranking on the set S (and answers randomly outside of S). Our goal is to minimise the description size of the hash function: we show that, for a set S of n elements out of a universe of 2w elements, O (nlog log w) bits are sufficient to hash monotonically in time O (log w). Alternatively, we can get space O (n log w) bits with O (1) query time. Both of these data structures improve a straightforward construction with O (n log w) space and O (log w) query time. As a consequence, it is possible to search a sorted table with O (1) accesses to the table (using additional O (n log log w) bits). Our results are based on a structure (of independent interest) that represents very compactly a trie, but allows for errors. As a further application of the same structure, we show how to compute the predecessor (in the sorted order of S) of an arbitrary element, using O (1) accesses in expectation and an index of O (n log w) bits, improving the trivial result of O (nw) bits. This implies an efficient index for searching a blocked memory.

Joint work with Djamal Belazzougui, Paolo Boldi, and Sebastiano Vigna. To appear at SODA '09.

This paper studies real-world road networks from an algorithmic perspective, motivated from empirical studies that yield useful properties of road networks that can be exploited in the design of fast algorithms that deal with geographic data. Unlike previous approaches, our study is not based on the assumption that road networks are planar graphs. Indeed, based on the number of experiments we have performed on the road networks of the 50 United States and District of Columbia, we provide strong empirical evidence that road networks are quite non-planar. Our approach therefore instead is directed at finding algorithmically-motivated properties of road networks as non-planar geometric graphs, focusing on alternative properties of road networks that can still lead to efficient algorithms for such problems as shortest paths and Voronoi diagrams. Our empirical analysis uses the U.S. TIGER/Line road network database, as provided by the Ninth DIMACS Implementation Challenge, which is comprised of over 24 million vertices and 29 million edges.

We study a simple greedy tree packing of a graph and use it to derive better algorithms for fully-dynamic min-cut and for the static k-way cut problem.

A greedy tree packing is a sequence of spanning tree where each new tree is a minimum spanning tree with respect to the edge loads from the previous trees, that is, the load of an edge is the number of times it has been used by the previous trees.

A minimum k-way cut is a minimum set of edges whose removal splits the graph in k components. A min-cut is a minimum 2-way cut.

If the (unknown) edge connectivity of the graph is c, we show that if we pack c⁷*log³ m trees, then some min-cut is crossed exactly once by some tree. This leads to the best fully-dynamic min-cut algorithm (presented at STOC'01) If we pack k³*log n trees, then every minimum k-way cut is crossed 2k-2 times by some tree. This leads to the best determinstic algorithm for k-way cut (presented at STOC'08).

We observe that many important computational problems in NC1 share a simple self-reducibility property. We then show that, for any problem A having this self-reducibility property, A has polynomial size TC0 circuits if and only if it has TC0 circuits of size n^1+epsilon for every epsilon > 0 (counting the number of wires in a circuit as the size of the circuit). As an example of what this observation yields, consider the Boolean Formula Evaluation problem (BFE), which is complete for NC1 and has the self-reducibility property. It follows from a lower bound of Impagliazzo, Paturi, and Saks, that BFE requires depth d TC0 circuits of size n^1+epsilon_d. If one were able to improve this lower bound to show that there is some constant epsilon>0 such that every TC0 circuit family recognizing BFE has size n^1+epsilon, then it would follow that TC0 != NC1. We show that proving lower bounds of the form n^1+epsilon is not ruled out by the Natural Proof framework of Razborov and Rudich and hence there is currently no known barrier for separating classes such as ACC0, TC0 and NC1 via existing ``natural'' approaches to proving circuit lower bounds.

We also show that problems with small uniform constant-depth circuits have algorithms that simultaneously have small space and time bounds. We then make use of known time-space tradeoff lower bounds to show that SAT requires uniform depth d TC0 and AC0[6] circuits of size n^1+c for some constant c depending on d.

Joint work with Eric Allender

Suppose you have a fixed set of n numbers and you want to create a data structure that allows a fast search in this set. How fast can such a search be? Well it depends on what computer you have. But theoreticians don't have computers, instead we have models of computation. But what is a model of computation other that saying what things you can do in what amount of time? Being able to set the rules by which our algorithms are evaluated should make it easier to design fast algorithms. Traditionally, models of computation have had some relation to actual computers, but insisting on this relationship can result in slower algorithms than if one is unconstrained by reality. In particular, we discuss how non-standard, but plausible, CPU and memory designs can allow the design of asymptotically faster fundamental algorithms.

Consider a point set D with a measure function mu : D -> R. Let A be the set of subsets of D induced by containment in a shape from some geometric family (e.g. axis-aligned rectangles, half planes, balls, k- oriented polygons). We say a range space (D, A) has an epsilon-sample (a.k.a. epsilon-approximation) P if

We describe algorithms for deterministically constructing discrete epsilon-samples for continuous point sets such as distributions or terrains. Furthermore, for certain families of subsets A, such as those described by axis-aligned rectangles, we reduce the size of the epsilon-samples by almost a square root from O(1/epsilon² log 1/epsilon) to O(1/epsilon polylog 1/epsilon). This is often the first step in transforming a continuous problem into a discrete one for which combinatorial techniques can be applied. I will describe applications of this result in geo-spatial analysis, biosurveillance, and sensor networks.

The B-tree is the classic external-memory-dictionary data structure. The B-tree is typically analyzed in a two-level memory model (called the DAM or I/O model) in which internal memory of size M is organized into size-B blocks, and there is an arbitrarily large external memory.

The cost in the model is the number of block transfers between internal and external memory. An N-element B-tree supports supports searches, insertions, and deletions in O(log_B N) block transfers.

In fact, there is a tradeoff between the cost of searching and inserting in external-memory dictionaries [Brodal,Fagerberg 03], and the B-tree achieves only one point on this tradeoff. A more general tradeoff is exhibited by their buffered B-tree.

This talk presents two points on the insert/search tradeoff for cache-oblivious (CO) data structures, the "cache-oblivious lookahead array (COLA)," and the "shuttle tree." The CO model is similar to the DAM model, except that the block size B and memory size M are unknown to the algorithm. The buffered B-tree is not cache oblivious-buffer sizes are chosen according to B.

The COLA implements searches in O(log_2 N) I/Os and inserts in amortized O( (log_2 N) / B) I/Os. Notice that the searches are worse than in the B-tree by a log_2(B) factor, but the inserts are better by a B/log_2(B) factor. These bounds represent one optimal point on insert/search tradeoff space. In fact, when made into a cache-aware data structure, the lookahead array achieves the same tradeoff as the buffered B-tree.

The shuttle tree implements searches in the optimal O(log_B N) block transfers. Inserts cost o(log_B N) block transfers, improving on the B-tree by a superconstant factor.

Joint work with: Michael A. Bender, Martin Farach-Colton, Yonatan R. Fogel, Bradley C. Kuszmaul, and Jelani Nelson.

We show that generating all negative cycles of a weighted graph is hard in both directed and undirected cases. More precisely, all negative cycles cannot be generated in time polynomial in the number of such cycles, unless P=NP. As a corollary we solve in the negative two well-known generating problems from linear programming:

* Given an infeasble system of linear inequalities, generating all minimal infeasible subsystems (so-called Helly subsystems) is hard. Yet, for generating maximal feasible subsystems the complexity remains open.

* Given a feasible system of linear inequalities, generating all vertices of the corresponding polyhedron is hard. Yet, the problem reamins open in the case of bounded polyhedra.

Joint work with L. Khachiyan, E. Boros, K. Borys, K. Elbassioni and H.R. Tiwary

It is shown that any weakly-skew circuit can be converted into a skew circuit with constant factor overhead, while preserving either syntactic or semantic multilinearity. This leads to considering syntactically multilinear algebraic branching programs (ABPs), which are defined by a natural read-once property. A 2^n/4 size lower bound is proven for ordered syntactically multilinear ABPs computing an explicitly constructed multilinear polynomial in 2n variables. Without the ordering restriction a lower bound of level Omega(n^3/2/log n) is observed, by considering the generalization of a hypercube covering problem by Galvin.

It is shown that any weakly-skew circuit can be converted into a skew circuit with constant factor overhead, while preserving either syntactic or semantic multilinearity. This leads to considering syntactically multilinear algebraic branching programs (ABPs), which are defined by a natural read-once property. A 2^n/4 size lower bound is proven for ordered syntactically multilinear ABPs computing an explicitly constructed multilinear polynomial in 2n variables. Without the ordering restriction a lower bound of level Omega(n^3/2/log n) is observed, by considering the generalization of a hypercube covering problem by Galvin.

The splay tree is a dynamic binary search tree that is conjectured to be universally efficient in the following way. On any sequence of accesses the splay tree is conjectured to take time within a constant factor of the optimal (offline) dynamic binary search tree. Splay trees are traditionally analyzed using potential functions or some other counting argument.

In this talk I will present a new way to analyze splay trees (and dynamic data structures in general). The three-part strategy is to (1) transcribe the operations of the data structure as some combinatorial object, (2) show the object has some forbidden substructure, and (3) to prove upper bounds on the size of such a combinatorial object. As an example of this strategy, we show that splay trees execute a sequence of N deque operations (push, pop, inject, and eject) in O(Na^* (N)) time, where a^* is the iterated-inverse-Ackermann function. This bound is within a tiny a^*(N) factor of that conjectured by Tarjan in 1985.

We prove that the weighted monotone circuit satisfiability problem has no fixed-parameter tractable approximation algorithm with constant or polylogarithmic approximation ratio unless FPT = W[P]. The parameterized complexity class FPT consists of all fixed-parameter tractable problems, and the class W[P] may be viewed as an analogue of the class NP in the world of parameterized complexity theory. Our result answers a question of Alekhnovich and Razborov, who proved that the weighted monotone circuit satisfiability problem has no fixed-parameter tractable 2-approximation algorithm unless every problem in the parameterized complexity class W[P] can be solved by a randomized fpt algorithm and asked whether their result can be derandomized.

The decision version of the monotone circuit satisfiability problem is known to be complete for the class W[P]. By reducing them to the monotone circuit satisfiability problem with suitable approximation preserving reductions, we prove similar inapproximability results for all other natural minimisation problems known to be W[P]-complete.

Joint work with Martin Grohe and Magdalena Grüber

At AAAI'07, Zinkevich, Bowling and Burch introduced the Range of Skill measure of a two-player game and used it as a parameter in the analysis of the running time of an algorithm for finding approximate solutions to such games. They suggested that the Range of Skill of a typical natural game is a small number, but only gave heuristic arguments for this. In this work, we provide the first methods for rigorously estimating the Range of Skill of a given game. We provide some general, asymptotic bounds that imply that the Range of Skill of a perfectly balanced game tree is almost exponential in its size (and doubly exponential in its depth). We also provide techniques that yield concrete bounds for unbalanced game trees and apply these to estimate the Range of Skill of Tic-Tac-Toe and Heads-Up Limit Texas Hold'em Poker. In particular, we show that the Range of Skill of Tic-Tac-Toe is more than 100,000.

Joint work with Peter Bro Miltersen and Troels Bjerre Sørensen, to appear at AAI'08.

We revisit the question of persistence-sensitive simplification on 2-manifolds. We call function g an epsilon-simplification of function f if the L_\infty distance between f and g is no more than epsilon, and the persistence diagrams of g are the same as those of f except all points within L_1-distance at most epsilon from the diagonal are removed. We give an algorithm for constructing epsilon-simplifications that is considerably simpler than its predecessor, allows for hierarchical simplification, and results in a bounded subdivision of the domain.

Joint work with Dominique Attali, Marc Glisse, Samuel Hornus, and Francis Lazarus.

When introducing the notion of an Evolutionarily Stable Strategy (ESS) to Game Theory, J. Maynard Smith and others simultaneously began a tradition for applying Game Theory to Evolutionary thinking. (The ESS describes a more restricted case of a Nash Equilibrium.) Game theory has since been an integral part of evolutionary biology. Expression such as evolution of cooperation and evolution of altruism can often be observed in the titles of evolutionary game theory. Obviously the Prisoner's Dilemma (PD) game is ubiquitous in evolutionary game theory, but also Maynard Smith's Hawk-Dove (HD) game has for example played a principal role. Unlike the PD game, it can result in a stable polymorphic state of the population containing both strategies. Here, I introduce a few diverse examples of game theoretical applications from biology ranging from competition among proliferating cells to competing mating strategies and species interactions. The former, constructed as the simplest possible n-player Prisoner's Dilemma game, showed interesting patterns such as bifurcation dynamics and hysteresis. Mating competition among male lizards has been shown to exhibit Rock-Scissors-Paper dynamics also allowing the population to simultaneously sustain all three strategies.

A Simple Stochastic Game is played by two players called Min and Max, moving turn by turn a pebble along edges of a graph. Some vertices are random and the next vertex is chosen randomly with fixed transition probabilities. Player Max wants the pebble to reach a special vertex called the target vertex.

Solving a simple stochastic game consists in computing the maximal probability with which player Max can enforce the pebble to reach the target vertex.

In this talk, we will review known algorithm for solving simple stochastic games and we will present a new algorithm especially efficient for games with few random vertices.

Boolean Operations on polyhedra are a basic building block of many geometric applications such as the visual hull, robot motion planning, computer-aided design and packing problems. Since exact geometry is considered to be slow, industrial applications usually rely on data structures and algorithms that are neither complete nor robust.

We implemented Boolean operations on Nef polyhedra as a part of the Computational Geometry Algorithm Library (CGAL). The implementation is complete, exact and still fast enough to compete with industry products. In comparison to the widely used ACIS CAD kernel our CGAL implementation is about 4-7 times slower, while ACIS does not always supply correct results. In scenarios that are (close to) degenerate our Nef polyhedra can be faster than ACIS.

Based on Nef polyhedra we present the first robust implementation of the Minkowski sum of two non-convex polyhedra.

Computational mechanism design (CMD) seeks to understand how to design games that induce desirable outcomes in multi-agent systems despite private information, self-interest and limited computational resources. CMD finds application in many settings, from allocating wireless spectrum and airport landing slots, to Internet advertising, to expressive sourcing in the supply chain, to allocating shared computational resources. In meeting the demands for CMD in these rich domains, we often need to bridge from the classic theory of economic mechanism design to the practice of deployable, scalable mechanisms.

Of particular interest is the problem of designing coordination mechanisms for dynamic environments, with agent arrivals and departures and agents that experience changes to local information (e.g., about preferences or capabilities), or more generally changes to their local state. We can conceptualize these systems as loosely-coupled Markov Decision Processes (MDPs), with each agent's local problem modeled as a privately known and privately observable MDP and constraints on joint action profiles. This formulation also allows for environments in which agents are learning about their value for resources with "information-state MDPs" modeling Bayesian-optimal learning. I sketch a sequence of models for dynamic coordination problems, and an overview of how the family of Groves mechanisms can be generalized to these environments. In offering some remarks about computational challenges and opportunities in these domains, I will also outline a complementary direction in "computational ironing", which dynamically modifies online stochastic combinatorial optimization algorithms to provide them with appropriate monotonicity properties, and therefore make them non-manipulable. Time permitting, I will touch on some directions for future work.

Joint work with Ruggiero Cavallo, Quang Duong, and Satinder Singh.

We present a tradeoff between the length of a 3-query probabilistically checkable proof of proximity (PCPP) and the best possible soundness obtained by querying it. Consider the task of distinguishing between ``good'' inputs w in 0,1^n that are codewords of a linear error correcting core C over the binary alphabet and ``bad'' inputs that differ from every word of C on 1/2 of their bits. To perform this task, we allow oracle access to w and an auxiliary proof pi, however, we place the following limitations on our verifier: (i) it can read at most 3 bits from w and pi, (ii) it must accept every ``good'' input with probability one (when accompanied by a suitable proof), and (iii) its decision must be *linear* - i.e., based on the parity of the sum of the queried bits. We notice that all known techniques for PCPP constructions yield verifiers for linear codes that satisfy these conditions, so our tradeoff applies to all of them.

Our main result implies that for certain codes, every verifier accessing a proof of polynomial length (in the length of the input), will accept some ``bad'' words with probability at least 2/3. In contrast, if no limitation is placed on the proof length, we can construct a verifier that rejects any ``bad'' word with the largest possible probability of 1/2. In other words, the closer the rejection probability is to the best possible, the longer the proof our verifier will require. This tradeoff between proof length and soundness holds for any code that is not locally testable, including codes with large dual distance and most random Low Density Parity Check (LDPC) codes.

We develop a polynomial-time algorithm for finding the extensive form correlated equilibrium(EFCE) for multiplayer extensive games with perfect recall. The EFCE concept is defined by von Stengel and Forges (2007). We describe the set of EFCE with polynomial number of incentive constraints for multiplayer perfect-recall extensive games without chance moves. We explain that linear programming duality, the ellipsoid algorithm, and Markov chain steady state computations employed by Papadimitriou and Roughgarden (2007) for computing correlated equilibrium can also be used for computing EFCE. We explain how to apply this algorithm to multiplayer perfect-recall extensive games with chance moves. We also describe a possible interpretation of the variables in the dual system.

The index of a Nash equilibrium is an integer that is related to notions of ``stability'' of the equilibrium. The index is a relatively complicated topological notion, essentially a geometric orientation of the equilibrium. We prove the following theorem, first conjectured by Hofbauer (2003), which characterizes the index in much simpler strategic terms:

Theorem. A generic bimatrix game has index +1 if and only if it can be made the unique equilibrium of an extended game with additional strategies of one player. In an mxn game, it suffices to add 3m strategies of the column player.

The main tool to prove this theorem is a novel geometric-combinatorial method that we call the ``dual construction'', which we think is of interest of its own. It allows to visualize all equilibria of an mxn game in a diagram of dimension m-1. For example, all equilibria of a 3xn game are visualized with a diagram (essentially, of suitably connected n+3 points) in the plane. This should provide new insights into the geometry of Nash equilibria.

Joint work with Arndt von Schemde.

We consider the problem of computing a minimum-distortion embedding of a finite metric space into a low-dimensional Euclidean space. It has been shown by Matousek [Mat90] that for any d\geq 1, any n-point metric can be embedded into R^d with distortion O(n^2/d) via a random projection, and that in the worst case this bound is essentially optimal. This clearly also implies an O(n^2/d)-approximation algorithm for minimizing the distortion. We show that for any fixed d\geq 2, there is no polynomial-time algorithm for embedding into R^d, with approximation ratio better than Omega(n^1/(17d)), unless P=NP. Our result establishes that random projection is not too far, concerning the dependence on d, from the best possible approximation algorithm for this problem. Our proof uses a result from Combinatorial Topology due to Sarkaria, that characterizes the embeddability of a simplicial complex in terms of the chromatic number of a certain Kneser graph.

We complement the above result by showing that for the special case where the input space is an ultrametric, there exists a polynomial-time algorithm for embedding into R^d with poly-logarithmic approximation ratio.

Joink work with Jiri Matousek, and Krzysztof Onak.

This paper adapts two optimization routines to deal with objective functions for DSGE models. The optimization routines are i) a version of Simulated Annealing developed by Corana, Marchesi & Ridella (1987) and ii) the evolutionary algorithm CMA-ES developed by Hansen, Muller & Koumoutsakos (2003). Following these modifications we examine the ability of the two routines to maximize the likelihood function for a DSGE model. Our results show that the CMA-ES routine clearly outperforms Simulated Annealing in its ability to find the global optimum and in efficiency. With 10 unknown structural parameters in the likelihood function the CMA-ES routine is able to find the global optimum in 9

The optimal consumption, portfolio, house size and labor choice of an economic agent is analyzed in a continuous-time, continuous-state model that allows for stochastic house prices, wage and interest rates. The wage rates and the house prices can be instantaneously correlated with both interest rates, bond prices and stock prices. The model allows for the expected wage rate growth to be an affine function of the real short-term interest rate in order to encompass business cycle variations. In this setup I show how the optimal stock/bond/cash allocation of a long-term investor is affected in the presence of housing. In the absence of portfolio restrictions, liquidity constraints and when both the wage rate and the house prices is spanned by the financial market, i.e. when the economy is complete, I derive the solution in close-form and state the optimal strategies. The model is analyzed by numerical methods when the economy is incomplete.

We present a cache-oblivious algorithm for computing single-source shortest paths in undirected graphs with non-negative edge lengths. The algorithm incurs O(.(nm log w)/B+(m/B) log n +MST (n, m)) memory transfers on a graph with n vertices, m edges, and real edge lengths between 1 and W; B denotes the cache block size, and MST(n, m) denotes the number of memory transfers required to compute a minimum spanning tree of a graph with n vertices and m edges. Our algorithm is the first cache-oblivious shortest-path algorithm incurring less than one memory transfer per vertex if the graph is sparse (m = O(n)) and W = 2B).

We examine the problem of integer representation in near minimal number of bits so that the increment and the decrement (and indeed the addition and the subtraction) operations can be performed using few bit inspections and fewer bit changes. In particular, we prove a new lower bound of Omega(sqrt(n)) for the increment and the decrement operation, where n is the minimum number of bits required to represent the number. The model of computation we considered is the bit probe model, where the complexity measure counts only the bitwise accesses to the data structure. We present several efficient data structures to represent integer that use a logarithmic number of bit inspections and a constant number of bit changes per operation. Finally, we present an extension to our data structure to support a special form of addition and subtraction while retaining the same asymptotic bounds for the increment and the decrement operations.

A Nash equilibrium of a noncooperative game is a pair of strategies such that no player has an incentive to unilaterally deviate from his current strategy. Recent results (e.g. Daskalakis, Goldberg, Papadimitriou '06 and Chen, Deng, Teng '06) indicate that polynomial time algorithms for finding an exact Nash equilibrium are unlikely to exist.

In this talk we will consider the question of computing approximate Nash equilibrium strategies in bimatrix games. In particular, given a bimatrix game where the entries of both payoff matrices are in the interval [0,1], we will say that a pair of strategies is an epsilon-Nash equilibrium if no player can gain more than epsilon by deviating. I will first summarize the existing results on the complexity of this problem. Then I will present a new polynomial time approximation algorithm that achieves an improved approximation guarantee of epsilon = 0.36.

The classical secretary problem studies the problem of selecting online an element (a "secretary") with maximum value in a randomly ordered sequence. The difficulty lies in the fact that an element must be either selected or discarded upon its arrival, and this decision is irrevocable. Constant-competitive algorithms are known for the classical secretary problems and several variants. In this talk, I present extensions of this problem to combinatorial settings and settings with weights and discounts. These generalizations can be used to build mechanisms for a class of online combinatorial auctions.

Parts of this talk are based on joint work with Moshe Babaioff, Michael Dinitz, Anupam Gupta, David Kempe, Robert Kleinberg, and Kunal Talwar.

We study the flow of water on fat terrains, that is, triangulated surfaces where the minimum angle of any triangle is bounded from below by a positive constant. We show that the worst-case complexity of any path of steepest descent on a fat terrain of n triangles is Theta(n), and that the worst-case complexity of the river network on such terrains is Theta(n²). This improves the corresponding bounds for arbitrary terrains by a linear factor. We prove that in general similar bounds cannot be proven for Delaunay triangulations: these can have river networks of complexity Theta(n³).

Moreover, we present an acyclic graph, the descent graph that enables us to trace flow paths on triangulated surfaces I/O-efficiently. We use the descent graph to obtain I/O-efficient algorithms for computing river networks and watershed-area maps of fat terrains in O(sort(r + n)) I/O's, where r is the complexity of the river network. We also describe a data structure for reporting the boundary of the watershed of a query point q (or the flow path from q) in O(l + k) I/O's, where 1 is the number of I/O's used for planar point location and k is the size of the reported output.

Phase transitions not only occur in physics but also in many problems in computer science. An especially important problem is the satisfiability problem, SAT, for Boolean formulas. K-SAT is the problem, where the formulas are restricted to clauses consisting of exactly K literals. When the density of clauses (i.e., the ratio between the number of clauses and the number of variables) is increased in random K-SAT problems, there is an abrupt change in the probability from being satisfiable to being unsatisfiable. Numerous experimental results are available, but the exact location of the phase transition is not known for the random K-SAT problem with K > 2. There are only lower and upper bounds which are rigorously proven.

We consider formulas with more structure, the model of fixed balanced shapes introduced by Navarro and Voronkov in 2005. They provided first upper bounds for the location of the critical value, i.e., where the phase transition occurs. These upper bounds were obtained by using the first moment method (FMM).

In this talk, we present how to improve the upper bounds by a method which is based on locally maximal solutions. This method has been proposed by Creignou and Daud in 2007. Since this method requires a sensitivity polynomial as an input, we show how such polynomials can be computed for shapes in general.

The "Names in boxes" game is presented by Peter Winkler (College Math. J, vol 37:4, page 260) as follows:

"The names of one hundred prisoners are placed in one hundred wooden boxes, one name to each box, and the boxes are lined up on a table in a room. One by one, the prisoners are led into the room; they may look into up to fifty of the boxes to try to find their own name but must leave the room exactly as it was. They are permitted no further communication after leaving the room. The prisoners have a chance to plot a strategy in advance and they are going to need it, because unless they all find their own names they will all be executed. There is a strategy that has a probability of success exceeding thirty percent - find it"

The game first appeared (in a somewhat less elegant version) in Anna Gal and Peter Bro Miltersen, "The cell probe complexity of succinct data structures", at ICALP 2003.

In this talk we present the history of the game and explain its original motivation from the study of cell probe complexity, a combinatorial theory of compact representation and retrieval of data. In particular, we explain how the "Names in boxes" game relates to the following fundamental question of data retrieval: Can data be stored, so that EVERY data base query with a polynomial time algorithm can be answered in logarithmic time by a sequential algorithm?

We address the extension of the binary search technique from sorted arrays and totally ordered sets to trees and tree-like partially ordered sets. As in the sorted array case, the goal is to minimize the number of queries required to find a target element in the worst case. However, while the optimal strategy for searching an array is straightforward (always query the middle element), the optimal strategy for searching a tree is dependent on the tree's structure and is harder to compute. We present an O(n)-time algorithm that finds the optimal strategy for binary searching a tree, improving the previous best O(n3)-time algorithm. The significant improvement is due to a novel approach for computing subproblems, as well as a method for reusing parts of already computed subproblems, and a linear-time transformation from a solution in the form of an edge-weighed tree into a solution in the form of a decision tree.

In this talk, I will present a framework for algorithms for learning statistical models of clustering in the streaming model of computation. The streaming model is a paradigm for the design of algorithms for massive data sets, in which the algorithm may make only a small number of sequential passes over the input while using a very small amount of working memory in order to accomplish the computational task at hand.

Our algorithms will consider the following statistical model for clustering, known as a mixture of distributions. We are given k different probability distributions F_1, ..., F_k, each of which is given a weight w_i >0. A point is drawn according to the mixture by choosing a distribution F_i with probability proportional to w_i and then choosing a point according to F_i. The data are then ordered arbitrarily and placed into a data stream and the algorithm's task is to learn the density function of the mixture.

I will present a multiple pass streaming algorithm that uses P passes over the data, where P is an input parameter to the algorithm. The memory requirement of the algorithm falls significantly as a function of P, showing a strong trade-off between the number of passes and memory required. Using communication complexity, this trade-off can be proved to be nearly tight, for a slightly stronger learning problem.

I will show how this framework can be adapted to solving clustering problems in combinatorial optimization.

A story of academic researchers taking their findings to the market will be told. Trade Extensions was founded in 2000 as an offspring of theoretical research on how to combine electronic negotiations with optimization techniques and algorithm design. The company now has offices in Sweden and UK, presence in more countries, and a global customer base. Some reflections will be given on the challenges in taking academic research to the "real world".

We study multi-commodity auction where some bidders have synergies between commodities. That is, a bidder gets an extra value if he manages to win all in a specific group of commodities. In such a situation, it is a common belief that the auctioneer gets a better revenue by letting the bidder bid on explicit combinations, a so-called combinatorial auction. However, so far there has been no proof that a combinatorial auction actually gives higher revenue. Indeed, the only existing analysis is for a small auction with two commodities, and where the result is the opposite; it is better for the auctioneer to only allow single bids.

In this work, we provide the first analytical comparison of the revenue with and without combinatorial bids for a multi-commodity auction with more than two commodities. By giving bounds on the optimal bidding strategies for combinatorial and non-combinatorial auctions, we manage to prove that a combinatorial indeed gives higher revenue to the auctioneer.

Joint work with Arne Andersson.

A succinct data structure occupies an amount of space that is close to the information-theoretic minimum plus an additional term. The latter is not necessarily a lower-order term and, in several cases, completely dominates the space occupancy both in theory and in practice. We present several solutions to partially overcome this problem, introducing new techniques of independent interest that allow us to improve over previously known upper and lower bounds.

Joint work with: Alex Golynski, Ankur Gupta, Roberto Grossi, and Srinivasa Rao

In recent years, there has been an increased interest in understanding selfish routing in large networks like the Internet. Since the Internet is operated by different economic entities with varying interests, it is natural to model these entities as selfish agents who are only interested in maximizing their own benefit. Congestion games are a classical model for resource allocation among selfish agents. We consider the special case of network congestion games, in which the resources are the edges of a graph and every player wants to allocate a path between her source and target node. The delay of an edge increases with the number of players allocating it, and every player is interested in allocating a routing path with minimum delay.

It is well known that there are stable states of the game in which no player has an incentive to change her strategy, since all alternative paths have greater delays than the one chosen. These states are known as Nash equilibria and are not necessarily optimal with respect to some overall measure of the state the game is in. In the development process of a network architecture one might be interested in analysing its performance when a Nash equilibrium is reached, for which such a state has to be computed. However, it has been shown that the problem of computing Nash equilibria in network congestion games is PLS-complete, which basically means that there is no known efficient algorithm to solve the problem. A standard approach in computer science to circumvent such impediments is to approximate a solution to the problem. But there is also a different reason to consider approximations in the first place. In many applications, players incur some costs when they change their strategy. Hence, it is reasonable to assume that a player is only interested in changing her strategy if this decreases her delay significantly. These considerations lead to the notion of an .-approximate Nash equilibrium, which is a state in which no player can decrease her delay by more than a factor of (1 + .) by unilaterally changing her strategy. Unfortunately, it was lately shown that the problem of computing an .-approximate Nash equilibrium in congestion games is PLS-complete too and it is strongly believed that this result also holds for network congestion games.

However, the delay functions used in the reductions are quite artificial. Therefore we formulate some restrictions on the delay functions, and by that obtain an efficient algorithm using the method of randomised rounding to compute .-approximate Nash equilibria for network congestion games We then study the delay function classes that result from the found restrictions, including polynomi- als, exponential functions, a mixture of the first two, and functions from queuing theory.

The fully worked out thesis treating the described issues can be reviewed at http://www-users.rwth-aachen.de/andreas.feldmann/thesis.pdf.

Study of Network Formation Games constitutes an exciting research branch of Algorithmic Game Theory, aiming at understanding performance of networks formed by selfish autonomous entities. In this talk we give a brief overview of results on network formation games, and focus on distributed caching/replication networks in particular.

We study implications of selfish behavior in total bandwidth consumption over a distributed replication network formed by autonomous users/nodes. A user may choose to replicate (up to constrained local storage capacity) a subset of frequently accessed information objects, and retrieve the rest from neighboring nodes, so as to minimize his individual access cost. For the related strategic game we prove existence of pure strategy Nash equilibria on certain network topologies, and study their quality in terms of the prices of anarchy and stability. We also discuss related open problems.

In the finite capacity dial-a-ride problem the input is a metric space, a set of objects, where each object d_i specifies a source s_i and a destination t_i, and an integer k - the capacity of the vehicle used for making the deliveries. The goal is to compute a shortest tour for the vehicle in which all objects can be delivered to their destinations (from their sources) while ensuring that the vehicle carries at most k objects at any point in time. There are two variants of the problem: the non-preemptive case, in which an object once loaded on the vehicle stays on it until delivered to its destination, and the preemptive case in which an object may be dropped at intermediate locations and then picked up later by the vehicle and delivered.

The dial-a-ride problem generalizes the Traveling Salesman problem (TSP) even for k=1 and is thus NP-hard.

Let N be the number of nodes in the input graph, i.e., the number of points that are either sources or destinations. Charikar and Raghavachari gave a minO(log N), O(k)-approximation algorithm for the preemptive version of the problem.

We show that the preemptive dial-a-ride problem has no minO(log^(1/4-epsilon)N),k^(1-epsilon)-approximation algorithm for any epsilon>0 unless NP is a subset of ZP(n^(polylog n)). ZP(n^(\polylog n)) is the class of problems solvable by a randomized algorithm that always returns the right answer and has expected running time O(n^(polylog n)), where n is the size of the input.

We will also discuss why this lower bound not extends to the non-preemptive case and discuss ideas for showing hardness of approximation of this variant of the problem.

We define and study new variants of the network interdiction problem, where the objective is to destroy high-capacity paths from the source to the destination. We consider both global and local, node-wise limited, budgets of arc removals. We suggest a polynomial time algorithm for global budgets and an almost-linear time comparison based algorithm for local budgets. The extistence of a linear time algorithm remains an open problem.

This talk is based on joint work with Peter Bro Miltersen, Troels Bjerre Sorensen, and Kristoffer Arnsfelt Hansen.

During the last years there has been an interest in research that explores the connections between game theory and cryptography, especially in the context of protocol design.

In this talk, we first give a brief overview of some existing work in the area of rational cryptography, which studies game-theoretic analysis of cryptographic protocols and cryptography-based implementations of game-theoretic concepts. We then describe a multi-party protocol for securely computing a class of functions in a model where none of the participating parties are honest: they are either rational, acting in their selfish interest to maximize their utility, or adversarial, acting arbitrarily.

Consider a task like the execution of a computer program or a file transfer that may fail before being completed. Standard schemes for failure recovery are RESUME (continue after repair), REPLACE (start a new task of the same type) and RESTART (start the same task from the beginning), but also ideas like checkpointing have been discussed. Failure times are considered random and often also ideal task times. In both cases, the total actual task time is random. RESUME and REPLACE have been analyzed in work by Trivedi, Kulkarni and others, whereas RESTART has resisted detailed analysis until recently. We present a discussion of the various schemes and more detailed results on the structure of the total task time for RESTART. Also some applications to parallel computing are outlined.

It is well known that Nash equilibria of two-player zero-sum extensive form games can be found using linear programming. Despite the widespread use of this technique, the strategies computed suffer from certain deficiencies as they sometimes fail to prescribe sensible play in all parts of the game. This issue is addressed by the concept of equilibrium refinements. A well established refinement is the normal form proper equilibrium, which has many desirable properties.

In this talk, we show how to find a normal form proper equilibrium in behavior strategies of a given two-player zero-sum extensive form game with imperfect information but perfect recall. Our algorithm solves a finite sequence of linear programs and runs in polynomial time. For the case of a perfect information game, we show how to find a normal form proper equilibrium in linear time by a simple backwards induction procedure.

This is joint work with Peter Bro Miltersen.

We develop two new methods for creating high-quality tetrahedral meshes: one with guaranteed good dihedral angles, and one that in practice produces far better dihedral angles than any prior method. The isosurface stuffing algorithm fills an isosurface with a uniformly sized tetrahedral mesh whose dihedral angles are bounded between 10.7 degrees and 165 degrees. The algorithm is whip fast, numerically robust, and easy to implement because, like Marching Cubes, it generates tetrahedra from a small set of precomputed stencils. Our angle bounds are guaranteed by a computer-assisted proof. Our second contribution is a mesh improvement method that uses optimization-based smoothing, topological transformations, and vertex insertions and deletions to achieve extremely high quality tetrahedra.

Joint work with Francois Labelle and Bryan Klingner.

Trees are one of the most fundamental structures in computing. They are used in almost every aspect of modeling and representation for explicit computations. Standard representations of trees using pointers are quite wasteful of space, and could account for the dominant space cost in applications such as storing a suffix tree. For example, a standard representation of a binary tree on n nodes uses 2n pointers or 2n log n bits. This is a factor of log n more than the minimum number of bits necessary, as there are less than 4^n distinct binary trees on n nodes. Also, this only supports finding the left/right child of a node efficiently.

In this talk, starting with a brief introduction to succinct or highly space efficient data structures, I will present some tree representations that take only 2n + o(n) bits and support various useful queries efficiently. I will also briefly mention some applications where these can be used.

We show how to compute Delaunay triangulations of utterly huge, well-distributed point sets in 2D and 3D on an ordinary computer by exploiting the natural spatial coherence in a stream of points. We achieve large performance gains by introducing spatial finalization into point streams: we partition space into regions, and augment a stream of input points with finalization tags that indicate when a point is the last in its region. By extending an incremental algorithm for Delaunay triangulation to use finalization tags and produce streaming mesh output, we compute a billion-triangle terrain representation for the Neuse River system from 11.2 GB of LIDAR data in 48 minutes using only 70 MB of memory on a laptop with two hard drives. This is a factor of twelve faster than the previous fastest out-of-core Delaunay triangulation software.

This talk discusses combinatorial group testing, which began from work on detecting diseases in blood samples taken from GIs in WWII. Given a parameter d, which provides an upper bound on the number of defective (e.g., diseased) samples, the main objective of such problems is to design algorithms that identify all the defective samples without explicitly testing all n samples. This classic problem has a number of interesting modern applications, and we provide several new efficient algorithms that can be applied in these new contexts. In particular, modern applications we will discuss include problems in DNA sequencing, wireless broadcasting, and network security.

Biography:

Prof. Goodrich received his B.A. in Mathematics and Computer Science from Calvin College in 1983 and his PhD in Computer Sciences from Purdue University in 1987. He is a Chancellor's Professor at the University of California, Irvine, where he has been a faculty member in the Department of Computer Science since 2001. Dr. Goodrich's research is directed at the design of high performance algorithms and data structures for solving large-scale problems motivated from information assurance and security, the Internet, information visualization, and geometric computing.

In a hedonic game a set of players N splits up in coalitions and the payoff for a player is only dependent on the members of the coalition of the player. A hedonic game is additively separable if a utility function v_p exists for each player p so that the payoff for p for belonging to coalition C is sum_{i \in C} v_p(i). A partition of N is Nash stable if no player would be strictly better of by moving to another coalition in the partition.

Ballester has shown that the problem of deciding whether a Nash stable partition exists in a hedonic game with arbitrary preferences is NP-complete. We show that the problem remains NP-complete even when restricting to additively separable hedonic games.

Bogomolnaia and Jackson have shown that a Nash stable partition exists in every additively separable hedonic game with symmetric preferences. We show that the problem of deciding whether a non-trivial Nash stable partition exists in an additively separable hedonic game with non-negative and symmetric preferences is NP-complete.

This presentation will also be given at the conference CiE 2007 - a conference on computation and logic in the real world.

Tetris, Sudoku and Minesweeper are some of the well known puzzles that have been studied from a complexity theoretic point of view. While these are inventions of the late 20th century, there is one puzzle that has been around for more than 600 years(!) and has never had its complexity investigated. Until now, that is...

This presentation will also be given at the Fourth International Conference on Fun with Algorithms (FUN 2007).

Some recent results on high dimensional search are presented. We define d- dimensional search is high when d approaches log n, for n = number of points or objects to be searched. For example, the l-level k-range is reported to have orthogonal range time Q(n, d) = O(log n + A) for A = number of points or ob- jects in range. Our results show that the l-level k-range requires Q(n, d, l) = O((2l)^(d-1)(log N +A)) time for orthogonal range search, making it impractical for range search, even for relatively low d. For d-dimensional point data, the venerable k-d tree is found to be competitive with the Patricia trie adapted for d-dimensional search. For large d, we present a technique based on the pyramid technique that we call the PKD-tree. The PKD-tree shows good performance in testing with uni- formly distributed random data points ( n <= 1.000.000 and d <= 100) and with 68.040 32-d data points from a colour histogram dataset.

We adapted the pyramid technique to implement a k-nearest neighbour algo- rithm called the decreasing radius or DR pyramid technique. Results indicate that for uniformly distributed random data, the DR pyramid and BBD-tree algorithms are comparable. For d>= 16, we discovered that a naive (brute force) search was faster than six other algorithms for k-nearest neighbour search. The talk presents some observations about why efficient search in high dimensions is challenging.

We propose a simple variant of kd-tree, called rank-based kd-tree, for sets of points in R^d. We show that a rank-based kd-tree, like an ordinary kd-tree, supports range search queries in O(n^1-1/d+k) time, where k is the output size. The main advantage of rank-based kd-tree is that they can be efficiently kinetized: the KDS processes O(n²) events in the worst case and each event can be handled in O(log n) time, and each point is involved in O(1) certificates.

We investigate the complexity of finding Nash equilibria in which the strategy of each player is uniform on its support set. We show that, even for a restricted class of win-lose bimatrix games, deciding the existence of such uniform equilibria is an NP-complete problem. Our proof exploits a connection between uniform equilibria and some appropriately defined graph structures associated to the game.

This talk will present some of my recent and current work on non-cooperative games in large networks. The first part will treat a class of games for cost sharing between selfish users. The games encompass a variety of optimization settings, e.g. for covering, facility location, and Steiner tree creation problems. Pure Nash equilibria in these games do not necessarily exist. If they exist, they can be very inefficient and hard to compute. However, all games considered admit cheap and stable approximate Nash equilibria. They can be computed in polynomial time, and the talk will present algorithmic procedures based on primal-dual approximation algorithms and problem-specific combinatorial approaches. In addition, special cases of the games are presented, which admit pure Nash equilibria that are efficient and/or computable in polynomial time. The second part of the talk will give some ideas of my current work in progress on Stackelberg network pricing and average-case aspects of selfish routing.

We present improved and simplified IO-efficient algorithms for map overlay and point location in planar subdivisions (also called planar maps). These are two important problems in computational geometry with application in Geographic Information Systems (GIS). We analyze the IO-complexity of our algorithms on the popular external-memory IO-model. We show that the IO-complexity scales well with both the parameters of the memory hierarchy and the geometric complexity of the input. Our algorithms and data structures improve on the previous best known bounds for general subdivisions both in the number of IOs and storage space; they are significantly simpler and easier to implement.

Specifically, we show how to preprocess a so-called low-density subdivision with n edges in O(sort(n)) IOs into a compressed linear quadtree such that one can:

(i) compute the overlay of two such preprocessed subdivisions in O(scan(n)) IOs, where n is the total number of edges in the two subdivisions, and

(ii) answer a single point location query in O(\log_B n) IOs and k batched point location queries in O(scan(n) + sort(k)) IOs.

For the special case where the subdivision is a fat triangulation, we show how to obtain the same bounds with an ordinary (uncompressed) quadtree, and we show how to make the structure fully dynamic using O(\log_B n) IOs per update.

We study the complexity of restricted versions of st-connectivity, which is the standard complete problem for NL. Grid graphs are a useful tool in this regard, since

* reachability on grid graphs is logspace-equivalent to reachability in general planar digraphs, and

* reachability on certain classes of grid graphs gives natural examples of problems that are hard for NC1 under AC0 reductions but are not known to be hard for DLOG; they thus give insight into the structure of DLOG.

In addition to explicating the structure of DLOG, another of our goals is to expand the class of digraphs for which connectivity can be solved in logspace, by building on the work of Jakoby et al. who showed that reachability in series-parallel digraphs is solvable in DLOG.

Our main results are:

* Reachability on planar graphs (and grid graphs) is logspace-equivalent to reachability on graphs of genus 1. Nothing is known about genus 2 and higher, except for the trivial NL upper bound.

* Reachability on "layered" grid graphs can be done in UL (a subclass of NL).

* Many of the natural restrictions on grid-graph reachability (GGR) are equivalent under AC0 reductions (for instance, undirected GGR, out-degree-one GGR, and indegree-one-outdegree-one GGR are all equivalent). These problems are all equivalent to the problem of determining if a completed game position in HEX is a winning position, as well as to the problem of reachability in mazes studied by Blum and Kozen. This gives rise to a hierarchy of complexity classes between NC1 and L.

* Series-Parallel digraphs are a special case of single-source-single-sink planar dags; reachability for such graphs logspace reduces to single-source-single-sink acyclic grid graphs. We show that reachability on such grid graphs AC0 reduces to undirected GGR.

* We build on this to show that reachability for single-source multiple-sink planar dags is solvable in DLOG.

This is joint work with David A. Mix Barrington, Tanmoy Chakraborty, Samir Datta, and Sambuddha Roy.

We present exact algorithms to compute the chromatic number and the chromatic polynomial in time and space within a polynomial factor of 2ⁿ. The result is based on a novel inclusion-exclusion characterisation of set covering, simple and completely self- contained. A brief historical overview is included, including Birkhoff's 1912 definition of the chromatic polynomial.

Apart from graph colouring, the algorithm works for a family of related problems such as Domatic Number, Bin Packing, and other graph partitioning problems. We also present polynomial space variants.

Joint work with Andreas Björklund.

This talk is devoted to the design and analysis of combinatorial algorithms for solving one-player versions of several prominent infinite duration games pertinent to automated verification of computerized systems.

We present the first two strongly polynomial algorithms for solving one-player discounted payoff games, running in time O(mn2) and O(mn2 log m), where the latter algorithm allows edges to have different discounting factors. As applications, we are able to improve the best previously known strongly subexponential algorithms for solving two-player discounted payoff games and the ergodic partitioning problem for mean payoff games.

In this talk we will review some low-dimension geometric approximation algorithms that work by extracting a small subset of the input, and performing the computation on this small subset. Such subsets, referred to as coresets, had emerged as a powerful tool, and we will survey some of the resulting algorithms and future challenges associated with coresets.

Suppose we are given a set of objects that cover a region and a duration associated with each object. Viewing the objects as jobs, can we schedule their beginning times to maximize the length of time that the original region remains covered? This is the Sensor Cover Problem. For example, suppose you wish to monitor activity along a fence (interval) by sensors placed at various fixed locations. Each sensor has a range (also an interval) and limited battery life. The problem is then to schedule when to turn on the sensors so that the fence is fully monitored for as long as possible.

This one-dimensional problem involves intervals on the real line. Associating a duration to each yields a set of rectangles in space and time, each specified by a pair of fixed horizontal endpoints and a height. The objective is to assign a bottom position to each rectangle (by moving them up or down) so as to maximize the height at which the spanning interval is fully covered. We call this one-dimensional problem Restricted Strip Covering. If we replace the covering constraint by a packing constraint (rectangles may not overlap, and the goal is to minimize the highest point covered), then the problem becomes identical to Dynamic Storage Allocation, a well-studied scheduling problem, which is in turn a restricted case of the well known problem Strip Packing.

We present a collection of algorithms for Restricted Strip Covering. We show that the problem is NP-hard and present an O(logloglog n)- approximation algorithm. We also present better approximation or exact algorithms for some special cases, including when all intervals have equal width. For the general Sensor Cover Problem, we distinguish between cases in which elements have uniform or variable durations. The results depend on the structure of the region to be covered: We give a polynomial-time, exact algorithm for the uniform-duration case of Restricted Strip Covering but prove that the uniform-duration case for higher-dimensional regions is NP-hard. We give some more specific results for two-dimensional regions.

This is joint work with Alon Efrat, Shaili Jain, Suresh Venkatasubramanian, and Ke Yi.

The problem of finding dominators in a directed graph calls for computing, for each vertex v, the set of vertices that are visited in all paths from r to v, where r is a distinguished root vertex of the graph. This is a fundamental problem in graph algorithms with several applications, including program optimization, circuit testing, constraint programming and theoretical biology.

In the first part of this talk we present an experimental study of practical algorithms for finding dominators. These include a simple, iterative algorithm proposed by Cooper et al., the well-known algorithm of Lengauer and Tarjan, and a new, hybrid algorithm that we introduce.

In the second part we present the first linear-time algorithm for computing dominators on a pointer-machine. Previous linear-time algorithms, given by Alstrup et al. and Buchsbaum et al., were implementable only on the random-access model of computation. Although our linear-time algorithm settles the complexity of finding dominators, some variants of this problem remain open. We conclude with a discussion of such problems and their motivating applications.

This is joint work with R. E. Tarjan. The experimental part was performed in collaboration with R. F. Werneck, S. Triantafyllis and D. I. August.

For a 0-1 matrix C = c_ij_, column j is said to _cover_ row i if c_ij_ =1. A _cover_ is a subset of columns covering all rows. Unweighted SET COVER (USC) is the problem of finding a cover containing as few columns as possible. An seemingly innocent brain teaser was published in a Danish journal in 2003. Not much reflection is needed to realize that the solution of a highly structured instance C of USC will answer the question posed. The instance C or rather, the _family_ of instances C(n) is a square matrix of size 3^n, n = 1,2, ... . Provided that C(1) is known, the fractal-like structure of the matrices allows for C(n) to be constructed recursively for any value of n. Let r(n) be the number of columns in an optimal solution to C(n). Some preliminary investigations have enabled us to determine r(n), n=1,2,3,4, and to show that r(5) must be either 12 or 13. 12 or 13? Unfortunately LP-based bounds take us nowhere in this case since the optimum is flat as a pancake. It offers some consolation though that experiments with CPLEX were not too encouraging either. For n=5, C(5) is a matrix of size 243x243. Nothing was returned after 24 hours CPU time. Eventually, upon an investment of 72 hours CPU time, CPLEX managed to come up with r(5)=12. The original problem asks for r(12), that is, an optimal solution to a square matrix of size 531,441. After a week the originator of the problem, using an invalid argument, announced his own answer, r(12)=512, and cashed the award. We have so far shown that r(12) is bounded to belong to the in- terval [210, 377]. We also need to conclude that no brute force approach such as further experiments with CPLEX is likely to work whereas paper and pencil _may_ suffice in providing the final result.

--------

The text above is a slightly extended version of the abstract used when a few preliminary results for n < 6 were presented at meetings in 2004 and 2005. State-of-affairs as per today: the transition from _patches_ to _tiles_ in the investigation of feasible solutions has reduced the dimension by a factor of 3^4. In terms of tiles a full-scale verification of the opti- mal solution found for n=6 (729x729) occupies only a single A4 sheet. Moreover, n=7 has lead to new insight into an important notion called _compatibility_, to the corresponding _STU forms_, to the concept of _even/odd keys_, and to the discovery of _matching cliques_. February 2006: paper and pencil have been supplemented by a puzzle with pieces of transparent strips showing three or six letters each. The puzzle is readily solvable within a few minutes, for example, on an over- head projector. It is believed that the patterns thereby generated repre- sent a significant step ahead towards the general "n -> n+1" (recursive) solution procedure aimed for. Being born optimists we also conjecture that the lower bounds are _tight_ for all values of n. If true, r(12) = 210. Disregarding the distant and, for our purpose, largely irrelevant fam- iliarity with the "Coupon Collector Problem", nothing useful whatsoever has been found in the literature that we are familiar with. Thus, if the nut can be fully cracked, the visible result will presumably be an indeed self-contained paper as reflected by the total absence of references.

The talk will discuss cache-oblivious structures for 2- and 3-sided planar orthogonal range searching. The structure for 2-sided range searching is the first cache-oblivious structure for this problem that achieves the optimal query bound and linear space. Using this structure, a new structure for 3-sided range searching can be obtaind that matches the query and space bounds of the best previous structure, but is simpler. At the expense of a slightly worse query bound, the 2-sided structure can be made semi-dynamic, supporting insertions in the same amortized bound as cache-oblivious B-trees.

A total dominating set S in a graph G=(V(G),E(G)) is a set of vertices such that every vertex in G is adjacent to a vertex in S. In other words \forall x \in V(G) \exists s \in S: xs \in E(G).

The minimum size of a total dominating set, gamma_t(G), in a graph, G, is well studied. We will talk about the following new bounds, where delta(G) is the minimum degree of G and Delta(G) is the maximum degree in G:

(a):

gamma_t(G) <= 3/7|V(G)|, when delta(G) >= 4.

(b):

gamma_t(G) <= |V(G)| - (2|E(G)|)/(Delta(G)+2\sqrt{Delta(G)}), when Delta(G) >= 4.

In fact we can improve (a) above, if we exclude one specific graph, G₁₄, on 14 vertices. In this case we can obtain the following bound.

(c):

gamma_t(G) <= (3/7-1/5943)|V(G)|, when delta(G) >= 4 and G contains no connected components isomorphic to G₁₄.

(b) above generalises a result by M. Henning. Using this result we can show that the following holds, where alpha'(G) denotes the size of a maximum matching in a graph G.

(d):

If G is a k-regular graph with k >= 3, then gamma_t(G) <= alpha'(G).

There are however examples of (non-regular) graphs, G, with arbitrary high minimum degree where gamma_t(G) > alpha'(G). So (d) cannot be extended in this way. We also mention new (best possible) lower bounds on the size of a maximum matching in connected regular graphs. These results can be used to shorten the proofs of (d).

We will also mention other related results and open problems. Many of the results mentioned in this talk have been obtained by observing that a total dominating set in a graph G is also a transversal in the hypergraph H(G) on the same vertex-set as G and with edge-set { N(x) | x \in V(G) }. This allows us to use hypergraph techniques in order to obtain the above results.

(partially joint work with S. Thomasse and M. Henning)

Given a bipartite graph G=(X \dotcup D, E\subseteq Xx D), an X-perfect matching is a matching in G that covers every node in X. In this talk we study the following generalisation of the X-perfect matching problem, which has applications in constraint programming: Given a bipartite graph as above and a collection F \subseteq 2^X of k subsets of X, find a subset M\subseteq E of the edges such that for each C\in F, the edge set M\cap (Cx D) is a C-perfect matching in G (or report that no such set exists). We show that the decision problem is NP-complete and that the corresponding optimisation problem is in APX when k=O(1) and even APX-complete already for k=2. On the positive side, we show that a 2/(k+1)-approximation can be found in 2^k poly(k,|X\cup D|) time.

This is joint work with Khaled Elbassioni, Martin Kutz and Meena Mahajan, to be presented at ISAAC 2005. The paper can be downloaded from http://www.brics.dk/ irit/pub/SM.ps

Motivated by an application in computational topology, we consider a novel variant of the problem of efficiently maintaining dynamic rooted trees. This variant allows an operation that merges two tree paths. In contrast to the standard problem, in which only one tree arc at a time changes, a single merge operation can change many arcs. In spite of this, we develop a data structure that supports merges and all other standard tree operations in O(log² n) amortized time on an n-node forest. For the special case that occurs in the motivating application, in which arbitrary arc deletions are not allowed, we give a data structure with an O(log n) amortized time bound per operation, which is asymptotically optimal. The analysis of both algorithms is not straightforward and requires ideas not previously used in the study of dynamic trees. We explore the design space of algorithms for the problem and also consider lower bounds for it.

A solution to an optimisation problem can be viewed as a collection of decisions (e.g., "node v1 is in the independent set, node v2 is not in the independent set, etc..."). An optimal solution O is then a collection of choices that maximizes the profit or minimizes the cost of the solution.

Let O[C] be the optimal solution that can be obtained if we are forced to make the choice C. In several applications in constraint programming, it is useful to compute (or approximate) the values O[C1],...,O[Ck] where C1,...,Ck is a set of mutually exclusive choices. The main question in sub-optimality is: Will it help us to compute O first?

The focus of the talk will not be on applications. I will discuss sub-optimality is a computational- theoretic concept and try to interest you in further research into it. I will partially answer the "main question" by showing that the answer is "sometimes".

The talk is based on joint work with Russell Bent and Pascal van Hentenryck, which is to be presented at CP 2005 (http://www.iiia.csic.es/cp2005/).

The talk discusses three algorithmic problems (a weight balancing problem; a data management problem; a sequencing problem vaguely related to dartboards), some of their combinatorial properties, and one unifying theorem.

Given a digraph G=(V,E) with a set U of vertices marked ``interesting,'' we want to find a smaller digraph H = (V',E') with V' \supseteq U in such a way that the reachabilities amongst those interesting vertices in G and H are the same. So with respect to the reachability relations within U, the digraph H is a substitute for G. This problem has applications, for example, in network design and also as an important building block in the context of dynamic reachability.

The complexity of finding such a reachability substitute of minimum size has so far been open. We prove that the problem is NP-hard. Our main contribution is about planar digraphs: While almost all digraphs do not allow reachability substitutes smaller than Omega(|U|²/log |U|), every planar digraph has a reachability substitute of size O(|U| log² |U|). Our proof is constructive and offers an efficient algorithm to find a reachability substitute of this size.

The talk describes joint work with Irit Katriel and Martin Skutella.

I will describe an efficient algorithm to compute the shortest path homotopic to a given path on a given combinatorial surface. The algorithm has two phases. In the preprocessing phase, we construct a set of simple cycles, each as short as possible in its homotopy class, that decompose the surface into topological disks each with eight edges. This decomposition allows us to approximate the given irregular metric with a standard hyperbolic metric, defined by a regular tiling of the hyperbolic plane by right-angled octagons. In the query phase, we exploit this hyperbolic structure and techniques in combinatorial group theory to reduce the shortest-path search to a small subset of the universal cover. Dijkstra's algorithm then finds the true shortest path quickly.

This is joint work in progress with Eric Colin de Verdiere.

In this talk I will present efficient indexing techniques for answering range and nearest neighbor queries, which are essential operations for most practical applications dealing with very large spatio-temporal datasets. Generating and storing huge amounts of data is a typical characteristic of spatio-temporal applications, given the highly dynamic nature of such environments. Therefore, indexing spatio-temporal data for answering queries efficiently has become a very important issue. In this direction, I will present specialized algorithms for approximating and indexing spatio-temporal objects cost-effectively. These algorithms introduce a space-utilization vs. index-quality tradeoff that enables index performance tuning according to application requirements. The presented solutions are based on dynamic programming and greedy techniques for producing high quality object approximations. The main characteristic of our solutions is that they decrease the amount of empty volume introduced in the index, while keeping the complexity of the approximations low.

Consider a dynamic file where new keys are inserted with a probability that obeys an unknown smooth distribution mu and existing keys are deleted at random. We show that the probabilistic analyses of the known dynamic interpolation search data structures, for storing this file, retain their correctness only when the produced elements are pairwise distinct, otherwise they fail. Moreover, we present a new dynamic interpolation search data structure whose probabilistic analysis is always valid and which exhibits similar expected asymptotic performance as the aforementioned structures.

Quicksort was first introduced in 1961 by Hoare. Many variants have been developed, the best of which are among the fastest generic sorting algorithms available, as testified by the choice of Quicksort as the default sorting algorithm in most programming libraries. Some sorting algorithms are adaptive, i.e. they have a complexity analysis which is better for inputs which are nearly sorted, according to some specified measure of presortedness. Quicksort is not among these, as it uses Omega(n log n) comparisons even when the input is already sorted. However, in this paper we demonstrate empirically that the actual running time of Quicksort is adaptive with respect to the presortedness measure Inv. Differences close to a factor of two are observed between instances with low and high Inv value. We then show that for the randomized version of Quicksort, the number of element swaps performed is provably adaptive with respect to the measure Inv. More precisely, we prove that randomized Quicksort performs expected O(n(1+log (1+Inv/n))) element swaps, where Inv denotes the number of inversions in the input sequence. This result provides a theoretical explanation for the observed behavior, and gives new insights on the behavior of the Quicksort algorithm. We also give some empirical results on the adaptive behavior of Heapsort and Mergesort.

Joint work with Gerth S. Brodal and Rolf Fagerberg.

Even though a large number of external memory graph algorithms have been developed in recent years, very little effort went into investigating the practical merits of theoretically developed I/O-efficient algorithms. In this talk, I will discuss the implementation and comparative study undertaken by us, between Munagala-Ranade's BFS algorithm and Mehlhorn-Meyer's randomized BFS algorithm on various graph classes. I will also describe the STXXL design framework for implementing external memory algorithms, with a particular reference to the concept of pipelining.

This talk considers integer sorting on a RAM. We show that adaptive sorting of a sequence with qn inversions is asymptotically equivalent to multisorting groups of at most q keys, and a total of n keys. Using the recent O(n \sqrt(loglog n)) expected time sorting of Han and Thorup on each set, we immediately get an adaptive expected sorting time of O(n \sqrt(loglog q)). Interestingly, for any positive constant e, we show that multisorting and adaptive inversion sorting can be performed in linear time if q<= 2^(log n)^(1-e). We also show how to asymptotically improve the running time of any traditional sorting algorithm on a class of inputs much broader than those with few inversions.

Joint work with Rasmus Pagh and Mikkel Thorup

Given a set A of n bit strings, we would like to encode the elements of A with about log |A|, rather than n bits. Information theoretically we can achieve this bound. We examine the question of if this bound can still be achieved when we further demand that every element x \in A can be printed from its description in polynomial time, assuming the decompression function is given oracle access to the set A.

It is not too hard to come up with sets A for which this is not possible for polynomial time decompression functions, even randomized ones. We show however, that when the decompression function is allowed to be nondeterministic and randomized we can achieve the information theoretic bound up to a factor of O(log³ n). The proof of this result uses hardness vs. randomness tradeoffs based on the Nisan-Wigderson pseudorandom generator.

Time permitting we will show an application of this result to prove a weak form of polynomial time symmetry of information. This reveals an interesting connection between polynomial time symmetry of information and a long-standing open problem in complexity theory.

Are many-one reductions different from Turing reductions? The talk concerns this question.

Informally, with Turing reductions an instance of a problem can be solved by asking polynomially many queries about the instances of another problem. Many-one reductions require an instance of one problem to be mapped into an instance of the other in a decision preserving manner. Since a many-one reduction is also a Turing reduction, a problem that is NP-complete under many-one reductions is also NP-complete under Turing reductions. On the other hand, it appears that many-one reductions are much more restrictive than Turing reductions and a fundamental question is whether these completeness notions are indeed different. If P=NP then the answer is negative. Thus we need complexity-theoretic assumptions to answer this question. A major open problem on this topic is to show that these completeness notions differ using any reasonable average-case hardness assumption about problems in NP.

In this talk we separate Turing NP-completeness from many-one NP-completeness using an (admittedly weak) average-case assumption which we call partial-biimmunity assumption. A problem L is partially biimmune if any deterministic machine that decides L correctly, takes at least 2^{n^epsilon} time on all but 2^{logl n} instances of length n for some l. Under the assumption we construct a problem that is Turing NP-complete but not many-one NP-complete.

This is a joint work with John Hitchcock and A. Pavan, and will be presented in the 19th IEEE Conference on Computational Complexity, 2004 (CCC 04).

In this talk we present two novel generic schemes for approximation algorithms for optimization NP-hard graph problems constrained to partial k-trees. Our first scheme yields deterministic polynomial-time algorithms achieving typically an approximation factor of k/log^(1-epsilon) n for k = polylog (n).

The second scheme yields randomized polynomial-time algorithms achieving an approximation factor of k/log n, where k is superlogarithmic. Both our approximation methods lead to the best known approximation guarantees for some basic optimization problems. In particular, we obtain best known polynomial-time approximation guarantees for the classical maximum independent set problem in partial trees.

Joint work with Artur Czumaj (New Jersey Institute of Technology) and Andrzej Lingas (Lund University).

In this talk we are concerned with algorithms for k-colouring and for finding the chromatic number of a graph. For that use, we will look at algorithms for enumerating all maximal independent sets of a graph.

There exists a tight upper bound on the number of maximal independent sets in a graphs and algorithms for enumerating them all in time proportional to their number. Such algorithms have been used for both 3- and 4-colouring and for finding the chromatic number of a graph.

To improve this, we look at maximal independent sets of size k. We give tight upper bounds for all k and algorithms for enumerating them all in time within a polynomial factor of these bounds. Using these algorithms, we can improve on the running time for 4-, 5- and 6-colouring, as well as the time for finding the chromatic number. To do the last, we also give algorithms for finding all maximal k-colourable subgraphs.

We present recent results on the hardness of approximating the longest path and the longest cycle in graphs and directed graphs. This includes an algorithm for Longest Path in graphs with performance guarantee n loglog n/log² n, and a hardness result for digraphs: that there is no polynomial time algorithm that always finds a path of length Omega(log^2+epsilon n) (under reasonable complexity assumptions).

References:

* Finding a path of superlogarithmic length. Andreas Björklund and Thore Husfeldt. SIAM J. Computing. Vol. 32 (2003), No. 6, pp. 1395-1402.

* Approximating Longest Directed Path. Andreas Björklund, Thore Husfeldt, Sanjeev Khanna. ECCC TR03-032

We present a new algorithm for answering short path queries in planar graphs. For any fixed constant k and a given unweighted planar graph G=(V,E) one can build in O(|V|) time a data structure, which allows to check in O(1) time whether two given vertices are distant by at most k in G and if so a shortest path between them is returned. This significantly improves the previous result of D. Eppstein where after a linear preprocessing the queries are answered in O(log |V|) time. Our approach can be applied to compute the girth of a planar graph and a corresponding shortest cycle in O(|V|) time provided that the constant bound on the girth is known.

Our results can be easily generalized to other wide classes of graphs - for instance we can take graphs embeddable in a surface of bounded genus or graphs of bounded tree-width.

Joint work with Lukasz Kowalik. Presented at the Proc. 35th Symp. Theory of Computing (STOC), 2003.

We present new algorithms for finding short cycles (of length at most 6) in planar graphs. Although there is an O(n) algorithm for finding any fixed subgraph H in a given n-vertex planar graph, the multiplication constant hidden in ``O'' notation (which depends on the size of H) is so high, that it rather cannot be used in practice even when |V(H)| = 4. Our approach gives faster ``practical algorithms'' which are additionally much easier to implement.

As a side-effect of our approach we show that the maximum number of k-cycles in n-vertex planar graph is Theta(n^{\lfloor k/2 \rfloor}).

Work presented at the Proc. 28th Workshop Graph-Theoretic Concepts in Comp. Sci. (WG 2003).

In this talk, we present lower bounds for permuting and sorting in the cache-oblivious model. We prove that

(1) I/O optimal cache-oblivious comparison based sorting is not possible without a tall cache assumption

(2) there does not exist an I/O optimal cache-oblivious algorithm for permuting, not even in the presence of a tall cache assumption.

These results demonstrate a separation between the I/O-model and the cache-oblivious model. In more detail, the result for sorting shows the existence of an inherent trade-off in the cache-oblivious model between the strength of the tall cache assumption and the overhead for the case M >> B, and shows that Funnelsort and recursive binary mergesort are both optimal algorithms in the sense that they attain this trade-off.

This is joint work with Gerth Stølting Brodal, to be presented at STOC'03.

Many algorithms and data structures employing hashing have been analyzed under the uniform hashing assumption, i.e., the assumption that hash functions behave like truly random functions. Starting with the discovery of universal hash functions, many researchers have studied to what extent this theoretical ideal can be realized by hash functions that do not take up too much space and can be evaluated quickly. In this paper we present an almost ideal solution to this problem: A hash function that, on any set of n inputs, behaves like a truly random function with high probability, can be evaluated in constant time on a RAM, and can be stored in O(n) words, which is optimal. For many hashing schemes this is the first hash function that makes their uniform hashing analysis come true, with high probability, without incurring overhead in time or space.

One would like to take advantage of the fact that real-world access sequences often have patterns that intelligently designed systems can make use of, even though the exact distribution of operations is seldom not known in advance. Still, there is often reason to believe that the stream of queries and updates arriving at such systems is far from random. We will present theory of what we call input-sensitive behavior of query-based data structures. The objective of input-sensitive data structures and input-sensitive analysis is to create data structures and algorithms whose runtime is expressed as a function of the patterns that occur in the input, with the goal of speeding up the performance, relative to input sequences that exhibit no favorable patters, or are completely random.

We will present an overview of input sensitive structures and techniques. We begin by reviewing the splay tree structure of Sleator and Tarjan and paring heaps of Fredman, Sedgewick, Sleator and Tarjan. These classic self adjusting structures structures are able to run several (but not all) desirable classes of operation patterns quickly. We will then present the results of our recent work to develop new input sensitive structures for dictionaries, heaps and geometric problems.

This is joint work with Erik Demaine and Stefan Langerman.

As the memory systems of modern computers become more complex, it is increasingly important to design algorithms that are sensitive to the structure of memory. One of the essential features of modern memory systems is that they consist of a hierarchy of several levels of cache, main memory, and disk. While traditional theoretical computational models assumed a ``flat'' memory with uniform access time, the access times of different levels of memory can vary by several orders of magnitude in current machines. To amortize the large access time of memory levels far away from the processor, memory systems often transfer data between memory levels in large blocks. Thus it is becoming increasingly important to obtain high data locality in memory access patterns.

While a lot of research has been done in two-level (external) memory models, relatively little work has been done in models for multilevel hierarchies, mainly because of the many parameters in such models. Recently however, a promising new line of research has aimed at developing memory-hierarchy-sensitive algorithms that avoid any memory-specific parameterization whatsoever. These "cache-oblivious" algorithms work optimally on a multilevel memory hierarchy if they work optimally on a two-level hierarchy. In this talk, we describe cache-oblivious dynamic data structures for multidimensional range searching.

Joint work with Pankaj Agarwal, Andrew Danner, and Bryan Holland-Minkley to be presented at 19th ACM Symposium on Computational Geometry.

We present a new algorithm for the all-pairs shortest path problem on real-weighted graphs. Our algorithm improves on Dijkstra's classical shortest path algorithm - the previous best - and runs in time O(mn + n² loglog n), where m and n are the number of edges and vertices, respectively.

The new ingredients in our algorithm are (1) a method for representing the dependencies between shortest paths emanating from nearby vertices and (2) a method for computing exact distances from approximate distances.

In this talk we study trade-offs between the update time and the query time for comparison based external memory dictionaries.

We will present two lower bound trade-offs between the I/O complexity of member queries and insertions: If N>M insertions perform at most delta*N/B I/Os, then (1) there exists a query requiring N/(M*(M/B)^O(delta)) I/Os, and (2) there exists a query requiring Omega(log(N/M)/log(delta log² N) I/Os when delta is O(B/log³ N) and N is at least M².

For both lower bounds data structures exist which give matching upper bounds for a wide range of parameters, thereby showing the lower bounds to be tight within these ranges.

This is joint work with Rolf Fagerberg. Talk given at SODA'03.

The cache oblivious model of computation is a two-level memory model with the assumption that the parameters of the model are unknown to the algorithms. A consequence of this assumption is that an algorithm efficient in the cache oblivious model is automatically efficient in a multi-level memory model. Arge et al. recently presented the first optimal cache oblivious priority queue, and demonstrated the importance of this result by providing the first cache oblivious algorithms for graph problems. Their structure uses cache oblivious sorting and selection as subroutines. In this paper, we devise an alternative optimal cache oblivious priority queue based only on binary merging. We also show that our structure can be made adaptive to different usage profiles.

In this talk we consider the computational power of cylindrical circuits. We show that every polynomial size constant depth circuit with at most one layer of MOD gates and at most two layers of AND/OR-gates above the MOD gates can be simulated by a polynomial size constant width cylindrical circuits. On the other hand, we show that every polynomial size constant width cylindrical circuit can be simulated in ACC⁰.

This is joint work with Kristoffer Arnsfelt Hansen and V Vinay.

In a connected simple graph G the following random experiment is carried out: each node chooses one of its neighbors uniformly at random. We say a rendezvous occurs if there are adjacent nodes u and v such that u chooses v and v chooses u. Metivier et al. (2000) formulated the conjecture that the probability for a rendezvous to occur in G is at least as large as the probability of a rendezvous if the same experiment is carried out in the complete graph on the same number of nodes. In this talk we show that the conjecture is true.

An error-correcting code is said to be locally decodable if a randomized algorithm can recover any single bit of the message by reading only a small number of symbols of a possibly corrupted encoding of the message.

Katz and Trevisan (STOC 2000, pp. 80-86) showed that any such code

C: {0,1}ⁿ -> Sigma^m

with a decoding algorithm that makes at most q probes must satisfy

m = Omega((n/log |Sigma|)^q/(q-1)).

They assumed that the decoding algorithm was non-adaptive, and left open the question of proving similar bounds when the decoder is adaptive.

We show lower bounds without assuming that the decoder is non-adaptive. Our argument is based on an anlysis a sampling algorithm by estimating the variance.

(Joint work with Amit Deshpande, Rahul Jain, T Kavitha and Satyanaryana V Lokam, this work was presented at Complexity 2002)

We consider space efficient data structures for the off-line string matching problem: given a text string and a pattern string, to find an occurrence (or all occurrences) of the pattern in the text, after preprocessing the text string. We look at space efficient implementations of the well known data structure, suffix tree. We also look at some compressed suffix array representations and their use in space efficient suffix trees.

Joint work with Venkatesh Raman and J. Ian Munro.

Motivated by the fact that competitive analysis yields too pessimistic results when applied to the paging problem, there has been considerable research interest in refining competitive analysis and in developing alternative models for studying online paging. The goal is to devise models in which theoretical results capture phenomena observed in practice.

In the talk a new, simple model for studying paging with locality of reference is presented. The model is closely related to Denning's working set concept and directly reflects the amount of locality that request sequences exhibit.

We use the page fault rate to evaluate the quality of paging algorithms, which is the performance measure used in practice. In our model LRU is optimal whereas FIFO and deterministic marking strategies are not optimal in general.

This is joint work with Susanne Albers, University of Freiburg, and Oliver Giel, University of Dortmund.

It is well known that Santa Claus distributes gifts to billions of children around December 24. What may be less well known is the way in which he organizes the presents in order to be able to quickly get to the right present for a given child. (Sorting in advance is just too much work... And besides, people move around all the time.)

To formalize Santa's problem, let n be the number of children, and u the number of possible children's identifiers. In the good old days when Santa was able to memorize O(log n + loglog u) bits, he used a scheme where he just had to read a single bit to find the right present. Now that his memory is worse, he has been in need of something else. Luckily, a recent scheme using expander graphs now allows him to find the right present by just looking at O(loglog u) bits, expected, without having to memorize anything. Thus, once again, christmas appears to be saved!

The talk will describe Santa's old and new gift-finding schems.

We propose a version of cache oblivious search trees which is simpler than the previous proposal of Bender, Demaine and Farach-Colton and has the same complexity bounds. In particular, our data structure avoids the use of weight balanced B-trees, and can be implemented as just a single array of data elements, without the use of pointers. The structure also improves space utilization.

For storing n elements, our proposal uses (1+epsilon)n times the element size of memory, and performs searches in worst case O(log_B n) memory transfers, updates in amortized O((log² n)/(epsilon B)) memory transfers, and range queries in worst case O(log_B n + k/B) memory transfers, where k is the size of the output.

The basic idea of our data structure is to maintain a dynamic binary tree of height log n+O(1) using existing methods, embed this tree in a static binary tree, which in turn is embedded in an array in a cache oblivious fashion, using the van Emde Boas layout of Prokop.

We also investigate the practicality of cache obliviousness in the area of search trees, by providing an empirical comparison of different methods for laying out a search tree in memory.

This is joint work with Gerth Stølting Brodal and Rolf Fagerberg. The talk is to be given at SODA'02.

An undirected graph G is said to be d-distinguishable if there is a d-coloring of its vertex set V(G) such that no nontrivial automorphism of G preserves the coloring. In other words, the graph has a d-coloring that breaks all its symmetries, making the colored graph rigid. The distinguishing number of a graph G is the minimum d for which it is d-distinguishable.

In this talk we will discuss the complexity of computing the distingui- shing number of a graph. In particular, we will describe efficient algorithms for computing the distinguishing numbers of trees and planar graphs, and discuss an approach for bounded degree graphs.

In this talk we present the first provably I/O-efficient dynamic data structure for point location in a general planar subdivision. Our structure uses O(N/B) disk blocks to store a subdivision of size N, where B is the disk block size. Queries can be answered in O(log_B² N) I/Os in the worst-case, and insertions and deletions can be performed in O(log²_B N) and O(log_B N) I/Os amortized, respectively. Previously, an I/O-efficient dynamic point location structure was only known for monotone subdivisions.

Joint work with Jan Vahrenhold presented at SoCG 2000.

We study the fundamental problem of sorting n integers of w bits on a unit-cost RAM with word size w, and in particular consider the time-space trade-off (product of time and space in bits) for this problem. For comparison-based algorithms, the time-space complexity is known to be Theta(n²). A result of Beame shows that the lower bound also holds for non-comparison-based algorithms, but no algorithm has met this for time below the comparison-based Omega(nlg n) lower bound.

We show that if sorting within some time bound T' is possible, then time T \in O(T'+nlg^* n) can be achieved with high probability using space S \in O(n²/T+w), which is optimal. Given a deterministic priority queue using amortized time t(n) per operation and space n^O(1), we provide a deterministic algorithm sorting in time T \in O(n(t(n) + lg^* n)) with S \in O(n²/T+w). Both results require that w<= n^1-Omega(1). Using existing priority queues and sorting algorithms, this implies that we can deterministically sort time-space optimally in time Theta(T) for T>= n(lglg n)², and with high probability for T>= nlglg n.

Our results imply that recent lower bounds for deciding element distinctness in o(nlg n) time are nearly tight.

Joint work with Jakob Pagter.

Consider the problem of compactly representing a subset of size n of a universe of size m, so that membership queries can be answered efficiently.

A bitvector is one solution to this problem. It uses m bits for representing the set (which is a quite a lot if m is big, compared to n). On the other hand, one can answer a membership query by inspecting only a single bit of the data structure.

A hash table is another solution. It uses only O(nlog m) bits for representing the set (which is optimal if n is not too close to m). On the other hand, to answer a membership query one must inspect O(log m) bits of the data structure.

In this talk we present a solution combining the desirable aspects of both the above solutions: We devise a representation using only O(nlog m) bits to represent any set, so that any membership query can be answered by inspecting only a single bit of the data structure.

This is joint work with Harry Buhrman, Jaikumar Radhadkrishnan and Srinivasan Venkatesh, previously presented at STOC'00.

In this paper we study the algorithmic problem of constructing rooted evolutionary trees in the so called experiment model. This model was first presented by Kannan, Lawler, and Warnow. We present new techni- ques of efficiently merging and updating partial evolutionary trees in this model.

We show that two partial evolutionary trees for disjoint sets of species can be merged using experiments in time O(dn), where n is the total number of species in the resulting evolutionary tree and d is its maximum degree. We prove our upper time bound on merging evolutionary trees to be asymptotically optimal.

We show also that after O(nlog n)-time preprocessing, a partial evolutionary tree can be maintained under a sequence of m species insertions or deletions in time O(dm log (n+m)). By applying our algorithm for merging evolutionary trees, or alternatively, our algo- rithm for updating evolutionary trees, we obtain an O(dnlog n)- time bound on the problem of constructing an evolutionary tree for n species and maximum degree d from experiments. The classic O(nlog n)-time bound on sorting in the comparison-based model can be seen as a very special case of this upper bound.

We present optimal data structure for static range reporting in one dimension. For a set of n integers each of w bits, we construct a data structure that requires space O(n) words on a unit cost RAM with word size w. Given a query interval the data structure supports the reporting of all elements from the set contained within the interval in optimal time O(k), where k is the number of elements reported. An extension of the data structure supports approximate range counting queries in constant time. The data structures can be constructed in expected time O(n\sqrt{w}).

Joint work with Stephen Alstrup and Theis Rauhe.

The dynamic maintenance of the convex hull of a set of points in the plane is one of the most important problems in computational geometry. We present a data structure supporting point insertions in amortized O(log n·logloglog n) time, point deletions in amortized O(log n·loglog n) time, and various queries about the convex hull in optimal O(log n) worst-case time. The data structure requires O(n) space. Applications of the new dynamic convex hull data structure are improved deterministic algorithms for the k-level problem and the red-blue segment intersection problem where all red and all blue segments are connected.

Joint work with Gerth Stølting Brodal.

In this talk we will define external memory (or I/O) models which also capture space complexity and develop a general technique for deriving I/O-space trade-offs in these models from internal memory model time-space trade-offs. Using this technique we show strong I/O-space product lower bounds for Sorting.

This talk is based on joint work with Lars Arge (Duke University) to be presented at SWAT'20000.

We consider dictionaries over the universe U={0,1}^w on a unit-cost RAM with word size w and a standard instruction set, and present a linear space deterministic dictionary accommodating membership queries in time (log log n)^O(1) and updates in amortized time (log n)^O(1), where n is the size of the set stored. Previous deterministic dictionaries either had query time (log n)^Omega(1) or update time 2^{omega(\sqrt{log n})} in the worst case.

To be presented at SWAT 2000.

This talk will give a history and philosophy of diagonalization as a tool to prove lower bounds in computational complexity. We will give several examples and discuss four possible approaches to using diagonalization to separate log-space from nondeterministic polynomial-time.

It has been known for a long time now that the problem of counting the number of perfect matchings in a planar graph is in NC. This result is based on the notion of a pfaffian orientation of a graph. Recently, Galluccio and Loebl generalised this result to the case of graphs of bounded genus. However, it is not known if the corresponding search problem, that of finding one perfect matching in a planar graph, is in NC. This situation is intriguing as it seems to contradict our intuition that search should be easier than counting.

For the case of planar bipartite graphs, Miller and Naor showed that a perfect matching can indeed be found using an NC algorithm. Meena Mahajan and Kasturi R. Varadarajan present a very different NC-algorithm for this problem. Unlike the Miller-Naor algorithm, their approach directly uses the fact that counting is in NC, and it also generalizes to the problem of finding a perfect matching in a bipartite bounded genus graph. It also rekindles the hope for an NC-algorithm to find a perfect matching in a non-bipartite planar graph.

(To appear in STOC 2000)

In the L-phylogeny problem, one wishes to construct an evolutionary tree for a set of species represented by characters, in which each state of each character induces no more than L connected components. We consider the fixed-topology version of this problem for fixed-topologies of arbitrary degree. This version of the problem is known to be NP-complete when L is at least 3, even for degree-3 trees in which no state labels more than L+1 leaves (and therefore there is a trivial L + 1 phylogeny). We give a 2-approximation algorithm for all L for arbitrary input topologies. Dynamic programming techniques, which are typically used in fixed-topology problems, cannot be applied to L-phylogeny problems. Our 2-approximation algorithm is the first application of linear programming to approximation algorithms for phylogeny problems. We extend our results to a related problem in which characters are polymorphic.

This was joint work with Leslie Ann Goldberg and Cynthia A. Phillips.

We prove that AM (and hence Graph Nonisomorphism) is in NP if for some epsilon>0, some language in NE intersect coNE requires nondeterministic circuits of size 2^{epsilon n}. This improves recent results of Arvind and Kobler and of Klivans and Van Melkebeek who proved the same conclusion, but under stronger hardness assumptions.

The previous results on derandomizing AM were based on pseudorandom generators. In contrast, our approach is based on a strengthening of Andreev, Clementi and Rolim's hitting set approach to derandomization. As a spin-off, we show that this approach is strong enough to give an easy (if the existence of explicit dispersers can be assumed known) proof of the following implication: For some epsilon>0, if there is a language in E which requires nondeterministic circuits of size 2^{epsilon n}, then P=BPP. This differs from Impagliazzo and Wigderson's theorem ``only'' by replacing deterministic circuits with nondeterministic ones.

Technically, our strengthening of the Andreev-Clementi-Rolim approach is in the form of the combination of this approach with the use of a certain error correcting code, based on the low degree extension. It is well known that the low degree extension plays an important role in the construction of pseudorandom generators, and so, it is not surprising that it would play an role here also. Interestingly however, the coding theoretic property of the low degree extension that is used in the construction of pseudorandom generators is local decodability. In our application, local decodability plays no role. We use a simpler property which will be explained in the talk.

This is joint work with N.V. Vinodchandran, to appear on FOCS'99.

Let G be a fixed collection of digraphs. Given a digraph H, a G-packing of H is a collection of vertex disjoint subgraphs of H, each isomorphic to a member of G. A G-packing, P, is maximum if the number of vertices belonging to some member of P is maximum, over all G-packings. The analogous problem for undirected graphs has been extensively studied in the literature. We will concentrate on the cases when G is a family of paths. We will show that G-packing is NP-complete when (essentially) G is not one of the families { P₁ }, or { P₁, P₂ }.

When G = { P₁ }, the G-packing problem is simply the matching problem. When G={P₁, P₂ }, the directed paths of length one and two, we will present a collection of augmenting configurations such that a packing is maximum if and only if it contains no augmenting configuration. We will also present a min-max condition which yields a concise certificate for maximality of packings. These results imply a polynomial time algorithm for finding a maximum { P₁, P₂ }-packings in arbitrary digraphs.

The p-dispersion-sum problem is the problem of locating p facilities at some of n predefined locations, such that the overall distance sum is maximized. The problem has applications in telecommunication (where it is desirable to locate radio transmitters as far away from each other in order to minimize interference problems), and in location of shops/service-stations (where the mutual competition should be minimized).

Simple upper bounds for the problem are presented, and it is shown how these bounds can be tightened through Lagrangian relaxation. A branch-and-bound algorithm is finally described which in each iteration finds upper bounds in O(n) time. Finally some computational results with randomly generated and geometrical problems are presented.

The related p-dispersion problem is the problem of locating p facilities such that the minimum distance between two facilities is as large as possible. Formulations and simple upper bounds will be presented, and it will be discussed whether a similar framework as for the p-dispersion sum problem can be used to tighten bounds.

A tandem repeat (or square) is a string aa, where a is a non-empty string. We present an O(|S|)-time algorithm that operates on the suffix tree T(S) for a string S, finding and marking the endpoint in T(S) of every tandem repeat that occurs in S. This decorated suffix tree implicitly represents all occurrences of tandem repeats in S, and can be used to efficiently solve many questions concerning tandem repeats and tandem arrays in S. This improves and generalizes several prior efforts to efficiently capture large subsets of tandem repeats.

Joint work with Dan Gusfield, UC Davis.

We define a game called ``Quantum Twenty Questions'' where Player 1 chooses a secret state s from a large set of possible states S and supplies copies of s, on request, to Player 2. It is the task of Player 2, with full knowledge of S, to design a sequence of ``quantum questions'', i.e. measurements, to determine the secret s with high probability in as few requests to Player 1 as possible. Sometimes the geometry of S, coupled with the idea of eliminating candidate states, suggests a natural measurement. If S is the set of states associated with the discrete logarithm problem or factoring, then it turns out that the natural measurement is the Fourier transform. This talk will present these ideas and show how viewing current quantum algorithms from the point of view of a search game may assist in the quest for new algorithms.

A combinatorial characteristic of a Boolean function is its sensitivity. Informally, the sensitivity of a Boolean function is the maximum number of input variables, such that changing the value of just one variable at a time, changes the value of the function as well. I will talk about an (almost tight) upper bound on the sensitivity of a multiple-output Boolean function in terms of the sensitivity of its coordinates and the size of the range of the function.

We apply this theorem to establish a tight tradeoff between randomness and the number of rounds in private computation. A private protocol to compute a Boolean function allows a number of players, each possessing a single input bit, to compute the value of the function on their combined input, in a way that no single player learns any ``unnecessary'' information (in particular, the inputs of the other players). We give lower bounds on the number of rounds of such protocols in terms of the sensitivity of the function being computed, and the amount of randomness used in the computation.

A fundamental operation on representations of graphs is the adjacency query: given two nodes u and v, tell whether or not the edge (u,v) is present in the graph.

Two standard textbook representations of graphs are adjacency matrices and adjacency lists. The first answers adjacency queries in O(1) time, but uses n² bits space, which is superlinear for sparse graphs. The latter uses linear space, but adjacency queries now involve searching adjacency lists, which may have length n.

The challenge therefore is to find representations which are both fast and compact - i.e. support adjacency queries in O(1) time and use linear size.

Quite a number of such representations have been developed, but so far only for static graphs. In this talk, we study the dynamic version of the problem and give a representation which also allows insertions and deletions of edges in O(1) and O(log n) amortized time per update, respectively.

The representation is a slight variation of the adjacency list representation, equipped with a very simple, almost canonical update algorithm. Our proof of complexity proceeds by first showing that this simple algorithm inherits the time complexity of any algorithm for maintaining such adjacency lists, and then giving a non-constructive proof of existence of an algorithm with the stated complexity.

Our representation works for graphs of bounded arboricity, which is a large class of sparse graphs containing e.g. the planar graphs and graphs of bounded treewidth.

This is joint work with Gerth Stølting Brodal.

Several recent algorithms for solving the all pairs shortest paths (APSP) problem in graphs will be discussed. All these algorithms use fast algorithms for algebraic matrix multiplication. Among the algorithms is an O(n^2.575) time algorithm for solving the APSP problem in unweighted directed graphs, and an O(n^omega) time algorithm for solving the problem in unweighted undirected graphs, where omega<2.376 is the exponent of algebraic matrix multiplication.

Graphs have been used for electric network theory since Kirchhoff, and for statics since Cremona and Maxwell (middle of the 19th century). However, quite a few problems of electrical engineering and in statics seem to be intractable using graphs only. Such problems include

• give a combinatorial necessary and sufficient condition for the unique solvability of electric networks composed of linear multiports,
• determine the order of complexity of such networks,
• decide whether linear multiports can be interconnected,
• give a combinatorial necessary and sufficient condition for the rigidity of generic k-dimensional bar-and-joint frameworks,
• determine a minimum system of joints whose location, if fixed, uniquely determines the location of every other joint.

Some features of these questions involve graph theory (like the interconnection structure of the network or the framework), some others require linear algebra (since linear multiports are given by matrices and infinitesimal rigidity is also expressed by a system of linear equations).

Matroid theory, a branch of combinatorics, can be considered as a common generalization of, among others, graph theory and linear algebra. Hence, it turned out to be an excellent tool for considering the above problems (and other, related ones, like questions in electric network synthesis, on the rigidity of some highly regular frameworks like grids, on the reconstruction of polyhedra from projected images for pattern recognition etc).

The present talk requires no preliminaries from any branch of engineering.

The problem of imperfect apparatus is an important open question in quantum cryptography. The main difficulty is that it is not enough to have an apparatus which is in principle secure in accordance with known experiments. For example, it may be well accepted that in laboratory a given kind of source should emit more than 1 photon less than one percent of the time (ignoring pulses with no photon detected). For cryptography, we also need to be able to prove this kind of assertions while making as little assumptions as possible. We propose an approach based on violations of Bell inequalities which allow us to test an apparatus with very little assumptions, even on the testing apparatus itself. The connection with the Self-Testing gates of Wim van Dam, Michele Mosca, Frederic Magniez and Miklos Santha will be briefly discussed.

We isolate and generalize a technique implicit in many quantum algorithms, including Shor's algorithms for factoring and discrete log. In particular, we show that the distribution sampled after a Fourier transform over Z_p can be efficiently approximated by transforming over Z_q for any q in a large range. Our result places no restrictions on the superposition to be transformed, generalizing previous applications. In addition, our proof easily generalizes to multi-dimensional transforms for any constant number of dimensions.

Joint work with Lisa Hales.

We study the k-round two-party communication complexity of pointer chasing problem for fixed k. Damm, Jukna and Sgall showed an upper bound of O(nlg^(k-1)n) for this problem. We prove a matching lower bound for this problem improving the lower bound of Omega(n) by Nisan and Wigderson. This yields a corresponding improvement in the hierarchy results for bounded-depth monotone circuits.

We also consider the bit version of the problem and show upper and lower bounds. This implies that there is an abrupt jump in complexity from linear to superlinear when the number of rounds is reduced below k/2.

The competitive ratio as a measure for the quality of on-line algorithms, has been criticized for giving bounds that are unrealistically pessimistic and for not being able to distinguish between algorithms with very different behavior in practical applications.

A new measure, the accommodating function, for the quality of on-line algorithms is presented. The accommodating function is a generalization of both the competitive ratio and the accommodating ratio. As an example, we investigate the measure for a variant of bin-packing in which the goal is to maximize the number of objects put in n bins. In this talk, focus will be on a natural algorithm, First-Fit, which is almost worst possible in the competitive sense, but when analyzed in this setting, it turns out to be strictly better than some other algorithms.

Joint work with Kim S. Larsen and Joan Boyar.

Poissonization is a general technique for simplifying average case analyses of algorithms. It has been used for hashing, digital tree, leader election, and probabilistic counting algorithms. It is applied in situations where the algorithm performs some action (for example, a hash table insertion) at discrete intervals. The poissonization analysis assumes instead that the actions are Poisson distributed. Special properties of the Poisson distribution then permit a simpler analysis. For example, in hashing algorithms, insertion at distinct locations become independent. From the analysis of the poissonized algorithm one obtains a solution to the original problem by a variety of analytic techiques. This is called depoissonization. We will give a general survey of poissonization and depoissonization and a number of examples where it is applied.

The j-State General Markov Model of evolution (due to Steel) is a stochastic model concerned with the evolution of strings over an alphabet of size j. In particular, the Two-State General Markov Model of evolution generalises a well-known model of evolution called the Cavender-Farris-Neyman model. I'll start my talk by describing these models.

Previously Farach and Kannan showed how to PAC-learn Markov Evolutionary Trees in the Cavender-Farris-Neyman model provided that the target tree satisfies the additional restriction that all pairs of leaves have a sufficiently high probability of being the same. I will talk about how to remove this restriction (and the restriction to the Cavender-Farris-Neyman model) and thereby obtain the first polynomial-time PAC-learning algorithm (in the sense of Kearns et al.) for the general class of Two-State Markov Evolu- tionary Trees.

This was joint research with Leslie Ann Goldberg and Paul Goldberg.

Finding space efficient simulations of space bounded randomized algorithms is addressed. The best known simulation to date is based on the ingenious construction of a pseudorandom generator by Noam Nisan.

In this talk, we will concentrate upon Nisan's pseudorandom generator and prove its usefulness towards derandomizing space bounded algorithms. Also, some approaches towards getting improved simulations will be discussed.

Binary search of a sorted list is the standard method for determining the membership of an input value in a set of numbers or for finding its predecessor: the largest element in the set smaller than the input value. The information theory lower bound says that binary search is the fastest comparison based algorithm for these problems. Binary search is also optimal on the standard RAM model.

I will present a survey of various deterministic searching algorithms, some recent and some less recent, that are better than binary search. Corresponding lower bounds will also be mentioned.

Let V(D) be the vertex set of a digraph D and let A(D) be the arc set of D. A complete digraph of order n is a digraph where the arcs xy and yx both lie in A(D), for all x,y \in V(D) (x != y) and |V(D)|=n. A Hamilton cycle in a digraph D is a directed cycle containing all vertices exactly once.

One of the best-known problems in combinatorial optimization and algorithmics is the Travelling Salesman Problem (TSP). The most general form of the TSP is the directed version, where we want to find a minimum cost Hamiltonian cycle in a complete digraph, where costs are assigned to the arcs. It is well-known that the TSP is NP-complete, which implies that we are unlikely to find a polynomial algorithm, which can solve this problem exactly.

Let D_n be a complete digraph of order n, with costs assigned to its arcs, and let H be any Hamilton cycle in D_n. The domination number of H is defined to be the number of distinct Hamilton cycles in D_n, which have cost greater than or equal to the cost of H.

We state several conjectures and results culminating in the fact that we in polynomial time can find a Hamilton cycle of any D_n, such that the domination number of our solution is at least (n-1)!/2. As there are only (n-1)! distinct Hamilton cycles in D, clearly (n-1)!/2 is half of all Hamilton cycles. Our result proves a conjecture by Glover and Punnen (1997). The above algorithm is not practical, but we will also state a practical algorithm, with domination number (n-2)!, which was the algorithm with the highest domination number up to a couple of weeks ago!

The TSP is a special case of the more difficult Quadratic Assignment Problem (QAP). Our polynomial method also works for the QAP, but we can only prove the (n-2)! bound when n is a prime. For general n we can prove the bound Omega((n!)/(kⁿ)) for any k>1. k>1. This is however the first method for the QAP, which gives exponential domination numbers (for polynomial algorithms). Contrary to the TSP, there didn't exist any algorithms for the QAP with high domination number, prior to the above algorithm.

The graph isomorphism problem asks whether two given graphs are isomorphic, i.e., whether there exists a one-to-one and onto mapping between their vertices that preserves adjacency. Graph isomorphism has both practical and theoretical relevance. Certain questions about chemical compounds translate into the isomorphism problem of two graphs. From a complexity theoretic point of view graph isomorphism forms one of the few candidate NP-problems believed to be neither in P nor NP-complete.

One of the reasons why complexity theorists believe graph isomorphism not to be NP-complete is the structure of its complement: The graph nonisomorphism problem seems easier than the complement of any known NP-complete language. A crucial open question in this context is whether, for any pair of nonisomorphic graphs, one can give a short proof that there exists no isomorphism between them. The shortest known proofs for graph nonisomorphism are of exponential size. We will provide the first strong evidence that one can do better: Under a widely accepted complexity theoretic conjecture (namely that the polynomial-time hierarchy does not collapse) we will exhibit subexponential size proofs. Under a stronger assumption we will be able to reduce the proof size to polynomial.

We obtain our results by derandomizing a randomized proof system for graph nonisomorphism known as an Arthur-Merlin game. Our derandomi- zation technique works for any Arthur-Merlin game, as well as for several other randomized processes. In particular, it applies to constructing universal traversal sequences, nonadaptively finding witnesses for NP-problems, learning Boolean circuits, and building rigid matrices.

This is joint work with Adam Klivans (MIT).

The constrained maximum flow problem is to send the maximum possible flow from a source node to a sink node in a directed network subject to the constraint that the total cost of the flow does not exceed a given budget. We present the first strongly polynomial time algorithm for the problem. Our algorithm is based on Megiddo's elegant parametric search technique and uses O(mlog n(loglog nlog n + log m)) minimum cost flow computations where n and m denote the number of nodes and arcs, respectively, in the network.

Joint work with Sven O. Krumke, Konrad-Zuse-Zentrum für Informationstechnik Berlin, Department Optimization.

The behaviour of three methods for constructing a binary heap is studied. The methods considered are the original one proposed by Williams [1964] based on repeated bottom-up heapifications, the improvement by Floyd [1964] based on repeatead top-down heapifications, and a level-wise construction method proposed, e.g., by Fadel et al. [1998]. Both the worst-case number of instructions and that of cache misses is analysed. It is well-known that Floyd's method has the best instruction count. However, our analysis shows that, under reasonable assumptions, the repeated bottom-up heapification method and the level-wise construction method both have the optimal O(n/B) cache behaviour, whereas the repeated top-down construction method, as programmed by Floyd, is not optimal but it causes Omega((n log₂ B)/B) cache misses, where n denotes the size of the heap to be constructed and B the length of the cache lines. On the other hand, a re-engineered version of Floyd's program reaches also the optimal O(n/B) cache miss bound, and makes it the fastest of the programs considred in practice.

Joint work with Jesper Bojesen and Maz Spork.

A classical and surprising result of Barrington states that the computational power of polynomial size, constant width branching programs is exactly NC¹. The same result holds for constant width contact schemes and constant width circuits.

In this talk, we shall consider polynomial size, constant width planar branching programs, contact schemes and (AND,OR)-circuits and show that their computational power is exactly AC⁰, i.e., their power is identical to polynomial size, constant depth, unbounded fan-in circuits. In contrast to Barrington's classical result, the proof for circuits is very different from the proofs for branching programs and contact schemes.

As a somewhat surprising application of these pure complexity results, we shall derive a dynamic connectivity algorithm for constant width grid graphs with a time complexity of O(loglog n) per operation.

This talk is based on joint work with Dave Barrington, Chi-Jen Lu, and Sven Skyum, appearing on STACS'98 and Computational Complexity '99.

In the talk I will present a very recent result: Any sequence psi_n of tautologies which expresses the validity of a fixed combinatorial principle either is ``easy'' i.e. have polynomial size tree-like resolution refutations or is ``difficult'' i.e require exponential size tree-like resolution refutations. I will as show that the same complexity gap apply to the Davis-Putnam procedure.

The first part of the talk will give some background in propositional logic and in the resolution method.

The talk will be kept on an elementary level.

The binary search tree is a fundamental data structure in computer science, due to its ability to maintain a set in sorted order during insertions and deletions. Almost any operation on a binary search tree takes time proportional to its height. The trivial lower bound on the height is \ceil{log (n+1)}, and as is wellknown, numerous rebalancing schemes exist for keeping the height within a multiplicative constant of this bound, while using O(log n) time per update.

A natural question to ask is: exactly how small a height can we maintain? Presumably, this depends on how much rebalancing we are willing to do for each update - for instance, with linear time per update, the trivial lower bound is clearly attainable by rebuilding the tree after each update. The question thus becomes: what is the best possible height maintainable with a given amount of rebalancing per update? Or, phrased another way, what is the intrinsic rebalancing complexity of binary search trees, as a function of the height maintained?

In this talk, we answer the question with respect to amortized complexity by proving new upper and lower bounds on the height of binary search trees. Specifically, we show that the height \ceil{log (n+1) + 1/f(n)} is not maintainable with o(f(n)) amortized rebalancing work per update, and we give a new rebalancing scheme achieving that height with O(f(n)) amortized rebalancing work per update. Here, f is any function (monotonically increasing and not too pathological) between Theta(1) and Theta(n).

We briefly mention some corresponding (but not completely matching) results for worst case complexity, and also consider the semi-dynamic case (i.e. insertions only).

In this talk I introduce a dynamic problem called the Marked Ancestor Problem. Consider a rooted tree whose nodes can be in two states: marked or unmarked. The marked ancestor problem is to maintain a data structure with the following operations: mark(v) marks node v; unmark(v) removes mark from node v; exists(v) returns true iff there is a marked node on the path from v to the root.

It turns out that this problem underlies several important dynamic problems and data structures such as priority search trees, static tree union-find, and problems from computational geometry. The talk will focus on a proof of an Omega(log n/loglog n) lower bound for the worst-case time per operation on the unit cost RAM, and provide examples on how this result implies similar bounds of the above dynamic problems.

Joint work with Thore Husfeldt and Stephen Alstrup.

Consider a scenario with two mutually distrusting parties, who want to reach some common goal, such as flip a common coin, or jointly compute some function on inputs that must be kept as private as possible. A classical example is Yao's ``millionaire's problem'': two millionaires want to find out who is richer without revealing to each other how many milllions they each own. It is well-known that if only error free, digital communication is available, then no non-trivial task of this type can be implemented without unproven computational assumptions.

But if a noisy channel is available, where each bit sent is flipped with a certain probability, it has been known for long that any two-party computation can be done provided, however, that the error probability is known exactly. Unfortunately this is not a very realistic assumption: in practice one can usually only assume that the error level is in some interval [a..b], where 0\le a, b<1/2.

We show that if b>= 2a(1-a), then no non-trivial two-party computation is possible. On the other hand, as soon as b<2a(1-a), so-called bit commitments can be implemented with unconditional security, implying that zero-knowledge proofs for all IP problems can be given in this model. If b<F(a), where F is a complicated function, a<F(a)<2a(1-a), then a stronger primitive called Oblivious Transfer can be built, implying that any joint two-party computation can be done with unconditional security. Finally, if quantum communication AND a noisy channel is available, Oblivious Transfer is possible alrady if b<2a(1-a).

Joint work with Joe Kilian and Louis Salvail.

We study the fundamental problem of sorting in a sequential model of computation and in particular consider the time-space trade-off (product of time and space) for this problem.

Beame has shown a lower bound of Omega(n²) for this product leaving a gap of a logarithmic factor up to the previously best known upper bound of O(n²log n) due to Frederickson. Since then, no progress has been made towards tightening this gap.

Our main contribution is a comparison based sorting algorithm which closes the gap by meeting the lower bound of Beame. The time-space product O(n²) upper bound holds for the full range of space bounds between log n and n/log n. Hence in this range our algorithm is optimal for comparison based models as well as for the very powerful general models considered by Beame.

The algorithm to be presented improves on the algorithm presented at the ALCOM-seminar in February. However, the techniques used are somewhat different.

Joint work with Theis Rauhe.

In the well-solved edge-connectivity augmentation problem we must find a minimum cardinality set F of edges to add to a given undirected graph to make it k-edge-connected. We solve the generalization where every edge of F must go between two different sets of a given partition of the vertex set. Our solution to the general partition-constrained problem gives a min-max formula for |F| and a strongly polynomial algorithm that solves our problem in time O(n(m+nlog n)log n). Here n and m denote the number of vertices and distinct edges of the given graph respectively. This bound is identical to the best-known time bound for the problem without partition constraints due to Nagamochi and Ibaraki. Our algorithm is based on the splitting off technique of Lovász, like several known efficient algorithms for the unconstrained problem. However unlike previous splitting algorithms, when k is odd our algorithm must handle ``obstacles'' that prevent all edges from being split off.

A special case of this partition-constrained problem, previously unsolved, is increasing the edge-connectivity of a bipartite graph to k while preserving bipartiteness. Based on this special case we present an application of our results in statics. In this application a square grid framework is given and the goal is to find a smallest set of diagonal rods whose addition results in a framework which remains rigid even if (at most) k-1 diagonal rods fail.

This talk is based on the following two papers:

• J. Bang-Jensen, H.N. Gabow, T. Jordán and Z. Szigeti, Edge-connectivity augmentation with partition constraints, Proc. 9th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA), 1998, 306-315.
• H.N. Gabow, T. Jordán, How to make a square grid framework with cables rigid, to appear in Proc. 10th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA), 1999.

The problem of storing a subset S of a finite universe U, is fundamental within data structures. A bit vector is an extremely simple solution to the problem, and offers constant lookup time, but in many cases the space usage of |U| bits is far too much.

During the 70s researchers worked on space-efficient representations with O(1) lookup time, and achieved O(|S|) words* for some ratios |U|/|S|. The breakthrough came in the early 80s, when Fredman, Komlos and Szemeredi achieved O(|S|) words for any |U| and |S|, using simple hashing techniques.

More recently, it has been studied how close one can get to the information theoretical lower bound (where the coding has just enough bits for each subset of a given size to be representable). It turns out that it is possible to get surprisingly close to this bound, while maintaining O(1) lookup time.

In this talk a review of the history of the problem will be given, and the new results will be discussed.

* Elements of U are assumed to fit into one machine word

We present a simple extensible theoretical framework for devising polynomial time approximation schemes for problems represented using natural syntactic (algebraic) specifications endowed with natural graph theoretic restrictions on input instances. Direct application of our technique yields polynomial time approximation schemes for all the problems studied in [LT80,NC88,KM96,Ba83,DTS93,HM+94a,HM+94] as well as the first known approximation schemes for a number of additional combinatorial problems. One notable aspect our work is that it provides insights into the structure of the syntactic specifications and the corresponding algorithms considered in [KM96,HM+94]. The understanding allows us to extend the class of syntactic specifications for which generic approximation schemes can be developed. The results can be shown to be tight in many cases, i.e. natural extensions of the specifications can be shown to yield non-approximable problems.

As specific examples of applicability of our techniques we get that

• Problems that can be naturally represented using this syntactic specification include maximization versions of constraint satisfaction problems in [Sc78,FV93,JCG97,KM96,HM+94] and graph problems considered in [Ba83,NC88,LT80,DTS93,HM+94a].
• Simple extensions of our ideas can be applied to devise PTAS for the problem of maximizing (or minimizing) a linear objective function subject to linear packing (or covering) constraints when restricted to planar instances. Problems that can be represented using this specification include natural NP-hard packing and covering problems including those studied in [Sr95,PSW97].

Joint work with Harry B. Hunt III, Madhav V. Marathe, and Richard E. Stearns.

Recently, Impagliazzo and Wigderson proved the following ``Gap'' theorem: Unless BPP is all of EXP, it can be simulated in deterministic subexponential time ``on the average''. This is the first general derandomization result using a uniform, non-cryptographic assumption. We present their proof which only uses 1990-1991 technology.

Andrzej Czygrinow will give a talk about the Regularity Lemma, a famous deep result by Szemeredi, and its algorithmic applications. The talk is divided into two parts. The first will be a tutorial-like introduction to the Lemma and its significance, and will end up with an overview of results from Andrzej's thesis. This part will be accessible to the widest audience. The second part, after the break, will be a more technical discussion of the thesis presenting algorithmic applications and extensions of the Lemma.

We present two techniques for proving lower bounds on dynamic algebraic problems. The first technique is essentially a counting argument that suffices to give a tight bound on matrix vector multiplication (and an almost tight bound bound on convolution) in a wide range of models. The second technique is both more involved and has a shorter range of application. It uses a recent lower bound result on the size of depth-2 super-concentrators by Radhakrishnan and Tashma, and it leads to nontight yet nontrivial bounds for the Discrete Fourier Transform. (Joint work with Peter Bro Miltersen and Johan P. Hansen)

Dynamic algebraic problems have been considered in a rather large body of literature by Fredman and collaborators and in a more general setting by Reif and Tate. We give an overview of the area. A substantial part of the discussion will concern the models of computation used for showing upper and lower bounds, as this turns out to be a somewhat subtle and potentially confusing point.

We show that maximal matchings can be computed deterministically in polylogarithmically many rounds in the synchronous, message-passing model of computation. This is one of the very few cases known of a non-trivial graph structure (and the only ``classical'' one) which can be computed distributively in polylogarithmic time without recourse to randomization.

We consider Random Access Machines with additional instructions such as bitwise boolean operations and integer multiplication and division. We study reducibility among different instruction sets. As it turns out, all interesting models of register computation are captured by RAMs with purely arithmetical instruction sets. In particular, we study the complexity class PTIME(+,*,<) which seems to be intimately related to numerical computation and of which absolutely nothing is known. An example of a problem in this class is MANDELBROT: Given a complex number x + iy, does (x,y) belong to the Mandelbrot set?

Watson-Crick complementarity is one of the very central components of DNA computing, the other central component being the massive parallelism of DNA strands. While the latter component drastically reduces time complexity, the former component is the essential cause behind the (Turing) universality of many models of DNA computing presented so far. The lecture makes this cause explicit, after giving a brief introduction to DNA computing. Also some case studies, discussions about universality in terms of specific models, are presented. Time permitting, another aspect of complementarity, the operational one, will be discussed in terms with Lindenmayer systems. Most of the lecture assumes no previous knowledge about the subject matter.

End-to-end communication is the problem of sending a sequence of data items from a sender to a receiver, even if the network through which they communicate is unreliable. New and existing algorithms will be surveyed and some lower bounds will be presented.

In recent work, Cramer, Damgaard and Maurer have shown that monotone span programs can be used to implement fault tolerant multiparty computations. The possible faulty subsets of the n players can be described in a natural way by a monotone Boolean function on n inputs bits. The protocols by CDM are efficient in scenarios where the function describing the possible faulty subsets has a poly-size monotone span program.

The performance of earlier protocols was connected in a similar way to the monotone formula complexity of these functions. We show that the well known separation between monotone span programs and monotone formulae carries over to the types of functions occurring here, which implies that monotone span programs give rise to strictly more efficient verifiable secret sharing protocols that what was known earlier.

If the separation we show could be proved to hold, also if the span program is required to have a special ``multiplication property'', this would imply that span programs can make general multiparty computations more efficient. This is open at the time of writing.

In this talk I will consider time-space tradeoff for sorting and some related problems. I will present an Omega(n²) lower bound for sorting, by way of a general lower bound technique for time-space tradeoffs (This is a result of Beame). After this I will present an algorithm improving the best known upper bound from O(n²lg n) to O((nlg^* n)²) (This part is joint work with Theis Rauhe).

After brief review of the current state of affairs in the quest for the fast winning strategies for Ramsey games (and ultimately better lower bounds on Ramsey numbers), a new winning strategy for the Ramsey Graph Game will be presented. I'll also state several open problems in the area.

The problem of text indexing is a classic area in data structures. Given a text T preprocess it such that occurrences of different patterns can be reported efficiently.

This talk is going to address the problem in a dynamic setting: A family F of text and/or patterns S₁,...,S_k are modified dynamically by various update operations such as insertions/deletions of characters, or concatenation/splitting of strings in the family.

In the talk I will present a data structure which supports such updates in polylogarithmic time together with a fast search operation; for any string S_i in family F, all occurrences of S_i in F can be reported in polylogartimic time per occurrence. The data structure is an extension of a data structure by Mehlhorn, Sundar and Uhrig which supports the above update operations, but only supports a query which tests for equality of a pair of strings in the family.

In the first part of the talk I will sketch the data structure by Mehlhorn, Sundar and Uhrig, and in the second part I describe the extension enabling the fast search.

In this talk we introduce a general model for the evolutionary distance between two coding DNA sequences in which a nucleotide event is penalized by the change it induces on the DNA as well as the change it induces on the encoded protein. We will furthermore describe a quadratic time algorithm for computing the optimal alignment in a biological reasonable restriction of the general model.

The Precoloring Extension problem is a decision problem whose input is an undirected graph G, an unchangeable coloring (``precoloring'') on a subset W of the vertex set, and a natural number k called color bound. The question is whether the coloring of W can be extended to a proper k-coloring of the entire G, i.e., to an assignment with at most k colors such that no monochromatic vertex pair is adjacent. In a more general setting, for list colorings one has to select colors from sets of admissible colors specified for each vertex. These problems are practically motivated and lead to many interesting theoretical questions, too. In the talk we mostly deal with problems and results related to algorithmic complexity.

Starting from the short summary of the basic definitions and facts, the goal of the talk is to present the solutions of some graph optimization problems which deal with certain connectivity properties of a graph (or digraph) and to illustrate the application of some useful techniques of this area. The plan is to discuss basic splitting off theorems (due to Lovasz, Mader and others) and their extensions, constructions of 2k-edge-connected graphs and k-edge-connected digraphs, Edmonds' branching theorem, optimal connectivity augmentation of graphs, etc.

We present zero-knowledge proofs and arguments for arithmetic circuits over finite prime fields, namely given a circuit, show in zero-knowledge that inputs can be selected leading to a given output. For a field GF(q), where q is an n-bit prime, a circuit of size O(n), and error probability 2^-n, our protocols require communication of O(n²) bits. This is the same worst-cast complexity as the trivial (non zero-knowledge) interactive proof where the prover just reveals the input values. If the circuit involves n multiplications, the best previously known methods would in general require communication of Omega(n³log n) bits.

Variations of the technique behind these protocols lead to other interesting applications. For the Boolean Circuit Satisfiability problem we give zero-knowledge proofs and arguments for a circuit of size n and error probability 2^-n in which there is an interactive preprocessing phase requiring communication of O(n²) bits. In this phase, the statement to be proved later need not be known. Later the prover can non-interactively prove any circuit he wants, i.e. by sending only one message, of size O(n) bits.

We also briefly show how related techniques plus secret sharing based on monotone span programs can be used to do efficient multiparty computations, both in the secure channel and the broadcast model.

Paper by Ronald Kramer and Ivan Damgård is available in paper copies.

It is well known that a graph G admits a strongly connected orientation if and only if G is 2-edge connected. In fact, such an orientation can be found in linear time. The things get more complicated when the goal is to find a strongly connected orientation that is optimal with respect to some natural measure of optimality (such as minimizing the maximal distance in the orientation, minimizing (weighted) sum of distances taken over all pairs of vertices,...). I will discuss the complexity of these problems, present optimal orientations for some classes of graphs that are important from practical point of view, and propose guidelines for design of efficient heuristic algorithms.

The Graph Minor Theorem (GMT) promises that finite forbidden substructure characterizations, in the manner of Kuratowski's characterization of planarity, exist for many natural graph properties. The proof of the GMT is nonconstructive at least to the extent that simply knowing how to recognize a graph ideal is not enough information to allow the set of obstructions to be effectively computed. The talk is about the big question:

``What kinds of information about an ideal allow the obstruction set to be computed?''

This is still far from being well-understood. The talk will describe a recent extension of earlier results of Fellows and Langston on the computation of obstruction sets. The new methods allow obstruction sets to be computed, e.g., from monadic second order logical descriptions of an ideal, or a Myhill-Nerode-type congruence for the ideal (these may sound exotic, but are usually available), without the necessity of a prior bound on maximum obstruction width. As an example, the new methods allow the intertwines of an arbitrary graph and a tree to be effectively computed, and can probably be extended to the intertwines of an arbitrary graph and a planar graph, and maybe to the intertwines of arbitrary graphs. Perhaps surprisingly, these methods are practical and have been at least partly implemented, and nontrivial previously unknown obstruction sets mechanically computed. The computation of the obstruction set for torus embeddings, for example, now appears to be within reach.

Despite these new positive results, there is the distinct possibility of much stronger noncomputability theorems as well. These will also be discussed. Altogether, this is an area in which there are many elegant open problems that will be highlighted.

Joint work with: Kevin Cattell (Univ. Victoria), Michael Dinneen (Univ. Auckland), Rod Downey (Victoria Univ., Wellington) and Mike Langston (Univ. Tennessee).

A protein evolves slower than its coding DNA making it more reliable to align (i.e. compare) the protein rather than the underlying DNA. However only aligning sequences at the protein level and disregard the fact that the protein corresponds to a coding sequence of DNA is not a biological sound solution. I will present a model for pairwise alignment in which the underlying coding DNA sequence is considered when aligning proteins. A simple O(n⁴) time algorithm computing the optimal alignment in the model was presented by Hein in 1994. I will present an improved algorithm computing the optimal alignment in time O(n²). This improvement was conjectured by Hein in 1994 and is achieved by application of dynamic programming.

We consider the ``standard'' problem in the theory of zero-knowledge protocols: showing in zero-knowledge that a Boolean formula of size n is satisfiable, with error probability 2^-n. We show that this can be done in two phases: an interactive pre-processing phase (which can be done in idle time since it is independent of the formula to handle later) with communication complexity O(n²log n) bits; and a proof phase, where the prover sends just one message of length O(nlog n) bits.

The best known interactive protocols have complexity O(n²) bits, so our results shows that at a marginal cost in total complexity, the actual proof can be made non-interactive and much smaller than what was previously known.

The constants involved are small enough to provide for realistic size formulas: a proof for a formula with 10.000 binary operators would be about 14 Kbyte.

The key to our result is the use of Karchmer and Wigderson's span programs to represent the formula in question.

The presentation is divided in two parts:

I: Faster deterministic sorting and searching in linear space

We present a significant improvement on linear space deterministic sorting and searching. On a unit-cost RAM with word size w, an ordered set of n w-bit keys (viewed as binary strings or integers) can be maintained in O(min (\sqrt{log n}, log n/log w + loglog n, log w loglog n)) time per operation, including insert, delete, member search, and neighbour search. The cost for searching is worst-case while the cost for updates is amortized. As an application, n keys can be sorted in linear space at O(n \sqrt{log n}) worst-case cost.

The best previous method for deterministic sorting and searching in linear space has been the fusion trees which supports updates and queries in O(log n/loglog n) amortized time and sorting in O(n log n/loglog n) worst-case time.

We also make two minor observations on adapting our data structure to the input distribution and on the complexity of perfect hashing.

II: Tight bounds for searching a sorted array of strings

Given n strings, each of k characters, arranged in alphabetical order (i.e., a string precedes another string if it has the smallest character in the first position in which the two strings differ), how many characters must we probe to determine whether a k-character query string is present? We assume that the strings are given in an array and that no extra information is available. If k is a constant, we can solve the problem using O(log n) probes by means of binary search, and this is optimal, but what happens for larger values of k? In the presence of preprocessing and extra storage, there are efficient methods, but what if we are just given the sorted strings?

The question is a fundamental one; we are simply asking for the complexity of searching a dictionary for a string, where the common assumption that entire strings can be compared in constant time is replaced by the assumption that only single characters can be compared in constant time. For sufficiently long strings, the latter assumption seems more realistic. At first glance the problem may appear easy-some kind of generalized binary search should do the trick. However, closer acquaintance with the problem reveals a surprising intricacy.

Here, we will present tight upper and lower bounds.

This seminar will be based on the paper ``P=BPP unless E has sub-exponential circuits: Derandomizing the XOR-lemma'' by Russell Impagliazzo and Avi Wigderson (IW). (To be presented at STOC'97)

Abstract of IW-paper:

Yao showed that the XOR of independent random instances of a somewhat hard Boolean function becomes almost completely unpredictable. In this paper we show that, in non-uniform settings, total independence is not necessary for this result to hold. We give a pseudo-random generator which produces n instances of the function for which the analog of the XOR lemma holds. This is the first derandomization of a ``direct product'' result. Our generator is a combination of two known ones - the random walks on expander graphs (Ajtai et al., 1987; Cohen and Wigderson, 1989; Impagliazzo and Zuckerman, 1989) and the nearly disjoint subsets generator (Nisan, 1991). The quality of the generator is proved via a new proof of the XOR lemma, which may be useful for other direct product results.

Combining our generator with the approach of Nisan and Wigderson (1994), Babai et al. (1993) and the generator of Impagliazzo (1995) gives substantially improved results for hardness vs. randomness trade-offs. In particular, we show that if any problem in E=DTIME(2^O(n)) has circuit complexity 2^Omega(n), then P=BPP.

I will present parts of the paper

[1] Noam Nisan and Avi Wigderson: Hardness vs. randomness, JCSS 49 (1994), no. 2, 149-167

This lies the foundation for the recent paper

[2] Russell Impagliazzo and Avi Wigderson: P=BPP unless E has sub-exponential circuits, STOC '97,

which I will tell about the following week.

Building on ideas developed by Blum and Micali, and Yao, [1] explains how the existence of a `really hard' function (somewhere around exponential time) implies P=BPP. From there, a handful of papers, which I won't cover (and don't understand), implied the statement

P=BPP unless *bla*,

where *bla* are increasingly unlikely statements, culminating in [2].

However, the intuition behind all these results: trading hardness for randomness, is the same as in [1].

Joint work with Theis Rauhe

We prove new lower bounds for dynamic algorithms from various fields. The results strengthen, generalise, and further simplify previous work with Søren Skyum that Theis Rauhe presented to the Alcom seminar last year. (In the talk I assume no familiarity with this previous work.)

The key result (again) is an extension of the time stamp method of Fredman and Saks, which generalises their result; the proof has been streamlined and is considerably more transparent than our previous work.

However, the talk will focus on applications of this result, which is much more fun. These include very easy reductions that yield lower bound proofs for dynamic planar point location and graph connectivity. After this warm-up, we will consider the complexity of the dynamic prefix problem for arbitrary symmetric functions. We exhibit connections to the Boolean circuit complexity of these functions.

This seminar will based mostly on the paper ``On Span Programs'' by Karchmer and Wigderson (KW). (presented at Structure in Complexity Theory '93)

We briefly review the concept of a span-program (SP) and some of the complexity results for SP's proved by KW. We then look in some detail at monotone span programs and KW's construction of secret sharing schemes from SP's.

We show how this solves a previously open problem in secret sharing: monotone functions do exist that have efficient secret sharing schemes, but require superpolynomial monotone formula size. Thus monotone formula size and efficiency of secret sharing are not equivalent, as previously conjectured by some researchers.

A general overview of the Euclidean Steiner Tree Problem will be given during the first part of the talk. The problem of finding a suboptimal Steiner tree inside a simple polygon will be addressed in the second part of the talk. An approach based on the concatenation of Steiner trees with few terminals provides solutions of good quality. Efficient methods of determining optimal Steiner trees with three and four terminals inside a simple polygon will be outlined.

References

General on Steiner trees (Euclidean, rectilinear and in graphs):

• F.K. Hwang, D.S. Richards and P.Winter, The Steiner Tree Problem, North-Holland 1992 (vol. 53 of Annals of Discrete Math.)

• M.W. Bern and R.L. Graham, The shortest network problem, Sci. Am., January 1989, 66-71

• Pawel Winter, Euclidean Steiner minimal trees for 3 terminals in simple polygons, Proc. of the 7-th Canadian Conference on Computational Geometry, Quebec City, Quebec, Canada (1995) 247-253
• Pawel Winter, Steiner minimal trees in simple polygons, Tech. Report 95-43, DIMACS, Rutgers Univ. (1995)

The fundamental problem of range searching has been the subject of much research, and many elegant (main memory) data structures have been developed for the problem and its special cases. Unfortunately most of these structures are not efficient when mapped to external memory. However, the practical need for I/O support has led to the development of a large number of external data structures, which have good average-case behavior for common problems but fail to be efficient in the worst case sense.

Very recently some progress has been made on the construction of external range searching structures with good worst-case I/O performance. In this talk we give a short survey of these results and present our optimal solution to the special case of external two-dimensional range searching called dynamic interval management. This problem has important applications especially in object-oriented databases and constraint logic programming.

We state a new sampling lemma and use it to improve the running time of dynamic graph algorithms. For the dynamic connectivity problem the previously best randomized algorithm takes expected time O(log³ n) per update, amortized over Omega(m) updates. Using the new sampling lemma, we improve its running time to O(log² n). Similarly improved running times are achieved for 2-edge connectivity, k-weight minimum spanning tree, and bipartiteness.

Joint work with Monika Rauch Henzinger.

The aim of the course is to investigate how linear algebraic methods may be employed in combinatorics and algorithms, in particular to graph problems. Starting from the basics of algebraic graph theory, the focus will be on the Lovasz function of a graph (a P-time computable function sandwiched between two NP-complete parameters of a graph) and on methods stemming from it such as semi-definite programming and its applications in developing approximation algorithms for graph problems such as colouring.

Topics:

1. Basics of algebraic graph theory: the spectrum of the adjacency matrix and graph properties.
2. The Lovasz Theta Function: definitions and characterisations, association schemes, applications to the Erdos-Ko-Rado theorem.
3. Semi-Definite Programming and its application to graph colouring.

References

• LAMCCS-1: Scattered material, no single source.
• LAMCCS-2,3:
  • L. Lovasz: ``On the Shannon Capacity of a Graph'', IEEE Tran. on Computer Systems, IT-25, no 1, Jan. 1979.
  • D.E. Knuth, ``The Sandwich Theorem'', The Electronic Journal of Combinatorics, 1. 1-48. 1994.
  • M. Grötschel, L. Lovasz, A. Schrijver, Geometric Algorithms and Combinatorial Optimisation, Springer-Verlag, 1988 sec. 9.3.
• LAMCCS-4,5:
  • D. Karger, R. Motwani and M. Sudan, ``Approximate Graph Colouring by Semi-definite Programming'', FOCS 1994, pp. 2-13.

The construction of priority queues is a classical topic in data structures. Recently, it has been considered how to implement priority queues on parallel machines. In this talk we focus on how to achieve optimal speedup for the individual priority queue operations known from the sequential setting.

We present time and work optimal priority queues for the CREW PRAM. Our priority queues support FindMin in constant time with one processor, and MakeQueue, Insert, Meld, FindMin, ExtractMin, Delete and DecreaseKey in constant time with O(log n) processors. A priority queue can be build in time O(log n) with O(n/log n) processors. In parallel k elements can be inserted into a priority queue in time O(log k) with O(log n+k/log k) processors. With a slowdown of O(loglog n) in time the priority queues adopt to the EREW PRAM without increasing the work. A pipelined version of our priority queues can be implemented on a processor array of size O(log n), supporting the operations MakeQueue, Insert, Meld, FindMin, ExtractMin, Delete and DecreaseKey in constant time.

We address the issue of efficiently searching on external dynamic data structures for strings, introducing the following External Dynamic Substring Search problem. Consider a set of (external) text strings kept in secondary storage. The set can be dynamically changed by inserting or deleting strings, and on-line searched to find all the occurrences of an arbitrary pattern string as a substring of the text strings in the set.

In the first part, we describe a text indexing data structure for secondary storage, called the SB-Tree, which allows us to solve the External Dynamic Substring Search problem with provably good worst-case I/O bounds. It requires optimal space and makes the on-line search alphabet independent also in main memory.

In the second part, we show that SB-trees combine the best of B-trees and suffix arrays, overcoming the limitations of inverted files, suffix arrays, suffix trees, and prefix B-trees. The performance of SB-trees is evaluated in a practical setting, under a number of searching and updating experiments. Improved performance is obtained by a new space-efficient and alphabet- independent organization of the internal nodes of SB-trees, and a new batch insertion procedure that avoids thrashing.

Let S be a finite alphabet and a₁,a₂,...,a_k be strings over S with length n₁,n₂,...,n_k. Let S' be the alphabet S extended with a special `space'-character `-'. An alignment of the strings a₁,a₂,...,a_k is specified by a (k x m)-matrix, where m>=max{n₁,n₂,...,n_k}. Each element of the matrix is a member of S' and each row i contains the characters of a_i in order, interspersed by m - n_i spaces. Let d : S' x S' -> R be a pseudo-metric. The sum-of-pair score (SP-score) for an alignment A of the strings a₁,a₂,...,a_k is defined as

A DNA sequence can be considered to be a string over the finite alphabet {C,G,T,A} (and a protein sequence a string over a slightly larger but still finite alphabet). A common model is that the volution of DNA consists of three events: (1) A nucleotide (a character) can be substituted with another nucleotide. (2) A nucleotide can be removed. (3) A new nucleotide can be inserted. Each of the events are assigned cost according to the assumed probability of the event happening. Given two sequences S₁ and S₂ it is likely that the real course of events in the evolution from S₁ to S₂ is close to the cheapest. Aligning a set of DNA sequences thus gives some idea of how they are related in the evolutional history and which parts are homologous.

Computing optimal alignments w.r.t. SP-score are by no means an agreed upon biologically correct method of aligning sets of sequences but practice has shown that it usually provides plausible alignments.

We will present results from two articles. In [1] it is shown that it is NP-complete to compute the optimal alignment w.r.t. SP-score. In [2] an approximation algorithm for aligning k sequences is given. The algorithm has performance guarantee 2 - l/k for a fixed l<k and the running time is polynomial in n (maximum of the n_i's) and k.

References

1. Lusheng Wang & Tao Jing ``On the Complexity of Multiple Sequence Alignment''
2. Vineet Bafna et al. ``Approximation Algorithms for Multiple Sequence Alignment''

Consider a protocol, in which a prover can convince a verifier that a given word x belongs to a language L. This is called a proof system for L. If the verifier gets only negligible information except for the fact that x is in L, even regardless of his computing power, the protocol is said to be statistical zero-knowledge.

What characterizes a language that has a statistical zero-knowledge proof system? This seems to be a very difficult question. The class of such languages, known as SZKIP, contains both languages in NP and languages beleived not to be in NP. On the other hand, SZKIP does not contain NP unless the poly-time hierachy collapses. In this work, we try to approach the nature of SZKIP by showing that many languages in SZKIP are in a certain sense stable under monotone operations. More precisely, we consider the following scenario:

Suppose we are given a language L in SZKIP. From this and a monotone Boolean function f on n inputs, we can construct in a natural way a new language f(L): Suppose we are given a division of some word x into n sub-words x₁,..,x_n; then we create an n-bit string B by saying that the i'th bit of B is 1 iff x_i is in L. We define that x is in f(L) iff f(B)=1. If for example f is a threshold function with threshold k, we are simply asking whether at least k of the n sub-words are in L.

We show that under certain conditions on L and f, both f(L) and f(L') (where L' is the complement of L) are in SZKIP. More specifically, it is sufficient that the proof system of L is a 3-move Arthur-Merlin game and that f has a polynomial size monotone formula.

This in fact means that any language previously known to be in SZKIP immediately gives rise to an infinite family of languages in SZKIP.

Joint work with Ronald Cramer, CWI.

I will present Haken's proof of an exponential lower bound for the size of monotone solutions to NP-complete problems (Armin Haken: Counting Bottlenecks to Show Monotone P!=NP. FOCS '95)

The method of proving lower bounds by bottleneck counting is illustrated for monotone Boolean circuits. This paper gives another proof of the result of Razborov and Andreev, that monotone Boolean circuits must have exponential size when solving a problem in NP. More specifically, the paper defines a graph recognition problem called BMS. Any monotone circuit that solves BMS, must contain a quantity of gates that is exponential in the eighth root of the input size. The actual instances of the BMS problem used to prove the lower bound are easy to separate for non-monotone circuits. The proof is self-contained and uses only elementary combinatorics.