Special Computer Science/Discrete Mathematics Seminar

A nxn matrix M over GF(2) is said to be (r,\delta)-rigid if every matrix M' within \delta n^2 Hamming distance from M has rank at least r. A long standing open problem is to construct explicit rigid matrices. In a recent remarkable result, Alman and Chen gave explicit constructions of rigid matrices using an NP oracle. In this talk, we will give a simplified and improved construction of their result that proves explicit (r,0.01)-rigid matrices in P^NP where 2 = 2^{(log n)^{1-o(1)}}. We obtain our improvement by considering PCPs where the query and randomness satisfy a certain "rectangular property".

Joint work with Amey Bhangale, Orr Paradise and Avishay Tal