default search action
Faith Ellen
Faith E. Fich – Faith Ellen Fich
Person information
- affiliation: University of Toronto, Department of Computer Science, ON, Canada
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2024
- [j54]Faith Ellen, Rati Gelashvili, Leqi Zhu:
Revisionist Simulations: A New Approach to Proving Space Lower Bounds. SIAM J. Comput. 53(4): 1039-1084 (2024) - 2023
- [j53]Dan Alistarh, James Aspnes, Faith Ellen, Rati Gelashvili, Leqi Zhu:
Why Extension-Based Proofs Fail. SIAM J. Comput. 52(4): 913-944 (2023) - [j52]Dan Alistarh, Faith Ellen, Joel Rybicki:
Wait-free approximate agreement on graphs. Theor. Comput. Sci. 948: 113733 (2023) - 2022
- [c75]Hagit Attiya, Faith Ellen:
The Step Complexity of Multidimensional Approximate Agreement. OPODIS 2022: 6:1-6:12 - 2021
- [j51]Faith Ellen, Rati Gelashvili, Philipp Woelfel, Leqi Zhu:
Space Lower Bounds for the Signal Detection Problem. Theory Comput. Syst. 65(4): 687-705 (2021) - [j50]Faith Ellen, Barun Gorain, Avery Miller, Andrzej Pelc:
Constant-Length Labeling Schemes for Deterministic Radio Broadcast. ACM Trans. Parallel Comput. 8(3): 14:1-14:17 (2021) - [c74]Kayman Brusse, Faith Ellen:
Reductions and Extension-Based Proofs. PODC 2021: 497-507 - [c73]Dan Alistarh, Faith Ellen, Joel Rybicki:
Wait-Free Approximate Agreement on Graphs. SIROCCO 2021: 87-105 - [c72]Yilun Sheng, Faith Ellen:
Extension-Based Proofs for Synchronous Message Passing. DISC 2021: 36:1-36:17 - [i12]Dan Alistarh, Faith Ellen, Joel Rybicki:
Wait-free approximate agreement on graphs. CoRR abs/2103.08949 (2021) - 2020
- [j49]Faith Ellen, Jörg-Rüdiger Sack:
Preface. Comput. Geom. 89: 101632 (2020) - [j48]Faith Ellen, Rati Gelashvili, Nir Shavit, Leqi Zhu:
A complexity-based classification for multiprocessor synchronization. Distributed Comput. 33(2): 125-144 (2020) - [j47]Joan Boyar, Faith Ellen, Kim S. Larsen:
Randomized distributed online algorithms against adaptive offline adversaries. Inf. Process. Lett. 161: 105973 (2020) - [j46]Faith Ellen, Luís Rodrigues:
Preface. Theor. Comput. Sci. 842: 130 (2020) - [c71]Dan Alistarh, James Aspnes, Faith Ellen, Rati Gelashvili, Leqi Zhu:
Brief Announcement: Why Extension-Based Proofs Fail. PODC 2020: 54-56 - [c70]Faith Ellen, Seth Gilbert:
Constant-Length Labelling Schemes for Faster Deterministic Radio Broadcast. SPAA 2020: 213-222
2010 – 2019
- 2019
- [j45]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) - [j44]Joan Boyar, Faith Ellen:
Tight Bounds for Restricted Grid Scheduling. Int. J. Found. Comput. Sci. 30(3): 375-405 (2019) - [j43]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): 544-559 (2019) - [c69]Lorenzo Alvisi, Shlomi Dolev, Faith Ellen, Idit Keidar, Fabian Kuhn, Jukka Suomela:
2019 Edsger W. Dijkstra Prize in Distributed Computing. PODC 2019: 1 - [c68]Faith Ellen, Barun Gorain, Avery Miller, Andrzej Pelc:
Constant-Length Labeling Schemes for Deterministic Radio Broadcast. SPAA 2019: 171-178 - [c67]Faith Ellen, Rati Gelashvili, Philipp Woelfel, Leqi Zhu:
Space Lower Bounds for the Signal Detection Problem. STACS 2019: 26:1-26:13 - [c66]Dan Alistarh, James Aspnes, Faith Ellen, Rati Gelashvili, Leqi Zhu:
Why extension-based proofs fail. STOC 2019: 986-996 - [e4]Peter Robinson, Faith Ellen:
Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC 2019, Toronto, ON, Canada, July 29 - August 2, 2019. ACM 2019, ISBN 978-1-4503-6217-7 [contents] - 2018
- [j42]James Aspnes, Hagit Attiya, Keren Censor-Hillel, Faith Ellen:
Erratum: Limited-Use Atomic Snapshots with Polylogarithmic Step Complexity. J. ACM 65(6): 38:1-38:2 (2018) - [c65]Faith Ellen, Rati Gelashvili, Leqi Zhu:
Revisionist Simulations: A New Approach to Proving Space Lower Bounds. PODC 2018: 61-70 - [e3]Jiannong Cao, Faith Ellen, Luís Rodrigues, Bernardo Ferreira:
22nd International Conference on Principles of Distributed Systems, OPODIS 2018, December 17-19, 2018, Hong Kong, China. LIPIcs 125, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2018, ISBN 978-3-95977-098-9 [contents] - [i11]Joan Boyar, Faith Ellen, Kim S. Larsen:
The Scheduler is Very Powerful in Competitive Analysis of Distributed List Accessing. CoRR abs/1807.06820 (2018) - [i10]Dan Alistarh, James Aspnes, Faith Ellen, Rati Gelashvili, Leqi Zhu:
Why Extension-Based Proofs Fail. CoRR abs/1811.01421 (2018) - 2017
- [j41]Hagit Attiya, Faith Ellen, Adam Morrison:
Limitations of Highly-Available Eventually-Consistent Data Stores. IEEE Trans. Parallel Distributed Syst. 28(1): 141-155 (2017) - [e2]Faith Ellen, Antonina Kolokolova, Jörg-Rüdiger Sack:
Algorithms and Data Structures - 15th International Symposium, WADS 2017, St. John's, NL, Canada, July 31 - August 2, 2017, Proceedings. Lecture Notes in Computer Science 10389, Springer 2017, ISBN 978-3-319-62126-5 [contents] - [i9]Hagit Attiya, Hyun Chul Chung, Faith Ellen, Saptaparni Kumar, Jennifer L. Welch:
Simulating a Shared Register in a System that Never Stops Changing. CoRR abs/1708.03274 (2017) - [i8]Faith Ellen, Barun Gorain, Avery Miller, Andrzej Pelc:
Constant-Length Labeling Schemes for Deterministic Radio Broadcast. CoRR abs/1710.03178 (2017) - [i7]Faith Ellen, Rati Gelashvili, Leqi Zhu:
Revisionist Simulations: A New Approach to Proving Space Lower Bounds. CoRR abs/1711.02455 (2017) - [i6]Trevor Brown, Faith Ellen, Eric Ruppert:
A General Technique for Non-blocking Trees. CoRR abs/1712.06687 (2017) - [i5]Trevor Brown, Faith Ellen, Eric Ruppert:
Pragmatic Primitives for Non-blocking Data Structures. CoRR abs/1712.06688 (2017) - 2016
- [j40]Faith Ellen, Panagiota Fatourou, Eleftherios Kosmas, Alessia Milani, Corentin Travers:
Universal constructions that ensure disjoint-access parallelism and wait-freedom. Distributed Comput. 29(4): 251-277 (2016) - [j39]Arkadev Chattopadhyay, Jeff Edmonds, Faith Ellen, Toniann Pitassi:
Upper and Lower Bounds on the Power of Advice. SIAM J. Comput. 45(4): 1412-1432 (2016) - [c64]Faith Ellen:
Participating Sets, Simulations, and the Consensus Hierarchy (Keynote Abstract). OPODIS 2016: 4:1-4:1 - [c63]Yehuda Afek, Faith Ellen, Eli Gafni:
Deterministic Objects: Life Beyond Consensus. PODC 2016: 97-106 - [c62]Faith Ellen, Trevor Brown:
Concurrent Data Structures. PODC 2016: 151-153 - [c61]Faith Ellen, Rati Gelashvili, Nir Shavit, Leqi Zhu:
A Complexity-Based Hierarchy for Multiprocessor Synchronization: [Extended Abstract]. PODC 2016: 289-298 - [i4]Faith Ellen, Rati Gelashvili, Nir Shavit, Leqi Zhu:
A Complexity-Based Hierarchy for Multiprocessor Synchronization. CoRR abs/1607.06139 (2016) - 2015
- [j38]James Aspnes, Hagit Attiya, Keren Censor-Hillel, Faith Ellen:
Limited-Use Atomic Snapshots with Polylogarithmic Step Complexity. J. ACM 62(1): 3:1-3:22 (2015) - [c60]Leqi Zhu, Faith Ellen:
Atomic Snapshots from Small Registers. OPODIS 2015: 17:1-17:16 - [c59]Hagit Attiya, Faith Ellen, Adam Morrison:
Limitations of Highly-Available Eventually-Consistent Data Stores. PODC 2015: 385-394 - [c58]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: 75-91 - 2014
- [b1]Hagit Attiya, Faith Ellen:
Impossibility Results for Distributed Computing. Synthesis Lectures on Distributed Computing Theory, Morgan & Claypool Publishers 2014, ISBN 978-3-031-00882-5 - [j37]James Aspnes, Faith Ellen:
Tight Bounds for Adopt-Commit Objects. Theory Comput. Syst. 55(3): 451-474 (2014) - [c57]Faith Ellen, Panagiota Fatourou, Joanna Helga, Eric Ruppert:
The amortized complexity of non-blocking binary search trees. PODC 2014: 332-340 - [c56]Trevor Brown, Faith Ellen, Eric Ruppert:
A general technique for non-blocking trees. PPoPP 2014: 329-342 - [i3]Joan Boyar, Faith Ellen:
Tight Bounds for an Online Bin Packing Problem. CoRR abs/1404.7325 (2014) - 2013
- [c55]Joan Boyar, Faith Ellen:
Bounds for Scheduling Jobs on Grid Processors. Space-Efficient Data Structures, Streams, and Algorithms 2013: 12-26 - [c54]Mark Braverman, Faith Ellen, Rotem Oshman, Toniann Pitassi, Vinod Vaikuntanathan:
A Tight Bound for Set Disjointness in the Message-Passing Model. FOCS 2013: 668-677 - [c53]Trevor Brown, Faith Ellen, Eric Ruppert:
Pragmatic primitives for non-blocking data structures. PODC 2013: 13-22 - [c52]Faith Ellen, Philipp Woelfel:
An Optimal Implementation of Fetch-and-Increment. DISC 2013: 284-298 - [i2]Mark Braverman, Faith Ellen, Rotem Oshman, Toniann Pitassi, Vinod Vaikuntanathan:
Tight Bounds for Set Disjointness in the Message Passing Model. CoRR abs/1305.4696 (2013) - 2012
- [j36]Faith Ellen, Danny Hendler, Nir Shavit:
On the Inherent Sequentiality of Concurrent Objects. SIAM J. Comput. 41(3): 519-536 (2012) - [c51]Faith Ellen, Panagiota Fatourou, Eleftherios Kosmas, Alessia Milani, Corentin Travers:
Universal constructions that ensure disjoint-access parallelism and wait-freedom. PODC 2012: 115-124 - [c50]James Aspnes, Hagit Attiya, Keren Censor-Hillel, Faith Ellen:
Faster than optimal snapshots (for a while): preliminary version. PODC 2012: 375-384 - [c49]Arkadev Chattopadhyay, Jeff Edmonds, Faith Ellen, Toniann Pitassi:
A little advice can be very helpful. SODA 2012: 615-625 - [c48]Faith Ellen, Vijaya Ramachandran, Philipp Woelfel:
Efficient Fetch-and-Increment. DISC 2012: 16-30 - 2011
- [j35]Alex Brodsky, Faith Ellen, Philipp Woelfel:
Fully-adaptive algorithms for long-lived renaming. Distributed Comput. 24(2): 119-134 (2011) - [j34]Hagit Attiya, Faith Ellen, Panagiota Fatourou:
The complexity of updating snapshot objects. J. Parallel Distributed Comput. 71(12): 1570-1577 (2011) - [c47]James Aspnes, Faith Ellen:
Tight bounds for anonymous adopt-commit objects. SPAA 2011: 317-324 - 2010
- [c46]Faith Ellen, Panagiota Fatourou, Eric Ruppert, Franck van Breugel:
Non-blocking binary search trees. PODC 2010: 131-140 - [c45]Phong Chuong, Faith Ellen, Vijaya Ramachandran:
A universal construction for wait-free transaction friendly data structures. SPAA 2010: 335-344
2000 – 2009
- 2008
- [j33]Faith Ellen, Panagiota Fatourou, Eric Ruppert:
The space complexity of unbounded timestamps. Distributed Comput. 21(2): 103-115 (2008) - 2007
- [j32]Faith Ellen, Panagiota Fatourou, Eric Ruppert:
Time lower bounds for implementations of multi-writer snapshots. J. ACM 54(6): 30 (2007) - [c44]Faith Ellen, Yossi Lev, Victor Luchangco, Mark Moir:
SNZI: scalable NonZero indicators. PODC 2007: 13-22 - [c43]Hagit Attiya, Faith Ellen, Panagiota Fatourou:
The complexity of updating multi-writer snapshot objects. PODC 2007: 318-319 - [c42]Faith Ellen, Panagiota Fatourou, Eric Ruppert:
The Space Complexity of Unbounded Timestamps. DISC 2007: 223-237 - 2006
- [j31]James Aspnes, Faith Ellen Fich, Eric Ruppert:
Relationships between broadcast and shared memory in reliable anonymous distributed systems. Distributed Comput. 18(3): 209-219 (2006) - [j30]Faith Ellen Fich, Danny Hendler, Nir Shavit:
On the inherent weakness of conditional primitives. Distributed Comput. 18(4): 267-277 (2006) - [c41]Faith Ellen, Sivaramakrishnan Subramanian, Jennifer L. Welch:
Maintaining Information About Nearby Processors in a Mobile Environment. ICDCN 2006: 193-202 - [c40]Hagit Attiya, Faith Ellen, Panagiota Fatourou:
The Complexity of Updating Multi-writer Snapshot Objects. ICDCN 2006: 319-330 - [c39]Panagiota Fatourou, Faith Ellen Fich, Eric Ruppert:
Time-space tradeoffs for implementations of snapshots. STOC 2006: 169-178 - [c38]Alex Brodsky, Faith Ellen, Philipp Woelfel:
Fully-Adaptive Algorithms for Long-Lived Renaming. DISC 2006: 413-427 - 2005
- [j29]Faith Ellen Fich:
Introduction to the special issue DISC 2003. Distributed Comput. 18(2): 111-111 (2005) - [j28]Ben Gum, Richard J. Lipton, Andrea S. LaPaugh, Faith E. Fich:
Estimating the maximum. J. Algorithms 54(1): 105-114 (2005) - [j27]Faith Ellen Fich, André Kündgen, Michael J. Pelsmajer, Radhika Ramamurthi:
Graph Minors and Reliable Single Message Transmission. SIAM J. Discret. Math. 19(4): 815-847 (2005) - [c37]Faith Ellen Fich, Danny Hendler, Nir Shavit:
Linear Lower Bounds on Real-World Implementations of Concurrent Objects. FOCS 2005: 165-173 - [c36]Faith Ellen Fich:
How Hard Is It to Take a Snapshot?. SOFSEM 2005: 28-37 - [c35]Faith Ellen Fich, Victor Luchangco, Mark Moir, Nir Shavit:
Obstruction-Free Algorithms Can Be Practically Wait-Free. DISC 2005: 78-92 - [c34]Matei David, Alex Brodsky, Faith Ellen Fich:
Restricted Stack Implementations. DISC 2005: 137-151 - [c33]Faith Ellen Fich, Victor Luchangco, Mark Moir, Nir Shavit:
Obstruction-Free Step Complexity: Lock-Free DCAS as an Example. DISC 2005: 493-494 - 2004
- [c32]Hagit Attiya, Faith Ellen Fich, Yaniv Kaplan:
Lower bounds for adaptive collect and related objects. PODC 2004: 60-69 - [c31]Alex Brodsky, Faith Ellen Fich:
Efficient synchronous snapshots. PODC 2004: 70-79 - [c30]Faith E. Fich, Danny Hendler, Nir Shavit:
On the inherent weakness of conditional synchronization primitives. PODC 2004: 80-87 - [c29]James Aspnes, Faith E. Fich, Eric Ruppert:
Relationships Between Broadcast and Shared Memory in Reliable Anonymous Distributed Systems. DISC 2004: 260-274 - 2003
- [j26]Faith E. Fich, Eric Ruppert:
Hundreds of impossibility results for distributed computing. Distributed Comput. 16(2-3): 121-163 (2003) - [c28]Panagiota Fatourou, Faith E. Fich, Eric Ruppert:
A tight time lower bound for space-optimal implementations of multi-writer snapshots. STOC 2003: 259-268 - [e1]Faith Ellen Fich:
Distributed Computing, 17th International Conference, DISC 2003, Sorrento, Italy, October 1-3, 2003, Proceedings. Lecture Notes in Computer Science 2848, Springer 2003, ISBN 3-540-20184-X [contents] - 2002
- [j25]Paul Beame, Faith E. Fich:
Optimal Bounds for the Predecessor Problem and Related Problems. J. Comput. Syst. Sci. 65(1): 38-72 (2002) - [c27]Panagiota Fatourou, Faith E. Fich, Eric Ruppert:
Space-optimal multi-writer snapshot objects are slow. PODC 2002: 13-20 - 2001
- [c26]John Watkinson, Micah Adler, Faith E. Fich:
New Protocols for Asymmetric Communication Channels. SIROCCO 2001: 337-350 - [c25]Faith E. Fich, Colette Johnen:
A Space Optimal, Deterministic, Self-Stabilizing, Leader Election Algorithm for Unidirectional Rings. DISC 2001: 224-239 - 2000
- [c24]Micah Adler, Faith E. Fich, Leslie Ann Goldberg, Mike Paterson:
Tight Size Bounds for Packet Headers in Narrow Meshes. ICALP 2000: 756-767 - [c23]Faith E. Fich, Eric Ruppert:
Lower Bounds in Distributed Computing. DISC 2000: 1-28 - [c22]Faith E. Fich, Andreas Jakoby:
Short Headers Suffice for Communication in a DAG with Link Failures. DISC 2000: 360-373
1990 – 1999
- 1999
- [c21]Micah Adler, Faith E. Fich:
The Complexity of End-to-End Communication in Memoryless Networks. PODC 1999: 239-248 - [c20]Paul Beame, Faith E. Fich:
Optimal Bounds for the Predecessor Problem. STOC 1999: 295-304 - 1998
- [j24]Faith E. Fich, Maurice Herlihy, Nir Shavit:
On the Space Complexity of Randomized Synchronization. J. ACM 45(5): 843-862 (1998) - [c19]Faith E. Fich:
End to End Communication. OPODIS 1998: 37-44 - [i1]Paul Beame, Faith E. Fich:
On Searching Sorted Lists: A Near-Optimal Lower Bound. Electron. Colloquium Comput. Complex. TR98 (1998) - 1997
- [j23]Paul Beame, Faith E. Fich, Rakesh K. Sinha:
Separating the Power of EREW and CREW PRAMs with Small Communication Width. Inf. Comput. 138(1): 89-99 (1997) - [j22]Anne Condon, Faith E. Fich, Greg N. Frederickson, Andrew V. Goldberg, David S. Johnson, Michael C. Loui, Steven Mahaney, Prabhakar Raghavan, John E. Savage, Alan L. Selman, David B. Shmoys:
Strategic directions in research in theory of computing. SIGACT News 28(3): 75-93 (1997) - [j21]Faith E. Fich:
Infrastructure issues related to theory of computing research. SIGACT News 28(3): 94-99 (1997) - 1996
- [j20]Faith E. Fich:
Infrastructure Issues Related to Theory of Computing Research. ACM Comput. Surv. 28(4es): 217 (1996) - [j19]Faith E. Fich, Russell Impagliazzo, Bruce M. Kapron, Valerie King, Miroslaw Kutylowski:
Limits on the Power of Parallel Random Access Machines with Weak Forms of Write Conflict Resolution. J. Comput. Syst. Sci. 53(1): 104-111 (1996) - [j18]Patrick W. Dymond, Faith E. Fich, Naomi Nishimura, Prabhakar Ragde, Walter L. Ruzzo:
Pointers versus Arithmetic in PRAMs. J. Comput. Syst. Sci. 53(2): 218-232 (1996) - 1995
- [j17]Faith E. Fich, Miroslaw Kowaluk, Miroslaw Kutylowski, Krzysztof Lorys, Prabhakar Ragde:
Retrieval of Scattered Information by EREW, CREW, and CRCW PRAMs. Comput. Complex. 5(2): 113-131 (1995) - [j16]Faith E. Fich, J. Ian Munro, Patricio V. Poblete:
Permuting in Place. SIAM J. Comput. 24(2): 266-278 (1995) - [c18]Faith E. Fich, Peter Bro Miltersen:
Tables Should Be Sorted (On Random Access Machines). WADS 1995: 482-493 - 1994
- [j15]Joan Boyar, Faith E. Fich, Kim S. Larsen:
Bounds on Certain Multiplications of Affine Combinations. Discret. Appl. Math. 52(2): 155-167 (1994) - 1993
- [c17]Patrick W. Dymond, Faith E. Fich, Naomi Nishimura, Prabhakar Ragde, Walter L. Ruzzo:
Pointers versus Arithmetic in PRAMs. SCT 1993: 239-252 - [c16]Faith E. Fich, Maurice Herlihy, Nir Shavit:
On the Space Complexity of Randomized Synchronization. PODC 1993: 241-249 - [c15]Faith E. Fich, Russell Impagliazzo, Bruce M. Kapron, Valerie King, Miroslaw Kutylowski:
Limits on the Power of Parallel Random Access Machines with Weak Forms of Write Conflict Resolution. STACS 1993: 386-397 - [c14]Paul Beame, Faith E. Fich, Rakesh K. Sinha:
Separating the Power of EREW and CREW PRAMs with Small Communication Width. WADS 1993: 163-174 - 1992
- [c13]Faith E. Fich, Miroslaw Kowaluk, Krzysztof Lorys, Miroslaw Kutylowski, Prabhakar Ragde:
Retrieval of scattered information by EREW, CREW and CRCW PRAMs. SWAT 1992: 30-41 - 1990
- [j14]