default search action
Zvi Galil
Person information
- affiliation: Columbia University, New York City, USA
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
Books and Theses
- 1975
- [b1]Zvi Galil:
The Complexity of Resolution Procedures for Theorem Proving in the Propositional Calculus. Cornell University, USA, 1975
Journal Articles
- 2022
- [j110]Umakishore Ramachandran, Zvi Galil:
Creating a revolutionary academic program. Commun. ACM 65(10): 46-56 (2022) - 2020
- [j109]Zvi Galil:
OMSCS: the revolution will be digitized. Commun. ACM 63(8): 27-29 (2020) - 2016
- [j108]Alberto Apostolico, Maxime Crochemore
, Martin Farach-Colton
40 years of suffix trees. Commun. ACM 59(4): 66-73 (2016) - 2014
- [j107]Dany Breslauer, Zvi Galil:
Real-Time Streaming String-Matching. ACM Trans. Algorithms 10(4): 22:1-22:12 (2014) - 2004
- [j106]Richard Cole, Zvi Galil, Ramesh Hariharan, S. Muthukrishnan, Kunsoo Park:
Parallel two dimensional witness computation. Inf. Comput. 188(1): 20-67 (2004) - [j105]Zvi Galil, Jong Geun Park, Kunsoo Park:
Three-Dimensional Periodicity and Its Application to Pattern Matching. SIAM J. Discret. Math. 18(2): 362-381 (2004) - 2002
- [j104]Amir M. Ben-Amram, Zvi Galil:
Lower Bounds for Dynamic Data Structures on Algebraic RAMs. Algorithmica 32(3): 364-395 (2002) - 2001
- [j103]Amir M. Ben-Amram, Zvi Galil:
A Generalization of a Lower Bound Technique due to Fredman and Saks. Algorithmica 30(1): 34-66 (2001) - [j102]Amir M. Ben-Amram, Zvi Galil:
Topological Lower Bounds on Algebraic Random Access Machines. SIAM J. Comput. 31(3): 722-761 (2001) - 2000
- [j101]Matthew K. Franklin, Zvi Galil, Moti Yung:
Eavesdropping games: a graph-theoretic approach to privacy in distributed systems. J. ACM 47(2): 225-243 (2000) - 1999
- [j100]Zvi Galil, Giuseppe F. Italiano, Neil Sarnak:
Fully Dynamic Planarity Testing with Applications. J. ACM 46(1): 28-91 (1999) - 1998
- [j99]David Eppstein, Zvi Galil, Giuseppe F. Italiano, Thomas H. Spencer:
Separator-Based Sparsification II: Edge and Vertex Connectivity. SIAM J. Comput. 28(1): 341-381 (1998) - 1997
- [j98]Zvi Galil, Oded Margalit:
All Pairs Shortest Distances for Graphs with Small Integer Length Edges. Inf. Comput. 134(2): 103-139 (1997) - [j97]David Eppstein, Zvi Galil, Giuseppe F. Italiano, Amnon Nissenzweig:
Sparsification - a technique for speeding up dynamic graph algorithms. J. ACM 44(5): 669-696 (1997) - [j96]Zvi Galil, Oded Margalit:
All Pairs Shortest Paths for Graphs with Small Integer Length Edges. J. Comput. Syst. Sci. 54(2): 243-254 (1997) - [j95]Noga Alon, Zvi Galil, Oded Margalit:
On the Exponent of the All Pairs Shortest Path Problem. J. Comput. Syst. Sci. 54(2): 255-262 (1997) - [j94]Maxime Crochemore, Zvi Galil, Leszek Gasieniec, Kunsoo Park, Wojciech Rytter:
Constant-Time Randomized Parallel String Matching. SIAM J. Comput. 26(4): 950-960 (1997) - 1996
- [j93]David Eppstein, Zvi Galil, Giuseppe F. Italiano
Separator Based Sparsification. I. Planary Testing and Minimum Spanning Trees. J. Comput. Syst. Sci. 52(1): 3-27 (1996) - [j92]Zvi Galil, Kunsoo Park:
Alphabet-Independent Two-Dimensional Witness Computation. SIAM J. Comput. 25(5): 907-935 (1996) - 1995
- [j91]Dany Breslauer, Zvi Galil:
Finding All Periods and Initial Palindromes of a String in Parallel. Algorithmica 14(4): 355-366 (1995) - [j90]Amir M. Ben-Amram, Zvi Galil:
On the Power of the Shift Instruction. Inf. Comput. 117(1): 19-36 (1995) - [j89]Zvi Galil:
A Constant-Time Optimal Parallel String-Matching Algorithm. J. ACM 42(4): 908-918 (1995) - [j88]Alberto Apostolico, Dany Breslauer, Zvi Galil:
Parallel Detection of all Palindromes in a String. Theor. Comput. Sci. 141(1&2): 163-173 (1995) - 1994
- [j87]Moshe Dubiner, Zvi Galil, Edith Magen:
Faster Tree Pattern Matching. J. ACM 41(2): 205-213 (1994) - [j86]Amihood Amir, Martin Farach
Dynamic Dictionary Matching. J. Comput. Syst. Sci. 49(2): 208-222 (1994) - [j85]Zvi Galil, Kunsoo Park:
Parallel Algorithms for Dynamic Programming Recurrences with More than O(1) Dependency. J. Parallel Distributed Comput. 21(2): 213-222 (1994) - 1993
- [j84]Pavol Duris, Zvi Galil:
On the Power of Multiple Reads in a Chip. Inf. Comput. 104(2): 277-287 (1993) - [j83]Zvi Galil, Oded Margalit:
Witnesses for Boolean Matrix Multiplication and for Transitive Closure. J. Complex. 9(2): 201-221 (1993) - [j82]Dany Breslauer, Zvi Galil:
Efficient Comparison Based String Matching. J. Complex. 9(3): 339-365 (1993) - [j81]Zvi Galil, Giuseppe F. Italiano:
Maintaining the 3-Edge-Connected Components of a Graph On-Line. SIAM J. Comput. 22(1): 11-28 (1993) - 1992
- [j80]David Eppstein, Zvi Galil, Raffaele Giancarlo, Giuseppe F. Italiano
Sparse Dynamic Programming I: Linear Cost Functions. J. ACM 39(3): 519-545 (1992) - [j79]David Eppstein, Zvi Galil, Raffaele Giancarlo, Giuseppe F. Italiano
Sparse Dynamic Programming II: Convex and Concave Cost Functions. J. ACM 39(3): 546-567 (1992) - [j78]Amir M. Ben-Amram, Zvi Galil:
On Pointers versus Addresses. J. ACM 39(3): 617-648 (1992) - [j77]Zvi Galil, Raffaele Giancarlo:
On the Exact Complexity of String Matching: Upper Bounds. SIAM J. Comput. 21(3): 407-437 (1992) - [j76]Dany Breslauer, Zvi Galil:
A Lower Bound for Parallel String Matching. SIAM J. Comput. 21(5): 856-862 (1992) - [j75]Zvi Galil, Giuseppe F. Italiano:
Fully Dynamic Algorithms for 2-Edge Connectivity. SIAM J. Comput. 21(6): 1047-1069 (1992) - [j74]Zvi Galil:
Renato Capocelli. SIGACT News 23(2): 104 (1992) - [j73]Zvi Galil, Kunsoo Park:
Dynamic Programming with Convexity, Concavity, and Sparsity. Theor. Comput. Sci. 92(1): 49-76 (1992) - [j72]Yuval Rabani
On the Space Complexity of Some Algorithms for Sequence Comparison. Theor. Comput. Sci. 95(2): 231-244 (1992) - 1991
- [j71]Zvi Galil, Giuseppe F. Italiano
Data Structures and Algorithms for Disjoint Set Union Problems. ACM Comput. Surv. 23(3): 319-344 (1991) - [j70]Zvi Galil, Giuseppe F. Italiano
A Note on Set Union with Arbitrary Deunions. Inf. Process. Lett. 37(6): 331-335 (1991) - [j69]Pavol Duris, Zvi Galil:
Two Lower Bounds in Asynchronous Distributed Computation. J. Comput. Syst. Sci. 42(3): 254-266 (1991) - [j68]Zvi Galil, Raffaele Giancarlo:
On the Exact Complexity of String Matching: Lower Bounds. SIAM J. Comput. 20(6): 1008-1020 (1991) - [j67]Zvi Galil, Oded Margalit:
An Almost Linear-Time Algorithm for the Dense Subset-Sum Problem. SIAM J. Comput. 20(6): 1157-1189 (1991) - [j66]Zvi Galil, Giuseppe F. Italiano:
Reducing edge connectivity to vertex connectivity. SIGACT News 22(1): 57-61 (1991) - [j65]Amir Averbuch, Zvi Galil, Shmuel Winograd:
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]/<u^n>. Theor. Comput. Sci. 86(2): 143-203 (1991) - 1990
- [j64]Zvi Galil, Kunsoo Park:
A Linear-Time Algorithm for Concave One-Dimensional Dynamic Programming. Inf. Process. Lett. 33(6): 309-311 (1990) - [j63]Zvi Galil, Kunsoo Park:
An Improved Algorithm for Approximate String Matching. SIAM J. Comput. 19(6): 989-999 (1990) - [j62]Dany Breslauer, Zvi Galil:
An Optimal O(log log n) Time Parallel String Matching Algorithm. SIAM J. Comput. 19(6): 1051-1058 (1990) - 1989
- [j61]Zvi Galil, Ravi Kannan, Endre Szemerédi:
On 3-pushdown graphs with large separators. Comb. 9(1): 9-19 (1989) - [j60]Zvi Galil, Victor Y. Pan:
Parallel Evaluation of the Determinant and of the Inverse of a Matrix. Inf. Process. Lett. 30(1): 41-45 (1989) - [j59]Harold N. Gabow, Zvi Galil, Thomas H. Spencer:
Efficient implementation of graph algorithms using contraction. J. ACM 36(3): 540-572 (1989) - [j58]Mark Chaimovich, Gregory Freiman, Zvi Galil:
Solving dense subset-sum problems by using analytical number theory. J. Complex. 5(3): 271-282 (1989) - [j57]Zvi Galil, Ravi Kannan, Endre Szemerédi:
On Nontrivial Separators for k-Page Graphs and Simulations by Nondeterministic One-Tape Turing Machines. J. Comput. Syst. Sci. 38(1): 134-149 (1989) - [j56]Zvi Galil, Stuart Haber, Moti Yung:
Minimum-Knowledge Interactive Proofs for Decision Problems. SIAM J. Comput. 18(4): 711-739 (1989) - [j55]Zvi Galil, Raffaele Giancarlo:
Speeding up Dynamic Programming with Applications to Molecular Biology. Theor. Comput. Sci. 64(1): 107-118 (1989) - 1988
- [j54]Zvi Galil, Victor Y. Pan:
Improved processor bounds for combinatorial problems in RNC. Comb. 8(2): 189-200 (1988) - [j53]Zvi Galil, Baruch Schieber:
On finding most uniform spanning trees. Discret. Appl. Math. 20(2): 173-175 (1988) - [j52]Zvi Galil, Éva Tardos:
An O(n²(m + n log n)log n) min-cost flow algorithm. J. ACM 35(2): 374-386 (1988) - [j51]Zvi Galil, Raffaele Giancarlo:
Data structures and algorithms for approximate string matching. J. Complex. 4(1): 33-72 (1988) - [j50]Amir Averbuch, Zvi Galil, Shmuel Winograd:
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. 58: 17-56 (1988) - 1987
- [j49]Pavol Duris, Zvi Galil, Georg Schnitger:
Lower Bounds on Communication Complexity. Inf. Comput. 73(1): 1-22 (1987) - [j48]Zvi Galil, Moti Yung:
Partitioned Encryption and Achieving Simultaneity by Partitioning. Inf. Process. Lett. 26(2): 81-88 (1987) - [j47]Zvi Galil, Christoph M. Hoffmann, Eugene M. Luks, Claus-Peter Schnorr, Andreas Weber:
An O(n³log n) deterministic and an O(n³) Las Vegs isomorphism test for trivalent graphs. J. ACM 34(3): 513-531 (1987) - [j46]Noga Alon, Zvi Galil, V. D. Milman:
Better Expanders and Superconcentrators. J. Algorithms 8(3): 337-347 (1987) - [j45]Zvi Galil, Gad M. Landau, Mordechai M. Yung:
Distributed Algorithms in Synchronous Broadcasting Networks. Theor. Comput. Sci. 49: 171-184 (1987) - [j44]Zvi Galil, Raffaele Giancarlo:
Parallel String Matching with k Mismatches. Theor. Comput. Sci. 51: 341-348 (1987) - 1986
- [j43]Harold N. Gabow, Zvi Galil, Thomas H. Spencer
Efficient algorithms for finding minimum spanning trees in undirected and directed graphs. Comb. 6(2): 109-122 (1986) - [j42]Zvi Galil:
Efficient Algorithms for Finding Maximum Matching in Graphs. ACM Comput. Surv. 18(1): 23-38 (1986) - [j41]Zvi Galil, Silvio Micali, Harold N. Gabow:
An O(EV log V) Algorithm for Finding a Maximal Weighted Matching in General Graphs. SIAM J. Comput. 15(1): 120-130 (1986) - [j40]Zvi Galil, Raffaele Giancarlo:
Improved string matching with k mismatches. SIGACT News 17(4): 52-54 (1986) - 1985
- [j39]Zvi Galil:
Optimal Parallel Algorithms for String Matching. Inf. Control. 67(1-3): 144-157 (1985) - 1984
- [j38]Pavol Duris, Zvi Galil, Wolfgang J. Paul, Rüdiger Reischuk:
Two Nonlinear Lower Bounds for On-Line Computations. Inf. Control. 60(1-3): 1-11 (1984) - [j37]Pavol Duris, Zvi Galil:
A Time-Space Tradeoff for Language Recognition. Math. Syst. Theory 17(1): 3-12 (1984) - [j36]Pavol Duris, Zvi Galil:
Two Tapes are Better than One for Nondeterministic Machines. SIAM J. Comput. 13(2): 219-227 (1984) - 1983
- [j35]Zvi Galil, Wolfgang J. Paul:
An Efficient General-Purpose Parallel Computer. J. ACM 30(2): 360-387 (1983) - [j34]Daniel Leven, Zvi Galil:
NP Completeness of Finding the Chromatic Index of Regular Graphs. J. Algorithms 4(1): 35-44 (1983) - [j33]Zvi Galil, Joel I. Seiferas:
Time-Space-Optimal String Matching. J. Comput. Syst. Sci. 26(3): 280-294 (1983) - 1982
- [j32]Pavol Duris, Zvi Galil:
On Reversal-Bounded Counter Machines and on Pushdown Automata with a Bound on the Size of their Pushdown Store. Inf. Control. 54(3): 217-227 (1982) - [j31]Albert G. Greenberg, Richard E. Ladner
Efficient Parallel Algorithms for Linear Recurrence Computation. Inf. Process. Lett. 15(1): 31-35 (1982) - [j30]Zvi Galil:
An Almost Linear-Time Algorithm for Computing a Dependency Basis in a Relational Database. J. ACM 29(1): 96-102 (1982) - [j29]Pavol Duris, Zvi Galil:
Fooling a two Way Automaton or one Pushdown Store is better than one Counter for two Way Machines. Theor. Comput. Sci. 21: 39-53 (1982) - 1981
- [j28]Zvi Galil:
String Matching in Real Time. J. ACM 28(1): 134-149 (1981) - [j27]Ofer Gabber, Zvi Galil:
Explicit Constructions of Linear-Sized Superconcentrators. J. Comput. Syst. Sci. 22(3): 407-420 (1981) - [j26]Zvi Galil, Joel I. Seiferas:
Linear-Time String-Matching Using only a Fixed Number of Local Storage Locations. Theor. Comput. Sci. 13: 331-336 (1981) - [j25]Zvi Galil:
On the Theoretical Efficiency of Various Network Flow Algorithms. Theor. Comput. Sci. 14: 103-111 (1981) - 1980
- [j24]Zvi Galil:
Applications of Efficient Mergeable Heaps for Optimization Problems on Trees. Acta Informatica 13: 53-58 (1980) - [j23]Zvi Galil:
An O(V5/3 E2/3) Algorithm for the Maximal Flow Problem. Acta Informatica 14: 221-242 (1980) - [j22]Zvi Galil, Amnon Naamad:
An O(EVlog²V) Algorithm for the Maximal Flow Problem. J. Comput. Syst. Sci. 21(2): 203-217 (1980) - [j21]Zvi Galil:
Finding the Vertex Connectivity of Graphs. SIAM J. Comput. 9(1): 197-199 (1980) - [j20]Zvi Galil, Joel I. Seiferas:
Saving Space in Fast String-Matching. SIAM J. Comput. 9(2): 417-438 (1980) - 1979
- [j19]Zvi Galil:
On Improving the Worse Case Running Time of the Boyer-Moore String Matching Algorithm. Commun. ACM 22(9): 505-508 (1979) - [j18]Zvi Galil, Nimrod Megiddo:
A Fast Selection Algorithm and the Problem of Optimum Distribution of Effort. J. ACM 26(1): 58-64 (1979) - [j17]Nimrod Megiddo, Zvi Galil:
On Fulkerson's Conjecture About Consistent Labeling Processes. Math. Oper. Res. 4(3): 265-267 (1979) - [j16]Arnold L. Rosenberg, Derick Wood, Zvi Galil:
Storage Representations for Tree-Like Data Structures. Math. Syst. Theory 13: 105-130 (1979) - 1978
- [j15]Zvi Galil, Joel I. Seiferas:
A Linear-Time On-Line Recognition Algorithm for "Palstar". J. ACM 25(1): 102-111 (1978) - [j14]Zvi Galil:
Palindrome Recognition in Real Time by a Multitape Turing Machine. J. Comput. Syst. Sci. 16(2): 140-157 (1978) - [j13]Zvi Galil:
Killing two birds with one stone. SIGACT News 10(1): 22-24 (1978) - 1977
- [j12]Zvi Galil:
Some Open Problems in the Theory of Computation as Questions about Two-Way Deterministic Pushdown Automaton Languages. Math. Syst. Theory 10: 211-228 (1977) - [j11]Joel I. Seiferas, Zvi Galil:
Real-Time Recognition of Substring Repetition and Reversal. Math. Syst. Theory 11: 111-146 (1977) - [j10]Zvi Galil:
On Resolution with Clauses of Bounded Size. SIAM J. Comput. 6(3): 444-459 (1977) - [j9]Zvi Galil:
On the Complexity of Regular Resolution and the Davis-Putnam Procedure. Theor. Comput. Sci. 4(1): 23-46 (1977) - [j8]Zvi Galil, Nimrod Megiddo:
Cyclic Ordering is NP-Complete. Theor. Comput. Sci. 5(2): 179-182 (1977) - 1976
- [j7]Zvi Galil:
Hierarchies of Complete Problems. Acta Informatica 6: 77-88 (1976) - [j6]Kurt Mehlhorn, Zvi Galil:
Monotone switching circuits and boolean matrix product. Computing 16(1-2): 99-111 (1976) - [j5]Zvi Galil:
Two Fast Simulations Which Imply Some Fast String Matching and Palindrome-Recognition Algorithms. Inf. Process. Lett. 4(4): 85-87 (1976) - [j4]Zvi Galil, Janos Simon:
A Note on Multiple-Entry Finite Automata. J. Comput. Syst. Sci. 12(3): 350-351 (1976) - 1975
- [j3]Zvi Galil:
Functional Schemas with Nested Predicates. Inf. Control. 27(4): 349-368 (1975) - [j2]Zvi Galil:
On converting on-line algorithms into real-time and on real-time algorithms for string-matching and palindrome recognition. SIGACT News 7(4): 26-30 (1975) - 1974
- [j1]Zvi Galil:
On some direct encodings of nondeterministic Turing machines operating in polynomial time into p-complete problems. SIGACT News 6(1): 19-24 (1974)
Conference and Workshop Papers
- 2022
- [c79]Geonmo Gu, Yehyun Nam
Efficient Graph Isomorphism Query Processing using Degree Sequences and Color-Label Distributions. ICDE 2022: 872-884 - 2021
- [c78]Geonmo Gu, Yehyun Nam
Scalable Graph Isomorphism: Combining Pairwise Color Refinement and Backtracking via Compressed Candidate Space. ICDE 2021: 1368-1379 - 2013
- [c77]Alberto Apostolico, Maxime Crochemore, Martin Farach-Colton
Forty Years of Text Indexing. CPM 2013: 1-10 - 2011
- [c76]Dany Breslauer, Zvi Galil:
Real-Time Streaming String-Matching. CPM 2011: 162-172 - 2010
- [c75]Zvi Galil:
Old and New in Stringology. CPM 2010: 26 - 1997
- [c74]Zvi Galil:
Open Problems In Stringology, Thirteen years Later. SEQUENCES 1997: 347 - [c73]Zvi Galil, Jong Geun Park, Kunsoo Park:
Three-Dimensional Pattern Matching. SPAA 1997: 53-62 - 1995
- [c72]Noga Alon, Zvi Galil, Moti Yung:
Efficient Dynamic-Resharing "Verifiable Secret Sharing" Against Mobile Adversary. ESA 1995: 523-537 - [c71]Zvi Galil, Alain J. Mayer, Moti Yung:
Resolving Message Complexity of Byzantine Agreement and beyond. FOCS 1995: 724-733 - [c70]Amir M. Ben-Amram, Zvi Galil:
Lower Bounds on Algebraic Random Access Machines (Extended Abstract). ICALP 1995: 360-371 - [c69]Pavol Duris, Zvi Galil:
Sensing Versus Nonsensing Automata. ICALP 1995: 455-463 - [c68]Zvi Galil, Xiangdong Yu:
Short length versions of Menger's theorem (Extended Abstract). STOC 1995: 499-508 - [c67]Artur Czumaj, Zvi Galil, Leszek Gasieniec, Kunsoo Park, Wojciech Plandowski:
Work-time-optimal parallel algorithms for string problems. STOC 1995: 713-722 - 1994
- [c66]Alberto Apostolico, Dany Breslauer, Zvi Galil:
Parallel Detection of all Palindromes in a String. STACS 1994: 497-506 - 1993
- [c65]Richard Cole, Maxime Crochemore, Zvi Galil, Leszek Gasieniec, Ramesh Hariharan, S. Muthukrishnan, Kunsoo Park, Wojciech Rytter:
Optimally fast parallel algorithms for preprocessing and pattern matching in one and two dimensions. FOCS 1993: 248-258 - [c64]Amir M. Ben-Amram, Zvi Galil:
When can we sort in o(n log n) time? FOCS 1993: 538-546 - [c63]Matthew K. Franklin, Zvi Galil, Moti Yung:
Eavesdropping Games: A Graph-Theoretic Approach to Privacy in Distributed Systems. FOCS 1993: 670-679 - [c62]David Eppstein, Zvi Galil, Giuseppe F. Italiano, Thomas H. Spencer:
Separator based sparsification for dynamic planar graph algorithms. STOC 1993: 208-217 - 1992
- [c61]David Eppstein, Zvi Galil, Giuseppe F. Italiano, Amnon Nissenzweig:
Sparsification-A Technique for Speeding up Dynamic Graph Algorithms (Extended Abstract). FOCS 1992: 60-69 - [c60]Zvi Galil, Kunsoo Park:
Truly Alphabet-Independent Two-Dimensional Pattern Matching. FOCS 1992: 247-256 - [c59]Noga Alon, Zvi Galil, Oded Margalit, Moni Naor:
Witnesses for Boolean Matrix Multiplication and for Shortest Paths. FOCS 1992: 417-426 - [c58]Alberto Apostolico, Dany Breslauer, Zvi Galil:
Optimal Parallel Algorithms for Periods, Palindromes and Squares (Extended Abstract). ICALP 1992: 296-307 - [c57]Zvi Galil:
A Constant-Time Optimal Parallel String-Matching Algorithm. STOC 1992: 69-76 - [c56]Zvi Galil, Giuseppe F. Italiano, Neil Sarnak:
Fully Dynamic Planarity Testing (Extended Abstract). STOC 1992: 495-506 - 1991
- [c55]Noga Alon, Zvi Galil, Oded Margalit:
On the Exponent of the All Pairs Shortest Path Problem. FOCS 1991: 569-575 - [c54]Amir M. Ben-Amram, Zvi Galil:
Lower Bounds for Data Structure Problems on RAMs (Extended Abstract). FOCS 1991: 622-631 - [c53]Zvi Galil, Giuseppe F. Italiano:
Maintaining Biconnected Components of Dynamic Planar Graphs. ICALP 1991: 339-350 - [c52]Pavol Duris, Zvi Galil:
On the Power of Multiple Reads in a Chip. ICALP 1991: 697-706 - [c51]Zvi Galil, Oded Margalit:
An Almost Linear-Time Algorithm for the Dense Subset-Sum Problem. ICALP 1991: 719-727 - [c50]Zvi Galil, Giuseppe F. Italiano:
Fully Dynamic Algorithms for Edge-Connectivity Problems (Extended Abstract). STOC 1991: 317-327 - [c49]Dany Breslauer, Zvi Galil:
A Lower Bound for Parallel String Matching. STOC 1991: 439-443 - 1990
- [c48]Livio Colussi, Zvi Galil, Raffaele Giancarlo:
On the Exact Complexity of String Matching (Extended Abstract). FOCS 1990: 135-144 - [c47]Moshe Dubiner, Zvi Galil, Edith Magen:
Faster Tree Pattern Matching. FOCS 1990: 145-150 - [c46]Zvi Galil:
Recent Progress in String Algorithms. SIGAL International Symposium on Algorithms 1990: 1 - [c45]David Eppstein, Zvi Galil, Raffaele Giancarlo, Giuseppe F. Italiano:
Sparse Dynamic Programming. SODA 1990: 513-522 - 1989
- [c44]Zvi Galil, Stuart Haber, Moti Yung:
Security against Replay Chosen-Ciphertext Attack. Distributed Computing And Cryptography 1989: 183-190 - [c43]Zvi Galil, Stuart Haber, Moti Yung:
A Secure Public-key Authentication Scheme. EUROCRYPT 1989: 3-15 - [c42]David Eppstein, Zvi Galil:
Parallel Algorithmic Techniques for Combinatorial Computation. ICALP 1989: 304-318 - [c41]Zvi Galil, Kunsoo Park:
An Improved Algorithm for Approximate String Matching. ICALP 1989: 394-404 - [c40]Salvatore J. Stolfo, Zvi Galil, Kathleen R. McKeown, Russell Mills:
Speech Recognition in Parallel. HLT (2) 1989 - [c39]Omer Berkman, Dany Breslauer, Zvi Galil, Baruch Schieber, Uzi Vishkin:
Highly Parallelizable Problems (Extended Abstract). STOC 1989: 309-319 - 1988
- [c38]David Eppstein, Zvi Galil, Raffaele Giancarlo:
Speeding up Dynamic Programming. FOCS 1988: 488-496 - [c37]Amir M. Ben-Amram, Zvi Galil:
On Pointers versus Addresses (Extended Abstract). FOCS 1988: 532-538 - 1987
- [c36]Zvi Galil, Stuart Haber, Moti Yung:
Cryptographic Computation: Secure Faut-Tolerant Protocols and the Public-Key Model. CRYPTO 1987: 135-155 - [c35]Pavol Duris, Zvi Galil:
Two Lower Bounds in Asynchronous Distributed Computation (Preliminary Version). FOCS 1987: 326-330 - 1986
- [c34]Zvi Galil, Éva Tardos:
An O(n^2 (m + n log n) log n) Min-Cost Flow Algorithm. FOCS 1986: 1-9 - [c33]Amir Averbuch, Shmuel Winograd, Zvi Galil:
Classification of all the Minimal Bilinear Algorithms for Computing the Coefficients of the Product of Two Polynomials Modulo a Polynomial. ICALP 1986: 31-39 - [c32]Zvi Galil, Ravi Kannan, Endre Szemerédi:
On Nontrivial Separators for k-Page Graphs and Simulations by Nondeterministic One-Tape Turing Machines. STOC 1986: 39-49 - 1985
- [c31]Zvi Galil, Stuart Haber, Moti Yung:
Symmetric Public-Key Encryption. CRYPTO 1985: 128-137 - [c30]Zvi Galil, Stuart Haber, Moti Yung:
A Private Interactive Test of a Boolean Predicate and Minimum-Knowledge Public-Key Cryptosystems (Extended Abstract). FOCS 1985: 360-371 - [c29]Zvi Galil, Victor Y. Pan:
Improved Processor Bounds for Algebraic and Combinatorial Problems in RNC. FOCS 1985: 490-495 - [c28]Gad M. Landau, Mordechai M. Yung, Zvi Galil:
Distributed Algorithms in Synchronous Broadcasting Networks (Extended Abstract). ICALP 1985: 363-372 - 1984
- [c27]Harold N. Gabow, Zvi Galil, Thomas H. Spencer:
Efficient Implementation of Graph Algorithms Using Contraction. FOCS 1984: 347-357 - [c26]Pavol Duris, Zvi Galil, Georg Schnitger:
Lower Bounds on Communication Complexity. STOC 1984: 81-91 - [c25]Zvi Galil:
Optimal Parallel Algorithms for String Matching. STOC 1984: 240-248 - 1983
- [c24]Zvi Galil:
Efficient Algorithms for Finding Maximal Matching in Graphs. CAAP 1983: 90-113 - [c23]Pavol Duris, Zvi Galil, Wolfgang J. Paul, Rüdiger Reischuk:
Two Nonlinear Lower Bounds. STOC 1983: 127-132 - 1982
- [c22]Zvi Galil, Christoph M. Hoffmann, Eugene M. Luks, Claus-Peter Schnorr, Andreas Weber:
An O(n^3 log n) Deterministic and an O(n^3) Probabilistic Isomorphism Test for Trivalent Graphs. FOCS 1982: 118-125 - [c21]Zvi Galil, Silvio Micali, Harold N. Gabow:
Priority Queues with Variable Priority and an O(EV log V) Algorithm for Finding a Maximal Weighted Matching in General Graphs. FOCS 1982: 255-261 - [c20]Pavol Duris, Zvi Galil:
On Reversal-Bounded Counter Machines and on Pushdown Automata with a Bound on the Size of the Pushdown Store. ICALP 1982: 166-175 - [c19]Pavol Duris, Zvi Galil:
Two Tapes are Better than One for Nondeterministic Machines. STOC 1982: 1-7 - 1981
- [c18]Pavol Duris, Zvi Galil:
A Time-Space Tradeoff for Language Recognition. FOCS 1981: 53-57 - [c17]Zvi Galil, Joel I. Seiferas:
Time-Space-Optimal String Matching. STOC 1981: 106-113 - [c16]Pavol Duris, Zvi Galil:
Fooling a Two-Way Automaton or One Pushdown Store Is Better Than One Counter for Two Way Machines (Preliminary Version). STOC 1981: 177-188 - [c15]Zvi Galil, Wolfgang J. Paul:
An Efficient General Purpose Parallel Computer. STOC 1981: 247-262 - 1980
- [c14]Zvi Galil, Wolfgang J. Paul:
Effizienz Paralleler Rechner. GI Jahrestagung 1980: 54-64 - [c13]Zvi Galil:
An Almost Linaer Time Algorithm for Computing a Dependency Basis in a Relational Data Base. ICALP 1980: 246-256 - 1979
- [c12]Ofer Gabber, Zvi Galil:
Explicit Constructions of Linear Size Superconcentrators. FOCS 1979: 364-370 - [c11]Zvi Galil, Amnon Naamad:
Network Flow and Generalized Path Compression. STOC 1979: 13-26 - [c10]Arnold L. Rosenberg, Derick Wood, Zvi Galil:
Storage Representations for Tree-Like Data Structures. STOC 1979: 99-107 - 1978
- [c9]Zvi Galil:
A New Algorithm for the Maximal Flow Problem. FOCS 1978: 231-245 - [c8]Zvi Galil:
On Improving the Worst Case Running Time of the Boyer-Moore String Matching Algorithm. ICALP 1978: 241-250 - 1977
- [c7]Zvi Galil, Joel I. Seiferas:
Saving Space in Fast String-Matching. FOCS 1977: 179-188 - 1976
- [c6]Zvi Galil, Joel I. Seiferas:
Recognizing Certain Repetitions and Reversals Within Strings. FOCS 1976: 236-252 - [c5]Zvi Galil:
On Enumeration Procedures for Theorem Proving and for Integer Programming. ICALP 1976: 355-381 - [c4]Zvi Galil:
Real-Time Algorithms for String-Matching and Palindrome Recognition. STOC 1976: 161-173 - 1975
- [c3]Kurt Mehlhorn, Zvi Galil:
Monotone Switching Circuits and Boolean Matrix Product. MFCS 1975: 315-319 - [c2]Zvi Galil:
On the Validity and Complexity of Bounded Resolution. STOC 1975: 72-82 - 1974
- [c1]Zvi Galil:
Two Way Deterministic Pushdown Automaton Languages and Some Open Problems in the Theory of Computation. SWAT 1974: 170-177
Parts in Books or Collections
- 1999
- [p2]David Eppstein, Zvi Galil, Giuseppe F. Italiano:
Dynamic Graph Algorithms. Algorithms and Theory of Computation Handbook 1999 - 1997
- [p1]Zvi Galil, I. Yudkiewicz:
Off-line parallel exact string searching. Pattern Matching Algorithms 1997: 55-88
Editorship
- 1997
- [e6]Alberto Apostolico, Zvi Galil:
Pattern Matching Algorithms. Oxford University Press 1997, ISBN 978-019-511367-9 [contents] - 1995
- [e5]Zvi Galil, Esko Ukkonen:
Combinatorial Pattern Matching, 6th Annual Symposium, CPM 95, Espoo, Finland, July 5-7, 1995, Proceedings. Lecture Notes in Computer Science 937, Springer 1995, ISBN 3-540-60044-2 [contents] - 1993
- [e4]Alberto Apostolico, Maxime Crochemore, Zvi Galil, Udi Manber:
Combinatorial Pattern Matching, 4th Annual Symposium, CPM 93, Padova, Italy, June 2-4, 1993, Proceedings. Lecture Notes in Computer Science 684, Springer 1993, ISBN 3-540-56764-X [contents] - 1992
- [e3]Alberto Apostolico, Maxime Crochemore, Zvi Galil, Udi Manber:
Combinatorial Pattern Matching, Third Annual Symposium, CPM 92, Tucson, Arizona, USA, April 29 - May 1, 1992, Proceedings. Lecture Notes in Computer Science 644, Springer 1992, ISBN 3-540-56024-6 [contents] - [e2]Danny Dolev, Zvi Galil, Michael Rodeh:
Theory of Computing and Systems, ISTCS'92, Israel Symposium, Haifa, Israel, May 1992. Lecture Notes in Computer Science 601, Springer 1992, ISBN 3-540-55553-6 [contents] - 1985
- [e1]Mary S. Van Deusen, Zvi Galil, Brian K. Reid:
Conference Record of the Twelfth Annual ACM Symposium on Principles of Programming Languages, New Orleans, Louisiana, USA, January 1985. ACM Press 1985, ISBN 0-89791-147-4 [contents]
Informal and Other Publications
- 1995
- [i1]Amir M. Ben-Amram, Zvi Galil:
On Data Structure Tradeoffs and an Application to Union-Find. Electron. Colloquium Comput. Complex. TR95 (1995)
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from ,
, and
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and
to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from .
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2025-10-28 23:36 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: