Consider a set of processors that can communicate with each other. Each processor is either "good" or "faulty," and the processors can be used to test each other. (A good tester will tell whether the testee is good or faulty. A faulty tester may lie.) Tests may be performed in parallel, provided that each processor participates in at most one test per round.
In static fault diagnosis, we assume that a strict majority of the processors are good and that no processors fail during testing; the objective is to determine the status (good or faulty) of every processor. The best known algorithm takes only 10 rounds, independent of the number of processors. Some very recent algorithms tolerate "dynamic" faults, which occur during the testing process itself.
We will give an overview of parallel algorithms for static and dynamic fault diagnosis.
The use of public-key cryptography on a mass-market scale requires sophisticated mechanisms for managing trust. For example, any network service that receives a signed request for action is forced to answer the central question ``Is the key used to sign this request authorized to take this action?'' In certain services, this question reduces to ``Does this key belong to this person?'' In others, the authorization question is considerably more complicated, and resolving it requires techniques for formulating security policies and security credentials, determining whether particular sets of credentials satisfy the relevant policies, and deferring trust to third parties.
In this talk, I will flesh out the ``trust management problem'' and show how its relevance extends beyond cryptography into all network services that require deferral of trust. I will present in detail a particular trust management tool, called ``PolicyMaker'' (developed with AT&T colleagues Matt Blaze and Jack Lacy), and the general approach to the problem that is embodied in this tool. Finally, I will pose some general trust management research problems, both theoretical and experimental, now under investigation AT&T and elsewhere.
1. Gap Theorem: The sets that are complete under AC^0 and NC^0 reducibility coincide.
2. Isomorphism Theorem: The sets complete under AC^0 reductions are all isomorphic under isomorphisms computable and invertible by AC^0 circuits of depth three.
These theorems hold for any complexity class that is closed under TC^0 reductions, such as NC^1, DLOG, P, NP, ...
This Gap Theorem does not hold for strongly uniform reductions: there are sets complete for NC^1 under Dlogtime-uniform AC^0 reductions that are not complete under Dlogtime-uniform NC^0 reductions.
This is joint work with Manindra Agrawal and Steven Rudich.
The fundamental task of computer science is to predict the behavior of algorithms. One would like to do this by rigorous mathematical analysis, but in many situations of practical interest this is not yet possible. One alternative is to adopt the position of a natural scientist, and attempt to show how the behavior of an algorithm can be deduced from heuristic considerations. Of course, such predictions must be made in a precise and falsifiable manner, so they can be compared with empirical data.
I will illustrate these ideas using three number-theoretic problems of a computational flavor: small witnesses for primality testing, search methods for primitive roots, and growth rates for pseudopowers.
We consider the class Sigma^k_3 of unbounded fan-in depth-3 boolean circuits, for which the bottom fan-in is limited by k and the top gate is an OR.
It is known that the smallest such circuit computing the parity function has Omega(2^(epsilon*n/k)) gates (for k=O(n^(1/2))) for some epsilon >0, and this was the best lower bound known for explicit (P-time computable) functions.
In this talk, for k=2, we exhibit a function in uniform NC^1 that requires 2^(n - o(n)) size depth 3 circuits. The main tool is a theorem that shows that any Sigma^2_3 circuit on n variables that accepts A inputs and has size s must be constant on a projection (subset defined by equations of the form x_i=0, x_i=1, x_i=x_j or x_i=\bar{x}_j) of dimension at least log(A/s)/(log n).
This is joint work with Mike Saks and Francis Zane.
The issues of admission control and routing in high-speed networks have inspired theoretical work on network routing and bandwidth allocation. The network model used in approximation algorithms represents the links of the network as edges of fixed capacity, and connections as pairs of vertices with a fixed bandwidth demand between them. The algorithms and their analysis are motivated by this network flow perspective. In this talk we will briefly survey some these results.
The rest of the talk will concentrate on the issues inherent in dealing with bursty connections based on joint work with Jon Kleinberg and Yuval Rabani. Traffic in high-speed networks based on ATM and related technologies tends to be extremely bursty: the transmission rate of a single connection can vary greatly over time; there can be infrequent periods of very high peak rate, while the average rate is much lower. Much of the strength of ATM comes from the advantage of statistical multiplexing --- the packing of uncorrelated, bursty connections on the same link.
We consider one of the most commonly studied models in this domain: that of two communicating nodes connected by a set of parallel edges, where the rate of each connection between them is a random variable. We give approximation algorithms for several variants of the problem. A standard approach that has emerged for dealing with probabilistic resource requirements is the notion of effective bandwidth --- a fixed demand associated with a bursty connection that ``represents'' its distribution as closely as possible. Our approximation algorithms make use of the standard definition of effective bandwidth and also a new one that we introduce; the performance guarantees are based on new results showing that a combination of these measures can be used to provide bounds on the optimal solution.
We present a simple polynomial-time approximation scheme for geometric pinstances of the $k$-MST problem, the traveling salesman problem (TSP), and other network optimization problems. Our method employs a very simple modification to our SODA'96 paper, which in turn was based on a simplification of a method introduced by Blum, Chalasani, and Vempala (STOC'95).
In particular, the method is based on the concept of an ``$m$-guillotine subdivision''. Roughly speaking, an ``$m$-guillotine subdivision'' is a polygonal subdivision with the property that there exists a line (``cut''), whose intersection with the subdivision edges consists of a small number ($O(m)$) of connected components, and the subdivisions on either side of the line are also $m$-guillotine. The upper bound on the number of connected components allows one to apply dynamic programming to optimize over $m$-guillotine subdivisions, as there is a succinct specification of how the subdivision interacts with the cuts that make up the boundary of a rectangle that specifies a subproblem of the dynamic program.
Key to our method is a theorem showing that any polygonal subdivision can be converted into an $m$-guillotine subdivision by adding a set of edges whose total length is small: at most that of the original subdivision, times ${1\over m}$. This allows us to apply dynamic programming to optimize over the class of $m$-guillotine subdivisions having some prescribed properties, since the relevant subproblems are specified by only a constant ($O(m)$) number of parameters. This yields a $(1+{1\over m})$-approximation for various network optimizati
S. Arora has developed an alternative method to achieve similar results -- a PTAS for Euclidean TSP and related problems. His remarkable discovery predates the release of this paper by several weeks. Prior to Arora's breakthrough, the best approximation factor for the Euclidean TSP was the Christofides heuristic, which gave a factor of 1.5.
(paper available at http://ams.sunysb.edu/~jsbm/jsbm.html)
A monontone real circuit has wires that carry truth values that can be any real number and binary gates that compute monotone real functions, meaning that if one of the input values increases, the output does not decrease. In some ways such circuits are very powerful. Rosenbloom showed that any slice function can be computed by linear size log-depth monotone real circuits. Pudlak showed that lower bounds for monotone real circuits imply lower bounds for the cutting plane propositional proof system.
In this talk an exponential lower bound is shown for monotone real circuits computing a variant of the Clique function. The proof uses the method of "counting bottlenecks" and the combinatorics are self-contained.
This is joint work with Stephen Cook.
Performance of algorithms using hashing is often related to the largest number of keys mapped by the hash function to the same value. This motivates the study of the expected size of the largest bucket for the worst case set of keys of a given size. In this work, we study the performance of linear transformations as a family of hash functions by this measure.
Our main result is the linear mappings over GF[2] are excellent hash functions. They almost match the performance of the best possbile family of hash functions. (But, of course, are much more efficient.)
A surprising additional result we have implies that linear mappings over big finite fields (say modulo a prime) are the other way around. They are almost as bad as possbile for any universal family of hash functions.
The main tool in proving the main result may be of independent interest. We show that a random linear mapping applied on a set of cardinality cnlog(n) covers all the element of a size n range with probability at least (1-epsilon_c).
This is joint work with Noga Alon, Martin Ditzfelbinger, Peter Bro Miltersen, and Erez Petrank.
One of the most fascinating aspects of the theory of algorithms is the apparent power that randomness provides for algorithm design. Thus, for example, the best practical algorithm for testing whether a number is prime is a probabilistic test, which uses random bits within the algorithm. In essence, randomness is of value in such problems because the problem can be converted into a search problem, and random sampling can be used to speed the search.
The correctness and efficiency of randomized algorithms is generally proved by making the assumption that the source of random bits is fair: the bits are independent and unbiased. This assumption rarely (if ever) holds in practice, and the question has been raised: how much can this assumption be relaxed without sacrificing the correctness of the algorithm. A series of papers, starting with work of M. Santha, U. Vazirani and V. Vazirani considered this problem. The essence of this approach is to boil the problem down to the following one: design an efficient method for sampling from a largepopulation that is robust in the sense that the sample it chooses is representative even if the random source being used to select the sample is faulty. This problem can in turn be reformulated as a combinatorial problem,to give a computationally efficient construction for a family of graphs known as dispersers. A disperser is so named because its edges are (in some precise sense) evenly dispersed throughout the graph.
This talk describes work of Aravind Srinivasan, Shiyu Zhou, and myself in which we showed how to construct ``optimal'' dispersers in polynomial time. As a consequence, we are able to convert any probabilistic polynomial time decision algorithm to one that works even if the random source being used is extremely weak.
Recently, exciting new algorithms have been developed for the minimum cut problem. The new algorithms include those by Nagamochi and Ibaraki, Hao and Orlin, Karger and Stein, and Karger. These algorithms are very different from the earlier ones and from each other and substantially improve worst-case time bounds for the problem. However, only one of the algorithms has been implemented before our study, and nothing was known about relative performance of these algorithms in practice.
We conduct experimental evaluation of relative performance of the algorithms. In the process, we develop heuristics and data structures that substantially improve practical performance. We also develop problem families for testing minimum cut algorithms. Our work leads to a better understanding of practical performance of the minimum cut algorithms and produces very efficient codes for the problem.
The technical report NECI-TR-96-132 describing these results in detail is available via my home page.
Joint work with Chandra Chekuri, David Karger, Matt Levine, and Cliff Stein.
This talk surveys the state of the art in the theory of multistage interconnection networks. In particular, it focuses on a class of networks called multibutterflies. What distinguishes multibutterflies from traditional multistage networks is that they incorporate expander networks into their structure. As a consequence, they outperform traditional networks in three respects. First, they have fast deterministic algorithms for routing permutations in both the packet routing model and the wormhole routing model. Second, two back-to-back multibutterflies are nonblocking, and there are on-line algorithms for establishing new connections in them even if many requests for connections are made simultaneously. Third, multibutterflies are highly fault tolerant. Until recently, however, one capability that multibutterfly networks were not known to possess was the ability to sort deterministically in logarithmic time. Indeed, only the AKS sorting network was known to have this capability. Surprisingly, the class of multibutterfly networks have now been shown to contain the AKS sorting network. In particular, it is possible to embed an $N$-node AKS network into a $\frac{3n}{2}$-node degree-8 multibutterfly with load $1$, congestion $1$, and dilation $2$. This result makes multibutterflies the most powerful known multistage networks.
We discuss new approaches to the design of approximation algorithms for several NP-hard scheduling problems in which the objective is to minimize the average completion time.
If we schedule a set of $n$ jobs on a set of machines, each job $j$ finishes at some time $C_j$; our goal is to minimize $\sum_j C_j/n$. If all the jobs are available at time $0$ and there are no precedence constraints, this problem is known to be solvable in polynomial time. Once we introduce release dates, or precedence constraints, or add weights to the jobs, the problem becomes NP-hard. Until our recent work no approximation algorithms were known for any (non-trivial) variants of these problems.
We introduce several fairly general techniques for solving problems of this type and show how they lead to small-constant-factor approximation algorithms. Our basic framework is to solve a relaxed version of the problem, and use that to generate an ordering on the jobs. We will demonstrate and use several different types of relaxations including preemptive relaxations, one-machine relaxations, randomized relaxations and linear-programming relaxations. Applying these techniques, we get approximation algorithms for many problems including one-machine, parallel machines, and unrelated machines, and algorithms which can handle release dates and precedence constraints and weights on the jobs.
We will also demonstrate the existence of schedules that simultaneously approximate the optimal makespan (schedule length) as well; this leads to the following quite general result: for any instance of any (reasonable) scheduling problem, there is a schedule that simultaneously comes within a small constant factor of both the optimal makespan and the optimal average weighted completion time.
The work we discuss is from several papers joint with Soumen Chakrabarti (IBM), Chandra Chekuri (Stanford), Rajeev Motwani (Stanford), Balas Natarajan (HP), Cynthia Phillips (Sandia National Labs), Andreas Schulz (TU Berlin), David Shmoys (Cornell), and Joel Wein (Polytechnic)
Recently Ajtai established a connection between the worst case and the average case complexity of the shortest lattice vector problem. Based on this work Ajtai and Dowk have proposed a cryptographic protocol whose security is provably equivalent, up to a large polynomial factor, to a well known lattice problem, in the worst case. (Compare this with the RSA and the factoring problem.)
In provable terms, the Ajtai result is still far from being efficient for cryptographic purposes. It is also intellectually challenging to investigate the true extent to which the average case and the worst case complexity can be reduced to each other. We present improvements to this work, reducing the exponent in the polynomial factor in the connection from around 8 to around 3, making the prospect of cryptographic and other applications more realistic.
Joint work with Ajay Nerurkar.
Finite element mesh generation refers to the process of subdividing a geometric domain in two or three dimensions into a collection (called a ``mesh'') of small convex shapes, such as triangles (in 2D) or tetrahedra (in 3D). Mesh generation is a crucial preprocessing step for the finite element method, which in turn underlies much of modern scientific computing. Although automatic mesh generators have existed in some form for decades, it has only been since 1989 (starting with work of Chew) that a firm mathematical basis, rooted in computational geometry, has been proposed for the problem.
In this talk I will describe QMG, an algorithm for volumetric mesh generation of polyhedral regions in 3D. The QMG algorithm is the only known algorithm that has guaranteed bounds on the aspect ratios for general 3D polyhedral regions. Bounded aspect ratio is important for accuracy of the finite element. QMG also has a guarantee that it will not overrefine the domain. The QMG algorithm has consequences for other theoretical triangulation problems arising in computational geometry, such as max-min-altitude triangulation of high-dimensional polyhedral regions.
QMG has been implemented in C++ and is available on the Web. I will describe experiments comparing QMG to other mesh generators, as well as issues of representing geometric objects computationally.
Part of this talk represents joint work with S. Mitchell of Sandia National Laboratories.
Suppose you want to spread a rumor in a community you are part of. An undirected graph representation of the community contains a node for each member of your community and an edge between all pairs of members who would transmit the rumor between themselves. Consider the following telephone model for the spread of the rumor: any person calls at most one of her friends (neighbor in the graph) on a given night and exchanges information. Note that this implies that when you start disseminating the rumor to your friends, you can only call them one per night. When is the earliest possible night by which everyone in the community would have heard the rumor? This rapid rumor ramification problem is also known as the minimum broadcast time problem in the case when the graph represents a network of processors, due to its obvious application to fast broadcast of messages from a source node.
Computing the minimum broadcast time in an arbitrary network is NP-hard. This quantity is closely related to a quantity that I call the poise of the network; The poise of a spanning tree is the sum of its maximum degree and its diameter, and the poise of a graph is the minimum poise of any of its spanning trees. I will present the relation between these problems, and approximation algorithms for both with polylogarithmic performance ratios.
In this survey talk, we focus on the following problem and natural variants of it:
Given a set of values $ T = (x_1,f(x_1)),...,(x_n,f(x_n))$ a parameter $\delta$ and an integer $d$, find a degree $d$ polynomial $p$ such that $p$ and $f$ agree on at least a $\delta$ fraction of the inputs in $T$.
This problem has a wide range of applications, including coding theory, probabilistically checkable proof systems, and crytography. When $\delta=1$, this is just the problem of polynomial interpolation. The problem was solved by Berlekamp and Welsh in the case that $\delta >1/2$ and $n$ is large compared to $d$. Until recently, this seemed to be a natural barrier since when $\delta <1/2$ and $n$ is large compared to $d$, there may be more than one polynomial which agrees on a $\delta$ fraction of $T$. However, it turns out that the problem can be solved even when $\delta < 1/2$. We survey the recent advances on this problem.
A fully dynamic graph algorithm is a data structure for a graph with a fixed nodeset that supports the following three operations: (1) insert an edge e, (2) delete an edge e, and (3) answer a query, e.g. "Are nodes u and v connected?" or maintain information about the graph, e.g. its minimum spanning tree. The aim is to speed up computation on incrementally changing data by making use of previous solutions, thereby avoiding recomputation from scratch.
Researchers have been working on dynamic graph algorithms for over 15 years. In the past two years, Monika Henzinger and I have made significant progress on several important problems in this area, including connectivity, minimum spanning tree, 2-edge connectivity, reachability, biconnectivity, and a number of related problems.
Much of our work is based on a few central ideas. The goal of this talk is to give an overview: I'll discuss our techniques and how they've been applied to various problems.