Talks are held in Margaret Jacks Hall, on the Main Quad of Stanford's campus. Click here for directions.
Joint work with Uri Feige of The Weizmann Institute.
In this talk, I will present several fundamental properties of the large class of symmetric quadratic systems acting on populations over a fixed set of types. I will go on to give a complete analysis of one particular system, defined on populations over the set of matchings in a tree. In particular, it will turn out that convergence to the limit in this system requires only polynomial time. This demonstrates that such systems, though non-linear, are sometimes amenable to analysis.
This is joint work with Yuri Rabinovich and Avi Wigderson.
Our implementation works very well over a wide range of problem classes. In our experiments, it was always competitive with the established codes, and usually outperformed these codes by a wide margin.
Some heuristics we develop may apply to other network algorithms. Our experimental work on the minimum-cost flow problem motivated theoretical work on related problems.
In this talk, we will describe transformations which provide a basis for the compilation of ideal programs that allow synchronization, to run efficiently on asynchronous parallel machines with shared memory. In addition to being correct and efficient, the transformed programs have the important property that they are responsive. Essentially, responsive computations always make progress on the asynchronous target machine without waiting for slow or failed processors to complete their work. Therefore, responsive executions are fault-tolerant in the following strong sense: the computation will terminate correctly even if processors fail arbitrarily often during the computation, so long as at least one processor is executing correctly at any time. No implicit assumptions about the relative speeds of processors, or about synchronization primitives built into the target machines, are required for our methods to work. By using randomization, we can guarantee that the executions on the asynchronous targets are guaranteed to require only $O(\log n)$ extra space and $O(\log^3 n)$ additional expected work, compared to the original source programs.
This is joint work with Z. Kedem, M. Rabin and A. Raghunathan.
* Leader Election
* Spanning Tree (Minimum, BFS, etc.)
* Shortest-Path
* Deadlock Detection
* Network Reset
* Network Synchronization.
Our protocols work for asynchronous general topology networks of identical nameless nodes. Moreover, they are efficient and self-stabilizing i.e. the protocols can be executed begining from an arbitrary configuration. We stress that all the previous protocols (even without self-stabilization) required logarithmic memory per processor.
In fact, not only the above problems but everything computable in randomized linear space can be computed by an asynchronous coin-flipping network (with the same memory and in a self-stabilizing fashion). Thus, we obtain a tight and robust characterization of the power of randomized distributed networks.
Based on joint work with B. Awerbuch (MIT) and R. Ostrovsky (MIT, ICSI, Berkeley) and further developments by G. Itkis and Leonid Levin (BU).
If the equations are linear, then this condition is expressed by the determinant of the coefficient matrix. In order to solve linear equations, either symbolically or numerically, we first need to understand the structural properties of the determinant.
If the equations are non-linear, and possibly sparse, then the role of the determinant is played by the "sparse resultant". In this lecture we explore the combinatorial structure of the sparse resultant, and its application to solving non-linear algebraic equations.
It is easy to learn to Markov chain, just by observing it. However, the question we focus on is: if you know the Markov chain, what do you do with it? How can you use it to get the lowest possible fault rate?
We look at a number of natural algorithms, all of which turn out to have a high fault rate on some Markov chains. We then describe a specific algorithm that has a fault-rate at most a constant times optimal, for every Markov chain.
(Joint work with Anna Karlin and Prabhakar Raghavan)
We consider integer programming problems with a minimization objective and such that each constraint involves up to two variables. Such problems are NP-hard even if the variables are binary, (e.g. vertex cover), and even if the inequalities are monotone (the coefficients of the variables have opposite signs).
Let U be an upper bound on the value of the variables. An O(mnU^2 log n^2U/m)) algorithm is given for the problem over monotone inequalities, thus proving it is weakly NP -hard. This algorithm has a direct application for a problem of layout of VLSI circuits. This algorithm is also the key to the approximation in the general integer programming case.
For the general (nonmonotone) case, we show that the properties of the vertex cover problem are a special case of the properties of integer programs with 2 variables per inequality. The results include a O(mnU^2 log n^2U/m)) algorithm delivering a super-optimal solution that provides a lower bound that is only better than the corresponding bound derived from the linear programming relaxation. This super-optimal solution consists of integer multiple of 1/2 and it also has the property that some of its integer components retain their value in an optimal solution. It is shown how several approximation algorithms for the vertex cover, that exploit certain graph properties in order to derive better approximation algorithms, generalize to our integer programs.
Parts of this work are joint with J. Naor and with N. Megiddo and A. Tamir.
There is, however, an inherent mismatch between complexity and logic -- while computational devices work on encodings of problems, logic is applied directly to the underlying mathematical structures. To overcome this mismatch, we develop a theory of relational complexity, which bridges tha gap between standard complexity and fixpoint logic. On one hand, we show that questions about containments among standard complexity classes can be translated to questions about containments among relational complexity classes. On the other hand, the expressive power of fixpoint logic can be precisely characterized in terms of relational complexity classes. This tight three-way relationship among fixpoint logics, relational complexity and standard complexity yields in a uniform way logical analogs to all containments among the complexity classes P, NP, PSPACE, and EXPTIME. The logical formulation shows that some of the most tantalizing questions in complexity theory boil down to a single question: the relative power of inflationary vs. noninflationary 1st-order operators.
This talk represents joint work with S. Abiteboul and V. Vianu.
New work (joint with Clifford Stein) improves the bounds to $O^*(n^2)$ sequential time or parallel processors, thus providing the most efficient known algorithm for the minimum cut problem in both the sequential and the parallel case.
If time permits, we will show how a theorem based upon the above algorithm can be applied to minimum spanning trees. We give a simple and practical $O(m+ n\log^2 n)$ running time minimum spanning algorithm, as well as an EREW PRAM minimum spanning tree algorithm which runs $O(\log n)$ time using $O(m+n^{1+\epsilon})$ processors--this is the best possible running time and is work-efficient on dense graphs.
Here we analyze the pure literal rule heuristic for computing a satisfying assignment to a random 3-CNF formula with n variables. Previous works showed that the unit clause rule and the minimal clause rule can find satisfying assignments for almost all 3-CNF formulas with up to n clauses. We show that the pure literal rule by itself finds satisfying assignments for almost all 3-CNF formulas with up to 1.63 n clauses, but it fails for more than 1.7 n clauses.
The talk is intended for a relatively broad audience: I will try to build some intuition for the problem and give a sketch of the proofs, but will only skim the technical details of the analysis.
This is joint work with Alan Frieze (CMU), and Eli Upfal (IBM Almaden and Weizmann Institute).
The first result is joint work with N. Nisan, and the third is joint work with A. Wigderson.
In this work we provide the theoretical underpinnings needed to analyze the relative contention costs of distributed algorithms. We show that the bitonic counting network of Aspnes, Herlihy, and Shavit enjoys much lower contention costs than the single-variable solution to the counting problem. In addition, we obtain high lower bounds on contention and contention/latency tradeoffs for a variety of other problems, including consensus and mutual exclusion.
This is joint work with Maurice Herlihy and Orli Waarts.
Game semantics may also provide the ``missing link'' between programming language semantics and Complexity theory. We conclude with some speculative remarks on this theme.
The talk will describe our recent work on infinite structures and databases, including the high undecidability of many problems on recursive graphs, a completeness result for computable database queries, and ways of deducing results for the finite case from those for the infinite case and vice versa. In view of the recent results about the impossibility of approximating problems hard for Max-SNP, one of our results seems to be particularly interesting, since it shows that any problem in NP whose infinite version is highly undecidable cannot be in Max-SNP (in fact, it is not even in Max-NP).
A t-spanner of a graph G is a spanning subgraph of G such that distances in the spanner are within a factor of t from the corresponding distances in G. Much research was recently conducted on bounding the size and efficiently constructing t-spanners. All previous constructions, however, were based on solving many instances of the exact shortest-paths problem. We avoid that and construct t-spanners, of even smaller size, much more efficiently than known before.
The main tool we employ are efficient constructions of (t,W)-pairwise-covers of the input graph (where W>0 and t\geq 2). A (t,W)-cover is, roughly, a collection of subsets of vertices of total size ~O(n^{1+2/t}) such that any pair of vertices of distance at most W are both contained in at least one subset, and any pair of vertices which are in the same subset are of distance at most tW. We use a logarithmic number of pairwise covers for different values of W to generate a t(1+\eps)-spanner and paths of stretch t(1+\eps).
We argue that critical technology trends underlying parallel machine design offer opportunities to model a wide range of machines uniformly with a small number of parameters. Specifically, we offer the {\em LogP model} in which a parallel computer is viewed as a collection of homogeneous processors, each with a local memory, connected together in a network capable of delivering point-to-point messages of fixed size. The machine is characterized by four parameters: $P$, the number of processors; $L$, an upper bound on the latency of a message in the network; $o$, the send/receive overhead; and $g$, the minimum separation between consecutive sends/receives at a processor. Our model reveals important bottlenecks but is simple enough to support interesting algorithmic analysis.
This talk will describe the model and optimal algorithms for some broadcast problems, summation and for computing FFTs. All our algorithms are absolutely optimal in that not even the constant factors can be improved.
The LogP model is the result of work done jointly with David Culler, Richard Karp, David Patterson, Eunice Santos, Klaus Schauser, Ramesh Subramonian and Thorsten von Eicken.
In view of this phenomenon the following concern was recently identified as basic. Consider a problem whose input is split between two processors connected by a communication link; and for which an interactive protocol exists which solves the problem in $T$ transmissions on any input, provided the channel is noiseless. If in fact there is some noise on the channel, what is the effect upon the number of transmissions needed in order to solve the communication problem reliably?
We will address this question by describing a deterministic method for simulating noiseless-channel protocols on noisy channels, with only a constant slow-down. This is an analog for general interactive protocols of Shannon's coding theorem, which dealt only with data transmission, i.e. one-way protocols.
We will also discuss some of the principal directions for further work.
Communication delays arise from two major limitations: bandwidth and latency, which have different consequences for algorithm design. A Block PRAM model of computation (BPRAM for short) models these two effects by allowing processors to communicate by transferring blocks of data - here n words can be transferred in time l+bn where l corresponds to latency, and b represents the (inverse of) bandwidth per processor. This model can be used to study several phenomena which arise in practice: inherent limits to parallelizing communication, computation-communication tradeoffs, bandwidth limits for problems such as sorting, FFT etc., importance of using both temporal and spatial locality of reference, the role of the l.p product of a machine as a determiner of the difficulty of generating efficient algorithms, etc. Furthermore, one can model phenomena akin to practice where tiny changes in the communication pattern can result in catastrophic changes in the running time of certain algorithms.
The research was done jointly with Alok Aggarwal and Marc Snir.
We then apply these ideas to network flow. Cheriyan and Hagerup introduced an on-line game on a bipartite graph as a fundamental step in improving algorithms for computing the maximum flow in networks. They described a randomized strategy to play the game. King, Rao and Tarjan studied a modified version of this game, called "node kill", and gave a deterministic strategy. We obtain an improved deterministic algorithm for the node kill game (and hence for maximum flow) in all but the sparsest graphs.
These problems combine a demand for good competitive ratios with more traditional requirements of implementation efficiency. Our solutions deal with the tradeoffs between these measures.
This is joint work with Jeff Westbrook.
We view virtual circuit routing as a generalization of an on-line scheduling problem, and hence a major part of this work focuses on development of algorithms for non-preemptive on-line scheduling for related and unrelated machines. Specialization of routing to scheduling leads us to concentrate on scheduling in the case where jobs must be assigned immediately upon arrival; assigning a job to a machine increases this machine's load by an amount that depends both on the job and on the machine. The goal is to minimize the maximum load.
For the related machines case, we describe the first algorithm that achieves constant competitive ratio. For the unrelated case (with n machines), we describe a new method that yields O(log n)-competitive algorithm. This stands in contrast to the natural greedy approach, which we show has only a Theta(n) competitive ratio. The virtual circuit routing result follows as a generalization of the unrelated machines case. Our techniques can be extended to provide low congestion solutions for more general routing problems as well.
The talk is self contained.
This is joint work with James Aspnes from IBM Almaden Research Center, Yossi Azar from DEC Systems Research Center, Amos Fiat from Tel-Aviv University, and Serge Plotkin from Stanford University.
Using the decomposition theorem, we prove a lower bound of $\Omega(\sqrt{\log k / \log\log k})$ for the competitive ratio of randomized algorithms for the $k$-server problem against the oblivious adversary. The bound holds for arbitrary metric spaces (of at least $k+1$ points) and provides a new lower bound for the metrical task system problem as well. This improves the previous best lower bound of $\Omega(\log\log k)$ for arbitrary metric spaces \cite{KRR}, more closely approaching the conjectured lower bound of $\Omega(\log k)$. We also prove a lower bound of $\Omega(\log k / \log\log k)$ for the server problem on $k+1$ equally-spaced points on a line, which corresponds to several natural motion-planning problems.
This is joint work with Avrim Blum, Howard Karloff and Mike Saks.
This is joint work with Noam Nisan.
We show that there is a constant p*, 1/2 < p* < 2/3, such that
1. There is a constant c > 0, such that for p < p*, the probability that B_n(p) has a connected component of size cn tends to 1, as n tends to infinity.
2. If p > p*, then for any constant c' > 0, the probability that B_n(p) has a connected component of size c'n tends to 0, as n tends to infinity.
This is joint work with Greg Nelson (DEC SRC) and Hisao Tamaki (University of Toronto).
For the most part, we consider problems of producing labelings of the nodes of the network where the legality of a labeling can be checked locally (e.g., coloring). Two general results about such problems are: it is undecidable whether a given problem can be solved locally; and randomization does not help in solving problems locally. Regarding particular examples: there is a non-trivial labeling problem which can be solved locally; and this problem has been used as a basis for a local solution to a certain relaxed version of the dining philosophers problem. Open questions will also be discussed.
This is joint work with Moni Naor.
This is joint work with Juan Garay of IBM T.J. Watson Research Center.
In this talk, I will present a fundamentally new approach to organizing a parallel system, based on finite projective geometries. In the simplest (two dimensional) case of such a system, every pair of processors share a memory and every pair of memories share a processor. The instruction set of the machine is designed in such a way that each basic instruction results in massively parallel and conflict-free use of all components of the system (processors, memories and communication network) and the collection of all instructions has a rich mathematical structure that facilitates automatic transformation of user programs into sequences of basic instructions. Problem partitioning is based on a simple geometric rule implemented in hardware. As a result, many difficult problems arising in parallel architectures (such as load balancing, data routing, memory access conflicts etc.) are solved efficiently, without programmer intervention.
I will also present simulation results on large-scale problems arising in linear programming, solution of partial differential equations, signal processing, control systems and simulation of non-linear electronic circuits.
BIOGRAPHICAL SKETCH
Dr. Narendra Karmarkar received his Ph.D. in Computer Science from University of California, Berkeley in 1983. Since 1983 he has been a Member of Technical Staff, Mathematical Sciences Research Center, AT&T Bell Laboratories, Murray Hill, New Jersey.
He received the Lancaster Prize of the Operations Research Society of American for the best published contributions to operations research in the year 1984. AT&T honored him with a ``fellow'' of Bell Laboratories designation in the year 1986. He received the Fulkerson Prize in discrete mathematics given jointly by American Mathematical Society and Mathematical Programming Society in the year 1988.
He has received several patents for original invention in the field of linear programming and its implementation.
Thus, very loosely speaking, zero--knowledge is either useless (exists only for ``easy'' languages), or universal (exists for every provable language).
The talk will be self-contained.
Joint work with Avi Wigderson. The paper is to appear in the Israel Symposium on Theory of Computing and Systems (ISTCS93) this summer, where it won the Henry Taub Award.
I will then review applications of SDP to combinatorial optimization. The most striking application arises in Lovasz number of graphs, an invariant of graphs which is simultaneously an upper bound on the maximum clique and a lower bound on minimum coloring of a graph. Furthermore, this invariant is polynomial-time computable by virtue of the ellipsoid method. However, I will show that interior point methods also result in polytime algorithms for SDP in general, and Lovasz number in particular.
I will sketch a particular primal-dual method for solving SDP and argue that any linear programming interior point method can be mechanically transformed into a similar algorithm for SDP. As a result we can get a sublinear-time parallel algorithm for computing maximum cliques in perfect graphs (that is graphs for which clique number equals chromatic number and the same is true for all induced subgraphs). If there is time, I will also review a generalization of Lovasz numbers due to Narasimhan and Manber and derive some characterization of it.
Like computer algorithms, robot algorithms are abstractions that can be designed and analyzed independent of any particular technology. Moreover, algorithms based on very different principles can be used to perform the same task. However, robot algorithms also differ in significant ways from computer algorithms. While the latter apply to data that can be observed and acted upon without uncertainty (letting aside a few problems such as finite-precision arithmetics), robot algorithms apply to physical objects, which they attempt to control despite, or thanks to, the laws of nature. The real world is also so complex that, for most tasks, the set of states that may have to be considered by a robot algorithm is too large to be explicitly anticipated. Hence, most robot algorithms must incorporate a planner whose role is to dynamically change the control part of the algorithm. But many planning problems are known to be computationally hard. Hence, robot algorithms blend fundamental control issues (reachability and recognizability of states) and computational issues (computability, complexity) in a unique fashion.
Investigating robot algorithms casts new light on Robotics. As our understanding of these algorithms matures, robots will more and more appear as machines executing robot algorithms, just as computers are machines executing computation algorithms, independent of any ephemeral technology.
Applications to various problems and research areas motivate extensions of the ideas of shape and subcomplexes in a number of directions. For modeling molecules, it is important to understand the deeper connections between shapes and the popular space filling diagrams. For surface reconstruction methods it is necessary to vary the degree of detail at different places in space.
(Talk includes a demo on an SGI workstation).
We present a more natural algorithm that outperforms List whenever $m\ge6$ and has a competitive ratio of at most $(2 - .055) \approx 1.945$ for all $m$, which is significantly closer to the best known lower bound of $1.837$ for the problem. Our proof of this is computer aided because we need to solve many large linear programs. We then show that the analysis of our algorithm is almost tight by presenting a lower bound of $(2 - .0622)$ on its competitive ratio for large $m$.
This is joint work with David Karger and Steven Phillips of Stanford University.
Our solution is based on a bound that we obtain on the maximum combinatorial complexity of a single connected component in the three-dimensional configuration space of B, and on the ability to efficiently compute such a component. More specifically, assuming the polygon B has a constant number of sides and the obstacles are bounded by $n$ edges, we show that the complexity of a single connected component of the configuration space is $O(n^{2+\epsilon})$ for any $\epsilon>0$, where the constant of proportionality depends on $\epsilon$. We also present an algorithm for constructing a single component in $O(n^{2+\epsilon})$ time, for any $\epsilon>0$.
In the talk I'll also review related work in algorithmic motion planning in robotics as well as in the area of arrangements of surfaces, with an emphasis on recent advances in the study of the `lower envelope' and `single cell' problems.
This is joint work with Micha Sharir.
min multicut <= max flow <= min multicut
O(log k)
where k is the number of commodities.
A tighter approximate max-flow min-multicut theorem can be obtained for multicommodity flow on trees. This setting also captures a surprisingly rich collection of problems.
(The sorting results are joint with Mark Nodine and with Liddy Shriver. The online range searching results are joint with Paris Kanellakis, Sridhar Ramaswamy, and Darren Vengroff. The geometry results are joint with Mike Goodrich, J.-J. Tsay, and Darren Vengroff.)