Boaz Patt-Shamir: Publications 2000-2008
See DBLP
for publications since 2008.
S. Kutten, R. Ostrovsky and B. Patt-Shamir. The Las-Vegas Processor Identity Problem (How
and When to Be Unique). In Journal of
Algorithms, 37:468494, 2000.
Y. Frankel, B. Patt-Shamir and Y. Tsiounis. Exact Analysis of Exact Change. In
Y. Mansour and B. Patt-Shamir. Jitter Control in QoS Networks. In IEEE/ACM Transactions on Networking
9(4):492502, 2000.
B. Patt-Shamir. Transmission of
Real Time Streams. Survey article in SIGACT
News, 32(3):5362, September 2001.
Z. Lotker and B. Patt-Shamir. Average-Case Analysis of Greedy Packet Scheduling. In Theory of Computing Systems 35(6):667683, 2002.
A. Bar-Noy, A. Nisgav and B. Patt-Shamir. Nearly Optimal Perfectly Periodic Schedules. In a special issue of
Z. Lotker and B. Patt-Shamir. Nearly Optimal FIFO Buffer Management for Two Packet Classes. InComputer Networks,
42(4):481492, 2003.
Z. Brakerski, V. Dreizin
and B. Patt-Shamir. Dispatching in
Perfectly-Periodic Schedules. In Journal of
Algorithms 49(2):219239, 2003.
A. Bar-Noy, B. Patt-Shamir and
Y. Mansour, B. Patt-Shamir and O. Lapid. Optimal Smoothing Schedules for Real-Time
Streams. In
Z. Lotker, B. Patt-Shamir and A. Rosén.
New Stability Results for
Adversarial Queuing. In
K. Lieberherr, B. Patt-Shamir and D.
A. Kesselman, Z. Lotker, Y. Mansour, B.
Patt-Shamir, B. Schieber and M. Sviridenko.
Buffer Overflow Management in QoS
Switches. In
A. Bar-Noy, V. Dreizin
and B. Patt-Shamir. Efficient Algorithms for Periodic Scheduling. In Computer Networks 45(2):155173, 2004.
Z. Lotker, B. Patt-Shamir, E. Pavlov and D. Peleg. Minimum-Weight Spanning Tree Construction in O(log log n) Communication Rounds.
In
Z. Brakeski, A. Nisgav and B. Patt-Shamir. General
Periodic Scheduling. In Algorithmica
45(2):183208, 2006.
Z. Lotker, B. Patt-Shamir and D. Peleg. Distributed MST for Constant Diameter Graphs. In
Z. Brakerski and B. Patt-Shamir. Jitter-Approximation Tradeoff for Periodic Scheduling. In Best papers of WMAN
B. Patt-Shamir. A Note on Efficient
Aggregate Queries in Sensor Networks. In
Theoretical Computer Science 370:254264, 2007.
B. Awerbuch, Y. Azar, Z. Lotker, B.
Patt-Shamir and M. Tuttle. Collaborate
With Strangers To Find Own Preferences. In Theory
of Computing Systems special issue on SPAA 05, 42(1): 2741, 2008.
Z. Lotker, B. Patt-Shamir and M. Tuttle. A Game of Timing and Visibility.
In Games and Economic Behavior, 62(2):643660, 2008..
B. Awerbuch, S. Kutten, Y. Mansour, B.
Patt-Shamir and G. Varghese. Time
Optimal Self-Stabilizing Synchronizers Using Phase Clocks. In IEEE Transactions on Dependable and Secure Computing,
4(3): 180190, 2007.
N. Alon, B. Awerbuch,
Y. Azar and B. Patt-Shamir. Tell Me Who I Am: An Interactive
Recommendation System. Accepted to a special issue of Theory of Computing
Systems devoted to SPAA 06.
B. Patt-Shamir and A. Shafrir. Approximate
Distributed Top-k Queries. Accepted to Distributed Computing.
Y. Azar, S. Kutten and B. Patt-Shamir. Distributed Error
Confinement. Submitted to ACM Transactions
on Algorithms. Under revision.
A. Bar-Noy, B. Patt-Shamir and
Y. Mansour, B. Patt-Shamir and O. Lapid. Optimal Smoothing Schedules for Real-Time
Streams. Appeared in 19th ACM Symp. on Principles of
Z. Lotker and B. Patt-Shamir. Average-Case
Analysis of Greedy Packet Scheduling. In
19th ACM Symp. on Principles of
A. Hagai and B. Patt-Shamir. Multiple Priority, Per Flow, Dual GCRA Rate Controller
for ATM Switches. Appeared in Proc. of IEEE Workshop on High Performance
Switching and Routing, pages 169174, May 2001.
A. Kesselman, Z. Lotker, Y. Mansour, B.
Patt-Shamir, B. Schieber and M. Sviridenko.
Buffer Overflow Management in QoS
Switches. In Proc. of the 33rd Ann. ACM Symp. on
Theory of Computing, pages 520529, July 2001.
A. Bar-Noy, A. Nisgav and B. Patt-Shamir. Nearly Optimal Perfectly-Periodic
Schedules. In 20th ACM Symp.
on Principles of
Z. Lotker, B. Patt-Shamir and D. Peleg. Distributed MST for Constant Diameter Graphs. In 20th ACM Symp. on Principles
of
A. Bar-Noy, V. Dreizin
and B. Patt-Shamir. Efficient
Periodic Scheduling by Trees. In IEEE
INFOCOM 02, June 2002.
Z. Lotker and B. Patt-Shamir. Nearly
Optimal FIFO Buffer Management for DiffServ. In 21st ACM Symp. on Principles
of
Z. Brakeski, A. Nisgav and B. Patt-Shamir. General Periodic Scheduling. In 21st ACM Symp. On Principles
of
Z. Lotker, B. Patt-Shamir and A. Rosén.
New Stability Results for
Adversarial Queuing. In 14th ACM Symp. on Parallel Algorithms and Architectures, pages
192199, August 2002.
Z. Lotker, B. Patt-Shamir, E. Pavlov and D. Peleg. MST Construction in O(log log n) Communication Rounds. In 15th ACM Symp. on Parallel Algorithms and Architectures, pages
94100, June 2003.
Y. Azar, S. Kutten and B. Patt-Shamir. Distributed Error Confinement.
In 22nd ACM Symp. On Principles of
A. Kesselman, Z. Lotker, Y. Mansour and B.
Patt-Shamir. Buffer Overflows of Merging Streams.
In 11th Annual European Symposium on Algorithms, pages 349360, September 2003.
Z. Brakerski and B. Patt-Shamir. Jitter-Approximation Tradeoff for
Periodic Scheduling. In 4th Int. Workshop on
Algorithms for Wireless,
B. Awerbuch, B. Patt-Shamir, D. Peleg and M.
Tuttle. Collaboration of Untrusting
Peers with Changing Interests. In 5th ACM Conference on Electronic Commerce,
pages 112119, May 2004.
B. Patt-Shamir. A Note
on Efficient Aggregate Queries in Sensor Networks.
In 23rd ACM Symp. on Principles of
S. Kutten and B. Patt-Shamir. Adaptive
Stabilization of Reactive Protocols. In
24th Conf. on Foundations of Software Technology and Theoretical Computer
Science, pages 396407, December 2004.
B. Awerbuch, B. Patt-Shamir, D. Peleg and M.
Tuttle. Improved Recommendation Systems. In 16th ACM-SIAM Symposium on Discrete Algorithms, pages
11741183, January 2005.
B. Awerbuch, B. Patt-Shamir, D. Peleg and M.
Tuttle. Adaptive Collaboration in
Peer-to-Peer Systems. In 25th International
Conference on
B. Awerbuch, Y. Azar, Z. Lotker, B.
Patt-Shamir, D. Peleg and M. Tuttle. Collaborate
With Strangers To Find Own Preferences. In 17th
ACM Symposium on Parallelism in Algorithms and Architectures, pages 263269,
July 2005.
J. Burman, T. Herman, S. Kutten and B.
Patt-Shamir. Asynchronous and Fully
Self-Stabilizing Time-Adaptive Majority Consensus.
In 9th Int. Conf. on Principles of
G. Chockler, S. Gilbert and B. Patt-Shamir. Communication-Efficient Probabilistic
Quorum Systems for Sensor Networks. In 4th
IEEE Conference on Pervasive Computing and Communications Workshops, pages
111117, March 2006.
B. Patt-Shamir and A. Shafrir. Approximate Top-k Queries in Sensor Networks. In 13th Colloquium on
Structural Information and Communication Complexity, pages 319333, July 2006.
N. Alon, B. Awerbuch,
Y. Azar and B. Patt-Shamir. Tell Me Who I Am: An
Interactive Recommendation System. In 18th ACM Symposium on Parallelism in
Algorithms and Architectures, pages 1110, July 2006.
Z. Lotker, B. Patt-Shamir and M. Tuttle. Publish
and Perish: Definition and Analysis of an n-Person Publication Impact Game.
In 18th ACM Symposium on Parallelism in Algorithms and Architectures, pages
1118, July 2006.
Z. Lotker, B. Patt-Shamir and Adi Rosén.
Distributed Approximate Matching. In 26th ACM Symp. On Principles
of
H. Buhrman, M. Christandl,
M. Koucký, Z. Lotker, B. Patt-Shamir and N.
Vereshchagin. High Entropy Random
Selection Protocols. In 11th International
Workshop on Randomization and Computation, pages 366379, August 2007.
B. Awerbuch, A. Nisgav and B. Patt-Shamir. Asynchronous Recommendation Systems. In 11th International Conference on Principles Of
Z. Lotker, B. Patt-Shamir and D. Rawitz. Rent,
Lease or Buy: Randomized Algorithms for Multislope
Ski Rental. In 25th International Symposium on Theoretical Aspects of
Computer Science, pages 503514, February 2008.
B. Patt-Shamir and D. Rawitz. Video
Distribution Under Multiple Constraints (Extended
Abstract). To appear in 28th International Conference on