Arrow Research search

Author name cluster

Walter L. Ruzzo

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

11 papers
2 author rows

Possible papers

11

I&C Journal 1996 Journal Article

Time-Space Tradeoffs for Undirected Graph Traversal by Graph Automata

  • Paul Beame
  • Allan Borodin
  • Prabhakar Raghavan
  • Walter L. Ruzzo
  • Martin Tompa

We investigate time-space tradeoffs for traversing undirected graphs, using a variety of structured models that are all variants of Cook and Rackoff's “Jumping Automata for Graphs. ” Our strongest tradeoff is a quadratic lower bound on the product of time and space for graph traversal. For example, achieving linear time requires linear space, implying that depth-first search is optimal. Since our bound in fact applies to nondeterministic algorithms fornonconnectivity, it also implies that closure under complementation of nondeterministic space-bounded complexity classes is achieved only at the expense of increased time. To demonstrate that these structured models are realistic, we also investigate their power. In addition to admitting well known algorithms such as depth-first search and random walk, we show that one simple variant of this model is nearly as powerful as a Turing machine. Specifically, for general undirected graph problems, it can simulate a Turing machine with only a constant factor increase in space and a polynomial factor increase in time.

Details DOI

FOCS Conference 1990 Conference Paper

Time-Space Tradeoffs for Undirected Graph Traversal

  • Paul Beame
  • Allan Borodin
  • Prabhakar Raghavan
  • Walter L. Ruzzo
  • Martin Tompa

Time-space tradeoffs for traversing undirected graphs are proved. One of these tradeoffs is a quadratic lower bound on a deterministic model that closely matches the probabilistic upper bound of A. Z. Broder et al. (1989). The models used are variants of S. A. Cook and C. W. Rackoff's (1980) jumping automata for graphs. Some open problems are stated. >

Details

I&C Journal 1989 Journal Article

The iterated mod problem

  • Howard J. Karloff
  • Walter L. Ruzzo

The iterated mod problem is this: given a, b 1, b 2, …, b n, all integers or all polynomials in Q [x], is ((… ((a mod b 1) mod b 2) …) mod b n ) = 0? When the inputs are integers, we prove the problem P-complete with respect to log-space reductions, whereas in the polynomial case, we prove the problem is in NC. The significance of these results lies primarily in the similarity between the iterated mod problem and the Euclidean algorithm. We also show that the superincreasing knapsack problem is P-complete, using a very similar proof.

Details DOI

STOC Conference 1982 Conference Paper

Space-Bounded Hierarchies and Probabilistic Computations

  • Walter L. Ruzzo
  • Janos Simon
  • Martin Tompa

This paper studies two aspects of the power of space-bounded probabilistic Turing machines. Section 2 presents a simple alternative proof of Simon's recent result [13] that space-bounded probabilistic complexity classes are closed under complement. Section 3 demonstrates that any language in the log n space hierarchy can be recognized by an log n space-bounded probabilistic Turing machine with small error; this is a generalization of Gill's result that any language in NSPACE(log n) can be recognized by such a machine

Details

FOCS Conference 1979 Conference Paper

On Uniform Circuit Complexity (Extended Abstract)

  • Walter L. Ruzzo

We consider uniform circuit complexity, introduced by Borodin as a model of parallel complexity. Three main results are presented. First, we show that simultaneous size/depth of uniform circuits is the same as space/time of alternating Turing machines, with depth and time within a constant factor and likewise log(size) and space. Second, we apply this to characterize the class of polynomial size and polynomial-in-log depth circuits in terms of tree-size bounded alternating TM's, in particular showing that context-free recognition is in this class of circuits. Third, we investigate various definitions of uniform circuit complexity, showing that it is fairly insensitive to the choice of definition.

Details

STOC Conference 1979 Conference Paper

Tree-Size Bounded Alternation

  • Walter L. Ruzzo

The size of an accepting computation tree of an alternating Turing machine (ATM) is introduced as a complexity measure. Tree-size on ATM's is shown to closely correspond to time on nondeterministic TM's and on nondeterministic auxiliary pushdown automata. The later gives a useful new characterization of the class of languages log-space-reducible to context-free languages. Relationships with parallel-time complexity are also explored. ATM computations using at most space S(n) and tree-size Z(n) (simultaneously) can be simulated in alternating time S(n).log Z(n). Several well-known simulations, e.g., Savitch's theorem, are special cases of this result. It also leads to improved parallel-time bounds for many problems, e.g., context-free language recognition in time 0(log 2 n) on several parallel models.

Details

STOC Conference 1976 Conference Paper

On Line Context Free Language Recognition in Less than Cubic Time (Extended Abstract)

  • Susan L. Graham
  • Michael A. Harrison
  • Walter L. Ruzzo

A new on-line context free language recognition algorithm is presented which is derived from Earley's algorithm and has several advantages over the original. First, the new algorithm not only is conceptually simpler than Earley's, but also allows significant speed improvements. Second, our algorithm serves to explain the connections between Earley's algorithm and the Cocke-Kasami-Younger algorithm. Third, our algorithm allows an implementation which uses only 0(n 2 /log n) operations on bit vectors of length n, or 0(n 3 /log n) operations on a RAM. This makes it the fastest known on-line context free language recognition algorithm.

Details
v2026.09.13