[talks] G Hu general exam

[Melissa M. Lawson]

Guangda Hu will present his research seminar/general exam on Thursday May 9 
at 3PM in Room 402.  The members of his committee are:  Zeev Dvir, advisor,
Moses Charikar, and Mark Braverman.  Everyone is invited to attend his talk 
and those faculty wishing to remain for the oral exam following are welcome 
to do so.  His abstract and reading list follow below.
------------------------- 

Abstract:

Locally decodable code (LDC) is an error-correcting code that every bit of the original message can be recovered by reading only a small number of bits in the code. A major question is about the minimum length of constant query LDCs. It is known that 2-query LDC has length at least exponential of the message length. However, there is a huge gap between the lower and upper bounds if the query number is greater than 2. The lower bound for 3-query LDC is only quadratic while the best known construction has super-polynomial length.

The constructions of constant query LDCs all had exponential length until a very recent breakthrough. The sub-exponential, although still super-polynomial, constructions of LDCs are based on matching vector (MV) families. An MV family is defined as two lists of n-dimensional vectors in Z_m, where only the corresponding vectors of the two lists have inner product 0. A larger MV family implies a shorter code. MV families also arise in other combinatorial contexts as well, where a large MV family can also imply new results. Therefore it is interesting to figure out the maximum size of MV families.

For prime m, the upper bound of MV families are already tight. However, the question was not well understood for general composite m. In [DGY11], an upper bound m^{n-1+o(1)} was proved and m^{n/2} was conjectured. In [BDL13], the bound was improved to m^{n/2+O(log m)}. Inspired by previous works, we proved a new upper bound m^{n/2+O(1)}. Comparing to the known MV constructions, this is almost tight for m>>n.

Reading List:

Textbook: Computational Complexity: A modern approach. [ARORA-BARAK]

[Yek08] Towards 3-query locally decodable codes of subexponential length. Sergey Yekhanin.
[Efr09] 3-query Locally Decodable Codes of Subexponential Length. Klim Efremenko.
[DGY11] Matching Vector Codes. Zeev Dvir, Parikshit Gopalan, Sergey Yekhanin.
[KT00] On the efficiency of local decoding procedures for error-correcting codes. Jonathan Katz, Luca Trevisan.
[GKST02] Lower Bounds for Linear Locally Decodable Codes and Private Information Retrieval. Oded Goldreich, Howard Karloff, Leonard Schulman, Luca Trevisan.
[Woo07] New Lower Bounds for General Locally Decodable Codes. David P. Woodruff.
[Woo10] A Quadratic Lower Bound for Three-Query Linear Locally Decodable Codes over Any Field. David P. Woodruff.
[DS06] Locally Decodable Codes with 2 queries and Polynomial Identity Testing for depth 3 circuits. Zeev Dvir, Amir Shpilka.
[BDWY11] Rank Bounds for Design Matrices with Applications to Combinatorial Geometry and Locally Correctable Codes. Boaz Barak, Zeev Dvir, Avi Wigderson, Amir Yehudayoff.
[BDL13] New Bounds for Matching Vector Families. Abhishek Bhowmick, Zeev Dvir, Shachar Lovett.