1. On Limited versus Polynomial Nondeterminism by Uriel Feige and Joe Kilian, 12 March 1997

   In this paper, we show that efficient algorithms for some problems that require limited nondeterminism imply the subexponential simulation of nondeterministic computation by deterministic computation. In particular, if cliques of size O(log n) can be found in polynomial time, then nondeterministic time f(n) is contained in deterministic time 2^{O(\sqrt{f(n)polylog f(n)})}.




2. On the Hardness of Approximating Max k-Cut and Its Dual by Viggo Kann, Sanjeev Khanna, Jens Lagergren, Alessandro Panconesi, 3 June 1997

   We study the Max k-Cut problem and its dual, the Min k-Partition problem. In the Min k-Partition problem, given a graph G=(V,E) and positive edge weights, we want to find an edge set of minimum weight whose removal makes G k-colorable. For the Max k-Cut problem we show that, if P&neq;NP, no polynomial time approximation algorithm can achieve a relative error better than 1/34k. It is well known that a relative error of 1/k is obtained by a naive randomized heuristic.

   For the Min k-Partition problem, we show that for k>2 and for every epsilon>0, there exists a constant alpha such that the problem cannot be approximated within alpha|V^(2-epsilon)|, even for dense graphs. Both problems are directly related to the frequency allocation problem for cellular (mobile) telephones, an application of industrial relevance.




3. Self-Stabilization by Tree Correction by George Varghese, Anish Arora, and Mohamed Gouda, (Special Issue on Self-Stabilization, Shlomi Dolev and Jennifer Welch editors)4 November 1997

   We describe a simple tree-correction theorem that states that any locally checkable protocol that works on a tree can be efficiently stabilized in time proportional to the height of the tree. We show how new protocols can be designed, and how existing work can be easily understood using this theorem.




4. Superstabilizing Protocols for Dynamic Distributed Systems by Shlomi Dolev and Ted Herman, (Special Issue on Self-Stabilization, Shlomi Dolev and Jennifer Welch editors), 19 December 1997

   Two aspects of distributed-protocol reliability are the ability to recover from transient faults and the ability to function in a dynamic environment. Approaches for both of these aspects have been separately developed, but have revealed drawbacks when applied to environments with both transient faults and dynamic changes. This paper introduces definitions and methods for addressing both concerns in system design.

   A protocol is superstabilizing if it is (1) self-stabilizing, meaning that it is guaranteed to respond to an arbitrary transient fault by eventually satisfying and maintaining a legitimacy predicate, and it is (2) guaranteed to satisfy a passage predicate at all times when the system undergoes topology changes starting from a legitimate state. The passage predicate is typically a safety property that should hold while the protocol makes progress toward reestablishing legitimacy following a topology change.

   Specific contributions of the paper include: the definition of the class of superstabilizing protocols; metrics for evaluating superstabilizing protocols; superstabilizing protocols for coloring and spanning tree construction; a general method for converting self-stabilizing protocols into superstabilizing ones; and a generalized form of a self-stabilizing topology update protocol which may have useful applications for other research.




5. Determinant: Combinatorics, Algorithms, and Complexity by Meena Mahajan and V. Vinay, 31 December 1997

   We prove a new combinatorial characterization of the determinant. The characterization yields a simple combinatorial algorithm for computing the determinant. Hitherto, all (known) algorithms for the determinant have been based on linear algebra. Our combinatorial algorithm requires no division, and works over arbitrary commutative rings. It also lends itself to efficient parallel implementations.

   It has been known for some time now that the complexity class GapL characterizes the complexity of computing the determinant of matrices over the integers. We present a direct proof of this characterization.

Volume 1996 Abstracts

Volume 1998 Abstracts

Volume 1997

Published articles

Last modified: Tue Mar 10 20:34:52 CST