Liran Katzir
Liran Katzir is Research Scientist at Google Research. Liran's research interests include algorithmic statistical methods, streaming algorithms, and machine learning. His current project focus is the automation of medicine through intelligent imaging.
Liran Katzir received his B.A., M.A., and Ph.D. degrees in computer science from the Technion--Israel Institute of Technology, Haifa, Israel, in 2001, 2005, and 2008 respectively.
His Ph.D. thesis deals with scheduling algorithms in wireless access networks.
Then he took a series of positions in industrial research labs.
Research Areas
Authored Publications
Sort By
Detection of Elusive Polyps via a Large Scale AI System
Dan Livovsky
Danny Veikherman
Tomer Golany
Amit Aides
Valentin Dashinsky
Nadav Rabani
David Ben Shimol
Yochai Blau
Ilan Moshe Shimshoni
Ori Segol
Eran Goldin
Jesse Lachter
Ehud Rivlin
Daniel Freedman
Gastrointestinal Endoscopy (2021)
Preview abstract
Colorectal cancer (CRC) is the second leading cause of cancer death worldwide resulting in an estimated 900,000 deaths per year. Colonoscopy is the gold standard for detection and removal of precancerous lesions, and has been amply shown to reduce mortality. However, the miss rate for polyps during colonoscopies is 22-28%, while 20-24% of the missed lesions are histologically confirmed adenomas. To address this shortcoming, we propose a polyp detection system based on deep learning, which can alert the operator in real-time to the presence and location of polyps during a colonoscopy. We dub the system DEEP^2: DEEP DEtection of ElusivePolyps. The DEEP^2 system was trained on 3,611 hours of colonoscopy videos derived from two sources, and was validated on a set comprising 1,393 hours of video, coming from a third, unrelated source. For the validation set, the ground truth labelling was provided by offline GI annotators, who were able to watch the video in slow-motion and pause/rewind as required; two or three such annotators examined each video.
Overall, DEEP^2 achieves a sensitivity of 96.8% at 4.9 false alarms per video, which improves substantially on the current state of the art. These results are attained using a neural network architecture which is designed to provide fast computations, and can therefore run in real-time at greater than 30 frames per second. We further analyze the data by examining its performance on elusive polyps, those polyps which are particularly difficult for endoscopists to detect. First, we show that on fast polyps that are in the field of view for less than 5 seconds, DEEP^2 attains a sensitivity of 88.5%, compared to a sensitivity of 31.7% for the endoscopists performing the procedure. On even shorter duration polyps, those that are in the field of view for less than 2 seconds, the difference is even starker: DEEP^2 attains a sensitivity of 84.9% vs. 18.9% for the endoscopists. Second, we examine procedures which are apparently clean, in that no polyps are detected by either the performing endoscopist or the offline annotators. In these sequences, DEEP^2 is able to detect polyps -- not seen by either live endoscopists or offline annotators -- which were later verified to be real polyps: an average of 0.22 polyps per sequence, of which 0.10 are adenomas. Finally, a preliminary small clinical validation indicates that the system will be useful in practice: on 32 procedures, DEEP^2 discovered an average of 1.06 polyps per procedure that would have otherwise been missed by the GI performing the procedure. Future work will be needed to measure the clinical impact on a larger scale.
View details
Detecting Deficient Coverage in Colonoscopies
Amit Aides
Ariel Gordon
Daniel Freedman
Danny Veikherman
Ehud Rivlin
Ilan Moshe Shimshoni
Tomer Golany
Yochai Blau
IEEE Transactions on Medical Imaging (2020)
Preview abstract
Colorectal Cancer (CRC) is a global health problem, resulting in 900K deaths per year. Colonoscopy is the tool of choice for preventing CRC, by detecting polyps before they become cancerous, and removing them. However, colonoscopy is hampered by the fact that endoscopists routinely miss an average of 22-28% of polyps. While some of these missed polyps appear in the endoscopist's field of view, others are missed simply because of substandard coverage of the procedure, i.e. not all of the colon is seen. This paper attempts to rectify the problem of substandard coverage in colonoscopy through the introduction of the C2D2 (Colonoscopy Coverage Deficiency via Depth) algorithm which detects deficient coverage, and can thereby alert the endoscopist to revisit a given area. More specifically, C2D2 consists of two separate algorithms: the first performs depth estimation of the colon given an ordinary RGB video stream; while the second computes coverage given these depth estimates. Rather than compute coverage for the entire colon, our algorithm computes coverage locally, on a segment-by-segment basis; C2D2 can then indicate in real-time whether a particular area of the colon has suffered from deficient coverage, and if so the endoscopist can return to that area. Our coverage algorithm is the first such algorithm to be evaluated in a large-scale way; while our depth estimation technique is the first calibration-free unsupervised method applied to colonoscopies. The C2D2 algorithm achieves state of the art results in the detection of deficient coverage: it is 2.4 times more accurate than human experts.
View details
Interactive Proofs for Social Graphs
Clara Shikhelman
Eylon Yogev
Advances in Cryptology - CRYPTO 2020 - 40th Annual International Cryptology Conference,, Springer, Santa Barbara, CA, USA,, pp. 574-601
Preview abstract
We consider interactive proofs for social graphs, where the verifier has only oracle access to the graph and can query for the $i^{th}$ neighbor of a vertex $v$, given $i$ and $v$. In this model, we construct a doubly-efficient public-coin two-message interactive protocol for estimating the size of the graph to within a multiplicative factor $\eps>0$. The verifier performs $\widetilde{O}(1/\eps^2 \cdot \MixingTime \cdot \AverageDegree)$ queries to the graph, where $\MixingTime$ is the mixing time of the graph and $\AverageDegree$ is the average degree of the graph. The prover runs in quasi-linear time in the number of nodes in the graph.
Furthermore, we develop a framework for computing the quantiles of essentially any (reasonable) function $f$ of vertices/edges of the graph. Using this framework, we can estimate many health measures of social graphs such as the clustering coefficients and the average degree, where the verifier performs only a small number of queries to the graph.
Using the Fiat-Shamir paradigm, we are able to transform the above protocols to a non-interactive argument in the random oracle model. The result is that social media companies (e.g., Facebook, Twitter, etc.) can publish, once and for all, a short proof for the size or health of their social network. This proof can be publicly verified by any single user using a small number of queries to the graph.
View details
