Rotem Oshman

Publication Activity (10 Years)

Years Active: 2007-2024
Publications (10 Years): 46

Top Topics

Computational Power

Related Problems

Top Venues

Publications

Mark Braverman, Rotem Oshman, Tal Roth
Multi-Party Set Disjointness and Intersection with Bounded Dependence. PODC (2024)
Hagit Attiya, Michael A. Bender, Martin Farach-Colton, Rotem Oshman, Noa Schiller
History-Independent Concurrent Objects. CoRR (2024)
Hagit Attiya, Michael A. Bender, Martín Farach-Colton, Rotem Oshman, Noa Schiller
History-Independent Concurrent Objects. PODC (2024)
Rotem Oshman, Tal Roth
The Communication Complexity of Set Intersection Under Product Distributions. ICALP (2023)
Eden Aldema Tshuva, Elette Boyle, Ran Cohen, Tal Moran, Rotem Oshman
Locally Verifiable Distributed SNARGs. TCC (1) (2023)
Eden Aldema Tshuva, Rotem Oshman
On Polynomial Time Local Decision. OPODIS (2023)
Uri Meir, Rotem Oshman, Ofer Shayevitz, Yuval Volkov
Resilience of 3-Majority Dynamics to Non-Uniform Schedulers. ITCS (2023)
Orr Fischer, Rotem Oshman
A distributed algorithm for directed minimum-weight spanning tree. Distributed Comput. 36 (1) (2023)
Orr Fischer, Adi Horowitz, Rotem Oshman
Massively Parallel Computation in a Heterogeneous Regime. CoRR (2023)
Keren Censor-Hillel, Orr Fischer, François Le Gall, Dean Leitersdorf, Rotem Oshman
Quantum Distributed Algorithms for Detection of Cliques. CoRR (2022)
Eden Aldema Tshuva, Rotem Oshman
Brief Announcement: On Polynomial-Time Local Decision. PODC (2022)
Yoav Ben Shimon, Orr Fischer, Rotem Oshman
Proof Labeling Schemes for Reachability-Related Problems in Directed Graphs. SIROCCO (2022)
Keren Censor-Hillel, Orr Fischer, François Le Gall, Dean Leitersdorf, Rotem Oshman
Quantum Distributed Algorithms for Detection of Cliques. ITCS (2022)
Talya Eden, Nimrod Fiat, Orr Fischer, Fabian Kuhn, Rotem Oshman
Sublinear-time distributed algorithms for detecting small cliques and even cycles. Distributed Comput. 35 (3) (2022)
Aviv Bick, Gillat Kol, Rotem Oshman
Distributed Zero-Knowledge Proofs Over Networks. SODA (2022)
Orr Fischer, Adi Horowitz, Rotem Oshman
Massively Parallel Computation in a Heterogeneous Regime. PODC (2022)
Lior Solodkin, Rotem Oshman
Truthful Information Dissemination in General Asynchronous Networks. DISC (2021)
Orr Fischer, Rotem Oshman, Dana Shamir
Explicit Space-Time Tradeoffs for Proof Labeling Schemes in Graphs with Small Separators. OPODIS (2021)
Keren Censor-Hillel, Orr Fischer, Tzlil Gonen, François Le Gall, Dean Leitersdorf, Rotem Oshman
Fast Distributed Algorithms for Girth, Cycles and Small Subgraphs. CoRR (2021)
Iftach Haitner, Noam Mazor, Rotem Oshman, Omer Reingold, Amir Yehudayoff
On the Communication Complexity of Key-Agreement Protocols. CoRR (2021)
Assaf Ben-Yishai, Young-Han Kim, Rotem Oshman, Ofer Shayevitz
On the Interactive Capacity of Finite-State Protocols. Entropy 23 (1) (2021)
Nachum Dershowitz, Rotem Oshman, Tal Roth
The communication complexity of multiparty set disjointness under product distributions. STOC (2021)
Keren Censor-Hillel, Orr Fischer, Tzlil Gonen, François Le Gall, Dean Leitersdorf, Rotem Oshman
Fast Distributed Algorithms for Girth, Cycles and Small Subgraphs. DISC (2020)
Sepehr Assadi, Gillat Kol, Rotem Oshman
Lower Bounds for Distributed Sketching of Maximal Matchings and Maximal Independent Sets. PODC (2020)
Assaf Ben-Yishai, Young-Han Kim, Rotem Oshman, Ofer Shayevitz
On the Interactive Capacity of Finite-State Protocols. CoRR (2020)
Orr Fischer, Rotem Oshman, Uri Zwick
Public vs. private randomness in simultaneous multi-party communication complexity. Theor. Comput. Sci. 810 (2020)
Uri Meir, Dor Minzer, Rotem Oshman
Can Distributed Uniformity Testing Be Local? PODC (2019)
Talya Eden, Nimrod Fiat, Orr Fischer, Fabian Kuhn, Rotem Oshman
Sublinear-Time Distributed Algorithms for Detecting Small Cliques and Even Cycles. DISC (2019)
Orr Fischer, Rotem Oshman
A Distributed Algorithm for Directed Minimum-Weight Spanning Tree. DISC (2019)
Pierre Fraigniaud, Pedro Montealegre, Rotem Oshman, Ivan Rapaport, Ioan Todinca
On Distributed Merlin-Arthur Decision Protocols. SIROCCO (2019)
Mark Braverman, Gillat Kol, Rotem Oshman, Avishay Tal
On the Computational Power of Radio Channels. DISC (2019)
Iftach Haitner, Noam Mazor, Rotem Oshman, Omer Reingold, Amir Yehudayoff
On the Communication Complexity of Key-Agreement Protocols. ITCS (2019)
Orr Fischer, Uri Meir, Rotem Oshman
Distributed Uniformity Testing. PODC (2018)
Iftach Haitner, Noam Mazor, Rotem Oshman, Omer Reingold, Amir Yehudayoff
On the Communication Complexity of Key-Agreement Protocols. Electron. Colloquium Comput. Complex. 25 (2018)
Mohamad Ahmadi, Fabian Kuhn, Rotem Oshman
Distributed Approximate Maximum Matching in the CONGEST Model. DISC (2018)
Orr Fischer, Tzlil Gonen, Fabian Kuhn, Rotem Oshman
Possibilities and Impossibilities for Distributed Subgraph Detection. SPAA (2018)
Gillat Kol, Rotem Oshman, Raghuvansh R. Saxena
Interactive Distributed Proofs. PODC (2018)
Orr Fischer, Tzlil Gonen, Rotem Oshman
Superlinear Lower Bounds for Distributed Subgraph Detection. CoRR (2017)
Guy Even, Orr Fischer, Pierre Fraigniaud, Tzlil Gonen, Reut Levi, Moti Medina, Pedro Montealegre, Dennis Olivetti, Rotem Oshman, Ivan Rapaport, Ioan Todinca
Three Notes on Distributed Property Testing. DISC (2017)
Orr Fischer, Tzlil Gonen, Rotem Oshman
Distributed Property Testing for Subgraph-Freeness Revisited. CoRR (2017)
Orr Fischer, Shay Gershtein, Rotem Oshman
On The Multiparty Communication Complexity of Testing Triangle-Freeness. CoRR (2017)
Tzlil Gonen, Rotem Oshman
Lower Bounds for Subgraph Detection in the CONGEST Model. OPODIS (2017)
Gillat Kol, Rotem Oshman, Dafna Sadeh
Interactive Compression for Multi-Party Protocol. DISC (2017)
Mark Braverman, Rotem Oshman
A Rounds vs. Communication Tradeoff for Multi-Party Set Disjointness. FOCS (2017)
Orr Fischer, Shay Gershtein, Rotem Oshman
On the Multiparty Communication Complexity of Testing Triangle-Freeness. PODC (2017)
Orr Fischer, Rotem Oshman, Uri Zwick
Public vs. Private Randomness in Simultaneous Multi-party Communication Complexity. SIROCCO (2016)
Mark Braverman, Rotem Oshman
On Information Complexity in the Broadcast Model. PODC (2015)
Mark Braverman, Rotem Oshman
The Communication Complexity of Number-In-Hand Set Disjointness with No Promise. Electron. Colloquium Comput. Complex. 22 (2015)
Rotem Oshman
Communication Complexity Lower Bounds in Distributed Message-Passing. SIROCCO (2014)
Andrew Drucker, Fabian Kuhn, Rotem Oshman
On the power of the congested clique model. PODC (2014)
Mark Braverman, Faith Ellen, Rotem Oshman, Toniann Pitassi, Vinod Vaikuntanathan
A Tight Bound for Set Disjointness in the Message-Passing Model. FOCS (2013)
Rotem Oshman, Nir Shavit
The SkipTrie: low-depth concurrent search without rebalancing. PODC (2013)
Mark Braverman, Faith Ellen, Rotem Oshman, Toniann Pitassi, Vinod Vaikuntanathan
Tight Bounds for Set Disjointness in the Message Passing Model CoRR (2013)
Andrew Drucker, Fabian Kuhn, Rotem Oshman
The communication complexity of distributed task allocation. PODC (2012)
Thomas Moscibroda, Rotem Oshman
Resilience of mutual exclusion algorithms to transient memory faults. PODC (2011)
Fabian Kuhn, Rotem Oshman
Dynamic networks: models and algorithms. SIGACT News 42 (1) (2011)
Fabian Kuhn, Yoram Moses, Rotem Oshman
Coordinated consensus in dynamic networks. PODC (2011)
Fabian Kuhn, Rotem Oshman
The Complexity of Data Aggregation in Directed Networks. DISC (2011)
Fabian Kuhn, Thomas Locher, Rotem Oshman
Gradient Clock Synchronization in Dynamic Networks. Theory Comput. Syst. 49 (4) (2011)
Fabian Kuhn, Nancy A. Lynch, Calvin C. Newport, Rotem Oshman, Andréa W. Richa
Broadcasting in unreliable radio networks. PODC (2010)
Fabian Kuhn, Nancy A. Lynch, Rotem Oshman
Distributed computation in dynamic networks. STOC (2010)
Fabian Kuhn, Christoph Lenzen, Thomas Locher, Rotem Oshman
Optimal gradient clock synchronization in dynamic networks. PODC (2010)
Fabian Kuhn, Christoph Lenzen, Thomas Locher, Rotem Oshman
Optimal Gradient Clock Synchronization in Dynamic Networks CoRR (2010)
Fabian Kuhn, Rotem Oshman
Gradient Clock Synchronization using Reference Broadcasts CoRR (2009)
Rotem Oshman
An Automata-Theoretic Dynamic Completeness Criterion for Bounded Model-Checking. VMCAI (2009)
Fabian Kuhn, Rotem Oshman
Gradient Clock Synchronization Using Reference Broadcasts. OPODIS (2009)
Fabian Kuhn, Thomas Locher, Rotem Oshman
Gradient clock synchronization in dynamic networks. SPAA (2009)
Rotem Oshman, Orna Grumberg
A New Approach to Bounded Model Checking for Branching Time Logics. ATVA (2007)