Research Interests

My research interests are at the interface of coding theory, algorithms, and complexity. Here are some popular articles about my research:

• My attempt to explain what are error-correcting codes and what they are good for on public radio (in Hebrew): Three Who Know, Kan Tarbut, 27.11.22

• Article about my postdoctoral research on Locally Testable and Locally Decodable Codes: DIMACS Highlights

Below are some specific research projects in which I have been involved lately.

Algorithmic coding theory: 

Coding theory is concerned with reliable delivery of digital data over unreliable communication channels, and specifically with the design of error-correcting codes that are used to encode the data so that it can be recovered even if parts of it were corrupted. The main objective in algorithmic coding theory is to come-up with computationally efficient codes that admit efficient encoding and decoding algorithms. While for many communication scenarios we know these days of efficient (polynomial time) codes, it is still a major challenge in many such scenarios to find codes that admit low complexity algorithms that run in linear or even sublinear time. 

Complexity of coding: 

While we know these days of several families of efficient error-correcting codes, for some specific families of codes (e.g., random codes) we do not know of such algorithms and even conjecture that such algorithms do not exist. However, establishing the exact hardness of these codes is still elusive. Such codes can potentially be used in turn as the basis of cryptosystems whose security is based on hardness of decoding.

Coding for multiparty communication: 

Distributed computation often requires communication protocols and error-correction schemes for multiparty communication. As opposed to one-way communication, the multiparty setting is much less well understood and many fundamental challenges still remain in this setting.

Interplay between communication and computation: 

As communication lies at the core of many computational tasks, communication and error-correcting codes appear everywhere: complexity theory, cryptography, distributed computing, networks, and more. I am happy to collaborate with anyone interested in these topics.