Near-Resolution of the Tradeoff Conjecture in Distributed Proof Labeling Schemes
A. Filtser, O. Fischer.
Accepted to PODC'26
The Task Completion Problem and its Application to Crash-Resilient Computation
O. Fischer, R. Gelles.
Accepted to PODC'26
How to Walk a Dog in Parallel: on Parallel Computation of the Fréchet Distance
L. Barenboim, A. Filtser, O. Filtser, O. Fischer.
Manuscript, 2026
Two for One, One for All: Deterministic LDC-based Robust Computation in Congested Clique
K. Censor-Hillel, O. Fischer, R. Gelles, P. Soto.
DISC’25, Selected as Spotlight
Depth-Width Tradeoffs in Algorithmic Reasoning of Graph Tasks with Transformers
G. Yehudai, C. Sanford, M. Bechler-Speicher, O. Fischer, R. Gilad-Bachrach, A. Globerson.
NeurIPS’25, Selected as Spotlight
All-to-All Communication with Mobile Edge Adversary: Almost Linearly More Faults, For Free
O. Fischer, M. Parter.
PODC’25
Pointer Chasing with Unlimited Interaction
O. Fischer, R. Oshman, A. Rosen, T. Roth.
SIROCCO’25 - Selected for special issue
Embedding Dimension of Contrastive Learning and k-Nearest Neighbors
D. Avdiukhin, V. Chatziafratis, O. Fischer, G. Yaroslavtsev.
NeurIPS’24
Optimal Sample Complexity of Contrastive Learning
N. Alon, D. Avdiukhin, D. Elboim, O. Fischer, G. Yaroslavtsev.
ICLR 2023 - Selected as Spotlight
Distributed CONGEST Algorithms against Mobile Adversaries
O. Fischer, M.Parter.
PODC 2023
Tree Learning: Optimal Algorithms and Sample Complexity
D. Avdiukhin, G. Yaroslavtsev, D. Vainstein, O. Fischer, S. Das, F. Mirza.
AAAI 2023
Massively Parallel Computation in a Heterogeneous Regime
O. Fischer, A. Horowitz, R. Oshman.
PODC 2022 - Selected for special issue, Distributed Computing 2025
Proof Labeling Schemes for Reachability-Related Problems in Directed Graphs
Y. Ben-Shimon, O. Fischer R. Oshman.
SIROCCO 2022 - Best Paper & Best Student Paper
Quantum Distributed Algorithms for Detection of Cliques
K. Censor-Hillel, O. Fischer, D. Leitersdorf, F. Le Gall, R. Oshman.
ITCS 2022, QIP 2022
Explicit Space-Time Tradeoffs for Proof Labeling Schemes in Graphs with Small Separators
O. Fischer, R. Oshman, D. Shamir.
OPODIS 2021
Constant-Round Spanners and Shortest Paths in Congested Clique and MPC
M. Dory, O. Fischer, S. Khoury, D. Leitersdorf.
PODC 2021, Distributed Computing 2025
Fast Distributed Algorithms for Girth, Cycles and Small Subgraphs
K. Censor-Hillel, O. Fischer, T. Gonen, D. Leitersdorf, F. Le Gall, R. Oshman.
DISC 2020
Sublinear-Time Distributed Algorithms for Detecting Small Cliques and Even Cycles
T. Eden, N. Fiat, O. Fischer, F. Kuhn, R. Oshman.
DISC 2019 - Selected for special issue, Distributed Computing Journal 2021
A Distributed Algorithm for Directed Minimum-Weight Spanning Tree
O. Fischer, R. Oshman.
DISC 2019 - Best Paper, Distributed Computing Journal 2021
Distributed Uniformity Testing
O. Fischer, U. Meir, R. Oshman.
PODC 2018
Possibilities and Impossibilities for Distributed Subgraph Detection
O. Fischer, T. Gonen, F. Kuhn, R. Oshman.
SPAA 2018
3 Notes on Distributed Property Testing
G. Even, O. Fischer, P. Fraigniaud, T. Gonen, R. Levi, M. Medina, P. Montealegre, D. Olivetti, R. Oshman, I. Rapaport and I. Todinca.
DISC 2017
On The Multiparty Communication Complexity of Testing Triangle-Freeness
O. Fischer, S. Gershtein, R. Oshman.
PODC 2017
Public vs. Private Randomness in Simultaneous Multi-Party Communication Complexity
O. Fischer, R. Oshman, U. Zwick.
SIROCCO 2016 - Selected for special issue, TCS 2020
A Lower Bound on the Distributed Lovasz Local Lemma
S. Brandt, O. Fischer, J. Hirvonen, B. Keller, T. Lempiäinen, J. Rybicki, J. Suomela, J. Uitto.
STOC 2016