SHORT PCPS · Short and Simple PCPs

Lines connect the coordinator with its partners.

Project objective

Formal proofs are essential to many areas of computer science (e.g. cryptography, formal verification and distributed computing). Probabilistically Checkable Proofs (PCPs) offer an extremely efficient way of verifying proofs provided they are written in a particular format. However, the use of PCPs in computer science has so far been purely theoretical, mainly because of the length and inherent complexity of the format of these proofs. Our research goal is to find shorter and simpler PCPs, thus facilitating their practical use. We will pursue our research goal by studying the main building blocks of PCPs, such as locally testable codes and their algebraic construction. As corollaries of our research we hope to find new applications of PCPs to the fields of error correcting codes and algebraic computation.Our research plan is to form a leading group of students, post-doctoral researchers and visiting scientists that will collaborate to achieve our research goal. The group will maintain close connections with leading institutions in Europe and the United States via visits of group-members to other leading research centres, participation in international conferences and inviting researchers in the field to the host institution, Technion - Israel Institute of Technology. Previous research of the PI, conducted mainly at MIT and Harvard, has produced promising preliminary results.This proposal aims to expand this line of research at the host institution. The host institution has world-class researchers in many of the disciplines to which PCPs can be applied, such as cryptography, approximation algorithms, formal verification, distributed computing, electrical engineering and error correcting codes. We expect our research group to interact and collaborate with researchers in these diverse fields at the host institution, thus ensuring lasting reintegration.

Original text from CORDIS.

Participants

• TECHNION - ISRAEL INSTITUTE OF TECHNOLOGY · HAIFACoordinatorIsrael

Links

• View on CORDIS