Last update:
Sat Jul 22 16:57:10 MDT 2017
Noam Nisan and
Amnon Ta-Shma Symmetric \em Logspace is Closed Under
Complement . . . . . . . . . . . . . . .
Vince Grolmusz On the Weak $\bmod m$ Representation of
Boolean Functions . . . . . . . . . . .
Nils Klarlund and
Dexter Kozen Rabin Measures . . . . . . . . . . . . .
Anne Condon and
Joan Feigenbaum and
Carsten Lund and
Peter W. Shor Probabilistically Checkable Debate
Systems and Nonapproximability of
PSPACE-Hard Functions . . . . . . . . .
Moshe Y. Vardi Rank Predicates vs. Progress Measures in
Concurrent-Program Verification . . . .
Mitsunori Ogihara Sparse Hard Sets for P Yield
Space-Efficient Algorithms . . . . . . .
Ornan Gerstel and
Israel Cidon and
Shmuel Zaks Optimal Virtual Path Layout in ATM
Networks With Shared Routing Table
Switches . . . . . . . . . . . . . . . .
Gerhard Buntrock and
Gundula Niemann Weakly Growing Context-Sensitive
Grammars . . . . . . . . . . . . . . . .
H. James Hoover and
Piotr Rudnicki Uniform Self-Stabilizing Orientation of
Unicyclic Networks under Read/Write
Atomicity . . . . . . . . . . . . . . .
Martin Middendorf Manhattan Channel Routing is NP-complete
Under Truly Restricted Settings . . . .
Uriel Feige and
Joe Kilian On Limited versus Polynomial
Nondeterminism . . . . . . . . . . . . .
Viggo Kann and
Sanjeev Khanna and
Jens Lagergren and
Alessandro Panconesi On the Hardness of Approximating Max
$k$-Cut and its Dual . . . . . . . . . .
George Varghese and
Anish Arora and
Mohamed Gouda Self-Stabilization by Tree Correction
Shlomi Dolev and
Ted Herman Superstabilizing Protocols for Dynamic
Distributed Systems . . . . . . . . . .
Meena Mahajan and
V. Vinay Determinant: Combinatorics, Algorithms,
and Complexity . . . . . . . . . . . . .
Thomas Thierauf The Isomorphism Problem for Read-Once
Branching Programs and Arithmetic
Circuits . . . . . . . . . . . . . . . .
Orna Kupferman and
Moshe Y. Vardi Verification of Fair Transition Systems
Yehuda Afek and
Anat Bremler Self-Stabilizing Unidirectional Network
Algorithms by Power Supply . . . . . . .
Sandeep S. Kulkarni and
Anish Arora Multitolerance in Distributed Reset . .
Ted Herman Working Paper: A Comprehensive
Bibliography on Self-Stabilization . . .
Robert Beals and
Richard Chang and
William Gasarch and
Jacobo Torán On Finding the Number of Graph
Automorphisms . . . . . . . . . . . . .
Jie Wang Randomized Reductions and Isomorphisms
Stephen Fenner and
Frederic Green and
Steven Homer and
Alan L. Selman and
Thomas Thierauf and
Heribert Vollmer Complements of Multivalued Functions . .
Christoph Karg and
Johannes Köbler and
Rainer Schuler The Complexity of Generating Test
Instances . . . . . . . . . . . . . . .
Joan Feigenbaum and
Sampath Kannan and
Moshe Y. Vardi and
Mahesh Viswanathan The Complexity of Problems on Graphs
Represented as OBDDs . . . . . . . . . .
Arun Jagota Hopfield Neural Networks and
Self-Stabilization . . . . . . . . . . .
Eric Allender The Permanent Requires Large Uniform
Threshold Circuits . . . . . . . . . . .
Jeff Erickson Bounds for Linear Satisfiability
Problems . . . . . . . . . . . . . . . .
Martha J. Kosa Time Bounds for Strong and Hybrid
Consistency for Arbitrary Abstract Data
Types . . . . . . . . . . . . . . . . .
Zeev Collin and
Rina Dechter and
Shmuel Katz Self-Stabilizing Distributed Constraint
Satisfaction . . . . . . . . . . . . . .
Ramamohan Paturi and
Pavel Pudlak and
Francis Zane Satisfiability Coding Lemma . . . . . .
Jorg Rothe Heuristics Versus Completeness for Graph
Coloring . . . . . . . . . . . . . . . .
Manindra Agrawal and
Eric Allender and
Samir Datta and
Heribert Vollmer and
Klaus W. Wagner Characterizing Small Depth and Small
Space Classes by Operators of Higher
Type . . . . . . . . . . . . . . . . . .
Ulrich Schmid Orthogonal Accuracy Clock
Synchronization . . . . . . . . . . . .
William Aiello and
Costas Busch and
Maurice Herlihy and
Marios Mavronicolas and
Nir Shavit and
Dan Touitou Supporting Increment and Decrement
Operations in Balancing Networks . . . .
Jeffrey Beauquier and
Ajoy K. Datta and
Maria Gradinariu and
Frederic Magniette Self-Stabilizing Local Mutual Exclusion
and Definition Refinement . . . . . . .
V. Arvind and
K. V. Subrahmanyam and
N. V. Vinodchandran The Query Complexity of Program Checking
by Constant-Depth Circuits . . . . . . .