Speaker: Prof. Noga Ron-Zewi, University of Haifa
Date: 26/10/2020
Time: 13:00-14:00 (Israel Time)
Zoom ID: 810 3573 2468

Abstract: Interactive oracle proofs are a hybrid between interactive proofs and probabilistically-checkable proofs, where the prover is allowed to interact with a verifier by sending relatively long messages to the verifier, who in turn is only allowed to query a few of the bits that were sent. Efficient interactive oracle proofs are useful building blocks in constructing doubly-efficient interactive proofs, and are at the core of leading practical implementations of highly efficient proof-systems.

In this work we construct, for any NP relation for which membership can be decided in polynomial-time and bounded polynomial space (e.g., SAT, Hamiltonicity, Clique, Vertex-Cover, etc.), interactive oracle proofs in which the proof length approaches the witness length. The number of rounds, as well as the number of queries made by the verifier, are constant. Our proof leverages recent constructions of high-rate locally testable tensor codes. In particular, we bypass the barrier imposed by the low rate of multiplication codes (e.g., Reed-Solomon, Reed-Muller or AG codes) - a core component in prior constructions.

Joint work with Ron Rothblum, to appear in FOCS 2020.

Bio: Noga Ron-Zewi is a Senior Lecturer at the Department of Computer Science at the University of Haifa in Israel. Her research interests are in the theory of computation, with a focus on research topics at the interface of communication and computation. She received a Ph.D. degree in Computer Science from the Technion – Israel Institute of Technology in 2014. Prior to joining the University of Haifa, she was a Rothschild postdoctoral fellow at the Institute for Advanced Study (IAS) at Princeton and the Center for Discrete Mathematics and Theoretical Computer Science (DIMACS) at Rutgers, and a faculty member at Ben-Gurion University in Israel. She is a recipient of the Alon Fellowship and the Krill Prize.

Speaker: Prof. Ofer Shayevitz, Tel Aviv University
Date: 09/11/2020
Time: 13:00-14:00 (Israel Time)
Zoom ID: 810 3573 2468

Abstract: Let X_1,X_2... be an infinite sequence of i.i.d. Bernoulli random variables, with expectation p under hypothesis H_0, and q under hypothesis H_1. Consider a deterministic finite-state machine with S states that observes X_k at time k, and then updates its state according to a deterministic time-invariant rule. Assume that we let the machine run for a very long time, and then make our decision according to some fixed mapping from the state space to the hypothesis space. Our main contribution is a lower bound on the Bayes error probability P_e of any such machine. In particular, we show that the ratio between the maximal exponential decay rate of P_e with S for a deterministic machine and for a randomized one, can become unbounded, complementing a result by Hellman.

Joint work with Tomer Berg and Or Ordentlich.

Bio: Ofer Shayevitz is an Associate Professor in the department of EE - Systems at Tel Aviv University. He obtained his B.Sc. from the Technion, and his M.Sc. and PhD from Tel Aviv University, all in Electrical Engineering. Prior to joining the department, he was a postdoctoral fellow at the Information Theory and Application Center (ITA) at UCSD, and also worked as a quantitative analyst for the D.E. Shaw group in NY. Ofer's research interests span a variety of questions where information theory and statistics play a role, including problems in communication, data compression, computation, combinatorics and graph theory, high dimensional statistical inference, statistical signal processing, and data science. He is also actively involved in the hi-tech industry, and regularly consults to various startup companies.

Speaker: Dr. Amirbehshad Shahrasbi, Carnegie Mellon University
Date: 23/11/2020
Time: 17:00-18:00 (Israel Time)
Zoom ID: 810 3573 2468

Abstract: Following the inspiring works of Shannon and Hamming, a sophisticated and extensive body of research on error-correcting codes (ECCs) has led to a deep and detailed theoretical understanding of error-correction from symbol erasures and substitutions. While being remarkably successful in understanding the theoretical limits and trade-offs of reliable communication under symbol substitutions and erasures, the coding theory literature significantly lags behind when it comes to overcoming errors that concern the timing of communications, such as symbol insertions or deletions.

In this talk, we discuss coding against insertions and deletions. We broadly review some recent developments in the area in light of the introduction of combinatorial objects called “synchronization strings” in 2017 as well as questions around synchronization strings as combinatorial objects of interest in their own right.

We present a simple generic construction method for insertion-deletion codes through indexing codewords of an appropriately chosen ECC with synchronization strings. This leads to families of insertion-deletion codes that achieve near-optimal rate-distance trade-off. We also touch on constructions that enable fast encoding/decoding procedures for these codes. We address the same problem under the list-decoding regime, where the decoder is expected to provide a short list of codewords that is guaranteed to contain the sent message. We review recent results on fundamental limits of list-decoding for insertion-deletion errors such as the list-decoding capacity or maximal error resilience in this context. We also show that similar techniques can be used to extend some of the above-mentioned results to alternative communication problems such as coding from block transposition errors or coding for interactive communication.

Bio: Amirbehshad Shahrasbi is an incoming Post-doctoral Fellow at Harvard University. He is a recipient of CRA/CCC’s NSF-funded Computing Innovation Fellowship (CIFellowship). He received his Ph.D. from Carnegie Mellon University’s Computer Science Department in 2020 under the supervision of Bernhard Haeupler. Previously, he had received a B.Sc. in Computer Science and a B.Sc. in Electrical Engineering from Sharif University of Technology in 2015. During the summer of 2019, he worked as a research intern at Microsoft Research’s DNA Data Storage group under the supervision of Sergey Yekhanin. His research is currently focused on algorithmic coding theory.

Speaker: Prof. Anelia Somekh-Baruch, Bar Ilan University
Date: 07/12/2020
Time: 13:00-14:00 (Israel Time)
Zoom ID: 810 3573 2468

Abstract: The question of finding a computable (single-letter) formula for the mismatch capacity, which is the highest achievable rate of reliable communication when the receiver uses a sub-optimal decoding rule, has been a long standing open problem. This question has many applications in communications, Information-Theory, and Computer Science. For example, the zero-error capacity of a channel is a special case of mismatch capacity. While several lower bounds (achievability) have been derived during the years, a non-trivial upper bound (other than the Shannon capacity) was not known until recently. In this talk I will give a brief survey on the problem, and present a new bounding technique called "the multicasting approach" which yields non-trivial single-letter upper bounds (converse). I will also present equivalence classes of isomorphic channel-metric pairs that share the same mismatch capacity, and a sufficient condition for the tightness of the bound for the entire equivalence class.

Bio: Anelia Somekh-Baruch received the B.Sc. degree from Tel-Aviv University, Tel-Aviv, Israel, in 1996 and the M.Sc. and Ph.D. degrees from the Technion–Israel Institute of Technology, Haifa, Israel, in 1999 and 2003, respectively, all in electrical engineering. During 2003–2004, she was with the Technion Electrical Engineering Department. During 2005–2008, she was a Visiting Research Associate at the Electrical Engineering Department, Princeton University, Princeton, NJ. From 2008 to 2009 she was a researcher at the Electrical Engineering Department, Technion, and from 2009 she has been with the Bar-Ilan University Faculty of Engineering, Ramat-Gan, Israel. Her research interests include topics in information theory and communication theory. Dr. Somekh-Baruch received the Tel-Aviv University program for outstanding B.Sc. students scholarship, the Viterbi scholarship, the Rothschild Foundation scholarship for postdoctoral studies, and the Marie Curie Outgoing International Fellowship.

Speaker: Tal Yankovitz, Tel Aviv University
Date: 21/12/2020
Time: 13:00-14:00 (Israel Time)
Zoom ID: 810 3573 2468

Abstract: In a seminal work, Kopparty et al. constructed asymptotically good n-bit locally decodable codes (LDC) with 2^{\tilde{O}(\sqrt{log n})} queries. A key ingredient in their construction is a distance amplification procedure by Alon et al. which amplifies the distance δ of a code to a constant at a poly(1/δ) multiplicative cost in query complexity. Given the pivotal role of the AEL distance amplification procedure in the state-of-the-art constructions of LDC as well as LCC and LTC, one is prompt to ask whether the poly(1/δ) factor in query complexity can be reduced.

Our first contribution is a significantly improved distance amplification procedure for LDC. The cost is reduced from poly(1/δ) to, roughly, the query complexity of a length 1/δ asymptotically good LDC. We derive several applications, one of which allows us to convert a q-query LDC with extremely poor distance δ = n^{−(1−o(1))} to a constant distance LDC with q poly(log log n) queries. As another example, amplifying distance δ = 2^{−(log n)^α}, for any constant α < 1, will require q O(log log log n) queries using our procedure.

Motivated by the fruitfulness of distance amplification, we investigate the natural question of rate amplification. Our second contribution is identifying a rich and natural class of LDC and devise two (incomparable) rate amplification procedures for it. These, however, deteriorate the distance, at which point a distance amplification procedure is invoked. Combined, the procedures convert any q-query LDC in our class, having rate ρ and, say, constant distance, to an asymptotically good LDC with q^{poly(1/ρ)} queries.

Bio: Tal is a Ph.D. student at Tel Aviv university, under the supervision of Gil Cohen. He holds a B.Sc. in Computer Science from Tel-Aviv university. His fields of interests include coding theory, complexity and theory of computer science.

Speaker: Raghuvansh Saxena, Princeton University
Date: 04/01/2021
Time: 17:00-18:00 (Israel Time)
Zoom ID: 810 3573 2468

Abstract: Interactive error correcting codes are codes that encode a two party communication protocol to an error-resilient protocol that succeeds even if a constant fraction of the communicated symbols are adversarially corrupted, at the cost of increasing the communication by a constant factor. The fraction of corruptions that such codes can protect against is called the error resilience. Several recent results have shown that drastic gains in the error resilience can be achieved by using interactive codes that implement "feedback". I shall be reviewing (at least) two of these works in this talk.

Based on joint works with Klim Efremenko and Gillat Kol.

Bio: Raghuvansh R. Saxena is a graduate student in the Department of Computer Science at Princeton University. Prior to joining Princeton, he received his Bachelor of Technology degree in Computer Science and Engineering from IIT Delhi. Raghuvansh has a wide interest in theoretical computer science, especially in developing new complexity theoretic and coding tools for emergent problems in several areas of computing, such as distributed communication and electronic markets. Many of his works are driven by his search for "efficient" and "practical" solutions to modern day problems. Some of the honors that he has received are the Microsoft PhD Fellowship and a Siebel Scholarship in 2019 and the President's Gold Medal (IIT Delhi) in 2016.

Speaker: Dr. Mor Weiss, Bar Ilan University
Date: 18/01/2021
Time: 13:00-14:00 (Israel Time)
Zoom ID: 810 3573 2468

Abstract: In the past few decades, probabilistic checking techniques were shown to yield dramatic efficiency improvements in verifying proofs. In this talk, I will show connections between cryptography and "zero-knowledge" variants of these techniques, such as Probabilistically Checkable Proofs (PCPs). I will focus on constructing PCPs for NP with zero-knowledge guarantees, that can be verified non-adaptively, namely by making a single round of queries to the proof. These constructions are based on a connection to leakage-resilience.

Bio: Mor Weiss is an Assistant Professor at the Engineering Department at Bar-Ilan University, and a member of the Bar-Ilan Center for Research in Applied Cryptography and Cyber Security. Prior to that she was a postdoctoral researcher at IDC Herzliya, and a postdoctoral researcher at NEU. She holds a PhD in Computer Science from the Technion, where she was advised by Prof. Yuval Ishai. She holds a BSc in Computer Science and a BSc in Mathematics from the Technion. Her research field is cryptography, with a focus both on its theoretical foundations and interplay with complexity theory, as well as on designing cryptographic protocols for modern computing systems.