Conversation with Zeev 2-24-16

Circuit lower bounds and extractors

• The graph-theoretic argument applied to linear circuits reduces finding hard functions to finding rigid matrices.

We can reduce the rigidity problem to finding extractors for a certain class of a certain type.

Find extractors where * sources are: uniform over \(\fc n2\)-dimensional (or \(\ep n\)) subspaces \(V\subeq \F_p^n\) such that \(V\) has low-weight (sparse, \(n^\ep\)) basis. (Actually, we can also consider average sparsity.) * The extractor is linear \(E:\F_p^n\to \F_p^{\fc n4}\).

We know deterministic extractors for affine sources, however, here they have to be linear.

Claim: Let \(A\) be such that \(O=eA\). Then \(A\) is rigid.

Proof: \(A\) has rank \(\ge \fc{3n}4\). Suppose \(A=L+S\) where \(L\) has \(<\fc n4\)-rank and \(S\) is \(s\)-sparse. \(O=EA=EL+ES\) so \(-EL=ES\). However, \(-EL\) has low rank and \(ES\) has high rank (\(\fc n4\)) as \(E\) is an extractor.

Note it suffices to find a condenser; all we need is that \(\dim(\spn_s(E(S,s)))=\fc n4\).

(cf. no \(2s\) columns of \(E\) are linearly dependent.)

Rigid matrices

Find a small family of rigid matrices. Ex. if you only require linear randomness, then just wire them up too to get a lower bound.

Gabizon-Raz, Affine extractors: give a family of Vandermonde matrices \((x^{ij})\), \(x\in [n^3]\) (?). The hope is to get arithmetic lower bounds. Problem: the degree is too large, so the bounds are trivial. Try to lower the degree.

Best lower bounds for arithmetic circuits: for \(x_1^n,\ldots, x_n^n\), get \(n\lg n\). Use Bezout: use the highest degree of an algebraic variety made from the polynomials as a complexity measure, need to get to \(d^n\), so need \(n\ln d\) steps.

Zach Remscrim has a nice recent paper.