Selected Publications
This material is presented here to enhance timely
dissemination of scientific work.
Copyright and all rights therein are retained by the authors
or by other copyright holders.
Anyone accessing this information is expected to adhere to the
terms invoked by each copyright holder.
-
Online and Streaming Algorithms:
- G. Even, R. Levi, M. Medina, A. Rosén, Sublinear Random Access Generators for
Preferential Attachment Graphs.
ACM Transaction on Algorithms, Vol. 17, No. 4, pp.
28:1-28:26, 2021.
Early version Proc. of ICALP 2017, pp. 6:1-6:15.
- D. Rawitz, A. Rosén, Online Budgeted
Maximum Coverage.
Algorithmica, Vol. 89, N0. 9, pp. 2989-3014, 2021.
Early version Proc. of ESA 2016, pp. 73:1-73:17.
- S. Angelopoulos, C. Dürr, S. Kamali, M. P. Renault, A.
Rosén, Online Bin Packing with Advice
of Small Size.
Theory of Computing Systems, pp. 2006-2034, 2018.
Early version in Proc. of WADS 2015, pp. 40-53.
- M. Renault, A. Rosén, R. van Stee, Online
Algorithms with Advice for Bin Packing and Scheduling
Problems.
TCS, Vol. 600, pp. 155-170, 2015.
- A. López-Ortiz, M. P. Renault, A. Rosén, Paid Exchanges are Worth the Price.
TCS, 824-825, pp. 1-10, 2020.
Proc. of STACS 2015, pp. 636–648.
- Y. Emek, A. Rosén, Semi-Streaming Set
Cover,
ACM Transaction on Algorithms, Vol. 13, No. 1, pp. 6:1-6:22,
2016.
Early version in Proc. of ICALP 2014, pp. 453-464.
- A. Adamaszek, M. Renault, A. Rosén, R. van Stee, Reordering Buffer Management with Advice.
Journal of Scheduling, pp. 432-442, 2017.
Early version in Proc. of WAOA 2013.
- P. Fraigniaud, M. M. Halldorsson, B. Patt-Shamir, D.
Rawitz, A. Rosén, Shrinking Maxima,
Decreasing Costs: New Online Packing and Covering Problems
Algorithmica, Vol. 74, No. 4, pp. 1205-1223.
Early version in Proc. of APPROX-RANDOM 2013, pp. 158-172.
- C. Konrad, A. Rosén, Approximating
Semi-Matchings in Streaming and in Two-Party
Communication.
ACM Transaction on Algorithms, Vol. 12, No. 3, 32.
Early versions in Proc. of ICALP 2013, pp. 637–649.
- Y. Emek, M. Halldorson, A. Rosén, Space-Constrained
Interval Selection.
ACM Transaction on Algorithms, Vol. 12, No. 4, pp.
51:1-51:32, 2016.
Early version in Proc. of ICALP 2012, pp. 302–313.
- M. Renault, A. Rosén, On Online
Algorithms with Advice for the k-Server Problem.
Theory of Computing Systems, invited paper in the special
issue for WAOA 2011, Nov. 2012, pp. 1-19.
Early version in Proc. of WAOA 2011, pp. 198-210.
- Y. Emek, P. Fraigniaud, A. Korman, A. Rosén, On the Additive Constant of the k-Server
Work Function Algorithm.
IPL, Vol. 110, No. 24, pp. 1120-1123, 2010.
Early version in Proc. of WAOA 2009.
- Y. Emek, P. Fraigniaud, A. Korman, A. Rosén, Online Computation with Advice.
TCS, Vol. 412, No. 24, pp. 2642-2656 (Invited paper to the
special issue for ICALP 2009).
Early version in Proc. of ICALP 2009, 427-438.
- Y. Azar, Y. Bartal, E. Feuerstein, A. Fiat, S. Leonardi,
A. Rosén, On Capital Investment
Algorithmica, Vol. 25, No. 1, pp. 22-36, 99.
Early version ICALP 96.
- P. Berman, A. Blum, A. Fiat, H. Karloff, A. Rosén, M.
Saks, Randomized Robot Navigation
Algorithms.
Proc. of SODA 96, pp. 75-84.
- A. Fiat, Y. Mansour, A. Rosén, O. Waarts, Competitive Access Time via Dynamic
Storage Rearrangement .
Proc. of FOCS 95, pp. 392-401.
- Y. Bartal, A. Rosén, The Distributed
k-Server Problem --- A Distributed Competitive Translator
for k-Server Algorithms .
JALG Vol. 23, No. 2, pp. 241-264, 97.
Early version FOCS 92.
-
Private Computation and Communication Complexity:
- G. Couteau, A. Rosén, Random Sources in Private Computation.
ASIACRYPT 2022, pp. 443-473.
- E. Kushilevitz, R. Ostrovsky, E. Prouff, A. Rosén,
A. Thillard, D. Vergnaud, Lower
and Upper Bounds on the Randomness Complexity of Private
Computations of AND.
SIDMA, Vol. 35, No.1, pp. 465-484, 2021.
Early version Proc. of TCC 2019, pp. 386-406.
- A. Rosén, F. Urrutia, A New Approach to
Multi-Party Peer-to-Peer Communication Complexity.
Proc. of ITCS 2019, pp. 64:1-64:19.
- I. Kerenidis, A. Rosén, F. Urrutia, Multi-Party
Protocols, Information Complexity and Privacy.
ACM Transactions on Computation Theory, Vol. 11, No. 2, pp.
9:1-9:29, 2019.
Early version in Proc. of MFCS 2016, pp. 57:1-57:16.
- I. Damgĺrd, J. B. Nielsen, R. Ostrovsky, A. Rosén, Unconditionally Secure Computation with
Reduced Interaction.
Proc. of EUROCRYPT 2016, pp. 420-447.
- B. Applebaum, D. R. Kowalski, B. Patt-Shamir, A. Rosén, Clique Here: On the Distributed Complexity
in Fully-Connected Networks.
Parallel Processing Letters, Vol. 26, No. 1, 2016.
- A. Gál, A. Rosén, Lower Bounds on the
Amount of Randomness in Private Computation.
SICOMP, Vol. 34, No. 4, pp. 946-959.
Early version Proc. of STOC 2003, pp. 659-666.
- A. Gál, A. Rosén, A Theorem on
Sensitivity and Applications in Private Computation .
SICOMP, Vol. 31, No. 5, pp. 1424-1437, 2002.
Early version STOC 99.
- E. Kushilevitz, R. Ostrovsky, A. Rosén, Amortizing Randomness in Private
Computations .
SIDMA, Vol. 16, No. 4, pp. 533-544, 2003.
Early version PODC 98.
- R. Canetti, E. Kushilevitz, R. Ostrovsky, A. Rosén, Randomness vs. Fault-Tolerance .
Journal of Cryptography, Vol. 13, pp. 107-142, 2000.
Early version PODC 97.
- E. Kushilevitz, R. Ostrovsky, A. Rosén,
Characterizing Linear Size Circuits in Terms of Privacy .
JCSS, invited paper in the special issue for STOC 96, Vol.
58, No. 1, pp. 129-136, 99.
Early version STOC 96.
- E. Kushilevitz, A. Rosén, A
Randomness-Rounds Tradeoff in Private Computation .
SIDMA, Vol. 11, No. 1, pp. 61-80, 98.
Early version Crypto 94.
-
Communication Networks:
- G. Even, M. Medina, A. Rosén, A Constant
Approximation Algorithm for Scheduling Packets on Line
Networks.
Proc. of ESA 2016, pp. 40:1-40:16.
- P. Carmi, M. J. Katz, Z. Lotker, A. Rosén, Connectivity Guarantees for Wireless
Networks with Directional Antennas.
Computational Geometry, Vol. 44, No. 9, pp. 477-486.
- H. Räcke, A. Rosén, Approximation
Algorithms for Time-Constrained Scheduling on Line Networks.
Theory of Computing Systems, Vol. 49, No. 4, pp. 834-856
(Invited paper to the special issue for SPAA 2009).
Early version in Proc. of SPAA 2009, pp. 337-446.
- A. Rosén, G. Scalosub, Rate vs. Buffer Size -
Greedy Information Gathering on the Line.
ACM Transactions on Algorithms, Vol. 7, No. 3.
Early version in Proc. of SPAA 2007, pp. 305-314.
- Z. Lotker, B. Patt-Shamir, A. Rosén, Distributed
Approximate Matching.
SICOMP, Vol. 39, No. 2, pp. 445-460.
Early version in Proc. of PODC 2007, pp. 167-174.
- E. Gordon, A. Rosén, Competitive
Weighted Throughput Analysis of Greedy Protocols on DAGs.
ACM Transactions on Algorithms, Vol. 6, No. 3.
Early version in Proc. of PODC 2005, pp. 227-236.
- J. Naor , A. Rosén, G. Scalosub, Online
Time-Constrained Scheduling in Linear Networks.
Journal of Discrete Algorithms, Vol. 8, No. 4, pp. 346-355.
Early version in Proc. of INFOCOM 2005, pp. 855-865.
- H. Räcke, A. Rosén, Distributed Online
Call Control on General Networks.
Proc. of SODA 2005, pp. 791-800.
- A. Rosén, M. S. Tsirkin, On Delivery
Times in Packet Networks under Adversarial Traffic.
Theory of Computing Systems, invited paper in the special
issue for SPAA 2004, Vol. 39, No. 6, pp. 805-827.
Early version in Proc. of SPAA 2004.
- D. Guez, A. Kesselman, A. Rosén, Packet-Mode
Policies
for Input-Queued Switches.
Proc. of SPAA 2004, pp. 93-102.
- A. Kesselman, A. Rosén, Scheduling
Policies for CIOQ Switches.
JALG, Vol. 60, No. 1, pp. 60-83.
Early version SPAA 2003.
- W. Aiello, E. Kushilevitz, R. Ostrovsky, A. Rosén, Dynamic Routing on Networks with Fixed-Size
Buffers.
Proc. of SODA 2003, pp. 771-780.
- Z. Lotker, B. Patt-Shamir, A. Rosén,
New Stability Results for Adversarial Queuing .
SICOMP, Vol. 33, No. 2, pp. 286-303.
Early version SPAA 2002.
- M. Adler, A. Rosén, Tight Bounds for the
Performance of Longest in System on DAGs .
JALG, Vol. 55, No. 2, pp. 101-112.
Early version STACS 2002.
- A. Rosén, A Note on Models for
Non-Probabilistic Analysis of Packet-Switching Networks .
IPL, Vol. 84, No. 5, pp. 237-240, 2002.
- W. Aiello, Y. Mansour, S. Rajagopolan, A. Rosén, Competitive Queue Policies for
Differentiated Services .
JALG, Vol. 55, No. 2, pp. 113-141.
Early version Proc. of INFOCOM 2000, pp. 431-440.
- M. Adler, S. Khanna, R. Rajaraman, A. Rosén, Time-Constrained Scheduling of Weighted
Packets on Trees and Meshes .
Algorithmica, Vol. 36, No. 2, pp. 123-152.
Early version SPAA 99.
- W. Aiello, E. Kushilevitz, R. Ostrovsky, A. Rosén, Adaptive Packet Routing for Bursty
Adversarial Traffic .
JCSS, invited paper in the special issue for STOC 98, Vol. 60,
No. 3, pp. 482-509, 2000.
Early version STOC 98.
- S. Leonardi, A. Marchetti-Spaccamela, A. Presciutti, A.
Rosén, On-line Randomized Call Control
Revisited .
SICOMP, Vol. 31, No. 1, pp. 86-112, 2001.
Early version SODA 98.
- B. Awerbuch, Y. Azar, A. Fiat, S. Leonardi, A. Rosén, On-line Competitive Algorithms for Call
Admission in Optical Networks .
Algorithmica, Vol. 31, No. 1, pp. 29-43, 2001.
Early version ESA 96.
- E. Kushilevitz, R. Ostrovsky, A. Rosén,
Log-Space Polynomial End-to-End Communication .
SICOMP Vol. 27, No. 6, pp. 1531-1549, 98.
Early version STOC 95.
- B. Awerbuch, Y. Bartal, A. Fiat, A. Rosén, Competitive Non-Preemptive Call Control .
Proc. of SODA 94, pp. 312-320.
- Y. Afek, B. Awerbuch, E. Gafni, Y. Mansour, A. Rosén, N.
Shavit, Slide - The Key to Polynomial
End-to-End Communication .
JALG, Vol. 22, No. 1, pp. 158-186, 97.
- Y. Afek, E. Gafni, A. Rosén, The Slide
Protocol with Applications in Dynamic Networks.
Proc. of PODC 92, pp. 35-46.
Last updated: March 2022