Martin Tompa

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.

FOCS Conference 1990 Conference Paper

Communication-Space Tradeoffs for Unrestricted Protocols

• Paul Beame
• Martin Tompa
• Peiyuan Yan

Communicating branching programs are introduced, and a general technique for demonstrating communication-space tradeoffs for pairs of communicating branching programs is developed. The technique is used to prove communication-space tradeoffs for any pair of communicating branching programs that hashes according to a universal family of hash functions. Other tradeoffs follow from this result. For example any pair of communicating Boolean branching programs that computes matrix-vector products over GF(2) requires communication-space product Omega (n/sup 2/). These are the first examples of communication-space tradeoffs on a completely general model of communicating processes. >

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. >

STOC Conference 1989 Conference Paper

Lower Bounds on the Length of Universal Traversal Sequences (Detailed Abstract)

• Allan Borodin
• Walter L. Ruzzo
• Martin Tompa

I&C Journal 1989 Journal Article

Parallei graph algorithms that are efficient on average

• Don Coppersmith
• Prabhakar Raghavan
• Martin Tompa

The following three problems concerning random graphs can be solved in (logn) O(1)expected time using linearly many processors: (1) finding the lexicographically first maximal independent set, (2) coloring the vertices using a number of colors that is almost surely within twice the chromatic number, and (3) finding a Hamiltonian circuit.

STOC Conference 1989 Conference Paper

Tradeoffs Between Communication and Space

• Tak Wah Lam
• Prasoon Tiwari
• Martin Tompa

TARK Conference 1988 Conference Paper

Zero Knowledge Interactive Proofs of Knowledge (A Digest)

• Martin Tompa

FOCS Conference 1987 Conference Paper

Parallel Graph Algorithms that Are Efficient on Average

• Don Coppersmith
• Prabhakar Raghavan
• Martin Tompa

The following three problems concerning random graphs can be solved in (log n)O(1) expected time using linearly many processors: (1) finding the lexicographically first maximal independent set, (2) coloring the vertices using a number of colors that is almost surely within twice the chromatic number, and (3) finding a Hamiltonian circuit.

FOCS Conference 1987 Conference Paper

Random Self-Reducibility and Zero Knowledge Interactive Proofs of Possession of Information

• Martin Tompa
• Heather Woll

The notion of a zero knowledge interactive proof that one party "knows" some secret information is explored. It is shown that any "random self-reducible" problem has a zero knowledge interactive proof of this sort. The zero knowledge interactive proofs for graph isomorphism, quadratic residuosity, and "knowledge" of discrete logarithms all follow as special cases. Based on these results, new zero knowledge interactive proofs are exhibited for "knowledge" of the factorization of an integer, nonmembership in cyclic subgroups of Zp*, and determining whether an element generates Zp*. None of these proofs relies on any unproven assumptions.

FOCS Conference 1986 Conference Paper

A New Pebble Game that Characterizes Parallel Complexity Classes

• H. Venkateswaran
• Martin Tompa

A new two-person pebble game that models parallel computations is defined. This game extends the two-person pebble game defined in [DT85] and is used to characterize two natural parallel complexity classes, namely LOGCFL and AG1. The characterizations show a fundamental way in which the computations in these two classes differ. This game model also unifies the proofs of some well known results of complexity theory.

STOC Conference 1985 Conference Paper

The Parallel Complexity of Exponentiating Polynomials over Finite Fields

• Faith Ellen
• Martin Tompa

STOC Conference 1983 Conference Paper

Speedups of Deterministic Machines by Synchronous Parallel Machines

• Patrick W. Dymond
• Martin Tompa

STOC Conference 1982 Conference Paper

Probabilistic, Nondeterministic, and Alternating Decision Trees

• Udi Manber
• Martin Tompa

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

FOCS Conference 1981 Conference Paper

The Effect of Number of Hamiltonian Paths on the Complexity of a Vertex-Coloring Problem

• Udi Manber
• Martin Tompa

A generalization of Dobkin and Lipton's element uniqueness problem is introduced: for any fixed undirected graph G on vertex set {v1, v2, .. ., vn}, the problem is to determine, given n real numbers x1, x2, .. ., xn, whether xi ≠ xj for every edge {vi, vj} in G. This problem is shown to have upper and lower bounds of Θ(nlogn) linear comparisons if G is any dense graph. The proof of the lower bound involves showing that any dense graph must contain a subgraph with many Hamiltonian paths, and demonstrating the relevance of these Hamiltonian paths to a geometric argument. In addition, we exhibit relatively sparse graphs for which the same lower bound holds, and relatively dense graphs for which a linear upper bound holds.

STOC Conference 1980 Conference Paper

An Optimal Solution to a Wire-Routing Problem (Preliminary Version)

• Martin Tompa

STOC Conference 1980 Conference Paper

Two Familiar Transitive Closure Algorithms which Admit No Polynomial Time, Sublinear Space Implementations

• Martin Tompa

FOCS Conference 1979 Conference Paper

A Time-Space Tradeoff for Sorting on Non-Oblivious Machines

• Allan Borodin
• Michael J. Fischer
• David G. Kirkpatrick
• Nancy A. Lynch
• Martin Tompa

A model of computation is introduced which permits the analysis of both the time and space requirements of non-oblivious programs. Using this model, it is demonstrated that any algorithm for sorting n inputs which is based on comparisons of individual inputs requires time-space product proportional to n2. Uniform and non-uniform sorting algorithms are presented which show that this lower bound is nearly tight.

STOC Conference 1978 Conference Paper

Time-Space Tradeoffs for Computing Functions, Using Connectivity Properties of their Circuits

• Martin Tompa

Recent research has investigated time-space tradeoffs for register allocation strategies of certain fixed sets of expressions. This paper is concerned with the time-space tradeoff for register allocation strategies of any set of expressions which compute given functions. Time-space tradeoffs for pebbling superconcentrators and grates are developed. Corollaries which follow include tradeoffs for any straight-line program which computes polynomial multiplication, polynomial convolution, the discrete Fourier transform, oblivious merging, and most sets of linear forms.