Journal Publications

James Aspnes and Faith Ellen,
Tight bounds for adopt-commit objects,
Theory of Computing Systems, 2013,
Special issue for selected papers from SPAA 2011.

Faith Ellen, Danny Hendler, and Nir Shavit,
On the Inherent Sequentiality of Concurrent Objects,
SIAM Journal on Computing, volume 41, number 3, May 2012, pages 519-536.

Alex Brodsky, Faith Ellen, Philipp Woelfel,
Fully-adaptive Algorithms for Long-lived Renaming,
Distributed Computing, volume 24, number 2, September 2011, pages 119-134.

Hagit Attiya, Faith Ellen, Panagiota Fatourou,
The Complexity of Updating Snapshot Objects,
Journal of Parallel and Distributed Computing, Volume 71, number 12, August 2011, pages 1570-1577.

Faith Ellen, Panagiota Fatourou and Eric Ruppert,
The Space Complexity of Unbounded Timestamps,
Distributed Computing, Volume 21, Number 2, July 2008, pages 103--115.

Faith Ellen, Panagiota Fatourou, and Eric Ruppert,
Time lower bounds for implementations of multi-writer snapshots,
Journal of the ACM, Volume 54, Number 6, December 2007, 34 pages

Faith Ellen Fich, Danny Hendler, and Nir Shavit,
On the Inherent Weakness of Conditional Primitives,
Distributed Computing, Volume 18, Number 4, 2006, pages 267--277.
Special issue for selected papers from PODC 2004.

Jim Aspnes, Faith Ellen Fich, and Eric Ruppert,
Relationships Between Broadcast and Shared Memory in Reliable Anonymous Distributed Systems,
Distributed Computing, Volume 18, Number 3, February 2006, pages 209--219.
Special issue for selected papers from DISC 2004.

Faith Ellen Fich, Andre Kundgen, Michael Pelsmajer, and Radhika Ramamurthi,
Graph Minors and Reliable Single Message Transmission,
SIAM Journal on Discrete Mathematics, volume 19, number 4, December 2005, pages 815--847.

Ben Gum, Richard J. Lipton, Andrea LaPaugh, Faith Ellen Fich,
Estimating the maximum,
J. Algorithms, volume 54, number 1, 2005, pages 105-114.

Faith E. Fich and Eric Ruppert,
Hundreds of Impossibility Results for Distributed Computing,
Distributed Computing, volume 16, number 2--3, 2003, pages 121--163.
Special issue celebrating the 20th anniversary of PODC.

Paul Beame and Faith E. Fich,
Optimal Bounds for the Predecessor Problem and Related Problems,
Journal of Computer and Systems Sciences,
volume 65, number 1, August 2002, pages 38--72.
Special issue for selected papers from STOC 1999.

Faith Fich, Maurice Herlihy, and Nir Shavit,
On the Space Complexity of Randomized Synchronization,
JACM, volume 45, number 5, 1998, pages 843-862.

Paul Beame, Faith Fich, and Rakesh Sinha,
Separating the Power of CREW and EREW PRAMs with Small Communication Width,
Information and Computation, volume 138, number 1, 1997, pages 89-99.

Faith Fich, Russell Impagliazzo, Bruce Kapron, Valerie King, and Miroslaw Kutylowski,
Limits on the Power of Parallel Random Access Machines with Weak Forms of Write Conflict Resolution,
JCSS, volume 53, number 1, 1996, pages 104--111.

Patrick Dymond, Faith Fich, Naomi Nishimura,
Prabhakar Ragde, and Walter Ruzzo,
Pointers versus Arithmetic in PRAMs,
JCSS, volume 53, number 2, 1996, pages 218--232.
Special issue for selected papers from Structures 1993.

Faith Fich, Miroslaw Kowaluk, Krzysztof Lorys,
Miroslaw Kutylowski, and Prabhakar Ragde,
Retrieval of scattered information by EREW, CREW and CRCW PRAMs,
Computational Complexity, volume 5, 1995, pages 113--132.

Faith Fich, Ian Munro, and Patricio Poblete,
Permuting In Place , SIAM J. Comput., volume 24, number 2, 1995, pages 266--278.

Joan Boyar, Faith E. Fich, and Kim S. Larsen,
Bounds on Certain Multiplications of Affine Combinations,
Discrete Applied Math., volume 52, number 2, 1994, pages 155--167.

Faith E. Fich,
The Complexity of Computation on the Parallel Random Access Machine
in Synthesis of Parallel Algorithms, J. Reif, ed.,
Morgan-Kaufmann, 1993, pages 843--899.

Faith Fich and Avi Wigderson, Towards Understanding Exclusive Read,
SICOMP, volume 19, number 4, 1990, pages 718--727.

F. Fich, M. Li, P. Ragde, and Y. Yesha,
Lower Bounds for Parallel Random Access Machines with Read Only Memory,
Information and Computation, volume 83, number 2, 1989, pages 234--244.

A. Borodin, F. Fich, F. Meyer auf der Heide, E. Upfal, and A. Wigderson,
A Tradeoff Between Search and Update Time for the Implicit Dictionary Problem,
Theoretical Computer Science, volume 58, 1988, pages 57--68.

Faith E. Fich, Prabhakar Ragde, and Avi Wigderson,
Relations Between Concurrent-Write Models of Parallel Computation,
SIAM J. Comput., volume 17, number 3, 1988, pages 606--627.

Faith E. Fich, Prabhakar Ragde, and Avi Wigderson,
Simulations Among Concurrent-Write PRAMS,
Algorithmica, volume 3, 1988, pages 43--51.

Faith E. Fich and Martin Tompa,
The Parallel Complexity of Exponentiating Polynomials over Finite Fields,
JACM, volume 35, number 3, 1988, pages 651--667.

A. Borodin, F. Fich, F. Meyer auf der Heide, E. Upfal, and A. Wigderson,
A Time-Space Tradeoff for Element Distinctness,
SIAM J. Comput., volume 16, number 1, 1987, pages 97--99.

F. Fich, F. Meyer auf der Heide, and A. Wigderson,
Lower Bounds for Random Access Machines with Unbounded Shared Memory,
Advances in Computing Research, F. Preparata, ed.,
volume 4, 1987, pages 1--15.

Allan Borodin, Faith E. Fich, Danny Dolev, and Wolfgang Paul,
Bounds for Width Two Branching Programs,
SIAM J. Comput., volume 15, number 2, 1986, pages 549--560.

John A. Brzozowski and Faith E. Fich,
On Generalized Locally Testable Languages,
Discrete Mathematics, volume 50, 1984, pages 153--169.

Faith E. Fich,
Lower Bounds for the Cycle Detection Problem,
J. Comput. System Sci., volume 26, 1983, pages 392--409.
Special issue for selected papers from STOC 1981.

Karel Culik II, Faith E. Fich, and Arto Salomaa,
A Homomorphic Characterization of Regular Languages,
Discrete Applied Mathematics, volume 4, 1982, pages 149--152.

John A. Brzozowski and Faith E. Fich,
Languages of R-Trivial Monoids,
Journal for Computer and System Sciences, volume 20,
number 1, 1980, pages 32--49.

Edward A. Ashcroft and Faith E. Fich,
A Generalized Setting for Fixpoint Theory,
Theoretical Computer Science, volume 9, 1979, pages 243--256.