Fall 2019

Probabilistically Checkable and Interactive Proof Systems

Sep. 23Sep. 27, 2019

Add to Calendar

Justin Thaler (Georgetown University; chair), Omer Paneth (Tel Aviv University), Ron Rothblum (Technion)

Since their inception almost three decades ago, probabilistically checkable and interactive proof systems have served as lenses through which to view and solve disparate problems in computational complexity. Yet one of their most compelling uses is a direct one: a party wishes to convince another party of a statement and, due to a lack of a trust relationship, does so by way of a proof system. Crucially, this paradigm provides benefits such as speedups in verification time, or zero knowledge.

The increased demand for efficient proof systems has motivated intense research, across theoretical and applied conferences, that studies proof systems both from a practical perspective as well as posing theoretical questions motivated by practical concerns.

This workshop will focus on theoretical and practical aspects of such "positive" uses of proof systems. Topics will include probabilistically checkable and interactive proofs, argument systems, transformations from programs to circuits, and hardware implementations.

Further details about this workshop will be posted in due course. Enquiries may be sent to the organizers workshop-proofs1 [at] lists [dot] simons [dot] berkeley [dot] edu (at this address).

All events take place in the Calvin Lab auditorium.

Registration is required to attend this workshop. Space may be limited, and you are advised to register early. The link to the registration form will appear on this page approximately 10 weeks before the workshop. To submit your name for consideration, please register and await confirmation of your acceptance before booking your travel.