|
|
|
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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
- 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.
- 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.
- 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.
- 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.
- 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.
- 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 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.
- 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 Wait-Free Simulation for Lock-Free Data Structures. Proceedings 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.
- 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.
- Erez Petrank and Shahar Timnat.
Lock-Free Data-Structure 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 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.
- 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. 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.
- 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 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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 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.
- 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. 959-995, 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.
Black-Box Constructions
of Secure Protocols. Thirty-Eight Annual ACM Symposium on the
Theory
of Computing (STOCí06), pp. 99-108, May 2006.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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
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.
-
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.
-
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.
-
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 Zero-Knowledge 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.
Thread-Local 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 16-18, 2002
- Tzafrir Cohen, Joe Kilian, Erez Petrank.
Responsive
Round Complexity and Concurrent Zero-Knowledge. ASIACRYPT, December,
2001.
- 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.
- 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.
- 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.
- Erez Petrank and Charles Rackoff.
Message
Authentication of Unknown Variable Length Data''. Journal of
Cryptology, Vol. 13, No. 3, pp. 315-338, 2000.
- 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.
- 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.
- 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.
- 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.
- 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. 217-249, 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
Non-Interactive Zero-Knowledge Proof System for NP with General
Assumptions. Journal of Cryptography, Vol. 11, Pages 1--27,
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 97-11
.
- 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.
- 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. 83-121,
2002. An extended abstract appeared in the 37th IEEE Conference on the
Foundations of Computer Science, October 1996, pp. 494-503.
- 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.~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.
- 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.
- Mihir Bellare and Erez Petrank.
Making
Zero-Knowledge Provers Efficient. 24th ACM Symp. on Theory of
Computation, May 1992. pp. 711-722.
- 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.
- 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.
(A pdf version is here.)
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.
|
|
|
|