1. The Isomorphism Problem for Read-Once Branching Programs and Arithmetic Circuits by Thomas Thierauf (Special Issue on Computational Complexity from the 1996 Dagstuhl-Seminar, Eric Allender editor), 10 March 1998

   We investigate the computational complexity of the isomorphism problem for read-once branching programs (1-BPI): upon input of two read-once branching programs B_0 and B_1, decide whether there exists a permutation of the variables of B_1 such that it becomes equivalent to B_0.

   Our main result is that 1-BPI cannot be NP-hard unless the polynomial hierarchy collapses. The result is extended to the isomorphism problem for arithmetic circuits over large enough fields.

   We use the known arithmetization of read-once branching programs and arithmetic circuits into multivariate polynomials over the rationals. Hence, another way of stating our result is: the isomorphism problem for multivariate polynomials over large enough fields is not NP-hard unless the polynomial hierarchy collapses.

   We derive this result by providing a two-round interactive proof for the nonisomorphism problem for multivariate polynomials. The protocol is based on the Schwartz-Zippel theorem for probabilistically checking polynomial identities.

   Finally, we show that there is a perfect zero-knowledge interactive proof for the isomorphism problem for multivariate polynomials.




2. Verification of Fair Transition Systems by Orna Kupferman and Moshe Y. Vardi, 16 March 1998

   In program verification, we check that an implementation meets its specification. Both the specification and the implementation describe the possible behaviors of the program, although at different levels of abstraction. We distinguish between two approaches to implementation of specifications. The first approach is trace-based implementation, where we require every computation of the implementation to correlate to some computation of the specification. The second approach is tree-based implementation, where we require every computation tree embodied in the implementation to correlate to some computation tree embodied in the specification. The two approaches to implementation are strongly related to the linear-time versus branching-time dichotomy in temporal logic.

   In this work, we examine the trace-based and the tree-based approaches from a complexity-theoretic point of view. We consider and compare the complexity of verification of fair transition systems, modeling both the implementation and the specification in the two approaches. We consider unconditional, weak, and strong fairnesses. For the trace-based approach, the corresponding problem is fair containment. For the tree-based approach, the corresponding problem is fair simulation. We show that while both problems are PSPACE-complete, their complexities in terms of the size of the implementation do not coincide, and the trace-based approach is easier. As the implementation is normally much bigger than the specification, we see this as an advantage of the trace-based approach. Our results are at variance with the known results for the case of transition systems with no fairness, where no approach is evidently advantageous.




3. Self-Stabilizing Unidirectional Network Algorithms by Power Supply by Yehuda Afek and Anat Bremler (Special Issue on Self-Stabilization, Shlomi Dolev and Jennifer Welch editors), 7 December 1998

   Power supply, a surprisingly simple and new general paradigm for the development of self-stabilizing algorithms in different models, is introduced. The paradigm is exemplified by developing simple and efficient self-stabilizing algorithms for leader election and either breadth-first search or depth-first search spanning-tree constructions, in strongly connected unidirectional and bidirectional dynamic networks (synchronous and asynchronous). The different algorithms stabilize in O(n) time in both synchronous and asynchronous networks without assuming any knowledge of the network topology or size, where n is the total number of nodes. Following the leader election algorithms, we present a generic self-stabilizing spanning tree and/or leader election algorithm that produces a whole spectrum of new and efficient algorithms for these problems. Two variations that produce either a rooted depth-first search tree or a rooted breadth-first search tree are presented.




4. Multitolerance in Distributed Reset by Sandeep S. Kulkarni and Anish Arora (Special Issue on Self-Stabilization, Shlomi Dolev and Jennifer Welch editors), 7 December 1998

   A reset of a distributed system is safe if it does not complete ``prematurely,'' i.e., without having reset some process in the system. Safe resets are possible in the presence of certain faults, such as process fail-stops and repairs, but are not always possible in the presence of more general faults, such as arbitrary transients. In this paper, we design a bounded-memory distributed-reset program that possesses two tolerances: (1) in the presence of fail-stops and repairs, it always executes resets safely, and (2) in the presence of a finite number of transient faults, it eventually executes resets safely. Designing this multitolerance in the reset program introduces the novel concern of designing a safety detector that is itself multitolerant. A broad application of our multitolerant safety detector is to make any total program likewise multitolerant.

Volume 1997 Abstracts

Volume 1999 Abstracts

Volume 1998

Published articles

Last modified: Tue Feb 9 20:56:58 CST 1999