top of page

Publications
by subject (since 2010)
see DBLP for a nearly-complete list

Distributed computing with the cloud (CWC)

  1. Yehuda Afek, Gal Giladi, Boaz Patt-Shamir: Distributed Computing with the Cloud. SSS 2021: 1-20. doi

    • Yehuda Afek, Gal Giladi, Boaz Patt-Shamir: Distributed Computing With the Cloud. CoRR abs/2109.12930 (2021)

Cloud management

  1. Yossi Azar, Chay Machluf, Boaz Patt-Shamir, Noam Touitou: Competitive Vertex Recoloring. Algorithmica 85(7): 2001-2027 (2023). doi

    • Yossi Azar, Chay Machluf, Boaz Patt-Shamir, Noam Touitou: Competitive Vertex Recoloring. ICALP 2022: 13:1-13:20. doi

Proof labeling schemes and local computation algorithms (LCA)

  1. Boaz Patt-Shamir, Mor Perry: Proof-labeling schemes: Broadcast, unicast and in between. Theor. Comput. Sci. 923: 179-195 (2022). doi

    • Boaz Patt-Shamir, Mor Perry: Proof-Labeling Schemes: Broadcast, Unicast and in Between. SSS 2017: 1-17. doi​

  2. Pierre Fraigniaud, Boaz Patt-Shamir, Mor Perry: Randomized proof-labeling schemes. Distributed Comput. 32(3): 217-234 (2019). doi

    • Mor Baruch, Pierre Fraigniaud, Boaz Patt-Shamir: Randomized Proof-Labeling Schemes. PODC 2015: 315-324. doi​

  3. Yishay Mansour, Boaz Patt-Shamir, Shai Vardi: Constant-Time Local Computation Algorithms. Theory Comput. Syst. 62(2): 249-267 (2018). doi

    • Yishay Mansour, Boaz Patt-Shamir, Shai Vardi: Constant-Time Local Computation Algorithms. WAOA 2015: 110-121. doi​

  4. Uriel Feige, Boaz Patt-Shamir, Shai Vardi: On the Probe Complexity of Local Computation Algorithms. ICALP 2018: 50:1-50:14. doi

    • Uriel Feige, Boaz Patt-Shamir, Shai Vardi: On the Probe Complexity of Local Computation Algorithms. CoRR abs/1703.07734 (2017). doi​

  5. Lélia Blin, Pierre Fraigniaud, Boaz Patt-Shamir: On Proof-Labeling Schemes versus Silent Self-stabilizing Algorithms. SSS 2014: 18-32. doi

Routing and shortest paths

  1. Christoph Lenzen, Boaz Patt-Shamir, David Peleg: Distributed distance computation and routing with small messages. Distributed Comput. 32(2): 133-157 (2019). doi

  2. Christoph Lenzen, Boaz Patt-Shamir: Fast Partial Distance Estimation and Applications. PODC 2015: 153-162. doi

    • Christoph Lenzen, Boaz Patt-Shamir: Fast Partial Distance Estimation and Applications. CoRR abs/1412.7922 (2014)

  3. Christoph Lenzen, Boaz Patt-Shamir: Fast routing table construction using small messages: extended abstract. STOC 2013: 381-390. doi

    • Christoph Lenzen, Boaz Patt-Shamir: Fast Routing Table Construction Using Small Messages. CoRR abs/1210.5774 (2012). 

Placement in networks: SDN and more

  1. ​Guy Even, Moti Medina, Boaz Patt-Shamir: On-Line Path Computation and Function Placement in SDNs. Theory Comput. Syst. 63(2): 306-325 (2019). doi

    • Guy Even, Moti Medina, Boaz Patt-Shamir: On-Line Path Computation and Function Placement in SDNs. SSS 2016: 131-147. doi​

  2. Magnús M. Halldórsson, Sven Köhler, Boaz Patt-Shamir, Dror Rawitz: Distributed backup placement in networks. Distributed Comput. 31(2): 83-98 (2018). doi

    • Magnús M. Halldórsson, Sven Köhler, Boaz Patt-Shamir, Dror Rawitz:
      Distributed Backup Placement in Networks. SPAA 2015: 274-283. doi​

Packet forwarding and overflow management

  1. Boaz Patt-Shamir, Will Rosenbaum: Space-Optimal Packet Routing on Trees. INFOCOM 2019: 1036-1044. doi​​

  2. Avery Miller, Boaz Patt-Shamir, Will Rosenbaum: With Great Speed Come Small Buffers: Space-Bandwidth Tradeoffs for Routing. PODC 2019: 117-126. doi

    • Avery Miller, Boaz Patt-Shamir, Will Rosenbaum: With Great Speed Come Small Buffers: Space-Bandwidth Tradeoffs for Routing. CoRR abs/1902.08069 (2019)

  3. Lukasz Jez, Yishay Mansour, Boaz Patt-Shamir: Scheduling multipacket frames with frame deadlines. J. Sched. 20(6): 623-634 (2017). doi​

    • Lukasz Jez, Yishay Mansour, Boaz Patt-Shamir: Scheduling Multipacket Frames with Frame Deadlines. SIROCCO 2015: 76-90. doi​

  4. Boaz Patt-Shamir, Will Rosenbaum: The Space Requirement of Local Forwarding on Acyclic Networks. PODC 2017: 13-22. doi

  5. Avery Miller, Boaz Patt-Shamir: Buffer Size for Routing Limited-Rate Adversarial Traffic. DISC 2016: 328-341. doi

    • Avery Miller, Boaz Patt-Shamir: Buffer Size for Routing Limited-Rate Adversarial Traffic. CoRR abs/1707.03856 (2017)

  6. Guy Even, Moti Medina, Boaz Patt-Shamir: Better Deterministic Online Packet Routing on Grids. SPAA 2015: 284-293. doi​

    • Guy Even, Moti Medina, Boaz Patt-Shamir: Better Online Deterministic Packet Routing on Grids. CoRR abs/1501.06140 (2015)​

  7. Yishay Mansour, Boaz Patt-Shamir, Dror Rawitz: Competitive router scheduling with structured data. Theor. Comput. Sci. 530: 12-22 (2014). doi​

    • Yishay Mansour, Boaz Patt-Shamir, Dror Rawitz: Competitive Router Scheduling with Structured Data. WAOA 2011: 219-232. doi

  8. Alexander Kesselman, Boaz Patt-Shamir, Gabriel Scalosub: Competitive buffer management with packet dependencies. Theor. Comput. Sci. 489-490: 75-87 (2013). doi

  9. Yishay Mansour, Boaz Patt-Shamir, Dror Rawitz: Overflow management with multipart packets. Comput. Networks 56(15): 3456-3467 (2012). doi

    • Yishay Mansour, Boaz Patt-Shamir, Dror Rawitz: Overflow management with multipart packets. INFOCOM 2011: 2606-2614. doi​

Distributed CONGEST algorithms

  1. Mohsen Ghaffari, Andreas Karrenbauer, Fabian Kuhn, Christoph Lenzen, Boaz Patt-Shamir: Near-Optimal Distributed Maximum Flow. SIAM J. Comput. 47(6): 2078-2117 (2018). doi

    • Mohsen Ghaffari, Andreas Karrenbauer, Fabian Kuhn, Christoph Lenzen, Boaz Patt-Shamir: Near-Optimal Distributed Maximum Flow: Extended Abstract. PODC 2015: 81-90. doi​

  2. Avery Miller, Boaz Patt-Shamir, Will Rosenbaum: With Great Speed Come Small Buffers: Space-Bandwidth Tradeoffs for Routing. PODC 2019: 117-126. doi

    • Avery Miller, Boaz Patt-Shamir, Will Rosenbaum: With Great Speed Come Small Buffers: Space-Bandwidth Tradeoffs for Routing. CoRR abs/1902.08069 (2019)

  3. Benny Applebaum, Dariusz R. Kowalski, Boaz Patt-Shamir, Adi Rosén:
    Clique Here: On the Distributed Complexity in Fully-Connected Networks. Parallel Process. Lett. 26(1): 1650004:1-1650004:12 (2016)​. doi

  4. Zvi Lotker, Boaz Patt-Shamir, Seth Pettie: Improved Distributed Approximate Matching. J. ACM 62(5): 38:1-38:17 (2015). doi

  5. Christoph Lenzen, Boaz Patt-Shamir: Improved distributed steiner forest construction. PODC 2014: 262-271. doi

    • Christoph Lenzen, Boaz Patt-Shamir: Improved Distributed Steiner Forest Construction. CoRR abs/1405.2011 (2014)​

  6. Boaz Patt-Shamir, Dror Rawitz, Gabriel Scalosub: Distributed approximation of cellular coverage. J. Parallel Distributed Comput. 72(3): 402-408 (2012). doi​

  7. Zvika Brakerski, Boaz Patt-Shamir: Distributed discovery of large near-cliques. Distributed Comput. 24(2): 79-89 (2011). doi

  8. Boaz Patt-Shamir, Marat Teplitsky: The round complexity of distributed sorting: extended abstract. PODC 2011: 249-256. doi

  9. Alexander Kipnis, Boaz Patt-Shamir: On the complexity of distributed stable matching with small messages. Distributed Comput. 23(3): 151-161 (2010). doi

Recommender systems and collaborative filtering

  1. Yuval Carmel, Boaz Patt-Shamir: Comparison-based interactive collaborative filtering. Theor. Comput. Sci. 628: 40-49 (2016). doi

    • ​Yuval Carmel, Boaz Patt-Shamir: Comparison-Based Interactive Collaborative Filtering. SIROCCO 2015: 429-443. doi

  2. Aviv Nisgav, Boaz Patt-Shamir: Finding Similar Users in Social Networks. Theory Comput. Syst. 49(4): 720-737 (2011). doi

  3. Aviv Nisgav, Boaz Patt-Shamir: Finding Similar Users in Social Networks. Theory Comput. Syst. 49(4): 720-737 (2011). doi

  4. Aviv Nisgav, Boaz Patt-Shamir: Improved Collaborative Filtering. ISAAC 2011: 425-434. doi

  5. Yossi Azar, Aviv Nisgav, Boaz Patt-Shamir: Recommender systems with non-binary grades. SPAA 2011: 245-252. doi

Network management

  1. Shiri Chechik, Yuval Emek, Boaz Patt-Shamir, David Peleg: Sparse reliable graph backbones. Inf. Comput. 210: 31-39 (2012). doi

    • Shiri Chechik, Yuval Emek, Boaz Patt-Shamir, David Peleg: Sparse Reliable Graph Backbones. ICALP (2) 2010: 261-272. doi​

  • Boaz Patt-Shamir, Dror Rawitz: Video distribution under multiple constraints. Theor. Comput. Sci. 412(29): 3717-3730 (2011). doi

Self stabilization

  1. Yossi Azar, Shay Kutten, Boaz Patt-Shamir: Distributed error confinement. ACM Trans. Algorithms 6(3): 48:1-48:23 (2010). doi

Miscellaneous competitive algorithms

  1. Boaz Patt-Shamir, Evyatar Yadai: Non-Linear Ski Rental. SPAA 2020: 431-440. doi

  2. Pierre Fraigniaud, Magnús M. Halldórsson, Boaz Patt-Shamir, Dror Rawitz, Adi Rosén: Shrinking Maxima, Decreasing Costs: New Online Packing and Covering Problems. Algorithmica 74(4): 1205-1223 (2016). doi

    • Pierre Fraigniaud, Magnús M. Halldórsson, Boaz Patt-Shamir, Dror Rawitz, Adi Rosén: Shrinking Maxima, Decreasing Costs: New Online Packing and Covering Problems. APPROX-RANDOM 2013: 158-172. doi​

  3. Amir Levi, Boaz Patt-Shamir: Non-additive two-option ski rental. Theor. Comput. Sci. 584: 42-52 (2015). doi

    • Amir Levi, Boaz Patt-Shamir: Non-Additive Two-Option Ski Rental. SIROCCO 2013: 80-91​. doi

  4. Magnús M. Halldórsson, Boaz Patt-Shamir, Dror Rawitz: Online Scheduling with Interval Conflicts. Theory Comput. Syst. 53(2): 300-317 (2013). doi

    • Magnús M. Halldórsson, Boaz Patt-Shamir, Dror Rawitz: Online Scheduling with Interval Conflicts. STACS 2011: 472-483. doi​

  5. Boaz Patt-Shamir, Dror Rawitz: Vector bin packing with multiple-choice. Discret. Appl. Math. 160(10-11): 1591-1600 (2012). doi

  6. Yuval Emek, Magnús M. Halldórsson, Yishay Mansour, Boaz Patt-Shamir, Jaikumar Radhakrishnan, Dror Rawitz: Online Set Packing. SIAM J. Comput. 41(4): 728-746 (2012). doi

    • Yuval Emek, Magnús M. Halldórsson, Yishay Mansour, Boaz Patt-Shamir, Jaikumar Radhakrishnan, Dror Rawitz: Online set packing and competitive scheduling of multi-part tasks. PODC 2010: 440-449. doi​

  7. Zvi Lotker, Boaz Patt-Shamir, Dror Rawitz: Rent, Lease, or Buy: Randomized Algorithms for Multislope Ski Rental. SIAM J. Discret. Math. 26(2): 718-736 (2012). doi

  8. Boaz Patt-Shamir, Dror Rawitz: Vector Bin Packing with Multiple-Choice. SWAT 2010: 248-259. doi

Miscellaneous

  1. Harry Buhrman, Matthias Christandl, Michal Koucký, Zvi Lotker, Boaz Patt-Shamir, Nikolai K. Vereshchagin: High Entropy Random Selection Protocols. Algorithmica 83(2): 667-694 (2021). doi

  2. ​Yakov Babichenko, Yuval Emek, Michal Feldman, Boaz Patt-Shamir, Ron Peretz, Rann Smorodinsky: Stable Secretaries. Algorithmica 81(8): 3136-3161 (2019). doi

    • Yakov Babichenko, Yuval Emek, Michal Feldman, Boaz Patt-Shamir, Ron Peretz, Rann Smorodinsky: Stable Secretaries. EC 2017: 243-244. doi​

bottom of page