The Technion Theory Lunch is a seminar run by the theory group at the Department of Computer Science, Technion. The seminar holds weekly meetings in which graduate students and faculty from the Technion and other universities in Israel and abroad present recent results or other interesting topics in theoretical computer science. The seminar is open to faculty, graduate and undergraduate students interested in theory of computing.

**Wednesdays, 13:00-14:00 (food starts at 12:45)**

**Room 619, Amado Building (Math)**

If you are interested in giving a talk at the seminar, contact Ron Rothblum and/or David Wajc.

The seminar’s mailing list is used to announce our weekly meetings, and also to publicize CS theory related events, such as workshops and seminars, in Israel and abroad.

To join or leave our mailing list.

What are the minimal cryptographic assumptions necessary for constructing efficient argument systems, and for which computational tasks? In this talk, we explore constant-round, doubly-efficient argument systems for three different computational tasks, assuming only the existence of one-way functions.

The main result is an argument system with almost-linear verification time for bounded-depth computations. Known unconditionally sound interactive proofs for this class of computations do not rely on any cryptographic assumptions, but require a linear number of rounds [Goldwasser, Kalai, and Rothblum, STOC 2008]. In contrast, Kilian’s protocol [STOC 1992] applies to a broader class of computations, but assumes the existence of collision-resistant hash functions.

Building on these tools, we present two additional results. The first is a new argument system for batch-verification of k UP (NP statements with a unique witness) statements for witness relations that are verifiable in bounded depth, where the communication is quasi-linear in the length of a single witness. The second result introduces an argument system for languages in P that are computable by bounded-space Turing machines, that achieves an exponential improvement in the trade-off between the number of rounds and the communication complexity compared to known unconditionally sound protocols [Reingold, Rothblum, and Rothblum, STOC 2016].

Based on joint works with Guy Rothblum.

Tal Yankovitz (Tel Aviv University)

A q-locally correctable code (LCC) C:{0,1}^k->{0,1}^n is a code in which it is possible to correct every bit of a (not too) corrupted codeword by making at most q queries to the word. The cases in which q is constant are of special interest, and so are the cases that C is linear.

In a breakthrough result Kothari and Manohar (STOC 2024) showed that for linear 3-LCC n=2^Ω(k^1/8) . In this work we prove that n=2^Ω(k^1/4) . As Reed-Muller codes yield 3-LCC with n=2^O(k^1/2) , this brings us closer to closing the gap. Moreover, in the special case of design-LCC (into which Reed-Muller fall) the bound we get is n=2^Ω(k^1/3).