Erez Petrank

Papers available on-line

1. 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)
    
2. Shahar Timnat, Anastasia Braginsky, Alex Kogan, and Erez Petrank. Wait-Free 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. 
    
3. 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.
    
4. Anastasia Braginsky and Erez Petrank. A Lock-Free 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.
    
5. Alex Kogan and Erez Petrank. A Methodology for Creating Fast Wait-Free 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.
    
6. Alex Kogan and Erez Petrank. Wait-Free 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.
    

7. 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 SIGACT-SIGPLAN 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.
    

8. Anastasia Braginsky and Erez Petrank. Locality-Conscious Lock-Free 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.
    
9. Iftach Haitner, Yuval Ishai, Eyal Kushilevitz, Yehuda Lindell, and Erez Petrank. Black-Box Cnstructions of Protocols for Secure Computation. Siam Journal of Computing, Vol. 40, Num. 2, pp. 225-266, 2011.  
    
10. 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. 122-141, 2011.  
     
11. Katherine Barabash and Erez Petrank. Tracing Garbage Collection on Highly Parallel Platforms.  The 2010 International Symposium on Memory Management (ISMM'10), pp. 1-10, June, 2010.
    See also a PowerPoint presentation given by Katherine at the conference.
     
12. Erez Petrank, Madanlal Musuvathi, and Bjarne Steensgaard. Progress Guarantee via Bounded Lock-Freedom.  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.
     
13. Gabriel Kliot, Erez Petrank, and Bjarne Steensgaard. A Lock-Free, 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.
     
14. 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.
     
15. Filip Pizlo, Erez Petrank, and Bjarne Steensgaard. A study of concurrent real-time 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.
     
16. Filip Pizlo, Erez Petrank, and Bjarne Steensgaard. Path specialization: reducing phased execution overheads.  The 2008 International Symposium on Memory Management (ISMM'08), pp. 81-90, June, 2008.
    See also a presentation given by Filip at the conference.
     
17. Filip Pizlo, Daniel Frampton, Erez Petrank, and Bjarne Steensgaard. Stopless: A Real-Time Garbage Collector for Multiprocessors.  The 2007 International Symposium on Memory Management (ISMM'07), pp. 159-172, Canada, October, 2007.
     
18. 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.
     
19. Harel Paz and Erez Petrank. Using Prefetching to Improve Reference-Counting Garbage Collectors. Proceedings of the 16th International Conference on Compiler Construction (CC'07), March, 2007.
    See also a PowerPoint presentation given at the conference.
     
20. 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.
     
21. Hezi Azatchi and Erez Petrank. Integrating Generations with Advanced Reference Counting Garbage Collectors. Concurrency and Computation: Practice and Experience, Vol. 18, No. 9, pp. 959-995, August 2006.
     
22. 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.
     
23. Yuval Ishai, Eyal Kushilevitz, Yehuda Lindel, and Erez Petrank. Black-Box Constructions
    of Secure Protocols.  Thirty-Eight Annual ACM Symposium on the Theory
    of Computing (STOCí06), pp. 99-108, May 2006.
     
24. Yossi Levanoni and Erez Petrank.  An On-the-fly 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.
     
25. Katherine Barabash, Ori Ben-Yitzhak, 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.
     
26. Harel Paz, Erez Petrank, and Stephen M. Blackburn.  Age-Oriented Concurrent Garbage Collection.  14th International Conference on Compiler Construction (CC'05), April 2005.
    See also a PowerPoint presentation given at the conference.
     
27. Harel Paz, David F. Bacon, Elliot K. Kolodner, Erez Petrank, and V.T. Rajan.  Complete On-the-Fly Cycle Collection.  14th International Conference on Compiler Construction (CC'05), April 2005. 
    See also a PowerPoint presentation given by Harel Paz at the conference.
     
28. Diab Abuaiadh, Yoav Ossia, Erez Petrank, and Uri Silbershtein.   An Efficient Parallel Heap Compaction Algorithm.  ACM Conference on Object-Oriented Programming, Systems, Languages, and Applications  (OOPSLA'04), October 2004.
    See also a PowerPoint presentation given by Diab Abuaiadh at the conference.
     
29. Erez Petrank and Elliot K. Kolodner.  Parallel Copying Garbage Collection using Delayed Allocation.   Parallel Processing Letters  Vol. 14, No. 2, June 2004.
     
30. Hezi Azatchi, Yossi Levanoni, Harel Paz, and Erez Petrank  An on-the-fly Mark and Sweep Garbage Collector Based on Sliding Views. Proceedings of the ACM Conference on Object-Oriented Programming, Systems, Languages, and Applications  (OOPSLA'03), October 2003.
    See also a PowerPoint presentation given at the conference.
     

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

32. Niv Buchbinder and Erez Petrank.  Lower and Upper Bounds on Obtaining History Independence. Information and Computation, Vol. 204, No. 2, pp. 291-337, 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 full-hour talk he gave at other occasions.
     

33. Yuval Ishai, Kobbi Nissim, Joe Kilian, and Erez Petrank. Extending Oblivious Transfers Efficiently.  Proceedings of Advances in Cryptology - Crypto 2003, California, August 2003.
     

34. Daniele Micciancio and Erez Petrank. Efficient and Concurrent Zero-Knowledge from any public coin HVZK protocol, Proceedings of Advances in Cryptology - EUROCRYPT 2003, Poland, May 2003.
     
35. Hezi Azatchi and Erez Petrank. Integrating Generations with Advanced Reference Counting Garbage Collectors.  The 12th International Conference on Compiler Construction (CC'03), April 2003.
     
36. Tamar Domani, Gal Goldshtein, Elliot K. Kolodner, Ethan Lewis, Erez Petrank, and Dafna Sheinwald. Thread-Local Heaps for Java.  The 2002 International Symposium on Memory Management (ISMM'02), Germany, June, 2002.
     
37. 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 16-18, 2002
     
38. Tzafrir Cohen, Joe Kilian, Erez Petrank.   Responsive Round Complexity and Concurrent Zero-Knowledge. ASIACRYPT, December, 2001.
     
39. Yossi Levanoni and Erez Petrank.  An On-the-fly Reference Counting Garbage Collector for Java. Proccedings of the ACM Conference on Object-Oriented Programming, Systems, Languages, and Applications  (OOPSLA'01). October, 2001.   See also the Technical Report CS-0967, 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.
     
40. Joe Kilian, Erez Petrank, Ransom Richardson.  Concurrent Zero-Knowledge Proofs for NP.  Part of this work has appeared as: J. Kilian and E. Petrank.  Concurrent and Resettable Zero-Knowledge in Poly-logarithmic Rounds.  Thirty-Third Annual ACM Symposium on the Theory of Computing (STOC'01), July 6-8, 2001.
     
41. Ran Canetti, Joe Kilian, Erez Petrank and Alon Rosen.  Black Box Concurrent Zero-Knowledge Requires $\tilde{\Omega}(log n)$ Rounds.Thirty-Third Annual ACM Symposium on the Theory of Computing (STOC'01), July 6-8, 2001.
     
42. Erez Petrank and Charles Rackoff.  Message Authentication of Unknown Variable Length Data''.  Journal of Cryptology,  Vol. 13, No. 3, pp. 315-338, 2000.
     
43. Tamar Domani, Elliot K. Kolodner, Ethan Lewis, Elliot E. Salant, Katherine Barabash, Itai Lahan, Erez Petrank, Igor Yanover and Yossi Levanoni. Implementing an On-the-fly Garbage Collector for Java.  The 2000 International Symposium on Memory Management, October, 2000.
     
44. Tamar Domany, Elliot K. Kolodner, Erez Petrank. Generational On-the-fly Garbage Collector for Java. An extended abstract appears in the ACM SIGPLAN 2000 Conference on  Programming Language Design and Implementation (PLDI 2000), June, 2000.
     
45. Mihir Bellare, Oded Goldreich, and Erez Petrank.  Uniform Generation of NP-witnesses using an NP Oracle.  Information and Computation, Vol. 163, 2000, pp. 510-526.
     
46. Alain Azagury, Elliot K. Kolodner, Erez Petrank.  A Note on the Implementation of Replication-Based Garbage Collection for Multithreaded Applications and Multiprocessor Environments.  Parallel Processing Letters, Vol. 9,  No. 3 pp. 391-399, 1999.
     
47. 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.
     
48. Joe Kilian, Erez Petrank, and Charles Rackoff.  Lower Bounds for Concurrent Zero Knowledge . Combinatorica, Vol. 25, No. 2, pp. 217-249, 2005.   A preliminary version in 39th IEEE Conference on the Foundations of Computer Science (FOCS'98), November 1998.
     
49. Joe Kilian and Erez Petrank.  An Efficient Non-Interactive Zero-Knowledge Proof System for NP with General Assumptions.   Journal of Cryptography, Vol. 11, Pages 1--27, 1998.
     
50. 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.
     
51. Joe Kilian and Erez Petrank.  Identity Escrow .   Advances in Cryptology -- CRYPTO '98 Proceedings, Aug 1998 .     See also: Theory of Cryptography Library   -  Item 97-11 .
     
52. Erez Petrank and Ronny Roth.  Is Code Equivalence Easy to Decide?   IEEE Transactions on Information Theory, Vol. 43, No. 5, Sep. 1997. pp 1602-1605.
     
53. Joe Kilian, Erez Petrank, and Gabor Tardos.  Probabilistic Checkable Proofs with Zero Knowledge.   29th ACM Symp. on Theory of Computation, May 1997.
     
54. 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.
     
55. Erez Petrank and Gabor Tardos.   On the Knowledge Complexity of NP.   Combinatorica Vol. 22, No. 1, pp. 83-121, 2002.  An extended abstract appeared in the 37th IEEE Conference on the Foundations of Computer Science, October 1996, pp. 494-503.
     
56. Shai Halevi and Erez Petrank.  Storing Classified Files.   Manuscript, October 1995.
     
57. Oded Goldreich, Rafi Ostrovsky, and Erez Petrank.  Computational Complexity and Knowledge Complexity.   SIAM Journal on Computing, Volume 27, Number 4, pp.~1116--1141, August 1998. A preliminary version appeared in the Proceedings of the 26th ACM Symp. on Theory of Computation, May 1994. pp. 534-543.
     
58. Erez Petrank.  The Hardness of Approximations : Gap Location.   Computational Complexity, Vol. 4, 1994. pp. 133-157.   A preliminary version of this paper appeared in the Second IEEE Israel Symp. on Theory of Computation and Systems, June 1993, pp. 275-284.
     
59. Mihir Bellare and Erez Petrank.  Making Zero-Knowledge Provers Efficient.   24th ACM Symp. on Theory of Computation, May 1992. pp. 711-722.
     
60. Oded Goldreich and Erez Petrank.  Quantifying Knowledge Complexity.   Computational Complexity, Volume 8, pp.~50--98, 1999. A preliminary version appeared in the 32nd IEEE Conference on the Foundations of Computer Science, October 1991, pp. 59-68.
     
61. 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. 45-49.

1. 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.
    
2. Erez Petrank.   Quantifying Knowledge Complexity.   M.Sc. Thesis (in Hebrew), Computer Science Department, Technion - Israel Institute of Technology, Haifa, Israel. December 1991.