SUMMARY OF RESULTS Consider a simple n-vertex undirected graph and assume there are ^ edge-disjoint paths between two vertices u and v. We prove the following two results: ffl There are ^...
Noga Alon, Zvi Galil, Oded Margalit
The upper bound on the exponent, ω, of matrix multiplication over a ring that was three in 1968 has decreased several times and since 1986 it has been 2.376. On the other hand, the exponent of the...
Extended Abstract Summary of results (2008)
Noga Alon, Zvi Galil, Oded Margalit, Moni Naor
The subcubic (O(n ω) for ω < 3) algorithms to multiply Boolean matrices do not provide the witnesses; namely, they compute C = AB but if Cij = 1 they do not find an index k (a witness) such that...
ABSTRATI. An algorithm IS developed whtch finds the nth largeat element of a Ilnearly ordered \el S. glven In the form of rn pairwise dlsjo~nt subsets. Each of the rn subsets satisfies the property...
Highly Parallelizable Problems (Extended Abstract) (2007)
Omer Berkman, Dany Breslauer, Zvi Galil, Baruch Schieber, Uzi Vishkin
) Omer Berkman 1,4 Dany Breslauer 1,2 Zvi Galil 1,2 Baruch Schieber 3 Uzi Vishkin 1,4,5 Summary of Results. We establish that several problems are highly parallelizable. For each of these problems,...
Richard Cole, Zvi Galil, Ramesh Hariharan, S. Muthukrishnan
An optimal parallel CRCW-PRAM algorithm to compute witnesses for all non-period vectors of an m 1 m 2 pattern is given. The algorithm takes O(log log m) time and does O(m 1 m 2) work, where m = maxfm...
Separator-based sparsification II: Edge and vertex connectivity (1999)
David Eppstein, Zvi Galil, Giuseppe F. Italiano, Thomas H
Abstract. We consider the problem of maintaining a dynamic planar graph subject to edge insertions and edge deletions that preserve planarity but that can change the embedding. We describe algorithms...
Sarnak: Fully Dynamic Planarity Testing with Applications (1999)
This paper introduces compressed certificates for planarity, biconnectivity and triconnectivity in planar graphs, and prove many structural properties of certificates in planar graphs. As an...
Dynamic Graph Algorithms (1999)
David Eppstein, Zvi Galil, Giuseppe F. Italiano
Introduction In many applications of graph algorithms, including communication networks, graphics, assembly planning, and VLSI design, graphs are subject to discrete changes, such as additions or...
Parallel String Matching Algorithms, (1998)
The string matching problem is one of the most studied problems in computer science. While it is very easily stated and many of the simple algorithms perform very well in practice, numerous works...
Eavesdropping Games: A Graph-Theoretic Approach to Privacy in Distributed Systems (1998)
Matthew Franklin, Zvi Galil, Moti Yung
We initiate a graph-theoretic study of privacy in distributed environments with mobile eavesdroppers ("bugs"). For two privacy tasks---distributed database maintenance and message...
Dynamic-Resharing Verifiable Secret Sharing against Mobile Adversary (1995)
Noga Alon, Zvi Galil, Moti Yung
We present a novel efficient variant of Verifiable Secret Sharing (VSS) where the dealing of shares is dynamically refreshed (without changing or corrupting the secret) against the threat of the...
Work-Time-Optimal Parallel Algorithms for String Problems (Extended Abstract) (1995)
Arthur Czumaj, Zvi Galil, Wojciech Plandowski
) Artur Czumaj Zvi Galil y Leszek G¸asieniec z Kunsoo Park x Wojciech Plandowski -- Abstract A parallel algorithm is work-optimal if it uses the smallest possible work; a work-optimal algorithm is...
Efficient Comparison Based String Matching (1995)
Dany Breslauer, Zvi Galil, Dedicated Joseph, F. Traub
We study the exact number of symbol comparisons that are required to solve the string matching problem and present a family of efficient algorithms. Unlike previous string matching algorithms, the...
Finding All Periods and Initial Palindromes of a String in Parallel (1995)
An optimal O(log log n) time CRCW-PRAM algorithm for computing all period lengths of a string is presented. Previous parallel algorithms compute the period only if it is shorter than half of the...
Constant-Time Randomized Parallel String Matching (1994)
Maxime Crochemore, ZVI GALIL, Leszek Gasieniec, KUNSOO PARK, Wojciech Rytter
. Given a pattern string of length m for the string matching problem, we design an algorithm that computes deterministic samples of a sufficiently long substring of the pattern in constant time. This...
Parallel Detection of all Palindromes in a String (1994)
Alberto Apostolico, Dany Breslauer, Zvi Galil
This paper presents two efficient concurrent-read concurrent-write parallel algorithms that find all palindromes in a given string: 1. An O(log n) time, n-processor algorithm over general alphabets....
Improved Sparsification (1993)
David Eppstein, Zvi Galil, Giuseppe F. Italiano
In previous work we introduced sparsification, a technique that transforms fully dynamic algorithms for sparse graphs into ones that work on any graph, with a logarithmic increase in complexity. In...
Efficient Comparison Based String Matching (1993)
Dany Breslauer Cwi, Dany Breslauer, Zvi Galil
We study the exact number of symbol comparisons that are required to solve the string matching problem and present a family of efficient algorithms. Unlike previous string matching algorithms, the...
Richard Cole, Maxime Crochemore, Zvi Galil, Leszek Gasieniec, Ramesh Hariharan, S. Muthukrishnan, ...
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...
Dynamic Dictionary Matching (1993)
Amihood Amir, Zvi Galil, Raffaele Giancarlo, Martin Farach, Kunsoo Park, Martin Farach
We consider the dynamic dictionary matching problem. We are given a set of pattern strings (the dictionary) that can change over time; that is, we can insert a new pattern into the dictionary or...
An Overview of Secure Distributed Computing (1992)
Matthew Franklin, Zvi Galil, Moti Yung
Secure distributed computing protocols allow a group of players, within some specific computational environment, to evaluate jointly the output of a function while maintaining the secrecy of...
A Lower Bound for Parallel String Matching (1992)
We present an\Omega\Gamma/22 log m) lower bound on the number of rounds necessary for finding occurrences of a pattern string P [1::m] in a text string T [1::2m] in parallel using m comparisons in...
Parallel Dynamic Programming (1992)
Zvi Galil And Kunsoo Park, Zvi Galil, Correspondence Kunsoo Park
We study the parallel computation of dynamic programming. We consider four important dynamic programming problems which have wide application, and that have been studied extensively in sequential...
Optimal Parallel Algorithms for Periods, Palindromes and Squares (Extended Abstract) (1992)
Alberto Apostolico, Dany Breslauer, Zvi Galil
) Alberto Apostolico Purdue University and Universit`a di Padova Dany Breslauer yyz Columbia University Zvi Galil z Columbia University and Tel-Aviv University Summary of results Optimal...
Efficient Algorithms for Sequence Analysis (1991)
David Eppstein, Zvi Galil, Raffaele Giancarlo, Giuseppe F. Italiano
: We consider new algorithms for the solution of many dynamic programming recurrences for sequence comparison and for RNA secondary structure prediction. The techniques upon which the algorithms are...
Finding All Periods and Initial Palindromes of a String in Parallel (1991)
Dany Breslauer Columbia, Dany Breslauer, Zvi Galil
An optimal O(log log n) time CRCW-PRAM algorithm for computing all periods of a string is presented. Previous parallel algorithms compute the period only if it is shorter than half of the length of...
Maintaining Biconnected Components of Dynamic Planar Graphs (1991)
Zvi Galil, Giuseppe F. Italiano
We present algorithms for maintaining the biconnected components of a planar graph undergoing repeated dynamic modifications, such as insertions and deletions of edges and vertices. We show how to...
Parallel String Matching Algorithms (1990)
Dany Breslauer Columbia, Dany Breslauer, Zvi Galil
The string matching problem is one of the most studied problems in computer science. While it is very easily stated and many of the simple algorithms perform very well in practice, numerous works...
Parallel String Matching Algorithms (1990)
The string matching problem is one of the most studied problems in computer science. While it is very easily stated and many of the simple algorithms perform very well in practice, numerous works...
Work supported by NSF Grants CCR-86-05353 and CCR-88-14977 (1990)
Nd Ccr-, Dany Breslauer, Zvi Galil
An optimal O(log log n) time parallel algorithm for string matching on CRCWPRAM is presented. It improves previous results of [G] and [V]. 1 Introduction On a CRCW-PRAM we can solve some problems in...
Speech recognition in parallel (1989)
Salvatore J. Stolfo, Zvi Galil, Kathleen Mckeown, Russell Mills
Concomitantly with recent advances in speech coding, recognition and production, parallel computer systems are now commonplace delivenng raw computing power measured in hundreds of MIPS and...
Parallel algorithmic techniques for combinatorial computation (1988)
Parallel computation offers the promise of great improvements in the solution of problems that, if we were restricted to sequential computation, would take so much time that solution would be...
Speeding up Dynamic Programming (1988)
David Eppstein, Zvi Galil, Raffaele Giancarlo
this paper we consider the problem of computing two similar recurrences: the one-dimensional case
@ North-Holland Publishing Company CYCLIC ORDERING IS NP-COMPLETE (1977)
Zvi Galil, Nimrod Megiddo, Z. Galil, N. Megiddo
Abstract. The cyclic ordering problem is to recognize whether a collection of cyclically ordered triples of elements of a set T is derived from an arrangement of all the elements of T on a circle....
Monotone Switching Circuits and Boolean Matrix Product (1976)
We explore the concept of local transformations of monotone switching circuits, i.e. what kind of local changes in a network leave the input/output behavior invariant. We obtain several general...
The Complexity of Resolution Procedures for Theorem Proving in the Propositional Calculus (1975)
A comparative study on the complexity of various procedures for proving that a set of clauses is contradictory is described. All the procedures either use the resolution rule in some form or are...
The Complexity of Resolution Procedures for Theorem Proving in the Propositional Calculus (1975)
A comparative study on the complexity of various procedures for proving that a set of clauses is contradictory is described. All the procedures either use the resolution rule in some form or are...
The complexity of resolution procedures for theorem proving in the propositional calculus / (1975)
Thesis (Ph.D.)--Cornell University, June, 1975.
On the Complexity of Resolution Procedures for Theorem Proving (1974)
We study several procedures for theorem proving based on the resolution principle. We consider (1) Davis Putnam procedure; (2) regular resolution; (3) unrestricted resolution; (4) resolution with...
On the Complexity of Resolution Procedures for Theorem Proving (1974)
We study several procedures for theorem proving based on the resolution principle. We consider (1) Davis Putnam procedure; (2) regular resolution; (3) unrestricted resolution; (4) resolution with...
We consider some of the important unsolved problems in the theory of computation concerning the relationship between deterministic and nondeterministic computations, and between tape and time bounded...
We consider some of the important unsolved problems in the theory of computation concerning the relationship between deterministic and nondeterministic computations, and between tape and time bounded...
Functional Schemas with Nested Predicates (1973)
A class of (monadic) functional schemas with nested predicates is defined. It is shown that termination, divergence and freedom problems for these schemas are decidable. It is proved that when the...
Functional Schemas with Nested Predicates (1973)
A class of (monadic) functional schemas with nested predicates is defined. It is shown that termination, divergence and freedom problems for these schemas are decidable. It is proved that when the...