


 Anastasia Braginsky, Nachshon Cohen, and Erez Petrank. CBPQ: High Performance LockFree Priority Queue. Proceedings of
EuroPar 2016, the 22nd International Conference on Parallel and Distributed Computing,, Grenoble, France, August 2016.
A longer version of the paper is available here.
 Nachshon Cohen and Erez Petrank. Automatic Memory Reclamation for LockFree Data Structures. Proceedings of
the 2015 ACM SIGPLAN International Conference on ObjectOriented Programming, Systems, Languages, and Applications, OOPSLA 2015, Pittsburgh, PA, USA, October 2015.
Code can be found here.
 Shahar Timnat, Maurice Herlihy, and Erez Petrank, “A Practical Transactional Memory Interface”, Proceedings of EuroPar 2015, the 21st International Conference on Parallel Processing, August, 2015.
This paper won the distinguishedpaper award of the conference.
 Keren CensorHillel, Erez Petrank, Shahar Timnat. Help! Proceedings of
the ACM Symposium on Principles of Distributed Computing 2015 (PODC'15), July 2015.
See also a full version of this work.
 Chris Hawblitzel, Erez Petrank, Shaz Qadeer, and Serdar Tasiran. Automated and modular refinement reasoning for concurrent programs. Proceedings of
the 27th International Conference on Computer Aided Verification (CAV'15), July 2015.
See a technical report of this work.
 Nachshon Cohen and Erez Petrank. Efficient Memory Management for LockFree Data Structures with Optimistic Access. Proceedings of
the 27th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2015), June 2015.
A longer version of this paper appears here.
 Nachshon Cohen and Erez Petrank. Data Structure Aware Garbage Collector. Proceedings of
the 2015 International Symposium on Memory Management (ISMM'15), June 2015.
A longer version of this paper appears here.
 Shahar Timnat and Erez Petrank.
A Practical WaitFree Simulation for LockFree Data Structures.
Proceedings of the
19th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPOPP'14),
February 2014.
 Erez Petrank and Shahar Timnat.
LockFree DataStructure Iterators.
Proceedings of the
27th international symposium on distributed computing (DISC'13),
October 2013.
 Anastasia Braginsky, Alex Kogan, and Erez
Petrank.
Drop the Anchor: Lightweight Memory Management for NonBlocking Data Structures.
Proceedings of the 25th ACM Symposium
on Parallelism in Algorithms and Architectures (SPAA'13),
pp. 33  42, July 2013.
See also a
PowerPoint presentation given at the
conference.
 Nachshon Cohen and Erez
Petrank.
Limitations of Partial Compaction: Towards Practical Bounds.
Proceedings of the ACM SIGPLAN 2013
Conference on Programming
Language Design and Implementation (PLDI'13), pp. 309  320, June 2013.
A full version of this paper is available
here.
See also a
PowerPoint presentation given at the
conference.
 Haggai Eran and Erez
Petrank.
A Study of Data Structures with a Deep Heap Shapes.
Proceedings of the ACM SIGPLAN
Workshop on Memory Systems Performance and Correctness
(MSPC'13), June 2013.
See also a
PowerPoint presentation given by Haggai at the
conference.
 Anna Bendersky and Erez
Petrank.
Space Overhead Bounds for Dynamic Memory Management with Partial Compaction. ACM
Transactions on Programming Languages and Systems (TOPLAS), Vol 34,
No. 3, pp. Oct. 2012. (A short version of this paper appeared in
POPL'11)
 Shahar Timnat, Anastasia Braginsky, Alex Kogan, and Erez Petrank.
WaitFree
Linked Lists. The 16th International Conference On Principles Of
Distributed Systems (OPODIS'12), December 2012. A
short announcement of this result appeared in PPOPP 2012. A full
version of this paper can be found
here.
See also a
PowerPoint presentation given by Shahar at the
conference.
 Erez Petrank.
Can Parallel Data Structures Rely on Automatic Memory Managers? A
joint keynote talk for the 2012 International Symposium on
Memory Management and the Workshop on Memory Systems
Performance and Correctness
The presentation is
here.
 Anastasia Braginsky and Erez Petrank. A LockFree B+Tree. A
short version appears in The
24th ACM Symposium on
Parallelism in Algorithms and Architectures (SPAA'12), June
2012. See also a full version
here.
 Alex Kogan and Erez Petrank.
A Methodology for Creating Fast WaitFree Data Structures. The
17th ACM SIGPLAN Symposium on
Principles and Practice of Parallel Programming (PPoPP 2012).
February 2012.
See also a
PowerPoint presentation given by
Alex at the
conference.
 Alex Kogan and Erez Petrank.
WaitFree Queues With Multiple Enqueuers and Dequeuers. The
16th ACM SIGPLAN Symposium on
Principles and Practice of Parallel Programming (PPoPP 2011).
February 2011.
See also a
PowerPoint presentation given by
Alex at the
conference.

Anna Bendersky and Erez
Petrank.
Space Overhead Bounds for Dynamic Memory Management with Partial Compaction. A
short version of this paper appeared in
the 38th ACM SIGACTSIGPLAN
Symposium on Principles of Programming Languages (POPL 2011),
January 2011.
See also a
PowerPoint presentation given at the
conference, and the
lecture itself
in video format as videotaped at the conference.
 Anastasia Braginsky and Erez Petrank.
LocalityConscious LockFree Linked Lists.
The
12th International Conference on
Distributed Computing and Networking (ICDCN'11), January 2011.
See also a
full version.
See also a
PowerPoint presentation given by
Anastasia at the
conference.
 Iftach Haitner, Yuval Ishai, Eyal Kushilevitz, Yehuda Lindell, and
Erez Petrank.
BlackBox Cnstructions of Protocols for Secure Computation. Siam
Journal of Computing, Vol. 40, Num. 2, pp. 225266, 2011.
 Yuval Ishai, Jonathan Katz, Eyal Kushilevitz, Yehuda Lindell, and
Erez Petrank.
On Achieving the “Best of Both Worlds” in Secure Multiparty
Computation. Siam Journal of Computing, Vol. 40, Num. 1, pp.
122141, 2011.
 Katherine Barabash and Erez
Petrank.
Tracing Garbage Collection on Highly Parallel Platforms.
The 2010 International
Symposium on Memory Management (ISMM'10), pp. 110,
June, 2010.
See also a
PowerPoint presentation given by
Katherine at the
conference.
 Erez Petrank, Madanlal Musuvathi, and Bjarne Steensgaard.
Progress Guarantee via Bounded LockFreedom.
Proceedings of the ACM SIGPLAN 2009
Conference on Programming
Language Design and Implementation (PLDIí09), pp. 144  154, June 2009.
See also a
PowerPoint presentation given at the
conference.
 Gabriel Kliot, Erez
Petrank, and Bjarne Steensgaard.
A LockFree, Concurrent, and Incremental Stack Scanning for Garbage
Collectors.
Proceedings of the 2009
ACM SIGPLAN/SIGOPS International Conference on Virtual Execution
Environments (VEE'09), March 2009.
 Chris Hawblitzel and Erez
Petrank.
Automated Verification of Practical Garbage Collectors.
Proceedings of the 36th Annual
ACM SIGPLAN  SIGACT Symposium on Principles of Programming Languages (POPL'09),
Jan. 2009.
See also a
PowerPoint presentation given by Chris at the
conference.
 Filip Pizlo, Erez
Petrank, and Bjarne Steensgaard.
A
study of concurrent realtime garbage collectors.
Proceedings of the ACM SIGPLAN 2008
Conference on Programming
Language Design and Implementation (PLDIí08), pp. 33  44, June 2008.
See also a
presentation given by Filip at the
conference.
 Filip Pizlo, Erez
Petrank, and Bjarne Steensgaard.
Path specialization: reducing phased execution overheads.
The 2008
International Symposium on Memory Management (ISMM'08), pp. 8190,
June, 2008.
See also a
presentation given by Filip at the
conference.
 Filip Pizlo, Daniel Frampton, Erez
Petrank, and Bjarne Steensgaard.
Stopless: A RealTime Garbage Collector for Multiprocessors.
The 2007
International Symposium on Memory Management (ISMM'07), pp.
159172, Canada,
October, 2007.
 Liza Fireman, Erez Petrank, and Ayal Zaks.
New Algorithms for SIMD Alignment. Proceedings of the 16th
International Conference on Compiler Construction (CC'07), March,
2007.
See also a
PowerPoint presentation given at the
conference.
 Harel Paz and Erez Petrank.
Using Prefetching to Improve ReferenceCounting Garbage Collectors.
Proceedings of the 16th International Conference on Compiler
Construction (CC'07), March, 2007.
See also a
PowerPoint presentation given at the
conference.
 Yuval Ishai, Eyal Kushilevitz, Yehuda Lindel, and Erez Petrank.
On
Guaranteeing Output Delivery in Secure Multiparty Computation. Proceedings
of Advances in Cryptology  Crypto 2006, California, August 2006.
 Hezi Azatchi and Erez Petrank.
Integrating Generations with Advanced Reference Counting Garbage
Collectors. Concurrency and Computation: Practice and Experience,
Vol. 18, No. 9, pp. 959995, August 2006.
 Haim Kermany and Erez Petrank.
The Compressor: Concurrent, Incremental, and
Parallel Compaction. Proceedings of the ACM SIGPLAN 2006 Conference
on Programming
Language Design and Implementation (PLDIí06), pp. 354  363, June
2006.
See also a
PowerPoint presentation given by Haim
kermany at the conference.
 Yuval Ishai, Eyal Kushilevitz, Yehuda Lindel, and Erez Petrank.
BlackBox Constructions
of Secure Protocols. ThirtyEight Annual ACM Symposium on the
Theory
of Computing (STOCí06), pp. 99108, May 2006.
 Yossi Levanoni and Erez Petrank.
An
Onthefly Reference Counting Garbage Collector for Java. ACM
Transactions on Programming Languages and Systems, Vol. 28, No. 1,
January, 2006.
See also a
PowerPoint presentation
(a full hour talk) given at several occasions.
 Katherine Barabash, Ori BenYitzhak, Irit Goft, Elliot K. Kolodner,
Victor Leikehman, Yoav Ossia, Avi Owshanko, and Erez Petrank.
A Parallel, Incremental, Mostly Concurrent Garbage Collection for Servers.
ACM Transactions on Programming Languages and Systems, Vol. 27 No.
6, pp. 1097  1146, Nov. 2005.
 Harel Paz, Erez Petrank, and Stephen M. Blackburn.
AgeOriented
Concurrent Garbage Collection.
14th International Conference on Compiler
Construction (CC'05), April 2005.
See also a
PowerPoint presentation given at the
conference.
 Harel Paz, David F. Bacon, Elliot K. Kolodner, Erez Petrank, and V.T.
Rajan.
Complete OntheFly Cycle Collection.
14th International Conference on Compiler
Construction (CC'05), April 2005.
See also a
PowerPoint presentation given by Harel
Paz at the conference.
 Diab Abuaiadh, Yoav Ossia, Erez Petrank, and Uri Silbershtein.
An Efficient Parallel Heap Compaction Algorithm.
ACM Conference on ObjectOriented
Programming, Systems, Languages, and Applications (OOPSLA'04),
October 2004.
See also a
PowerPoint presentation given by Diab
Abuaiadh at the conference.
 Erez Petrank and Elliot K. Kolodner.
Parallel Copying Garbage Collection using Delayed Allocation.
Parallel Processing Letters Vol.
14, No. 2, June 2004.
 Hezi Azatchi, Yossi Levanoni, Harel Paz, and Erez Petrank
An
onthefly Mark and Sweep Garbage Collector Based on Sliding Views.
Proceedings of the ACM Conference on ObjectOriented Programming, Systems,
Languages, and Applications (OOPSLA'03), October 2003.
See also a
PowerPoint presentation given at the conference.

Katherina Barabash, Yoav Ossia, and Erez Petrank.
Mostly Concurrent Garbage Collection Revisited. Proceedings of
the ACM Conference on ObjectOriented Programming, Systems, Languages, and
Applications (OOPSLA'03), October 2003.
See also a
PowerPoint presentation given by Yoav
Ossia at the conference.

Niv Buchbinder and Erez Petrank.
Lower and Upper Bounds on Obtaining History Independence.
Information and Computation, Vol. 204, No. 2, pp. 291337, February
2006. An
extended abstract appears in the Proceedings of the Advances in
Cryptology  Crypto 2003, California, August 2003.
See also a
PowerPoint presentation given by Niv
Buchbinder at the conference, and a
fullhour talk he gave at other occasions.

Yuval Ishai, Kobbi Nissim, Joe Kilian, and Erez Petrank.
Extending Oblivious Transfers Efficiently. Proceedings of Advances
in Cryptology  Crypto 2003, California, August 2003.
 Daniele Micciancio and Erez Petrank.
Efficient
and Concurrent ZeroKnowledge from any public coin HVZK protocol,
Proceedings of Advances in Cryptology  EUROCRYPT 2003, Poland, May
2003.
 Hezi Azatchi and Erez Petrank.
Integrating Generations with Advanced Reference Counting Garbage
Collectors. The 12th International
Conference on Compiler Construction (CC'03), April 2003.
 Tamar Domani, Gal Goldshtein, Elliot K. Kolodner, Ethan Lewis, Erez
Petrank, and Dafna Sheinwald.
ThreadLocal Heaps for Java.
The 2002
International Symposium on Memory Management (ISMM'02), Germany,
June, 2002.
 Erez Petrank and Dror Rawitz.
The Hardness
of Cache Conscious Data Placement. An
extended abstract appears at the Proceedings of the
29th Annual ACM
Symposium on Principles of Programming Languages (POPL'02),
Portland, January 1618, 2002
 Tzafrir Cohen, Joe Kilian, Erez Petrank.
Responsive
Round Complexity and Concurrent ZeroKnowledge. ASIACRYPT, December,
2001.
 Yossi Levanoni and Erez Petrank.
An
Onthefly Reference Counting Garbage Collector for Java. Proccedings of the
ACM Conference on ObjectOriented
Programming, Systems, Languages, and Applications (OOPSLA'01).
October, 2001. See also the
Technical Report CS0967, Dept. of Computer Science, Technion, Nov.
1999.
See also a
PowerPoint presentation given at the
conference, and another
PowerPoint presentation
with more details (a full hour talk) given at several occasions.
 Joe Kilian, Erez Petrank, Ransom Richardson.
Concurrent ZeroKnowledge Proofs for NP. Part of this work has
appeared as: J. Kilian and E. Petrank.
Concurrent
and Resettable ZeroKnowledge in Polylogarithmic Rounds.
ThirtyThird Annual ACM Symposium on the Theory of Computing (STOC'01),
July 68, 2001.
 Ran Canetti, Joe Kilian, Erez Petrank and Alon Rosen.
Black Box
Concurrent ZeroKnowledge Requires $\tilde{\Omega}(log n)$ Rounds.ThirtyThird
Annual ACM Symposium on the Theory of Computing (STOC'01), July 68,
2001.
 Erez Petrank and Charles Rackoff.
Message
Authentication of Unknown Variable Length Data''. Journal of
Cryptology, Vol. 13, No. 3, pp. 315338, 2000.
 Tamar Domani, Elliot K. Kolodner, Ethan Lewis, Elliot E. Salant,
Katherine Barabash, Itai Lahan, Erez Petrank, Igor Yanover and Yossi
Levanoni.
Implementing an Onthefly Garbage Collector for Java.
The 2000 International
Symposium on Memory Management, October, 2000.
 Tamar Domany, Elliot K. Kolodner, Erez Petrank.
Generational
Onthefly Garbage Collector for Java. An
extended
abstract appears in the
ACM SIGPLAN 2000 Conference on Programming Language Design and
Implementation (PLDI 2000), June, 2000.
 Mihir Bellare, Oded Goldreich, and Erez Petrank.
Uniform
Generation of NPwitnesses using an NP Oracle. Information and
Computation, Vol. 163, 2000, pp. 510526.
 Alain Azagury, Elliot K. Kolodner, Erez Petrank.
A Note on
the Implementation of ReplicationBased Garbage Collection for
Multithreaded Applications and Multiprocessor Environments.
Parallel Processing Letters, Vol. 9, No. 3 pp. 391399, 1999.
 Anna Gal, Shai Halevi, Richard Lipton, and Erez Petrank.
Computing
from Partial Solutions. Proceedings of the 14th Annual IEEE
Conference on Computational Complexity, May 1999.
 Joe Kilian, Erez Petrank, and Charles Rackoff.
Lower Bounds
for Concurrent Zero Knowledge . Combinatorica, Vol. 25, No. 2,
pp. 217249, 2005. A preliminary version in 39th IEEE Conference on the
Foundations of Computer Science (FOCS'98), November 1998.
 Joe Kilian and Erez Petrank.
An Efficient
NonInteractive ZeroKnowledge Proof System for NP with General
Assumptions. Journal of Cryptography, Vol. 11, Pages 127,
1998.
 Alain Azagury, Elliot K. Kolodner, Erez Petrank, and Zvi Yehudai.
Combining
Card Marking with Remembered Sets: How to Save Scanning Time.
The 1998 International
Symposium on Memory Management, October 1998.
 Joe Kilian and Erez Petrank.
Identity Escrow . Advances in Cryptology  CRYPTO '98
Proceedings, Aug 1998 . See also:
Theory of Cryptography
Library 
Item 9711
.
 Erez Petrank and Ronny Roth.
Is Code
Equivalence Easy to Decide? IEEE Transactions on Information
Theory, Vol. 43, No. 5, Sep. 1997. pp 16021605.
 Joe Kilian, Erez Petrank, and Gabor Tardos.
Probabilistic
Checkable Proofs with Zero Knowledge. 29th ACM Symp. on Theory of
Computation, May 1997.
 Noga Alon, Martin Dietzfelbinger, Peter B. Miltersen, Erez Petrank,
and Gabor Tardos.
Linear
Hashing . Journal of the ACM Vol. 46, No. 5, September
1999. A preliminary version has appeared in the 29th ACM Symp. on
Theory of Computation, May 1997.
 Erez Petrank and Gabor Tardos.
On the Knowledge
Complexity of NP. Combinatorica Vol. 22, No. 1, pp. 83121,
2002. An extended abstract appeared in the 37th IEEE Conference on the
Foundations of Computer Science, October 1996, pp. 494503.
 Shai Halevi and Erez Petrank.
Storing
Classified Files. Manuscript, October 1995.
 Oded Goldreich, Rafi Ostrovsky, and Erez Petrank.
Computational
Complexity and Knowledge Complexity. SIAM Journal on Computing,
Volume 27, Number 4, pp.~11161141, August 1998. A preliminary version
appeared in the Proceedings of the 26th ACM Symp. on Theory of
Computation, May 1994. pp. 534543.
 Erez Petrank.
The Hardness of
Approximations : Gap Location. Computational Complexity, Vol.
4, 1994. pp. 133157. A preliminary version of this paper appeared in
the Second IEEE Israel Symp. on Theory of Computation and Systems,
June 1993, pp. 275284.
 Mihir Bellare and Erez Petrank.
Making
ZeroKnowledge Provers Efficient. 24th ACM Symp. on Theory of
Computation, May 1992. pp. 711722.
 Oded Goldreich and Erez Petrank.
Quantifying
Knowledge Complexity. Computational Complexity, Volume 8,
pp.~5098, 1999. A preliminary version appeared in the 32nd IEEE
Conference on the Foundations of Computer Science, October 1991, pp.
5968.
 Oded Goldreich and Erez Petrank.
The Best of
Both Worlds: Guaranteeing Termination in Fast Byzantine Agreement
Protocols. Information Processing Letters, Vol. 36, October
1990, pp. 4549.
Thesis
 Erez Petrank.
Knowledge
Complexity versus Computational Complexity and the Hardness of
Approximations. D.Sc. Thesis, Computer Science Department, Technion
 Israel Institute of Technology, Haifa, Israel. May 1995.
 Erez Petrank. Quantifying Knowledge Complexity. M.Sc. Thesis (in
Hebrew), Computer Science Department, Technion  Israel Institute of
Technology, Haifa, Israel. December 1991.



