Arrow Research search

Author name cluster

Zvi Galil

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.

60 papers
2 author rows

Possible papers

60

FOCS Conference 1995 Conference Paper

Resolving Message Complexity of Byzantine Agreement and beyond

  • Zvi Galil
  • Alain J. Mayer
  • Moti Yung

Byzantine Agreement among processors is a basic primitive in distributed computing. It comes in a number of basic fault models: "Crash", "Omission" and "Malicious" adversarial behaviors. The message complexity of the primitive has been known for the strong failure models of Malicious and Omission adversary since the early 80's, while the question for the more benign Crash failure model has been open. We show how to solve agreement in the presence of crash failures using O(n) messages which is optimal, thus settling a thirteen year old open problem. Our solution has almost linear time and our new algorithmic techniques have further implications: a family of "early stopping" agreement protocols with improved message-complexity; and a new solution to "Checkpoint" yielding a substantial improvement of the protocol for distributed work performance under adaptive parallelism in a network of workstations.

Details

FOCS Conference 1993 Conference Paper

Eavesdropping Games: A Graph-Theoretic Approach to Privacy in Distributed Systems

  • Matthew K. Franklin
  • Zvi Galil
  • Moti Yung

We initiate a graph-theoretic approach to study the (information-theoretic) maintenance of privacy in distributed environments in the presence of a bounded number of mobile eavesdroppers ("bugs"). For two fundamental privacy problems-secure message transmission and distributed database maintenance-we assume an adversary is "playing eavesdropping games, " coordinating the movement of the bugs among the sites to learn the current memory contents. We consider various mobility settings (adversaries), motivated by the capabilities (strength) of the bugging technologies (e. g. , how fast can a bug be reassigned). We combinatorially characterize and compare privacy maintenance problems, determine their feasibility (under numerous bug models), suggest protocols for the feasible cases, and analyze their computational complexity. >

Details

FOCS Conference 1993 Conference Paper

Optimally fast parallel algorithms for preprocessing and pattern matching in one and two dimensions

  • Richard Cole 0001
  • Maxime Crochemore
  • Zvi Galil
  • Leszek Gasieniec
  • Ramesh Hariharan
  • S. Muthukrishnan 0001
  • Kunsoo Park
  • Wojciech Rytter

All algorithms below are optimal alphabet-independent parallel CRCW PRAM algorithms. In one dimension: Given a pattern string of length m for the string-matching problem, we design an algorithm that computes a deterministic sample of a sufficiently long substring in constant time. This problem used to be a bottleneck in the pattern preprocessing for one- and two-dimensional pattern matching. The best previous time bound was O(log/sup 2/ m/log log m). We use this algorithm to obtain the following results. 1. Improving the preprocessing of the constant-time text search algorithm from O(log/sup 2/ m/log log m) to n(log log m), which is now best possible. 2. A constant-time deterministic string-matching algorithm in the case that the text length n satisfies n=/spl Omega/(m/sup 1+/spl epsiv//) for a constant /spl epsiv/>0. 3. A simple probabilistic string-matching algorithm that has constant time with high probability for random input. 4. A constant expected time Las-Vegas algorithm for computing the period of the pattern and all witnesses and thus string matching itself, solving the main open problem remaining in string matching. >

Details

FOCS Conference 1993 Conference Paper

When can we sort in o(n log n) time?

  • Amir M. Ben-Amram
  • Zvi Galil

We define two conditions on a random access machine (RAM) with arithmetic and Boolean instructions and possible bounds on word and memory sizes. One condition asserts that we either restrict attention to short words or allow non-uniform programs. The second asserts that we either allow a large memory or a double-precision multiplication. Our main theorem shows that the RAM can sort in o(nlog n) time if and only if both of these conditions hold. This theorem breaks down into four upper bounds only one of which has been known before, and two lower bounds neither of which has been known. >

Details

FOCS Conference 1992 Conference Paper

Sparsification-A Technique for Speeding up Dynamic Graph Algorithms (Extended Abstract)

  • David Eppstein
  • Zvi Galil
  • Giuseppe F. Italiano
  • Amnon Nissenzweig

The authors provide data structures that maintain a graph as edges are inserted and deleted, and keep track of the following properties: minimum spanning forests, best swap, graph connectivity, and graph 2-edge-connectivity, in time O(n/sup 1/2/log(m/n)) per change; 3-edge-connectivity, in time O(n/sup 2/3/) per change; 4-edge-connectivity, in time O(n alpha (n)) per change; k-edge-connectivity, in time O(n log n) per change; bipartiteness, 2-vertex-connectivity, and 3-vertex-connectivity, in time O(n log(m/n)) per change; and 4-vertex-connectivity, in time O(n log(m/n)+n alpha (n)) per change. Further results speed up the insertion times to match the bounds of known partially dynamic algorithms. The algorithms are based on a technique that transforms algorithms for sparse graphs into ones that work on any graph, which they call sparsification. >

Details

FOCS Conference 1992 Conference Paper

Truly Alphabet-Independent Two-Dimensional Pattern Matching

  • Zvi Galil
  • Kunsoo Park

A. Amir, G. Benson and M. Farach (see Proc. 24th STOC, p. 59-68 (1992)) gave an algorithm for two-dimensional pattern matching (ABF for short) whose text processing is independent of the alphabet and takes O(n/sup 2/) time, but whose pattern processing is dependent on the alphabet and takes O(m/sup 2/log mod Sigma mod ) time. The authors present an algorithm that is truly independent of the alphabet and takes linear O(m/sup 2/+n/sup 2/) time. As in the Knuth-Morris-Pratt algorithm, the only operation on the alphabet is the equality test of two symbols. All previous algorithms except the ABF algorithm reduce the two-dimensional problem into one-dimensional string matching, and use known techniques in string matching. The ABF algorithm uses two-dimensional periodicity for text processing, but their pattern processing resorts to one-dimensional techniques. The authors present a two-dimensional technique for both pattern processing and text processing. >

Details

FOCS Conference 1992 Conference Paper

Witnesses for Boolean Matrix Multiplication and for Shortest Paths

  • Noga Alon
  • Zvi Galil
  • Oded Margalit
  • Moni Naor

The subcubic (O(n/sup w/) for w(3) algorithms to multiply Boolean matrices do not provide the witnesses; namely, they compute C=A. B but if C/sub ij/=1 they do not find an index k (a witness) such that A/sub ik/=B/sub kj/=1. The authors design a deterministic algorithm for computing the matrix of witnesses that runs in O(n/sup w/) time, where here O(n/sup w/) denotes O(n/sup w/(log n)/sup O(1)/). The subcubic methods to compute the shortest distances between all pairs of vertices also do not provide for witnesses; namely they compute the shortest distances but do not generate information for computing quickly the paths themselves. A witness for a shortest path from v/sub i/ to v/sub j/ is an index k such that v/sub k/ is the first vertex on such a path. They describe subcubic methods to compute such witnesses for several versions of the all pairs shortest paths problem. As a result, they derive shortest paths algorithms that provide characterization of the shortest paths in addition to the shortest distances in the same time (up to a polylogarithmic factor) needed for computing the distances; namely O(n/sup (3+w)/2/) time in the directed case and O(n/sup w/) time in the undirected case. They also design an algorithm that computes witnesses for the transitive closure in the same time needed to compute witnesses for Boolean matrix multiplication. >

Details

FOCS Conference 1991 Conference Paper

Lower Bounds for Data Structure Problems on RAMs (Extended Abstract)

  • Amir M. Ben-Amram
  • Zvi Galil

A technique is described for deriving lower bounds and tradeoffs for data structure problems. Two quantities are defined. The output variability depends only on the model of computation. It characterizes in some sense the power of a model. The problem variability depends only on the problem under consideration. It characterizes in some sense the difficulty of the problem. The first theorem states that if a model's output variability is smaller than the problem variability, a lower bound on the worst case (average case) time for the problem follows. A RAM that can add, subtract and compare unbounded integers is considered. The second theorem gives an upper bound on the output variability of this model. The two theorems are used to derive lower bounds for the union-find problem in this RAM. >

Details

FOCS Conference 1990 Conference Paper

Faster Tree Pattern Matching

  • Moshe Dubiner
  • Zvi Galil
  • Edith Magen

Recently, R. Kosaraju (Proc. 30th IEEE Symp. on Foundations of Computer Science, 1989, p. 178-83) gave an O(nm/sup 0. 75/ polylog(m))-step algorithm for tree pattern matching. The authors improve this result by designing a simple O(n square root m polylog (m)) algorithm. >

Details

FOCS Conference 1990 Conference Paper

On the Exact Complexity of String Matching (Extended Abstract)

  • Livio Colussi
  • Zvi Galil
  • Raffaele Giancarlo

The maximal number of character comparisons made by a linear-time string matching algorithm, given a text string of length n and a pattern string of length m over a general alphabet, is investigated. The number is denoted by c(n, m) or approximated by (1+C)n, where C is a universal constant. The subscript 'online' is added when attention is restricted to online algorithms, and the superscript '1' is added when algorithms that find only one occurrence of the pattern in the text are considered. It is well known that n >

Details

FOCS Conference 1988 Conference Paper

On Pointers versus Addresses (Extended Abstract)

  • Amir M. Ben-Amram
  • Zvi Galil

The problem of determining the cost of random-access memory (RAM) is addressed by studying the simulation of random addressing by a machine which lacks it, called a pointer machine. The model allows the use of a data type of choice. A RAM program of time t and space s can be simulated in O(t log s) time using a tree. However, this is not an obvious lower bound since a high-level data type can allow the data to be encoded in a more economical way. The major contribution is the formalization of incompressibility for general data types. The definition extends a similar property of strings that underlies the theory of Kolmogorov complexity. The main theorem states that for all incompressible data types an Omega (t log s) lower bound holds. Incompressibility is proved for the real numbers with a set of primitives which includes all functions which are continuously differentiable except on a countable closed set. >

Details

FOCS Conference 1988 Conference Paper

Speeding up Dynamic Programming

  • David Eppstein
  • Zvi Galil
  • Raffaele Giancarlo

A number of important computational problems in molecular biology, geology, speech recognition, and other areas can be expressed as recurrences which have typically been solved with dynamic programming. By using more sophisticated data structures, and by taking advantage of further structure from the applications, the authors speed up the computation of several of these recurrences by one or two orders of magnitude. The algorithms used are simple and practical. >

Details

FOCS Conference 1987 Conference Paper

Two Lower Bounds in Asynchronous Distributed Computation (Preliminary Version)

  • Pavol Duris
  • Zvi Galil

We introduce new techniques for deriving lower bounds on the message complexity in asynchronous distributed computation. These techniques combine the choice of specific patterns of communication delays and crossing sequence arguments with consideration of the speed of propagation of messages, together with careful counting of messages in different parts of the network. They enable us to prove the following results, settling two open problems: An Ω(n log* n) lower bound for the number of messages sent by an asynchronous algorithm for computing any nonconstant function on a bidirectional ring of n anonymous processors. An Ω(n log n) lower bound for the average number of messages sent by any maximum finding algorithm on a ring of n processors, in case n is known.

Details

FOCS Conference 1986 Conference Paper

An O(n^2 (m + n log n) log n) Min-Cost Flow Algorithm

  • Zvi Galil
  • Éva Tardos

The minimum-cost flow problem is the following: given a network with n vertices and m edges, find a maximum flow of minimum cost. Many network problems are easily reducible to this problem. A polynomial-time algorithm for the problem has been known for some time [EK], but only recently a strongly polynomial algorithm was discovered [Ts]. In this paper we design an O(n2(m + n log n)log n) algorithm. The previous best algorithm had an O(m2 (m + n log n) log n) time bound ([F], [O]). Thus, we obtain an improvement of two orders of magnitude for dense graphs. Our algorithm is based on Fujishige's algorithm [F] (which is based on Tardos' algorithm [Ts]). Fujishige's algorithm consists of up to O(m log n) steps. Each step solves a single source shortest path problem with nonnegative edge lengths. We modify this algorithm in order to make an improved analysis possible. The new algorithm may still consist of up to m iterations, and an iteration may still consist of up to O(m log n) steps, but we can still show that the total number of steps is bounded by O(n2 log n). The improvement is due to a new technique that relates the time spent to the progress achieved.

Details

FOCS Conference 1984 Conference Paper

Efficient Implementation of Graph Algorithms Using Contraction

  • Harold N. Gabow
  • Zvi Galil
  • Thomas H. Spencer

We define a graph problem which we refer to as the component merging problem. Versions of the problem appear as bottlenecks in various graph algorithms. We show how to solve an important special case of the problem.

Details

FOCS Conference 1982 Conference Paper

An O(n^3 log n) Deterministic and an O(n^3) Probabilistic Isomorphism Test for Trivalent Graphs

  • Zvi Galil
  • Christoph M. Hoffmann
  • Eugene M. Luks
  • Claus-Peter Schnorr
  • Andreas Weber 0006

The main results of this paper are an O(n3) probabilistic algorithm and an O(n3 log n) deterministic algorithm that test whether two given trivalent graphs are isomorphic. In fact, the algorithms construct the set of all isomorphisms of the two graphs. Variants of these algorithms construct the set of all automorphisms of a trivalent graph. The algorithms make use of some new improved permutation group algorithms that exploit the fact that the groups involved are 2-groups. A remarkable property of the probabilistic algorithm is that it computes Isoe, ei(X, Y), i = 1, .. ., m, m = O(n) (the set of all isomorhisms φ: X → Y with φ(e)=ei) for the cost of computing the single set Isoe, el(X, Y).

Details

FOCS Conference 1982 Conference Paper

Priority Queues with Variable Priority and an O(EV log V) Algorithm for Finding a Maximal Weighted Matching in General Graphs

  • Zvi Galil
  • Silvio Micali
  • Harold N. Gabow

We define two generalized types of a priority queue by allowing some forms of changing the priorities of the elements in the queue. We show that they can be implemented efficiently. Consequently, each operation takes O(log n) time. We use these generalized priority queues to construct an O(EV log V) algorithm for finding a maximal weighted matching in general graphs.

Details

FOCS Conference 1981 Conference Paper

A Time-Space Tradeoff for Language Recognition

  • Pavol Duris
  • Zvi Galil

We define a language L and show that its time and space complexities T and S must satisfy T2S ≥ cn3 even allowing machines with multiple (non random) access to the input.

Details

FOCS Conference 1978 Conference Paper

A New Algorithm for the Maximal Flow Problem

  • Zvi Galil

A new algorithm for finding the maximal flow in a given network is presented. The algorithm runs in time O(V5/3E2/3) or O(n2. 33) where n = V + E is the length of the input.

Details

FOCS Conference 1976 Conference Paper

Recognizing Certain Repetitions and Reversals Within Strings

  • Zvi Galil
  • Joel I. Seiferas

Let P1 = {w ε Σ*: w = wR, |w| ≫ 1} be the set of all nontrivial palindromes over Σ. In Part I, we present a linear-time on-line recognition algorithm for P1* ("palstar") on a random-access machine with addition and uniform cost criterion. We also present a lineartime on-line recognition algorithm for P12 on a multitape Turing machine and a recognition algorithm for P12 on a two-way deterministic pushdown automaton. The correctness of these algorithms is based on new "cancellation lemmas" for the languages P1* and P12. In Part II, we present real-time recognition algorithms for the languages {wxyxz ε Σ*: |w|=r|x|, |y|=s|x|, |z|=t|x|} and {wxyxRz ε Σ*: |w|=r|x|, |y|=s|x|, |z|=t|x|} on multitape Turing machines, for arbitrary fixed r, s, and t.

Details

MFCS Conference 1975 Conference Paper

Monotone Switching Circuits and Boolean Matrix Product

  • Kurt Mehlhorn
  • Zvi Galil

Abstract We explore the concept of local transformations of monotone switching circuits, i. e. what kind of local changes in a circuit leave the functions computed by the circuit invariant. We obtain several general theorems in this direction. We apply these results to boolean matrix product and prove that the school-method for matrix multiplication yields the unique monotone circuit.

Details