#7,714

Most Influential Person

Israeli-American Computer Scientist and Mathematician, (1947 - ), Tel Aviv, Mandatory Palestine

**Areas of Specialization: Cryptography, Algorithms, Computational Complexity**

Zvi Galil is a computer scientist and mathematician who is the former dean of the Georgia Institute of Technology College of Computing. He earned a B.Sc. and M.Sc. in applied mathematics from Tel Aviv University (where he eventually served as president). He went on to earn a Ph.D. in computer science from Cornell University.

His mathematical and computer science research interests have included cryptography, the design and analysis of algorithms, stringology, sparsificaiton and computational complexity. He is a prolific writer with over 200 papers to his credit. His most frequently cited works include Efficient algorithms for finding maximum matching in graphs and Efficient algorithms for finding minimum spanning trees in undirected and directed graphs.

He is a fellow of the Association for Computing Machinery, the National Academy of Engineering and the American Academy of Arts and Sciences. He was instrumental in the development of Georgia Tech’s Online Master of Science in Computer Science program which is the largest online master’s program in computer science in the country.

He has also provided leadership in other ways, serving as the chair of Columbia University’s Computer Science program, the dean of the Fu Foundation School of Engineering & Applied Science, the Julian Clarence Levi Professor of Mathematical Methods and Computer Science and the Morris and Alma A. Schapiro Dean of Engineering at Columbia University.

**Featured in Top Influential Computer Scientists Today**

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.

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

This paper list is powered by the following services:

Zvi Galil is affiliated with the following schools:

This website uses cookies to enhance the user experience. Read the Privacy Policy for more.

Subscribe To Newsletter?Yes!