Hi all,
This is a reminder that next Thursday, March 18, 15:00 to 19:00, we are going to have the first GTACS of this year.
The event will be on zoom.
We will have four 45 mins talks, each talk followed by 15 minutes discussion/break.
The Speakers are Carmit Hazay, Jad Silbak, Ran Gelles and Daniel Wichs.
The program and abstracts are given below.
See you soon,
Iftach and Benny
Program:
15:00- 15:15: Virtual gathering (bring your own cookies)
15:15-16:00: Carmit Hazay on ZK-PCPs from Leakage-Resilient Secret Sharing
16:00-16:15: Q&A and break
16:15-17:00: Jad Silbak on Explicit Uniquely Decodable Codes for Space Bounded Channels That Achieve List-Decoding Capacity
17:00-17:15: Q&A and break
17:15-18:00: Ran Gelles on Efficient Multiparty Interactive Coding for Insertions, Deletions and Substitutions
18:00-18:15: Q&A and break
18:15-19:00: Daniel Wichs on Incompressible Encodings
Link to zoom
Google calendar entry
Abstracts
Carmit Hazay: ZK-PCPs from Leakage-Resilient Secret Sharing
Zero-Knowledge PCPs (ZK-PCPs; Kilian, Petrank, and Tardos, STOC `97) are PCPs with the additional zero-knowledge guarantee that the view of any (possibly malicious) verifier making a bounded number of queries to the proof can be efficiently simulated up to a small statistical distance. Similarly, ZK-PCPs of Proximity (ZK-PCPPs; Ishai and Weiss, TCC `14) are PCPPs in which the view of an adversarial verifier can be efficiently simulated with few queries to the input.
Previous ZK-PCP constructions obtained an exponential gap between the query complexity q of the honest verifier, and the bound q* on the queries of a malicious verifier (i.e., q=polylog(q*), but required either exponential-time simulation, or adaptive honest verification. This should be contrasted with standard PCPs, that can be verified non-adaptively (i.e., with a single round of queries to the proof). The problem of constructing such ZK-PCPs, even when q*=q, has remained open since they were first introduced more than 2 decades ago. This question is also open for ZK-PCPPs, for which no construction with non-adaptive honest verification is known (not even with exponential-time simulation).
We resolve this question by constructing the first ZK-PCPs and ZK-PCPPs which simultaneously achieve efficient zero-knowledge simulation and non-adaptive honest verification. Our schemes have a square-root query gap, namely q*/q = O(\sqrt(n)) where n is the input length.
Our constructions combine the ``MPC-in-the-head'' technique (Ishai et al., STOC `07) with leakage-resilient secret sharing. Specifically, we use the MPC-in-the-head technique to construct a ZK-PCP variant over a large alphabet, then employ leakage-resilient secret sharing to design a new alphabet reduction for ZK-PCPs which preserves zero-knowledge.
Joint work with Muthuramakrishnan Venkitasubramaniam and Mor Weiss.
Jad Silbak: Explicit Uniquely Decodable Codes for Space Bounded Channels That Achieve List-Decoding Capacity
We consider codes for space bounded channels. This is a model for communication under noise that was introduced by Guruswami and Smith (J. ACM 2016) and lies between the Shannon (random) and Hamming (adversarial) models. In this model, a channel is a space bounded procedure that reads the codeword in one pass, and modifies at most a p fraction of the bits of the codeword.
Our main result is that for every 0 ≤ p < 1/4 , there exists a constant δ > 0 and a uniquely decodable code with rate 1 − H(p) for channels with space n^δ . This code is explicit (meaning that encoding and decoding are in poly-time). This improves upon previous explicit codes by Guruswami and Smith, and Kopparty, Shaltiel and Silbak (FOCS 2019). Specifically, we obtain the same space and rate as earlier works, even though prior work gave only list-decodable codes (rather than uniquely decodable codes).
A key new ingredient in our construction is a new notion of “evasiveness” of codes, which is concerned with whether a decoding algorithm rejects a word that is obtained when a channel induces few errors to a uniformly chosen (or pseudorandom) string. We use evasiveness (as well as several additional new ideas related to coding theory and pseudorandomness) to identify the “correct” message in the list obtained by previous list-decoding algorithms.
