Ely Porat
I design provably optimal algorithms for massive data: finding patterns in streams too large to store, joining databases at the theoretical speed limit, and proving which problems cannot be solved faster.
Join the group
I am recruiting strong M.Sc. students, Ph.D. students and postdocs in algorithms and in the theory of AI. Strong candidates with publications, at every level, are especially encouraged to write.
Apply by emailWhat we look for and how to apply
Postdocs: a Ph.D. in computer science or mathematics and a strong publication record in theoretical computer science, typically at least three papers at top venues such as STOC, FOCS or SODA.
Ph.D. students: an M.Sc. in computer science or a related field, with at least one publication at a peer-reviewed international conference or journal.
You can follow your own line of research, though topics close to the group’s areas are encouraged. To apply, email a cover letter, CV, list of publications, and the names and contact details of at least two references, all as PDF files, to porately@cs.biu.ac.il.
Short bio
Copy-ready for talk announcements and introductions.
Honors & awards
ACM PODS Alberto O. Mendelzon Test-of-Time Award
For “Worst-case optimal join algorithms” (with H. Q. Ngo, C. Ré and A. Rudra), which introduced a new class of join algorithms now built into modern graph and relational database engines.
ERC Consolidator Grant
MPM: Modern Pattern Matching. €1,994,609, as Principal Investigator.
ACM PODS Best Paper Award
Worst-case optimal join algorithms.
IEEE INFOCOM Best Paper Runner-up
Optimal TCAM encodings of ranges.
Gehring Visiting Professor · Simons Institute
University of Michigan; then Visiting Scientist at the Simons Institute, UC Berkeley.
Latest
Israel at IOI 2026 (Uzbekistan): 3 gold and 1 bronze. I serve as Academic Director of the Israel National Computer Science Team, which prepares Israel’s olympiad delegations.
Israel's first IOAI delegation wins a team bronze in its debut (Astana).
Three papers at CPM 2026: Hamming Distance Oracles · Exploring the Gap Between LCS and LCStr · Set Parameterized Matching.
Program committee, ICALP 2025 Track A. “Locally Consistent Parsing” appears in SIAM J. Computing.
The questions I work on
My work combines algorithm design with matching lower bounds: first find the fastest method, then prove nothing faster exists.
Pattern matching at scale
How little memory does it take to find every approximate occurrence of a pattern?
Exact, k-mismatch and k-edit matching; dictionary matching; small-space text indexing. This was the core of the ERC project MPM.
Streaming & sketching
What can be computed about a huge data stream in one pass and almost no memory?
Moment estimation in optimal space, sketches of edit and shift distance, turnstile sampling, frequent items under time decay.
Distributed & parallel computing
How fast can many simple agents agree, communicate or balance load under adversarial conditions?
Population protocols for majority, resource-competitive broadcast against jamming, load balancing for every p-norm, parallel dynamic spanning forests.
Dynamic graphs & arboricity
Can a sparse graph keep a low out-degree orientation as it changes, with worst-case guarantees?
Edge orientations for graphs of bounded arboricity with worst-case update time, incremental orientation in forests, and dynamic set intersection.
Fine-grained complexity
Which polynomial running times are truly optimal, and can we prove it?
Conditional lower bounds from 3SUM, kSUM, set intersection and orthogonal vectors; space–time tradeoffs.
Data structures & filters
How small can a dynamic dictionary or filter be, and how fast can it answer?
A space lower bound for dynamic approximate membership, Bloom-filter replacements, cuckoo hashing and adaptive cuckoo filters, succinct dictionaries.
Group testing, sparsity & joins
How few measurements, or how little work, isolates the few items that matter?
Explicit nonadaptive group testing, sparse recovery that is optimal in both time and measurements, and worst-case optimal joins.
Algorithms meet AI
Can algorithmic guarantees make LLM training, agents and prompt optimization efficient and reliable?
Current work with AI21 Labs (Office of the CTO) on LLM training, action models and automated prompt optimization.
Key results
Problems where my work moved the best known bound, shown before and after.
Multiway database joins
Triangle query on relations of size NExact pattern matching in a stream
Pattern of length m, symbols arrive onlineExplicit nonadaptive group testing
d defectives among n items(1±ε) Hamming distance, all alignments
Text-to-pattern approximationStreaming k-mismatch
Matching with up to k errorsStreaming pattern matching, step by step
An interactive walkthrough of exact pattern matching in the streaming model with O(log m) words of memory: recursive pattern decomposition, Karp–Rabin-style forward fingerprints, and one candidate per level. The algorithm taught in Advanced Algorithms (Algo 2), presented at WAPMDS 2009; different from Porat & Porat, FOCS 2009.
k-Mismatch Walkthrough
Find every place where a pattern matches the text with at most k mismatches, in O(n√(k log m)) time (Amir, Lewenstein & Porat, SODA 2000; J. Algorithms 2004).
Wildcard k-Mismatch Walkthrough
Pattern matching with wildcards (don't cares) and up to k mismatches, built step by step as in the lecture (Clifford, Efremenko, Porat & Rothschild, ESA 2007; JCSS 2010).
MPM: Modern Pattern Matching
Consolidator Grant 683064 · Principal Investigator · Bar-Ilan University
Career
Starts B.Sc. at Bar-Ilan, age 15
B.Sc. summa cum laude, 1998; M.Sc. magna cum laude, 1999
Finished Ph.D. at 20, with distinction*
advisor Amihood Amir; joins BIU faculty
Tenured Associate Professor
Google Mountain View
Full Professor · PODS Best Paper
Michigan, Simons Institute
ERC Consolidator Grant
MPM Lab, 2017–2025
Academic Director of the National CS Team for the international olympiads; founds Israel's first IOAI and ICO delegations
AI21 Labs, CTO office (2024–)
* Finished his Ph.D. a month before turning 21.
Publications per year
Most frequent venues
Publications
Authors appear alphabetically, as is usual in theoretical computer science. Click a title to open a free copy. Publishers’ copyright agreements usually don’t allow posting their final typeset PDF on a personal site, so the free links go to the arXiv preprint or the author’s version of the same paper; the journal or proceedings version is under “Publisher”. An arXiv or author version is not always identical to the published one; please cite the published version. BibTeX for every paper: dblp.org/pid/02/836.bib.
Academic family
Postdocs
Ph.D. graduates
M.Sc. graduates
Current
All theses: 5 Ph.D. and 17 M.Sc.
Ph.D.
- Shay Golan, Online Algorithms for Big Data · 2020 · co-advised with T. Kopelowitz
- Isaac Goldstein, Polynomial Lower Bounds on Algorithms and Data Structures · 2020 · co-advised with M. Lewenstein
- Ariel Shiftan, Efficient Algorithms on Sets: Searching, Sampling and Indexing · 2016
- Guy Feigenblat, Processing Massive Data · 2016
- Erez Waisbard, Online Privacy and Integrity: Attacks, Infrastructure and Applications · 2015
M.Sc.
- Dvir Fried, Efficient Algorithms for k-Dyck Edit Distance Problems · 2023
- Or Birenzwige, Locally Consistent Parsing for Text Indexing in Small Space · 2021
- Matan Kraus, An O(log3/2 n) Parallel Time Population Protocol for Majority with O(log n) States · 2020
- Stav Ben-Nun, Time-Space Tradeoffs for Finding a Long Common Substring · 2019
- Hodaya Zipora Barr, Unconditional Lower Bound in Restricted Models · 2019
- Yair Rosenmutter, Improved Worst-Case Deterministic Parallel Dynamic Minimum Spanning Forest · 2017
- Shay Golan, Streaming Pattern Matching with d-Wildcards · 2015
- Amiad Rozenberg, Dictionary Matching with Wildcards · 2014
- Neta Barkay, Efficient Sampling of Non-strict Turnstile Data Streams · 2012
- Hagai Cohen, Text Indexing · 2010
- Benny Porat, Online Pattern Matching · 2010
- Amir Rothschild, Optimal Group Testing and Applications · 2009
- Assaf Tzur, Moment Distance · 2008
- Julia Umanski, Approximate Matching in the L1 Metric · 2005
- Estrella Eisenberg, Swap and Mismatch Edit Distance · 2004
- Michael Furman, The List-Traversal Synopses (LTS) System · 2003 · co-advised with Y. Matias
- Ohad Lipsky, Efficient Distance Computations · 2003
Most frequent co-authors
Researchers hosted at Bar-Ilan
Co-authors also include
Click a name to see our joint papers.
Academic Director, Israel National Computer Science Team
The team trains and selects Israel's delegations to the international olympiads. In 2026 I expanded it from one olympiad to three, founding Israel's first delegations to the International Olympiads in Artificial Intelligence (IOAI) and Cybersecurity (ICO).
won by Israeli students, 2026
2026
in its debut
Grants & service
Research funding
Service, industry & teaching
Full teaching history, 1999–2026
Bar-Ilan University: Advanced Algorithms (2001, 2002, 2014–present) · Algorithms 2 (2022–present) · Algorithms 1 (2023) · Discrete Structures (2024) · Introduction to Algorithms for Bioinformatics students (2023) · Computational Complexity (2000–2012, 2019, 2020) · Advanced Complexity (2001–2011) · Introduction to Complexity (2005–2009) · Data Structures (2003, 2017) · Data Science (2016) · Advanced Programming: Cloud Computing (2015) · Google Technologies for Cloud and Web Development (2012) · Internet Algorithms (2011) · Streaming Algorithms (2009, 2010) · Advanced Topics in Data Structures (2002, 2003) · Advanced Topics in Automata Theory (2003) · Computability (2001–2003) · Automata Theory (1999–2001) · Research Seminar (2000, 2001, 2010, 2019, 2020)
Tel Aviv University (visiting): Efficient Algorithms for Massive Data Sets (2004) · Pattern Matching (2002)
Contact
Department of Computer Science and Artificial Intelligence
Bar-Ilan University, Ramat Gan 5290002, Israel
Recruiting strong M.Sc. students, Ph.D. students and postdocs: see Join the group.