Faith Ellen

Publication Activity (10 Years)

Years Active: 2006-2024
Publications (10 Years): 40

Top Topics

Rapidly Changing

Marginal Probabilities

Extended Abstract

Top Venues

SIAM J. Comput.

Publications

Faith Ellen, Rati Gelashvili, Leqi Zhu
Revisionist Simulations: A New Approach to Proving Space Lower Bounds. SIAM J. Comput. 53 (4) (2024)
Dan Alistarh, Faith Ellen, Joel Rybicki
Wait-free approximate agreement on graphs. Theor. Comput. Sci. 948 (2023)
Dan Alistarh, James Aspnes, Faith Ellen, Rati Gelashvili, Leqi Zhu
Why Extension-Based Proofs Fail. SIAM J. Comput. 52 (4) (2023)
Hagit Attiya, Faith Ellen
The Step Complexity of Multidimensional Approximate Agreement. OPODIS (2022)
Dan Alistarh, Faith Ellen, Joel Rybicki
Wait-free approximate agreement on graphs. CoRR (2021)
Yilun Sheng, Faith Ellen
Extension-Based Proofs for Synchronous Message Passing. DISC (2021)
Faith Ellen, Barun Gorain, Avery Miller, Andrzej Pelc
Constant-Length Labeling Schemes for Deterministic Radio Broadcast. ACM Trans. Parallel Comput. 8 (3) (2021)
Faith Ellen, Rati Gelashvili, Philipp Woelfel, Leqi Zhu
Space Lower Bounds for the Signal Detection Problem. Theory Comput. Syst. 65 (4) (2021)
Kayman Brusse, Faith Ellen
Reductions and Extension-Based Proofs. PODC (2021)
Dan Alistarh, Faith Ellen, Joel Rybicki
Wait-Free Approximate Agreement on Graphs. SIROCCO (2021)
Faith Ellen, Jörg-Rüdiger Sack
Preface. Comput. Geom. 89 (2020)
Faith Ellen, Rati Gelashvili, Nir Shavit, Leqi Zhu
A complexity-based classification for multiprocessor synchronization. Distributed Comput. 33 (2) (2020)
Faith Ellen, Luís Rodrigues
Preface. Theor. Comput. Sci. 842 (2020)
Dan Alistarh, James Aspnes, Faith Ellen, Rati Gelashvili, Leqi Zhu
Brief Announcement: Why Extension-Based Proofs Fail. PODC (2020)
Joan Boyar, Faith Ellen, Kim S. Larsen
Randomized distributed online algorithms against adaptive offline adversaries. Inf. Process. Lett. 161 (2020)
Faith Ellen, Seth Gilbert
Constant-Length Labelling Schemes for Faster Deterministic Radio Broadcast. SPAA (2020)
Hagit Attiya, Hyun Chul Chung, Faith Ellen, Saptaparni Kumar, Jennifer L. Welch
Emulating a Shared Register in a System That Never Stops Changing. IEEE Trans. Parallel Distributed Syst. 30 (3) (2019)
Lorenzo Alvisi, Shlomi Dolev, Faith Ellen, Idit Keidar, Fabian Kuhn, Jukka Suomela
Edsger W. Dijkstra Prize in Distributed Computing 2019 - Call for Nominations. Bull. EATCS 127 (2019)
Dan Alistarh, James Aspnes, Faith Ellen, Rati Gelashvili, Leqi Zhu
Why extension-based proofs fail. STOC (2019)
Faith Ellen, Barun Gorain, Avery Miller, Andrzej Pelc
Constant-Length Labeling Schemes for Deterministic Radio Broadcast. SPAA (2019)
Lorenzo Alvisi, Shlomi Dolev, Faith Ellen, Idit Keidar, Fabian Kuhn, Jukka Suomela
2019 Edsger W. Dijkstra Prize in Distributed Computing. PODC (2019)
Joan Boyar, Faith Ellen
Tight Bounds for Restricted Grid Scheduling. Int. J. Found. Comput. Sci. 30 (3) (2019)
Faith Ellen, Rati Gelashvili, Philipp Woelfel, Leqi Zhu
Space Lower Bounds for the Signal Detection Problem. STACS (2019)
Faith Ellen, Rati Gelashvili, Leqi Zhu
Revisionist Simulations: A New Approach to Proving Space Lower Bounds. PODC (2018)
Joan Boyar, Faith Ellen, Kim S. Larsen
The Scheduler is Very Powerful in Competitive Analysis of Distributed List Accessing. CoRR (2018)
Dan Alistarh, James Aspnes, Faith Ellen, Rati Gelashvili, Leqi Zhu
Why Extension-Based Proofs Fail. CoRR (2018)
James Aspnes, Hagit Attiya, Keren Censor-Hillel, Faith Ellen
Erratum: Limited-Use Atomic Snapshots with Polylogarithmic Step Complexity. J. ACM 65 (6) (2018)
Trevor Brown, Faith Ellen, Eric Ruppert
A General Technique for Non-blocking Trees. CoRR (2017)
Trevor Brown, Faith Ellen, Eric Ruppert
Pragmatic Primitives for Non-blocking Data Structures. CoRR (2017)
Faith Ellen, Rati Gelashvili, Leqi Zhu
Revisionist Simulations: A New Approach to Proving Space Lower Bounds. CoRR (2017)
Hagit Attiya, Faith Ellen, Adam Morrison
Limitations of Highly-Available Eventually-Consistent Data Stores. IEEE Trans. Parallel Distributed Syst. 28 (1) (2017)
Hagit Attiya, Hyun Chul Chung, Faith Ellen, Saptaparni Kumar, Jennifer L. Welch
Simulating a Shared Register in a System that Never Stops Changing. CoRR (2017)
Faith Ellen, Barun Gorain, Avery Miller, Andrzej Pelc
Constant-Length Labeling Schemes for Deterministic Radio Broadcast. CoRR (2017)
Faith Ellen, Trevor Brown
Concurrent Data Structures. PODC (2016)
Faith Ellen, Panagiota Fatourou, Eleftherios Kosmas, Alessia Milani, Corentin Travers
Universal constructions that ensure disjoint-access parallelism and wait-freedom. Distributed Comput. 29 (4) (2016)
Faith Ellen, Rati Gelashvili, Nir Shavit, Leqi Zhu
A Complexity-Based Hierarchy for Multiprocessor Synchronization. CoRR (2016)
Arkadev Chattopadhyay, Jeff Edmonds, Faith Ellen, Toniann Pitassi
Upper and Lower Bounds on the Power of Advice. SIAM J. Comput. 45 (4) (2016)
Yehuda Afek, Faith Ellen, Eli Gafni
Deterministic Objects: Life Beyond Consensus. PODC (2016)
Faith Ellen
Participating Sets, Simulations, and the Consensus Hierarchy (Keynote Abstract). OPODIS (2016)
Faith Ellen, Rati Gelashvili, Nir Shavit, Leqi Zhu
A Complexity-Based Hierarchy for Multiprocessor Synchronization: [Extended Abstract]. PODC (2016)
James Aspnes, Hagit Attiya, Keren Censor-Hillel, Faith Ellen
Limited-Use Atomic Snapshots with Polylogarithmic Step Complexity. J. ACM 62 (1) (2015)
Hagit Attiya, Faith Ellen, Adam Morrison
Limitations of Highly-Available Eventually-Consistent Data Stores. PODC (2015)
Leqi Zhu, Faith Ellen
Atomic Snapshots from Small Registers. OPODIS (2015)
Hagit Attiya, Hyun Chul Chung, Faith Ellen, Saptaparni Kumar, Jennifer L. Welch
Simulating a Shared Register in an Asynchronous System that Never Stops Changing - (Extended Abstract). DISC (2015)
Trevor Brown, Faith Ellen, Eric Ruppert
A general technique for non-blocking trees. PPOPP (2014)
Faith Ellen, Panagiota Fatourou, Joanna Helga, Eric Ruppert
The amortized complexity of non-blocking binary search trees. PODC (2014)
James Aspnes, Faith Ellen
Tight Bounds for Adopt-Commit Objects. Theory Comput. Syst. 55 (3) (2014)
Joan Boyar, Faith Ellen
Tight Bounds for an Online Bin Packing Problem. CoRR (2014)
Joan Boyar, Faith Ellen
Bounds for Scheduling Jobs on Grid Processors. Space-Efficient Data Structures, Streams, and Algorithms (2013)
Trevor Brown, Faith Ellen, Eric Ruppert
Pragmatic primitives for non-blocking data structures. PODC (2013)
Faith Ellen, Philipp Woelfel
An Optimal Implementation of Fetch-and-Increment. DISC (2013)
Mark Braverman, Faith Ellen, Rotem Oshman, Toniann Pitassi, Vinod Vaikuntanathan
A Tight Bound for Set Disjointness in the Message-Passing Model. FOCS (2013)
Mark Braverman, Faith Ellen, Rotem Oshman, Toniann Pitassi, Vinod Vaikuntanathan
Tight Bounds for Set Disjointness in the Message Passing Model CoRR (2013)
Faith Ellen, Panagiota Fatourou, Eleftherios Kosmas, Alessia Milani, Corentin Travers
Universal constructions that ensure disjoint-access parallelism and wait-freedom. PODC (2012)
Faith Ellen, Danny Hendler, Nir Shavit
On the Inherent Sequentiality of Concurrent Objects. SIAM J. Comput. 41 (3) (2012)
James Aspnes, Hagit Attiya, Keren Censor-Hillel, Faith Ellen
Faster than optimal snapshots (for a while): preliminary version. PODC (2012)
Arkadev Chattopadhyay, Jeff Edmonds, Faith Ellen, Toniann Pitassi
A little advice can be very helpful. SODA (2012)
Faith Ellen, Vijaya Ramachandran, Philipp Woelfel
Efficient Fetch-and-Increment. DISC (2012)
Hagit Attiya, Faith Ellen, Panagiota Fatourou
The complexity of updating snapshot objects. J. Parallel Distributed Comput. 71 (12) (2011)
James Aspnes, Faith Ellen
Tight bounds for anonymous adopt-commit objects. SPAA (2011)
Alex Brodsky, Faith Ellen, Philipp Woelfel
Fully-adaptive algorithms for long-lived renaming. Distributed Comput. 24 (2) (2011)
Phong Chuong, Faith Ellen, Vijaya Ramachandran
A universal construction for wait-free transaction friendly data structures. SPAA (2010)
Faith Ellen, Panagiota Fatourou, Eric Ruppert, Franck van Breugel
Non-blocking binary search trees. PODC (2010)
Faith Ellen, Panagiota Fatourou, Eric Ruppert
The space complexity of unbounded timestamps. Distributed Comput. 21 (2) (2008)
Faith Ellen, Panagiota Fatourou, Eric Ruppert
Time lower bounds for implementations of multi-writer snapshots. J. ACM 54 (6) (2007)
Faith Ellen, Panagiota Fatourou, Eric Ruppert
The Space Complexity of Unbounded Timestamps. DISC (2007)
Faith Ellen, Yossi Lev, Victor Luchangco, Mark Moir
SNZI: scalable NonZero indicators. PODC (2007)
Hagit Attiya, Faith Ellen, Panagiota Fatourou
The complexity of updating multi-writer snapshot objects. PODC (2007)
Alex Brodsky, Faith Ellen, Philipp Woelfel
Fully-Adaptive Algorithms for Long-Lived Renaming. DISC (2006)
Hagit Attiya, Faith Ellen, Panagiota Fatourou
The Complexity of Updating Multi-writer Snapshot Objects. ICDCN (2006)
Faith Ellen, Sivaramakrishnan Subramanian, Jennifer L. Welch
Maintaining Information About Nearby Processors in a Mobile Environment. ICDCN (2006)