Conference Papers

1. (*) Guy Even and Moti Medina, "Revisiting Randomized Parallel Load Balancing Algorithms", 16th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2009), May 25-27, 2009, Piran, Slovenia [B].

2. (*) Guy Even and Moti Medina, "Parallel Randomized Load Balancing: A Lower Bound for a More General Model", 36th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2010), January 23–29, 2010, Špindlerův Mlýn, Czech Republic [B].

3. (*) Guy Even and Moti Medina, "An O(log n)-Competitive Online Centralized Randomized Packet-Routing Algorithm for Lines", 37th International Colloquium on Automata, Languages and Programming (ICALP 2010), July 5-10, 2010, Bordeaux, France [A].

4. (*) Guy Even and Moti Medina, "Online Packet-Routing in Grids with Bounded Buffers", 23rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2011), June 4-6, 2011, San Jose, California, USA [A].

5. Guy Even, Yakov Matsri, and Moti Medina, "Multi-Hop Routing and Scheduling in Wireless Networks in the SINR model'', 7th International Symposium on Algorithms for Sensor Systems, Wireless Ad Hoc Networks and Autonomous Mobile Entities (ALGOSENSORS 2011), September 8-9, 2011, Saarbruecken, Germany [C].

6. Guy Even, Yaniv Fais, Moti Medina, Shimon (Moni) Shahar, and Alexander Zadorojniy, "Real-Time Video Streaming in Multi-hop Wireless Static Ad Hoc Networks'', 7th International Symposium on Algorithms for Sensor Systems, Wireless Ad Hoc Networks, and Autonomous Mobile Entities (ALGOSENSORS 2011), September 8-9, 2011,  Saarbruecken, Germany [C].

7. (*) Guy Even, Moti Medina, Gregor Schaffrath, and Stefan Schmid, "Competitive and Deterministic Embeddings of Virtual Networks", 13th International Conference on Distributed Computing and Networking (ICDCN 2012), January 3-6, 2012, Hong Kong, China - Best paper in distributed computing track [B].

8. (*) Iftah Gamzu and Moti Medina, "Improved Approximation for Orienting Mixed Graphs'', 19th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2012), June 30 - July 2, Reykjavík, Iceland (also in arXiv) [B].

9. Guy Even and Moti Medina, "Online Multi-Commodity Flow with High Demands", 10th Workshop on Approximation and Online Algorithms (WAOA 2012), September 13-14, 2012, Ljubljana, Slovenia (also in arXiv) [B].

10. (*) Guy Even and Moti Medina, "A Nonmonotone Analysis with the Primal-Dual Approach: online routing of virtual circuits with unknown durations", 20th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2013), July 1-3, 2013, Ischia, Italy (also in arXiv) [B].

11. (*) Guy Even, Moti Medina, and Dana Ron, "Deterministic Stateless Local Centralized Algorithms for Bounded Degree Graphs", 22nd European Symposium on Algorithms (ESA 2014), September 8-10, Wrocław, Poland [A].

12. (*) Guy Even, Moti Medina, and Dana Ron, "Distributed Maximum Matching in Bounded Degree Graphs'', 16th International Conference on Distributed Computing and Networking (ICDCN 2015), January 4-7, 2015, Goa, India (also in arXiv) [B].

13. Guy Even, Moti Medina, and Boaz Patt-Shamir, "Better Online Deterministic Packet Routing on Grids'', 27th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2015), June 13 - 15, 2015, Portland, Oregon, USA (also in arXiv) [A]. ■

14. (*) Christoph Lenzen, and Moti Medina "Efficient Metastability-Containing Gray Code 2-Sort'', 22nd IEEE International Symposium on Asynchronous Circuits and Systems, (ASYNC 2016), May 8 - 11, 2016, Porto Alegre, Brazil (Preprint).

15. (*) Guy Even, Moti Medina, Adi Rosén, "A Constant Approximation Algorithm for Scheduling Packets on Line Networks’’, 24th European  Symposium on Algorithms (ESA 2016), August 22-24, 2016, Aarhus, Denmark (also in arXiv) [A].

16. Mika Göös, Juho Hirvonen, Reut Levi, Moti Medina, Jukka Suomela, "Non-Local Probes Do Not Help with Many Graph Problems’’, 30th International Symposium on Distributed Computing (DISC 2016), September 26-29, 2016, Paris, France (also in arXiv) [22%, A].

    • What “Property Testing Review” (by Eric Blais) thinks about this paper.

17. (*) Guy Even, Moti Medina, and Boaz Patt-Shamir, "Online Path Computation and Function Placement in SDNs'', 18th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2016), November 7-10, 2016, Lyon, France - Best paper. (Preprint) [B].

18. (*) Johannes Bund, Christoph Lenzen, and Moti Medina, "Near-Optimal Metastability-Containing Sorting Networks'', 20th Design, Automation and Test in Europe (DATE 2017), March 27 - 31, 2017, Lausanne, Switzerland (Preprint) [24%, B].

19. (*) Guy Even, Reut Levi, Moti Medina, Adi Rosén, "Sublinear Random Access Generators for Preferential Attachment Graphs’’, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017), July 10-14, 2017, Warsaw, Poland [29.7%, A].

    • What does “Property Testing Review” (by Seshadhri) thinks about this paper?

20. (*) Guy Even, Orr Fischer, Pierre Fraigniaud, Tzlil Gonen, Reut Levi, Moti Medina, Pedro Montealegre, Dennis Olivetti, Rotem Oshman, Ivan Rapaport, and Ioan Todinca, "Three Notes on Distributed Property Testing'', 31st International Symposium on Distributed Computing (DISC 2017), October 16–20, 2017, Vienna, Austria [24.4%, A].

    • The third note in this paper is based on: Guy Even, Reut Levi, and Moti Medina, "Faster and Simpler Distributed Algorithms for Testing and Correcting Graph Properties in the CONGEST Model''

      • What “Property Testing Review” (by Gautam "G" Kamath) thinks about this paper.

21. (*) Christoph Lenzen and Moti Medina, "Robust Routing Made Easy'', 19th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2017), November 5 - 8, 2017, Boston, Massachusetts, USA (Preprint) [42.6%, B]. ♦ 

22. (*) Johannes Bund, Christoph Lenzen, and Moti Medina, "Optimal Metastability-Containing Sorting Networks'', 21st Design, Automation and Test in Europe (DATE 2018), March 19 - 23, 2018, Dresden, Germany (Preprint) [24%, B].

23. Guy Even, Moti Medina and Dror Rawitz, "Online Generalized Caching with Varying Weights and Costs '',  30th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2018), July 16 - 18, 2018, Vienna, Austria [30%, A].

24. (*) Reut Levi, Moti Medina, and Dana Ron, "Property Testing of Planarity in the CONGEST Model'', 37th ACM Symposium on Principles of Distributed Computing (PODC 2018), July 23-27, 2018, Royal Holloway, University of London, Egham, UK (Full version on arXiv) [25.1%, A*]. 

    • What “Property Testing Review” (by Gautam "G" Kamath) thinks about this paper. 

25. Guy Even, Mohsen Ghaffari and Moti Medina  "Distributed Set Cover Approximation: Primal-Dual with Optimal Locality", 32nd International Symposium on Distributed Computing (DISC 2018), October 15–19, 2018, New Orleans, USA [23.6%, A]. ﹩ 

26. (*) Johannes Bund, Matthias Fuegger, Christoph Lenzen, Moti Medina, and Will Rosenbaum, "PALS: Plesiosynchronous and Locally Synchronous Systems", 26th IEEE International Symposium on Asynchronous Circuits and Systems (ASYNC 2020), Salt Lake City, UT, USA, May 17-20, 2020 (Full version on arXiv) [41.3%].

    • Recorded talk by Johannes Bund.

27. Reut Levi and Moti Medina, "Distributed Testing of Graph Isomorphism in the CONGEST model", 24th International Conference on Randomization and Computation (RANDOM 2020), August 17-19, 2020, Virtual Conference  (Full version on arXiv) [44.7%, A].

    • What does “Property Testing Review” (by Seshadhri) think about this paper?

    • RANDOM 2020 Recorded talk. ■■ ♦♦

28. Alex Kushnerov, Moti Medina, and Alex Yakovlev, "Towards Hazard-Free Multiplexer Based Implementation of Self-Timed Circuits", 27th IEEE International Symposium on Asynchronous Circuits and Systems (ASYNC 2021), September 7-10, 2021,  Virtual Conference [42.1%].

29. (*) Johannes Bund, Christoph Lenzen, and Moti Medina, "Small Hazard-free Transducers", 13th Innovations in Theoretical Computer Science Conference (ITCS 2022), January 31 - February 3, 2022, Virtual Conference (Preprint) [48.7%, A].

30. Gwendolyn Farach-Colton, Martin Farach-Colton, Leslie Ann Goldberg, Hanna Komlos, John Lapinskas, Reut Levi, Moti Medina, Miguel A. Mosteiro, "Graph Ranking and the Cost of Sybil Defense", 24th ACM Conference on Economics and Computation (EC 2023),  London, United Kingdom, July 9-12, 2023. (Preprint) [26%, A*]. 

31. Noy Biton, Reut Levi, Moti Medina, "Distributed CONGEST Algorithm for Finding Hamiltonian Paths in Dirac Graphs and Generalizations", 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023), August 28 – September 1, 2023, Bordeaux, France  (Full version on arXiv) [40%, A]. ﹩﹩

32. Reut Levi, Moti Medina, and Omer Tubul, "Nearly Optimal Local Algorithms for Constructing Sparse Spanners of Clusterable Graphs", 28th International Conference on Randomization and Computation (RANDOM 2024), August 28 – 30, 2024, London, UK. [47%, A]

(*)  A journal version is available here.