University Logo Header

הפקולטה למדעי המחשב והמידע

אוניברסיטת חיפה

EN

University Logo Header
להרשמה
Oren Weimann

Prof. Oren Weimann

עברית | English

About▼

I am a professor in the Department of Computer Science at the University of Haifa. My research is in theoretical computer science, in the design and analysis of algorithms and data structures. I am particularly interested in algorithms for planar graphs, pattern matching, and fine-grained complexity.

Publications▼

  • Maintaining a Kingdom in a Tournament, Weimann, O. & Yuster, R., 2026, SOFSEM 2026: Theory and Practice of Computer Science - 51st International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2026, Proceedings. Kozik, J. & Wolff, A. (eds.). Springer Science and Business Media Deutschland GmbH, p. 347-360 14 p. (Lecture Notes in Computer Science; vol. 16448 LNCS).
  • A Simple Distributed Deterministic Planar Separator, Abd-Elhaleem, Y., Dory, M. & Weimann, O., 2026, Structural Information and Communication Complexity - 33rd International Colloquium, SIROCCO 2026, Proceedings. Georgiou, C. (ed.). Springer Science and Business Media Deutschland GmbH, p. 1-20 20 p. (Lecture Notes in Computer Science; vol. 16488 LNCS).
  • Faster Construction of a Planar Distance Oracle with Õ(1) Query Time, Boneh, I., Golan, S., Mozes, S., Prigan, D. & Weimann, O., 30 Jun 2025, 52nd International Colloquium on Automata, Languages, and Programming, ICALP 2025. Censor-Hillel, K., Grandoni, F., Ouaknine, J. & Puppis, G. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 33. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 334).
  • Õptimal Fault-Tolerant Labeling for Reachability and Approximate Distances in Directed Planar Graphs, Boneh, I., Chechik, S., Golan, S., Mozes, S. & Weimann, O., 15 Jun 2025, STOC 2025 - Proceedings of the 57th Annual ACM Symposium on Theory of Computing. Koucky, M. & Bansal, N. (eds.). Association for Computing Machinery, p. 2249-2256 8 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).
  • Distributed Maximum Flow in Planar Graphs, Abd-Elhaleem, Y., Dory, M., Parter, M. & Weimann, O., 13 Jun 2025, PODC 2025 - Proceedings of the 2025 ACM Symposium on Principles of Distributed Computing. Association for Computing Machinery, p. 278-286 9 p. (Proceedings of the Annual ACM Symposium on Principles of Distributed Computing; vol. Part of F216205).
  • Brief Announcement: Distributed Maximum Flow in Planar Graphs, Abd-Elhaleem, Y., Dory, M., Parter, M. & Weimann, O., 24 Oct 2024, 38th International Symposium on Distributed Computing, DISC 2024. Alistarh, D. (ed.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 40. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 319).
  • Minimum Cut in O(mlog2n) Time, Gawrychowski, P., Mozes, S. & Weimann, O., Aug 2024, In: Theory of Computing Systems. 68, 4, p. 814-834 21 p.
  • Õptimal Dynamic Time Warping on Run-Length Encoded Strings, Boneh, I., Golan, S., Mozes, S. & Weimann, O., Jul 2024, 51st International Colloquium on Automata, Languages, and Programming, ICALP 2024. Bringmann, K., Grohe, M., Puppis, G. & Svensson, O. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 30. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 297).
  • What Else Can Voronoi Diagrams Do for Diameter in Planar Graphs?, Abboud, A., Mozes, S. & Weimann, O., Sep 2023, 31st Annual European Symposium on Algorithms, ESA 2023. Li Gortz, I., Farach-Colton, M., Puglisi, S. J. & Herman, G. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 4. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 274).
  • Almost Optimal Exact Distance Oracles for Planar Graphs, Charalampopoulos, P., Gawrychowski, P., Long, Y., Mozes, S., Pettie, S., Weimann, O. & Wulff-Nilsen, C., 25 Mar 2023, In: Journal of the ACM. 70, 2, 12.
  • Improved Compression of the Okamura-Seymour Metric, Mozes, S., Wallheimer, N. & Weimann, O., 1 Dec 2022, 33rd International Symposium on Algorithms and Computation, ISAAC 2022. Bae, S. W. & Park, H. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 27. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 248).
  • The Fine-Grained Complexity of Episode Matching, Bille, P., Gørtz, I. L., Mozes, S., Steiner, T. A. & Weimann, O., 1 Jun 2022, 33rd Annual Symposium on Combinatorial Pattern Matching, CPM 2022. Bannai, H. & Holub, J. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 4. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 223).
  • Fault-tolerant distance labeling for planar graphs, Bar-Natan, A., Charalampopoulos, P., Gawrychowski, P., Mozes, S. & Weimann, O., 29 May 2022, In: Theoretical Computer Science. 918, p. 48-59 12 p.
  • On the Hardness of Computing the Edit Distance of Shallow Trees, Charalampopoulos, P., Gawrychowski, P., Mozes, S. & Weimann, O., 2022, String Processing and Information Retrieval - 29th International Symposium, SPIRE 2022, Proceedings. Arroyuelo, D., Arroyuelo, D. & Poblete, B. (eds.). Springer Science and Business Media Deutschland GmbH, p. 290-302 13 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 13617 LNCS).
  • An almost optimal edit distance oracle, Charalampopoulos, P., Gawrychowski, P., Mozes, S. & Weimann, O., 1 Jul 2021, 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021. Bansal, N., Merelli, E. & Worrell, J. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 48. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 198).
  • Voronoi diagrams on planar graphs, and computing the diameter in deterministic Õ(n5/3) time∗, Gawrychowski, P. L., Kaplan, H., Mozes, S., Sharir, M. & Weimann, O., 2021, In: SIAM Journal on Computing. 50, 3, p. 509-554 46 p.
  • Planar negative k-cycle, Gawrychowski, P., Mozes, S. & Weimann, O., 2021, ACM-SIAM Symposium on Discrete Algorithms, SODA 2021. Marx, D. (ed.). Association for Computing Machinery, p. 2717-2724 8 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).
  • Voronoi diagrams on planar graphs, and computing the diameter in deterministic Õ(n5/3) time∗, Gawrychowski, P. L., Kaplan, H., Mozes, S., Sharir, M. & Weimann, O., 2021, In: SIAM Journal on Computing. 50, 2, p. 509-554 46 p.
  • Fault-Tolerant Distance Labeling for Planar Graphs, Bar-Natan, A., Charalampopoulos, P., Gawrychowski, P., Mozes, S. & Weimann, O., 2021, Structural Information and Communication Complexity - 28th International Colloquium, SIROCCO 2021, Proceedings. Jurdziński, T. & Schmid, S. (eds.). Springer Science and Business Media Deutschland GmbH, p. 315-333 19 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) ; vol. 12810 LNCS).
  • Top Tree Compression of Tries, Bille, P., Gawrychowski, P., Gørtz, I. L., Landau, G. M. & Weimann, O., 2021, In: Algorithmica. 83, 12, p. 3602-3628 27 p.
  • A Note on a Recent Algorithm for Minimum Cut, Gawrychowski, P., Mozes, S. & Weimann, O., 2021, 4th Symposium on Simplicity in Algorithms, SOSA 2021. King, V. & Le, H. V. (eds.). Society for Industrial and Applied Mathematics Publications, p. 74-79 6 p. (4th Symposium on Simplicity in Algorithms, SOSA 2021).
  • Minimum cut in O(m log2 n) time, Gawrychowski, P., Mozes, S. & Weimann, O., 1 Jun 2020, 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020. Czumaj, A., Dawar, A. & Merelli, E. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 57. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 168).
  • On the fine-grained complexity of parity problems, Abboud, A., Feller, S. & Weimann, O., 1 Jun 2020, 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020. Czumaj, A., Dawar, A. & Merelli, E. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 5. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 168).
  • Compressed range minimum queries, Gawrychowski, P., Jo, S., Mozes, S. & Weimann, O., 6 Apr 2020, In: Theoretical Computer Science. 812, p. 39-48 10 p.
  • Submatrix Maximum Queries in Monge and Partial Monge Matrices Are Equivalent to Predecessor Search, Gawrychowski, P., Mozes, S. & Weimann, O., Apr 2020, In: ACM Transactions on Algorithms. 16, 2, 16.
  • 31st Annual Symposium on Combinatorial Pattern Matching, Gørtz, I. L. (Editor) & Weimann, O. (Editor), 2020, Schloss Dagstuhl -- Leibniz-Zentrum für Informatik. (LIPIcs)
  • A faster FPTAS for #knapsack, Gawrychowski, P., Markin, L. & Weimann, O., 1 Jul 2018, 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018. Kaklamanis, C., Marx, D., Chatzigiannakis, I. & Sannella, D. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 64. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 107).
  • Near-optimal compression for the planar graph metric, Abboud, A., Gawrychowski, P., Mozes, S. & Weimann, O., 2018, 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018. Czumaj, A. (ed.). Association for Computing Machinery, p. 530-549 20 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).
  • Tree edit distance cannot be computed in strongly subcubic time (unless APSP can), Bringmann, K., Gawrychowski, P., Mozes, S. & Weimann, O., 2018, 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018. Czumaj, A. (ed.). Association for Computing Machinery, p. 1190-1206 17 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).
  • Dispersion on trees, Gawrychowski, P., Krasnopolsky, N., Mozes, S. & Weimann, O., 1 Sep 2017, 25th European Symposium on Algorithms, ESA 2017. Sohler, C., Sohler, C. & Pruhs, K. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 40. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 87).
  • Longest common extensions in trees, Bille, P., Gawrychowski, P., Gørtz, I. L., Landau, G. M. & Weimann, O., 25 Jul 2016, In: Theoretical Computer Science. 638, p. 98-107 10 p.
  • Bookmarks in grammar-compressed strings, Cording, P. H., Gawrychowski, P. & Weimann, O., 2016, String Processing and Information Retrieval - 23rd International Symposium, SPIRE 2016, Proceedings. Inenaga, S., Sadakane, K. & Sakai, T. (eds.). Springer Verlag, p. 153-159 7 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 9954 LNCS).
  • Random access to grammar-compressed strings and trees, Bille, P., Landau, G. M., Raman, R., Sadakane, K., Satti, S. R. & Weimann, O., 2015, In: SIAM Journal on Computing. 44, 3, p. 513-539 27 p.
  • Towards optimal packed string matching, Ben-Kiki, O., Bille, P., Breslauer, D., Ga̧sieniec, L., Grossi, R. & Weimann, O., 13 Mar 2014, In: Theoretical Computer Science. 525, p. 111-129 19 p.
  • Improved submatrix maximum queries in Monge matrices, Gawrychowski, P., Mozes, S. & Weimann, O., 2014, Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Proceedings. PART 1 ed. Springer Verlag, p. 525-537 13 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 8572 LNCS, no. PART 1).
  • Approximating the diameter of planar graphs in near linear time, Weimann, O. & Yuster, R., 2013, Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Proceedings. PART 1 ed. p. 828-839 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 7965 LNCS, no. PART 1).
  • Tree compression with top trees, Bille, P., Gørtz, I. L., Landau, G. M. & Weimann, O., 2013, Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Proceedings. PART 1 ed. p. 160-171 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 7965 LNCS, no. PART 1).
  • Fast RNA structure alignment for crossing input structures, Backofen, R., Landau, G. M., Möhl, M., Tsur, D. & Weimann, O., Mar 2011, In: Journal of Discrete Algorithms. 9, 1, p. 2-11 10 p.
  • The Stackelberg minimum spanning tree game, Cardinal, J., Demaine, E. D., Fiorini, S., Joret, G., Langerman, S., Newman, I. & Weimann, O., Feb 2011, In: Algorithmica. 59, 2, p. 129-144 16 p.
  • Optimal packed string matching, Ben-Kiki, O., Bille, P., Breslauer, D., Ga̧sieniec, L., Grossi, R. & Weimann, O., 2011, 31st International Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2011. p. 423-432 10 p. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 13).
  • Distance oracles for vertex-labeled graphs, Hermelin, D., Levy, A., Weimann, O. & Yuster, R., 2011, Automata, Languages and Programming - 38th International Colloquium, ICALP 2011, Proceedings. PART 2 ed. p. 490-501 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 6756 LNCS, no. PART 2).
  • Replacement paths via fast matrix multiplication, Weimann, O. & Yuster, R., 2010, Proceedings - 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010. IEEE Computer Society, p. 655-662 8 p. 5671330. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).
  • Fast algorithms for computing tree LCS, Mozes, S., Tsur, D., Weimann, O. & Ziv-Ukelson, M., 6 Oct 2009, In: Theoretical Computer Science. 410, 43, p. 4303-4314 12 p.
  • Speeding Up HMM Decoding and Training by Exploiting Sequence Repetitions, Lifshits, Y., Mozes, S., Weimann, O. & Ziv-Ukelson, M., Jul 2009, In: Algorithmica. 54, 3, p. 379-399 21 p.
  • Shortest paths in directed planar graphs with negative lengths: A linear-space O(n log2 n)-time algorithm, Klein, P., Mozes, S. & Weimann, O., 2009, Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms. p. 236-245 10 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).
  • Locality and gaps in RNA comparison, Backofen, R., Chen, S., Hermelin, D., Landau, G. M., Roytberg, M. A., Weimann, O. & Zhang, K., 1 Oct 2007, In: Journal of Computational Biology. 14, 8, p. 1074-1087 14 p.
  • An optimal decomposition algorithm for tree edit distance, Demaine, E. D., Mozes, S., Rossman, B. & Weimann, O., 2007, Automata, Languages and Programming - 34th International Colloquium, ICALP 2007, Proceedings. Springer Verlag, p. 146-157 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 4596 LNCS).
  • Indexing a dictionary for subset matching queries, Landau, G. M., Tsur, D. & Weimann, O., 2007, String Processing and Information Retrieval - 14th International Symposium, SPIRE 2007, Proceedings. Springer Verlag, p. 195-204 10 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 4726 LNCS).
  • Local alignment of RNA sequences with arbitrary scoring schemes, Backofen, R., Hermelin, D., Landau, G. M. & Weimann, O., 2006, Combinatorial Pattern Matching - 17th Annual Symposium, CPM 2006, Proceedings. Springer Verlag, p. 246-257 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 4009 LNCS).
  • Gene proximity analysis across whole genomes via PQ trees, Landau, G. M., Parida, L. & Weimann, O., Dec 2005, In: Journal of Computational Biology. 12, 10, p. 1289-1306 18 p.

Research Areas▼

  • Algorithms for planar graphs
  • Combinatorial pattern matching
  • Fine-grained complexity