Mulmuley recently gave an explicit version of Noether's Normalization lemma for ring of invariants of matrices under simultaneous conjugation, under the conjecture that there are deterministic black-box algorithms for polynomial identity testing (PIT). He argued that this gives evidence that constructing such algorithms for PIT is beyond current techniques. In ... more >>>

We introduce the problem of constructing explicit variety evasive subspace families. Given a family \mathcal{F} of subvarieties of a projective or affine space, a collection \mathcal{H} of projective or affine k-subspaces is (\mathcal{F},\epsilon)-evasive if for every \mathcal{V}\in\mathcal{F}, all but at most \epsilon-fraction of W\in\mathcal{H} intersect every irreducible component of \mathcal{V} ... more >>>