Picture of Erez

 

Erez Petrank

Papers available on-line

 

 

 

(Please read the copyright notice.)

 

 

 

 

           
Home
Publications
Courses
Projects
Committees
Collaborations
Patents
Students
Links
Bio
Hebrew

 

 

 

 

 

 

 
  1. Gal Sheffi and Erez Petrank. The ERA Theorem for Safe Memory Reclamation. Proceedings of the Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing (PODC'23) . Orlando, Florida, United States, June 2023.
    A longer version of this paper appears here.

  2. Gal Sheffi, Pedro Ramalhete, and Erez Petrank. EEMARQ: Efficient Lock-Free Range Queries with Memory Reclamation. Proceedings of the Proceedings of the 26th International Conference on Principles of Distributed Systems (OPODIS 2022).. Brussels, Belgium, December 2022.
    A longer version of this paper appears here.

  3. Gal Sela and Erez Petrank. Concurrent size. Proceedings of the Proceedings of the Object-Oriented Programming, Systems, Languages & Applications (OOPSLA'22). Auckland, New Zealand, December 2022.
    A longer version of this paper appears here.

  4. Yuanhao Wei, Naama Ben-David, Michal Friedman, Guy E. Blelloch, and Erez Petrank. FliT: A Library for Simple and Efficient Persistent Algorithms. Proceedings of the The 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP 2022). Seoul, South Korea, February 2022.

  5. Gal Milman, Alex Kogan, Yossi Lev, Victor Luchangco, and Erez Petrank. BQ: A Lock-Free Queue with Batching . ACM Transactions on Parallel Computing (TOPC), Volume 9, Issue 1, March 2022, Article No.: 5, pp. 1--49.

  6. Gali Sheffi, Maurice Herlihy, and Erez Petrank. VBR: Version Based Reclamation Proceedings of the the 35th International Symposium on Distributed Computing (DISC'21), Freiburg, Germany. October 2021.
    See also a longer version of this paper here.

  7. Gal (Milman) Sela, Maurice Herlihy, Erez Petrank. Brief Announcement: Linearizability: A Typo. Proceedings of the 33 ACM Symposium on Principles of Distributed Computing (PODC'21), Salerno, Italy, Virtual Conference, July 2021.
    See also a longer version of this paper here.

  8. Gal (Milman) Sela and Erez Petrank. Durable Queues: The Second Amendment. Proceedings of the 33 ACM Symposium on Parallelism in Algorithms and Architectures (SPAA'21). Virtual Conference. July 2021.
    See also a longer version of this paper here.

  9. Michal Friedman, Erez Petrank, and Pedro Ramalhete. Mirror: making lock-free data structures persistent. Proceedings of the 42st ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI 2021). Virtual Conference. June 2021.

  10. Gali Sheffi and Erez Petrank. Functional Faults. Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA'20). Philadelphia, PA, USA. July 2020.
    See also a longer version of this paper here.

  11. Michal Friedman, Naama Ben-David, Yuanhao Wei, Guy E. Blelloch, and Erez Petrank. NVTraverse: In NVRAM Data Structures, the Destination is More Important than the Journey. Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI 2020). London, United Kingdom. June 2020.
    See also a full version of this paper here.

  12. Yoav Zuriel, Michal Friedman, Gali Sheffi, Nachshon Cohen, and Erez Petrank. Efficient Lock-Free Durable Sets. Proceedings of the Object-Oriented Programming, Systems, Languages & Applications (OOPSLA'19). Athens, Greece. October 2019.
    See also a full version of this paper here.

  13. Avner Elizarov, Guy Golan Gueta, and Erez Petrank. LOFT: Lock-Free Transactional Data Structures. Proceedings of the The 24thACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP 2019). Washington, DC, USA, February 2018.
    For the full version of this paper see Avner Elizarov's M.Sc. thesis here.

  14. Benoit Daloze, Arie Tal, Stefan Marr, Hanspeter Mössenböck, and Erez Petrank. Parallelization of Dynamic Languages: Synchronizing Built-in Collections. Proceedings of the Object-Oriented Programming, Systems, Languages & Applications (OOPSLA'18). Boston, Massachusetts, United States. October 2018.

  15. Marcos Aguilera, Naama Ben-David, Irina Calciu, Rachid Guerraoui, Erez Petrank, and Sam Toueg. Passing Messages While Sharing Memory. Proceedings of the ACM Symposium on Principles of Distributed Computing 2018 (PODC'18), July 2018.

  16. Gal Milman, Alex Kogan, Yossi Lev, Victor Luchangco, and Erez Petrank. BQ: A Lock-Free Queue with Batching. Proceedings of the The 30th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2018). Vienna, Austria, July 2018.
    See also a presentation in keynote given by Gal at the conference.

  17. Gali Sheffi, Guy Golan-Guetta, and Erez Petrank. A Scalable Linearizable Multi-Index Table. The 38th IEEE International Conference on Distributed Computing Systems (ICDCS 2018), Vienna, Austria, July, 2018.
    See also a full version of this paper here.

  18. Michal Friedman, Maurice Herlihy, Virendra Marathe, and Erez Petrank. A Persistent Lock-Free Queue for Non-Volatile Memory. Proceedings of the The 23rd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP 2018). Vienna, Austria, February 2018.
    A longer version of this paper appears here.

  19. Nachshon Cohen, Maurice Herlihy, Erez Petrank and Elias Wald. The Teleportation Design Pattern for Hardware Transactional Memory Proceedings of the The 21st International Conference on Principles of Distributed Systems (OPODIS), , Lisboa, Portugal , December 2017.

  20. Nurit Moscovic, Nachshon Cohen, and Erez Petrank. A GPU-Friendly Skiplist Algorithm Proceedings of the The 26th International Conference on Parallel Architectures and Compilation Techniques (PACT), Portland, Oregon, USA, September 2017.

  21. Nachshon Cohen and Erez Petrank, “Limitations of Partial Compaction: Towards Practical Bounds. ACM Transactions on Programming Languages and Systems (TOPLAS), Vol 39, No. 1, March 2017

  22. Nachshon Cohen, Arie Tal, and Erez Petrank. Layout Lock: A Scalable Locking Paradigm for Concurrent Data Layout Modifications Proceedings of the 22nd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPOPP'17), Austin, Texas, USA, February 2017.

  23. Anastasia Braginsky, Nachshon Cohen, and Erez Petrank. CBPQ: High Performance Lock-Free Priority Queue Proceedings of Euro-Par 2016, the 22nd International Conference on Parallel and Distributed Computing, Grenoble, France, August 2016.
    A longer version of the paper is available here.

  24. Nachshon Cohen and Erez Petrank. Automatic Memory Reclamation for Lock-Free Data Structures Proceedings of the 2015 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications, OOPSLA 2015, Pittsburgh, PA, USA, October 2015.
    Code can be found here.

  25. Shahar Timnat, Maurice Herlihy, and Erez Petrank, “A Practical Transactional Memory Interface”, Proceedings of Euro-Par 2015, the 21st International Conference on Parallel Processing, August, 2015.
    This paper won the distinguished-paper award of the conference.

  26. Keren Censor-Hillel, 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.

  27. 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.

  28. Nachshon Cohen and Erez Petrank. Efficient Memory Management for Lock-Free 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.

  29. 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.

  30. Shahar Timnat and Erez Petrank. A Practical Wait-Free Simulation for Lock-Free Data StructuresProceedings of the 19th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPOPP'14), February 2014.
    See also a full version of this paper.
     
  31. Dana Drachsler-Cohen and Erez Petrank. LCD: Local Combining on Demand. Proceedings of the 18th International Conference on Principles of Distributed Systems (OPODIS 2014). December 2014., Orlando, Florida, USA.
     
  32. Erez Petrank and Shahar Timnat. Lock-Free Data-Structure IteratorsProceedings of the 27th international symposium on distributed computing (DISC'13), October 2013.
     
  33. Anastasia Braginsky, Alex Kogan, and Erez Petrank. Drop the Anchor: Lightweight Memory Management for Non-Blocking 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.

     
  34. Nachshon Cohen and Erez Petrank. Limitations of Partial Compaction: Towards Practical BoundsProceedings 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.

     
  35. Haggai Eran and Erez Petrank. A Study of Data Structures with a Deep Heap ShapesProceedings 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.
     
  36. 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)
     
  37. 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
    See also a PowerPoint presentation given by Shahar at the conference.
     
  38. 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.
     
  39. 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.
     
  40. 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.
     
  41. 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.
     
  42. 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.
     
  43. 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.
     
  44. 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.  
     
  45. 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.  
     
  46. Katherine Barabash and Erez Petrank. Tracing Garbage Collection on Highly Parallel PlatformsThe 2010 International Symposium on Memory Management (ISMM'10), pp. 1-10, June, 2010.
    See also a PowerPoint presentation given by Katherine at the conference.
     
  47. Erez Petrank, Madanlal Musuvathi, and Bjarne Steensgaard. Progress Guarantee via Bounded Lock-FreedomProceedings 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.
     
  48. Gabriel Kliot, Erez Petrank, and Bjarne Steensgaard. A Lock-Free, Concurrent, and Incremental Stack Scanning for Garbage CollectorsProceedings of the 2009 ACM SIGPLAN/SIGOPS International Conference on Virtual Execution Environments (VEE'09), March 2009.
     
  49. Chris Hawblitzel and Erez Petran. 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.
     
  50. 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.
     
  51. 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.
     
  52. 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.
     
  53. 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.
     
  54. 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.
     
  55. Yuval Ishai, Eyal Kushilevitz, Yehuda Lindel, and Erez Petrank. On Guaranteeing Output Delivery in Secure Multiparty ComputationProceedings of Advances in Cryptology - Crypto 2006, California, August 2006.
     
  56. 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.
     
  57. 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.
     
  58. 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.
     
  59. 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.
     
  60. 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.
     
  61. 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.
     
  62. 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.
     
  63. Diab Abuaiadh, Yoav Ossia, Erez Petrank, and Uri Silbershtein.   An Efficient Parallel Heap Compaction AlgorithmACM 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.
     
  64. Erez Petrank and Elliot K. Kolodner.  Parallel Copying Garbage Collection using Delayed Allocation.   Parallel Processing Letters  Vol. 14, No. 2, June 2004.
     
  65. 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.
     
  66. 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.
     

  67. 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.
     

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

  69. 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.
     
  70. Hezi Azatchi and Erez Petrank. Integrating Generations with Advanced Reference Counting Garbage Collectors.  The 12th International Conference on Compiler Construction (CC'03), April 2003.
     
  71. 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.
     
  72. Erez Petrank and Dror RawitzThe 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
     
  73. Tzafrir Cohen, Joe Kilian, Erez Petrank.   Responsive Round Complexity and Concurrent Zero-Knowledge. ASIACRYPT, December, 2001.
     
  74. Yossi Levanoni and Erez PetrankAn 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.
     
  75. 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.
     
  76. Ran Canetti, Joe Kilian, Erez Petrank and Alon RosenBlack 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.
     
  77. Erez Petrank and Charles RackoffMessage Authentication of Unknown Variable Length Data''.  Journal of Cryptology,  Vol. 13, No. 3, pp. 315-338, 2000.
     
  78. 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.
     
  79. 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.
     
  80. Mihir Bellare, Oded Goldreich, and Erez PetrankUniform Generation of NP-witnesses using an NP OracleInformation and Computation, Vol. 163, 2000, pp. 510-526.
     
  81. 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.
     
  82. 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.
     
  83. 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.
     
  84. 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.
     
  85. 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.
     
  86. Joe Kilian and Erez Petrank.  Identity Escrow .   Advances in Cryptology -- CRYPTO '98 Proceedings, Aug 1998 .     See also: Theory of Cryptography Library   -  Item 97-11 .
     
  87. 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.
     
  88. Joe Kilian, Erez Petrank, and Gabor Tardos.  Probabilistic Checkable Proofs with Zero Knowledge.   29th ACM Symp. on Theory of Computation, May 1997.
     
  89. 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.
     
  90. 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.
     
  91. Shai Halevi and Erez Petrank.  Storing Classified Files.   Manuscript, October 1995.
     
  92. 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.
     
  93. 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.
     
  94. Mihir Bellare and Erez Petrank.  Making Zero-Knowledge Provers Efficient.   24th ACM Symp. on Theory of Computation, May 1992. pp. 711-722.
     
  95. 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.
     
  96. 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.
  97. (A pdf version is here.)

Thesis

  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.