#5,232

Most Influential Person

Israeli-American Computer Scientist and Mathematician

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

Want to be an Academic Influence Insider?

Sign up to get the latest news, information, and rankings in our upcoming newsletter.