Zvi Galil | Academic Influence

Zvi Galil's AcademicInfluence.com Rankings

Zvi Galil

Computer Science

#458

World Rank

#476

Historical Rank

computer-science Degrees

Zvi Galil

Mathematics

#1638

World Rank

#2639

Historical Rank

Measure Theory

#1109

World Rank

#1423

Historical Rank

mathematics Degrees

Download Badge

Computer Science
Mathematics

Zvi Galil's Degrees

PhD Computer Science Cornell University

Similar Degrees You Can Earn

Best Online PhD of Computer Science (Doctorates) 2025

Why Is Zvi Galil Influential?

(Suggest an Edit or Addition)

According to Wikipedia, Zvi Galil is an Israeli-American computer scientist and mathematician. Galil served as the president of Tel Aviv University from 2007 through 2009. From 2010 to 2019, he was the dean of the Georgia Institute of Technology College of Computing. His research interests include the design and analysis of algorithms, computational complexity and cryptography. He has been credited with coining the terms stringology and sparsification. He has published over 200 scientific papers and is listed as an ISI highly cited researcher.

(See a Problem?)

Zvi Galil's Published Works

Number of citations in a given year to any of this author's works

Total number of citations to an author for the works they published in a given year. This highlights publication of the most important work(s) by the author

Published Works

Efficient algorithms for finding minimum spanning trees in undirected and directed graphs (1986) (552)
Efficient algorithms for finding maximum matching in graphs (1986) (507)
Explicit constructions of linear size superconcentrators (1979) (438)
Sparsification-a technique for speeding up dynamic graph algorithms (1992) (423)
Pattern matching algorithms (1997) (231)
On the Exponent of the All Pairs Shortest Path Problem (1991) (211)
Dynamic Graph Algorithms (2010) (210)
An Improved Algorithm for Approximate String Matching (1989) (205)
Lower bounds on communication complexity (1984) (199)
Time-Space-Optimal String Matching (1983) (183)
Data structures and algorithms for disjoint set union problems (1991) (183)
NP Completeness of Finding the Chromatic Index of Regular Graphs (1983) (182)
Priority queues with variable priority and an O(EV log V) algorithm for finding a maximal weighted matching in general graphs (1982) (158)
Proceedings of the 30th IEEE symposium on Foundations of computer science (1994) (157)
Data structures and algorithms for approximate string matching (1988) (156)
Sparse dynamic programming I: linear cost functions (1992) (153)
Combinatorial Algorithms on Words (1985) (144)
Optimal parallel algorithms for string matching (1984) (143)
Cryptographic Computation: Secure Faut-Tolerant Protocols and the Public-Key Model (1987) (135)
On improving the worst case running time of the Boyer-Moore string matching algorithm (1978) (134)
Faster tree pattern matching (1990) (122)
Speeding up Dynamic Programming with Applications to Molecular Biology (1989) (121)
Parallel Algorithmic Techniques for Combinatorial Computation (1988) (119)
Time- and Space-Saving Computer Methods, Related to Mitchell's DETMAX, for Finding D-Optimum Designs (1980) (118)
Highly parallelizable problems (1989) (112)
Efficient implementation of graph algorithms using contraction (1984) (111)
Improved string matching with k mismatches (1986) (111)
On the Complexity of Regular Resolution and the Davis-Putnam Procedure (1977) (109)
Dynamic Dictionary Matching (1994) (102)
$D$-Optimum Weighing Designs (1980) (100)
Finding the Vertex Connectivity of Graphs (1980) (87)
Sparse dynamic programming II: convex and concave cost functions (1992) (86)
An Almost Linear-Time Algorithm for Computing a Dependency Basis in a Relational Database (1982) (84)
All Pairs Shortest Paths for Graphs with Small Integer Length Edges (1997) (82)
Witnesses for Boolean matrix multiplication and for shortest paths (1992) (81)
Eavesdropping games: a graph-theoretic approach to privacy in distributed systems (1993) (80)
Truly alphabet-independent two-dimensional pattern matching (1992) (80)
Dynamic Programming with Convexity, Concavity, and Sparsity (1992) (75)
An Optimal O(log log n) Time Parallel String Matching Algorithm (1990) (74)
Speeding up dynamic programming (1988) (73)
A Linear-Time Algorithm for Concave One-Dimensional Dynamic Programming (1990) (71)
Parallel Algorithms for Dynamic Programming Recurrences with More than O(1) Dependency (1994) (70)
A Fast Selection Algorithm and the Problem of Optimum Distribution of Effort (1979) (70)
All Pairs Shortest Distances for Graphs with Small Integer Length Edges (1997) (70)
Reducing edge connectivity to vertex connectivity (1991) (70)
Resolving message complexity of Byzantine Agreement and beyond (1995) (70)
Comparison of Simplex Designs for Quadratic Mixture Models (1977) (68)
Better Expanders and Superconcentrators (1987) (65)
Cyclic Ordering is NP-Complete (1977) (63)
A private interactive test of a boolean predicate a minimum-knowledge public-key cryptosystems (1985) (63)
Open Problems in Stringology (1985) (63)
Optimally fast parallel algorithms for preprocessing and pattern matching in one and two dimensions (1993) (62)
A constant-time optimal parallel string-matching algorithm (1992) (58)
Maintaining the 3-Edge-Connected Components of a Graph On-Line (1993) (58)
Parallel Detection of all Palindromes in a String (1994) (58)
An O(EVlog²V) Algorithm for the Maximal Flow Problem (1980) (57)
Sparse dynamic programming (1990) (56)
String Matching in Real Time (1981) (53)
Separator based sparsification for dynamic planar graph algorithms (1993) (52)
Minimum-Knowledge Interactive Proofs for Decision Problems (1989) (47)
Separator Based Sparsification. I. Planary Testing and Minimum Spanning Trees (1996) (47)
On the Exact Complexity of String Matching: Lower Bounds (1991) (47)
A lower bound for parallel string matching (1991) (47)
On pointers versus addresses (1988) (47)
On the exact complexity of string matching (1990) (46)
Real-Time Streaming String-Matching (2011) (45)
An Almost Linear-Time Algorithm for the Dense Subset-Sum Problem (1991) (45)
Fully dynamic algorithms for edge connectivity problems (1991) (45)
On the Exact Complexity of String Matching: Upper Bounds (1992) (44)
Efficient cryptographic protocols preventing man-in-the-middle attacks (2002) (43)
Comparison of design for quadratic regression on cubes (1977) (43)
Maintaining Biconnected Components of Dynamic Planar Graphs (1991) (42)
Comparison of Rotatable Designs for Regression on Balls (1977) (42)
Construction Methods for $D$-Optimum Weighing Designs when $n \equiv 3 (\operatorname{mod} 4)$ (1982) (42)
An Efficient General-Purpose Parallel Computer (1983) (41)
Parallel Evaluation of the Determinant and of the Inverse of a Matrix (1989) (41)
On Resolution with Clauses of Bounded Size (1977) (40)
A Linear-Time On-Line Recognition Algorithm for ``Palstar'' (1978) (39)
Saving space in fast string-matching (1977) (38)
Fooling a two Way Automaton or one Pushdown Store is better than one Counter for two Way Machines (1982) (38)
Construction Methods for D-Optimum Weighing Designs when n ≡ 3(mod 4) (1985) (36)
On nontrivial separators for k-page graphs and simulations by nondeterministic one-tape Turing machines (1986) (36)
Real-time algorithms for string-matching and palindrome recognition (1976) (36)
Improved processor bounds for combinatorial problems in RNC (1988) (35)
Efficient Parallel Algorithms for Linear Recurrence Computation (1982) (35)
Optimal Parallel Algorithms for Periods, Palindromes and Squares (Extended Abstract) (1992) (34)
Hierarchies of complete problems (1976) (34)
Fully Dynamic Algorithms for 2-Edge Connectivity (1992) (33)
Witnesses for Boolean Matrix Multiplication and for Transitive Closure (1993) (33)
Extrapolation designs and Φp-optimum designs for cubic regression on the q-ball (1979) (32)
Finding all periods and initial palindromes of a string in parallel (1992) (32)
Alphabet-Independent Two-Dimensional Witness Computation (1996) (32)
40 years of suffix trees (2016) (31)
Symmetric Public-Key Encryption (1985) (31)
Efficient Dynamic-Resharing "Verifiable Secret Sharing" Against Mobile Adversary (1995) (29)
Fully dynamic planarity testing with applications (1999) (29)
On finding most uniform spanning trees (1988) (28)
Network flow and generalized path compression (1979) (27)
An O(n2(m + n log n) log n) min-cost flow algorithm (1986) (27)
Optimal Parallel Algorithms for Periods, Palindromes and Squares (Preliminary Version) (1991) (27)
A new algorithm for the maximal flow problem (1978) (27)
Separator-Based Sparsification II: Edge and Vertex Connectivity (1999) (26)
Solving dense subset-sum problems by using analytical number theory (1989) (26)
Improved processor bounds for algebraic and combinatorial problems in RNC (1985) (26)
Two lower bounds in asynchronous distributed computation (1987) (25)
Monotone switching circuits and boolean matrix product (1975) (25)
Comparison of Box-Draper and D-Optimum Designs for Experiments with Mixtures (1977) (24)
An O(n3log n) deterministic and an O(n3) Las Vegs isomorphism test for trivalent graphs (1987) (24)
An Overview of Secure Distributed Computing (1992) (24)
An O(n2(m + Nlog n)log n) min-cost flow algorithm (1988) (24)
Parallel String Matching with k Mismatches (1987) (23)
Improved Sparsification (1993) (22)
Time-space-optimal string matching (Preliminary Report) (1981) (22)
Short length versions of Menger's theorem (1995) (22)
Work-time-optimal parallel algorithms for string problems (1995) (22)
Two Fast Simulations Which Imply Some Fast String Matching and Palindrome-Recognition Algorithms (1976) (22)
Speech Recognition in Parallel (1989) (21)
Two nonlinear lower bounds (1983) (20)
Efficient Algorithms for Finding Maximal Matching in Graphs (1983) (20)
Palindrome Recognition in Real Time by a Multitape Turing Machine (1978) (19)
An O(V5/3E2/3) algorithm for the maximal flow problem (1980) (18)
Two Nonlinear Lower Bounds for On-Line Computations (1984) (18)
The nucleolus in games with major and minor players (1974) (18)
A time-space tradeoff for language recognition (1981) (17)
Two Way Deterministic Pushdown Automaton Languages and Some Open Problems in the Theory of Computation (1974) (17)
An O(n3 log n) deterministic and an O (n 3) probabilistic isomorphism test for trivalent graphs (1982) (15)
A Generalization of a Lower Bound Technique due to Fredman and Saks (2001) (15)
On Reversal-Bounded Counter Machines and on Pushdown Automata with a Bound on the Size of their Pushdown Store (1982) (15)
Two tapes are better than one for nondeterministic machines (1982) (15)
Computing D-Optimum Weighing Designs: Where Statistics, Combinatorics, and Computation Meet (1983) (15)
Constant-Time Randomized Parallel String Matching (1997) (15)
Efficient Comparison Based String Matching (1992) (15)
Applications of efficient mergeable heaps for optimization problems on trees (2004) (14)
On 3-pushdown graphs with large separators (1989) (14)
On some direct encodings of nondeterministic Turing machines operating in polynomial time into p-complete problems (1974) (13)
Fully dynamic planarity testing (extended abstract) (1992) (12)
The Complexity of Resolution Procedures for Theorem Proving in the Propositional Calculus (1975) (12)
On the Theoretical Efficiency of Various Network Flow Algorithms (1981) (12)
Highly Parallelizable Problems (Extended Abstract) (1989) (12)
Partitioned Encryption and Achieving Simultaneity by Partitioning (1987) (11)
An efficient general purpose parallel computer (1981) (11)
Some open problems in the theory of computation as questions about two-way deterministic pushdown automaton languages (1976) (11)
Topological Lower Bounds on Algebraic Random Access Machines (2002) (11)
On the validity and complexity of bounded resolution (1975) (11)
On Enumeration Procedures for Theorem Proving and for Integer Programming (1976) (11)
On the Power of the Shift Instruction (1995) (11)
A Note on Set Union with Arbitrary Deunions (1991) (10)
Lower bounds for data structure problems on RAMs (1991) (10)
Parallel Dynamic Programming (1991) (10)
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 (1988) (10)
On the Power of Multiple Reads in a Chip (1991) (9)
Comparison of designs equivalent under one or two criteria (1983) (9)
What can we sort in o(nlog n) time? (1993) (8)
On Reversal-Bounded Counter Machines and on Pushdown Automata with a Bound on the Size of the Pushdown Store (1982) (8)
Efficient Algorithms for Sequence Analysis (1993) (8)
Classification of all the Minimal Bilinear Algorithms for Computing the Coefficients of the Product of Two Polynomials Modulo a Polynomial (1986) (8)
A Note on Multiple-Entry Finite Automata (1976) (8)
Lower Bounds for Dynamic Data Structures on Algebraic RAMs (2002) (8)
Sequential and parallel algorithms for finding maximum matchings in graphs (1986) (8)
Fooling a two-way automaton or one pushdown store is better than one counter for two way machines (Preliminary Version) (1981) (7)
Linear-Time String-Matching Using only a Fixed Number of Local Storage Locations (1981) (7)
Maintaining biconnected components of dynamic planar graphs (extended abstract) (1991) (7)
On the Complexity of Resolution Procedures for Theorem Proving (1974) (6)
Recognizing certain repetitions and reversals within strings (1976) (6)
Theory of Computing and Systems (1992) (6)
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]/ (1991) (6)
Forty Years of Text Indexing (2013) (6)
On the Space Complexity of Some Algorithms for Sequence Comparison (1992) (5)
A Private Interactive Test of a Boolean Predicate and Minimum-Knowledge Public-Key Cryptosystems Extended Abstract (1985) (5)
Distributed Algorithms in Synchronous Broadcasting Networks (Extended Abstract) (1985) (5)
Functional Schemas with Nested Predicates (1975) (5)
An ) min-cost flow algorithm (1988) (5)
Short length versions of Menger's theorem (Extended Abstract). (1995) (4)
Efficient algorithms with applications to molecular biology (1990) (4)
Proceedings of the Third Annual Symposium on Combinatorial Pattern Matching (1992) (4)
Proceedings of the Israel Symposium on Theory of Computing and Systems (1992) (3)
Lower Bounds on Algebraic Random Access Machines (Extended Abstract) (1995) (3)
On converting on-line algorithms into real-time and on real-time algorithms for string-matching and palindrome recognition (1975) (3)
OMSCS: the revolution will be digitized (2020) (3)
A Secure Public-key Authentication Scheme (1989) (3)
Sensing Versus Nonsensing Automata (1995) (3)
Three-Dimensional Periodicity and Its Application to Pattern Matching (2005) (3)
On Fulkerson's Conjecture About Consistent Labeling Processes (1979) (2)
Two Lower Bounds in Asynchronous Distributed Computation (Preliminary Version) (1987) (2)
Security against Replay Chosen-Ciphertext Attack (1989) (2)
Parallel string matching algorithms (1993) (2)
On the Characterization of D-Optimum Weighing Designs for n ≡ 3(mod 4) (1985) (2)
Parallel two dimensional witness computation (2004) (1)
Real-time recognition of substring repetition and reversal (1977) (1)
Common subsequences and supersequences and their expected length (1995) (1)
Two Nonlinear Bounds for On-Line Computations (1983) (1)
An Almost Linaer Time Algorithm for Computing a Dependency Basis in a Relational Data Base (1980) (1)
OMSCS (2020) (1)
Speeding up Dynamic Programming with Application to the Computation of RNA Structure (1988) (1)
Storage representations for tree-like data structures (1979) (1)
Distributed Algorithms in Synchronous Broadcasting Networks (1987) (1)
Recent Progress in String Algorithms (1990) (0)
Number 17 (2017) (0)
Three-dimensional pattern matching (1997) (0)
selected papers from the third annual ACM-SIAM symposium on Discrete algorithms (1994) (0)
Commentary on Papers [8] and [20] (1986) (0)
On the Exact Complexity of String Matching (Extended Abstract) (1990) (0)
On Pointers versus Addresses (Extended Abstract) (1988) (0)
Creating a revolutionary academic program (2022) (0)
Killing two birds with one stone (1978) (0)
CGG90] L. Colussi, Z. Galil, R. Giancarlo. On the Exact Complexity of String Matching. Pro- ceedings of the Thirty First Annual IEEE Symposium on the Foundations of Computer Science, 1990, 135-143. (2007) (0)
Algorithms, bounds, and constructions for robust computation and communication (1996) (0)
CRNCH Summit Opening Remarks (2018) (0)
移動型敵対者に対する「検証可能秘密共有」(VSS)の効率的動的再共有 (1995) (0)
Open Problems In Stringology, Thirteen years Later (1997) (0)
Data structures and algorithms for approximate string matchingZvi Galil, Raffaele Giancarlo (1987) (0)
Efficient Graph Isomorphism Query Processing using Degree Sequences and Color-Label Distributions (2022) (0)
Old and New in Stringology (2010) (0)
Fully Dynamic Algorithms for Edge-Connectivity Problems (Extended Abstract) (1991) (0)
Comparison of Simplex Designs for Quadratic (1977) (0)
On Data Structure Tradeoffs and an Application to Union-Find (1995) (0)
Basic algorithms for control and applications of high-speed networks (1996) (0)
ming With Applications to Molecular Biology (2004) (0)
Scalable Graph Isomorphism: Combining Pairwise Color Refinement and Backtracking via Compressed Candidate Space (2021) (0)
Commentary on Papers [72], [74], [75], [76], [80] (1985) (0)
Approximating The Minimum Equivalent Digraph (1995) (0)
Forty Years of Suﬀix Trees Forty Years of Sufﬁx Trees (2018) (0)
β-trees, γ-systems, and a Theorem on F-heaps (1984) (0)
Combinatorial Pattern Matching: 6th Annual Symposium, CPM 95, Espoo, Finland, July 5 - 7, 1995. Proceedings (1995) (0)
A tribute to referees (2004) (0)
AN 0{n 2 (m + nlogn) logn) MIN-COST FLOW ALGORITHM (1986) (0)
Theory of Computing and Systems: Istcs '92 Israel Symposium Haifa, Israel, May 27-28, 1992 Proceedings (1992) (0)
Off-line parallel exact string searching (1997) (0)
6 Open Problem Acknowledgment I Thank Jee Kahn for His Help in Formulating and Proving Lemma 2. References Similarly. Simple Properties of Gray Codes Guarantee That (2007) (0)
Selected papers from the fourth annual ACM SIAM symposium on Discrete algorithms (1995) (0)
Symposium proceedings on Theory of computing and systems (1992) (0)

This paper list is powered by the following services:

Other Resources About Zvi Galil

en.wikipedia.org

What Schools Are Affiliated With Zvi Galil?

Zvi Galil is affiliated with the following schools:

Image Attributions

Image Source for Zvi Galil