EE Seminar: Sublinear algorithms in coding theory
(The talk will be given in English)
Speaker: Tom Gur
Weizmann Institute
Monday, March 19th, 2018
15:00 - 16:00
Room 011, Kitot Bldg., Faculty of Engineering
Sublinear algorithms in coding theory
Abstract
With the surge of massive data sets in recent years, our notions of “efficient” algorithms must evolve as well. Indeed, many scenarios require algorithms that run in sublinear time, and thus their decisions are made based on a small local view of a large object.
A prominent field wherein sublinear algorithms found great success is coding theory, which provides central tools in communication, storage, complexity, cryptography, and algorithms. Codes endow information with a structure that admits robustness to errors.
In this talk we will discuss the salient notions of sublinear time algorithms for coding theory, including locally decodable codes and locally testable codes, as well as applications of these codes inside and outside of coding theory.
Short bio
Tom Gur is a postdoc in the EECS Department at UC Berkeley. He received his PhD in computer science and mathematics from the Weizmann Institute of Science, where his advisor was Prof. Oded Goldreich. He is broadly interested in sublinear algorithms and verifiable computing, as well as in their interplay with coding theory, cryptography, complexity, quantum information, computational genetics, combinatorics, and more.
