• Calendar

April 4, Tuesday
12:00 – 14:00

In this work we study two, seemingly unrelated, notions. Locally Decodable Codes (LDCs) are codes that allow the recovery of each message bit from a constant number of entries of the codeword. Polynomial Identity Testing (PIT) is one of the fundamental problems of algebraic complexity: we are given a circuit computing a multivariate polynomial and we have to determine whether the polynomial is identically zero. We improve known results on locally decodable codes and on polynomial identity testing and show a relation between the two notions. In particular we obtain the following results:

1. We prove an exponential lower bound on the length of linear LDC with 2 queries over arbitrary fields (previously it was known only for fields of size smaller than $2^n$)
2. We show that from every depth 3 arithmetic circuit C, with a bounded (constant) top fan-in that computes the zero polynomial, one can construct an LDC with 2 queries.
3. We prove a structural theorem for depth 3 arithmetic circuits, with a bounded top fan-in, that compute the zero polynomial.
4. We give new PIT algorithms for depth 3 arithmetic circuits with a bounded top fan-in.

Joint work with Zeev Dvir from the Weizmann Institute

A short bio:
I finished my B.Sc. in the Hebrew university in 1996. I finished my Ph.D. also at the Hebrew university in 2001. I was a post-doc at Weizmann from 2001-2 and from 2003-5. I was a post-doc in Harvard and MIT in 2002-3. As of October I am a faculty member in the Technion.