Zvi Galil

According to our database1, Zvi Galil
  • authored at least 179 papers between 1974 and 2016.
  • has a "Dijkstra number"2 of three.

Awards

ACM Fellow

ACM Fellow 1995, "For fundamental contributions to the design and analysis of algorithms and outstanding service to the theoretical computer science community.".

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2016
40 years of suffix trees.
Commun. ACM, 2016

2014
Real-Time Streaming String-Matching.
ACM Trans. Algorithms, 2014

2013
Forty Years of Text Indexing.
Proceedings of the Combinatorial Pattern Matching, 24th Annual Symposium, 2013

2011
Real-Time Streaming String-Matching.
Proceedings of the Combinatorial Pattern Matching - 22nd Annual Symposium, 2011

2010
Old and New in Stringology.
Proceedings of the Combinatorial Pattern Matching, 21st Annual Symposium, 2010

2004
Three-Dimensional Periodicity and Its Application to Pattern Matching.
SIAM J. Discrete Math., 2004

Parallel two dimensional witness computation.
Inf. Comput., 2004

2002
Lower Bounds for Dynamic Data Structures on Algebraic RAMs.
Algorithmica, 2002

2001
Topological Lower Bounds on Algebraic Random Access Machines.
SIAM J. Comput., 2001

A Generalization of a Lower Bound Technique due to Fredman and Saks.
Algorithmica, 2001

2000
Eavesdropping games: a graph-theoretic approach to privacy in distributed systems.
J. ACM, 2000

1999
Fully Dynamic Planarity Testing with Applications.
J. ACM, 1999

1998
Separator-Based Sparsification II: Edge and Vertex Connectivity.
SIAM J. Comput., 1998

1997
Constant-Time Randomized Parallel String Matching.
SIAM J. Comput., 1997

All Pairs Shortest Paths for Graphs with Small Integer Length Edges.
J. Comput. Syst. Sci., 1997

On the Exponent of the All Pairs Shortest Path Problem.
J. Comput. Syst. Sci., 1997

Sparsification - a technique for speeding up dynamic graph algorithms.
J. ACM, 1997

All Pairs Shortest Distances for Graphs with Small Integer Length Edges.
Inf. Comput., 1997

Three-Dimensional Pattern Matching.
SPAA, 1997

Off-line parallel exact string searching.
Proceedings of the Pattern Matching Algorithms, 1997

1996
Alphabet-Independent Two-Dimensional Witness Computation.
SIAM J. Comput., 1996

Separator Based Sparsification. I. Planary Testing and Minimum Spanning Trees.
J. Comput. Syst. Sci., 1996

1995
On the Power of the Shift Instruction
Inf. Comput., February, 1995

Parallel Detection of all Palindromes in a String.
Theor. Comput. Sci., 1995

A Constant-Time Optimal Parallel String-Matching Algorithm.
J. ACM, 1995

On Data Structure Tradeoffs and an Application to Union-Find
Electronic Colloquium on Computational Complexity (ECCC), 1995

Finding All Periods and Initial Palindromes of a String in Parallel.
Algorithmica, 1995

Short length versions of Menger's theorem (Extended Abstract).
Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995

Work-time-optimal parallel algorithms for string problems.
Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995

Sensing Versus Nonsensing Automata.
Proceedings of the Automata, Languages and Programming, 22nd International Colloquium, 1995

Lower Bounds on Algebraic Random Access Machines (Extended Abstract).
Proceedings of the Automata, Languages and Programming, 22nd International Colloquium, 1995

Resolving Message Complexity of Byzantine Agreement and beyond.
Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

Efficient Dynamic-Resharing "Verifiable Secret Sharing" Against Mobile Adversary.
Proceedings of the Algorithms, 1995

1994
Parallel Algorithms for Dynamic Programming Recurrences with More than O(1) Dependency.
J. Parallel Distrib. Comput., 1994

Dynamic Dictionary Matching.
J. Comput. Syst. Sci., 1994

Faster Tree Pattern Matching.
J. ACM, 1994

Parallel Detection of all Palindromes in a String.
Proceedings of the STACS 94, 1994

1993
On the Power of Multiple Reads in a Chip
Inf. Comput., June, 1993

Maintaining the 3-Edge-Connected Components of a Graph On-Line.
SIAM J. Comput., 1993

Witnesses for Boolean Matrix Multiplication and for Transitive Closure.
J. Complexity, 1993

Efficient Comparison Based String Matching.
J. Complexity, 1993

Separator based sparsification for dynamic planar graph algorithms.
Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993

Eavesdropping Games: A Graph-Theoretic Approach to Privacy in Distributed Systems
Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993

Optimally fast parallel algorithms for preprocessing and pattern matching in one and two dimensions
Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993

When can we sort in o(n log n) time?
Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993

1992
On the Space Complexity of Some Algorithms for Sequence Comparison.
Theor. Comput. Sci., 1992

Dynamic Programming with Convexity, Concavity, and Sparsity.
Theor. Comput. Sci., 1992

Fully Dynamic Algorithms for 2-Edge Connectivity.
SIAM J. Comput., 1992

On the Exact Complexity of String Matching: Upper Bounds.
SIAM J. Comput., 1992

A Lower Bound for Parallel String Matching.
SIAM J. Comput., 1992

Sparse Dynamic Programming II: Convex and Concave Cost Functions.
J. ACM, 1992

Sparse Dynamic Programming I: Linear Cost Functions.
J. ACM, 1992

On Pointers versus Addresses.
J. ACM, 1992

Fully Dynamic Planarity Testing (Extended Abstract)
Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992

A Constant-Time Optimal Parallel String-Matching Algorithm
Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992

Optimal Parallel Algorithms for Periods, Palindromes and Squares (Extended Abstract).
Proceedings of the Automata, Languages and Programming, 19th International Colloquium, 1992

Truly Alphabet-Independent Two-Dimensional Pattern Matching
Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 1992

Sparsification-A Technique for Speeding up Dynamic Graph Algorithms (Extended Abstract)
Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 1992

Witnesses for Boolean Matrix Multiplication and for Shortest Paths
Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 1992

1991
Classification of All the Minimal Bilinear Algorithms for Computing the Coefficients of the Product of Two Polynomials Modulo a Polynomial. Part II: The Algebra G[u]/.
Theor. Comput. Sci., 1991

An Almost Linear-Time Algorithm for the Dense Subset-Sum Problem.
SIAM J. Comput., 1991

On the Exact Complexity of String Matching: Lower Bounds.
SIAM J. Comput., 1991

Two Lower Bounds in Asynchronous Distributed Computation.
J. Comput. Syst. Sci., 1991

A Note on Set Union with Arbitrary Deunions.
Inf. Process. Lett., 1991

Data Structures and Algorithms for Disjoint Set Union Problems.
ACM Comput. Surv., 1991

Fully Dynamic Algorithms for Edge-Connectivity Problems (Extended Abstract)
Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 1991

A Lower Bound for Parallel String Matching
Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 1991

An Almost Linear-Time Algorithm for the Dense Subset-Sum Problem.
Proceedings of the Automata, Languages and Programming, 18th International Colloquium, 1991

Maintaining Biconnected Components of Dynamic Planar Graphs.
Proceedings of the Automata, Languages and Programming, 18th International Colloquium, 1991

On the Power of Multiple Reads in a Chip.
Proceedings of the Automata, Languages and Programming, 18th International Colloquium, 1991

Lower Bounds for Data Structure Problems on RAMs (Extended Abstract)
Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991

On the Exponent of the All Pairs Shortest Path Problem
Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991

1990
An Improved Algorithm for Approximate String Matching.
SIAM J. Comput., 1990

An Optimal O(log log n) Time Parallel String Matching Algorithm.
SIAM J. Comput., 1990

A Linear-Time Algorithm for Concave One-Dimensional Dynamic Programming.
Inf. Process. Lett., 1990

Sparse Dynamic Programming.
Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, 1990

Recent Progress in String Algorithms.
Proceedings of the Algorithms, 1990

Faster Tree Pattern Matching
Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

On the Exact Complexity of String Matching (Extended Abstract)
Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

1989
Speeding up Dynamic Programming with Applications to Molecular Biology.
Theor. Comput. Sci., 1989

Minimum-Knowledge Interactive Proofs for Decision Problems.
SIAM J. Comput., 1989

On Nontrivial Separators for k-Page Graphs and Simulations by Nondeterministic One-Tape Turing Machines.
J. Comput. Syst. Sci., 1989

Solving dense subset-sum problems by using analytical number theory.
J. Complexity, 1989

Efficient implementation of graph algorithms using contraction.
J. ACM, 1989

Parallel Evaluation of the Determinant and of the Inverse of a Matrix.
Inf. Process. Lett., 1989

On 3-pushdown graphs with large separators.
Combinatorica, 1989

Highly Parallelizable Problems (Extended Abstract)
Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989

An Improved Algorithm for Approximate String Matching.
Proceedings of the Automata, Languages and Programming, 16th International Colloquium, 1989

Parallel Algorithmic Techniques for Combinatorial Computation.
Proceedings of the Automata, Languages and Programming, 16th International Colloquium, 1989

A Secure Public-key Authentication Scheme.
Proceedings of the Advances in Cryptology, 1989

Security against Replay Chosen-Ciphertext Attack.
Proceedings of the Distributed Computing And Cryptography, 1989

1988
Classification of All the Minimal Bilinear Algorithms for Computing the Coefficients of the Product of Two Polynomials Modulo a Polynomial, Part I: The Algeabra G[u] / < Q(u)^l >, l > 1.
Theor. Comput. Sci., 1988

Data structures and algorithms for approximate string matching.
J. Complexity, 1988

An O(n²(m + n log n)log n) min-cost flow algorithm.
J. ACM, 1988

On finding most uniform spanning trees.
Discrete Applied Mathematics, 1988

Improved processor bounds for combinatorial problems in RNC.
Combinatorica, 1988

Speeding up Dynamic Programming
Proceedings of the 29th Annual Symposium on Foundations of Computer Science, 1988

On Pointers versus Addresses (Extended Abstract)
Proceedings of the 29th Annual Symposium on Foundations of Computer Science, 1988

1987
Lower Bounds on Communication Complexity
Inf. Comput., April, 1987

Distributed Algorithms in Synchronous Broadcasting Networks.
Theor. Comput. Sci., 1987

Parallel String Matching with k Mismatches.
Theor. Comput. Sci., 1987

Better Expanders and Superconcentrators.
J. Algorithms, 1987

An O(n³log n) deterministic and an O(n³) Las Vegs isomorphism test for trivalent graphs.
J. ACM, 1987

Partitioned Encryption and Achieving Simultaneity by Partitioning.
Inf. Process. Lett., 1987

Two Lower Bounds in Asynchronous Distributed Computation (Preliminary Version)
Proceedings of the 28th Annual Symposium on Foundations of Computer Science, 1987

Cryptographic Computation: Secure Faut-Tolerant Protocols and the Public-Key Model.
Proceedings of the Advances in Cryptology, 1987

1986
An O(EV log V) Algorithm for Finding a Maximal Weighted Matching in General Graphs.
SIAM J. Comput., 1986

Efficient Algorithms for Finding Maximum Matching in Graphs.
ACM Comput. Surv., 1986

Efficient algorithms for finding minimum spanning trees in undirected and directed graphs.
Combinatorica, 1986

On Nontrivial Separators for k-Page Graphs and Simulations by Nondeterministic One-Tape Turing Machines
Proceedings of the 18th Annual ACM Symposium on Theory of Computing, 1986

Classification of all the Minimal Bilinear Algorithms for Computing the Coefficients of the Product of Two Polynomials Modulo a Polynomial.
Proceedings of the Automata, Languages and Programming, 13th International Colloquium, 1986

An O(n^2 (m + n log n) log n) Min-Cost Flow Algorithm
Proceedings of the 27th Annual Symposium on Foundations of Computer Science, 1986

1985
Optimal Parallel Algorithms for String Matching
Information and Control, 1985

Distributed Algorithms in Synchronous Broadcasting Networks (Extended Abstract).
Proceedings of the Automata, 1985

Improved Processor Bounds for Algebraic and Combinatorial Problems in RNC
Proceedings of the 26th Annual Symposium on Foundations of Computer Science, 1985

A Private Interactive Test of a Boolean Predicate and Minimum-Knowledge Public-Key Cryptosystems (Extended Abstract)
Proceedings of the 26th Annual Symposium on Foundations of Computer Science, 1985

Symmetric Public-Key Encryption.
Proceedings of the Advances in Cryptology, 1985

1984
Two Tapes are Better than One for Nondeterministic Machines.
SIAM J. Comput., 1984

A Time-Space Tradeoff for Language Recognition.
Mathematical Systems Theory, 1984

Two Nonlinear Lower Bounds for On-Line Computations
Information and Control, 1984

Optimal Parallel Algorithms for String Matching
Proceedings of the 16th Annual ACM Symposium on Theory of Computing, April 30, 1984

Lower Bounds on Communication Complexity
Proceedings of the 16th Annual ACM Symposium on Theory of Computing, April 30, 1984

Efficient Implementation of Graph Algorithms Using Contraction
Proceedings of the 25th Annual Symposium on Foundations of Computer Science, 1984

1983
An Efficient General-Purpose Parallel Computer
J. ACM, April, 1983

Time-Space-Optimal String Matching.
J. Comput. Syst. Sci., 1983

NP Completeness of Finding the Chromatic Index of Regular Graphs.
J. Algorithms, 1983

Two Nonlinear Lower Bounds
Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 1983

Efficient Algorithms for Finding Maximal Matching in Graphs.
Proceedings of the CAAP'83, 1983

1982
On Reversal-Bounded Counter Machines and on Pushdown Automata with a Bound on the Size of their Pushdown Store
Information and Control, September, 1982

Fooling a two Way Automaton or one Pushdown Store is better than one Counter for two Way Machines.
Theor. Comput. Sci., 1982

An Almost Linear-Time Algorithm for Computing a Dependency Basis in a Relational Database.
J. ACM, 1982

Efficient Parallel Algorithms for Linear Recurrence Computation.
Inf. Process. Lett., 1982

Two Tapes are Better than One for Nondeterministic Machines
Proceedings of the 14th Annual ACM Symposium on Theory of Computing, 1982

On Reversal-Bounded Counter Machines and on Pushdown Automata with a Bound on the Size of the Pushdown Store.
Proceedings of the Automata, 1982

Priority Queues with Variable Priority and an O(EV log V) Algorithm for Finding a Maximal Weighted Matching in General Graphs
Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, 1982

An O(n^3 log n) Deterministic and an O(n^3) Probabilistic Isomorphism Test for Trivalent Graphs
Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, 1982

1981
Linear-Time String-Matching Using only a Fixed Number of Local Storage Locations.
Theor. Comput. Sci., 1981

On the Theoretical Efficiency of Various Network Flow Algorithms.
Theor. Comput. Sci., 1981

Explicit Constructions of Linear-Sized Superconcentrators.
J. Comput. Syst. Sci., 1981

String Matching in Real Time.
J. ACM, 1981

Time-Space-Optimal String Matching
Proceedings of the 13th Annual ACM Symposium on Theory of Computing, 1981

An Efficient General Purpose Parallel Computer
Proceedings of the 13th Annual ACM Symposium on Theory of Computing, 1981

Fooling a Two-Way Automaton or One Pushdown Store Is Better Than One Counter for Two Way Machines (Preliminary Version)
Proceedings of the 13th Annual ACM Symposium on Theory of Computing, 1981

A Time-Space Tradeoff for Language Recognition
Proceedings of the 22nd Annual Symposium on Foundations of Computer Science, 1981

1980
Saving Space in Fast String-Matching.
SIAM J. Comput., 1980

Finding the Vertex Connectivity of Graphs.
SIAM J. Comput., 1980

An O(EVlog²V) Algorithm for the Maximal Flow Problem.
J. Comput. Syst. Sci., 1980

An O(V5/3 E2/3) Algorithm for the Maximal Flow Problem.
Acta Inf., 1980

Applications of Efficient Mergeable Heaps for Optimization Problems on Trees.
Acta Inf., 1980

An Almost Linaer Time Algorithm for Computing a Dependency Basis in a Relational Data Base.
Proceedings of the Automata, 1980

Effizienz Paralleler Rechner.
Proceedings of the GI - 10. Jahrestagung, Saarbrücken, 30. September, 1980

1979
Storage Representations for Tree-Like Data Structures.
Mathematical Systems Theory, 1979

On Fulkerson's Conjecture About Consistent Labeling Processes.
Math. Oper. Res., 1979

A Fast Selection Algorithm and the Problem of Optimum Distribution of Effort.
J. ACM, 1979

On Improving the Worse Case Running Time of the Boyer-Moore String Matching Algorithm.
Commun. ACM, 1979

Storage Representations for Tree-Like Data Structures
Proceedings of the 11h Annual ACM Symposium on Theory of Computing, April 30, 1979

Network Flow and Generalized Path Compression
Proceedings of the 11h Annual ACM Symposium on Theory of Computing, April 30, 1979

Explicit Constructions of Linear Size Superconcentrators
Proceedings of the 20th Annual Symposium on Foundations of Computer Science, 1979

1978
Palindrome Recognition in Real Time by a Multitape Turing Machine.
J. Comput. Syst. Sci., 1978

A Linear-Time On-Line Recognition Algorithm for "Palstar".
J. ACM, 1978

On Improving the Worst Case Running Time of the Boyer-Moore String Matching Algorithm.
Proceedings of the Automata, 1978

A New Algorithm for the Maximal Flow Problem
Proceedings of the 19th Annual Symposium on Foundations of Computer Science, 1978

1977
Cyclic Ordering is NP-Complete.
Theor. Comput. Sci., 1977

On the Complexity of Regular Resolution and the Davis-Putnam Procedure.
Theor. Comput. Sci., 1977

On Resolution with Clauses of Bounded Size.
SIAM J. Comput., 1977

Real-Time Recognition of Substring Repetition and Reversal.
Mathematical Systems Theory, 1977

Some Open Problems in the Theory of Computation as Questions about Two-Way Deterministic Pushdown Automaton Languages.
Mathematical Systems Theory, 1977

Saving Space in Fast String-Matching
Proceedings of the 18th Annual Symposium on Foundations of Computer Science, Providence, Rhode Island, USA, 31 October, 1977

1976
A Note on Multiple-Entry Finite Automata.
J. Comput. Syst. Sci., 1976

Two Fast Simulations Which Imply Some Fast String Matching and Palindrome-Recognition Algorithms.
Inf. Process. Lett., 1976

Monotone switching circuits and boolean matrix product.
Computing, 1976

Hierarchies of Complete Problems.
Acta Inf., 1976

Real-Time Algorithms for String-Matching and Palindrome Recognition
Proceedings of the 8th Annual ACM Symposium on Theory of Computing, 1976

On Enumeration Procedures for Theorem Proving and for Integer Programming.
ICALP, 1976

Recognizing Certain Repetitions and Reversals Within Strings
Proceedings of the 17th Annual Symposium on Foundations of Computer Science, 1976

1975
Functional Schemas with Nested Predicates
Information and Control, April, 1975

On the Validity and Complexity of Bounded Resolution
Proceedings of the 7th Annual ACM Symposium on Theory of Computing, 1975

Monotone Switching Circuits and Boolean Matrix Product.
Proceedings of the Mathematical Foundations of Computer Science 1975, 1975

1974
Two Way Deterministic Pushdown Automaton Languages and Some Open Problems in the Theory of Computation
Proceedings of the 15th Annual Symposium on Switching and Automata Theory, 1974


  Loading...