Variety Evasive Sets

Zeev Dvir, János Kollár, Shachar Lovett

Research output: Contribution to journalArticle

2 Scopus citations

Abstract

We give an explicit construction of a large subset (formula presented), where (formula presented) is a finite field, that has small intersection with any affine variety of fixed dimension and bounded degree. Our construction generalizes a recent result of Dvir and Lovett (STOC 2012) who considered varieties of degree one (that is, affine subspaces).

Original languageEnglish (US)
Pages (from-to)509-529
Number of pages21
JournalComputational Complexity
Volume23
Issue number4
DOIs
StatePublished - Dec 2014

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Mathematics(all)
  • Computational Theory and Mathematics
  • Computational Mathematics

Keywords

  • Explicit constructions
  • de-randomization
  • finite fields

Fingerprint Dive into the research topics of 'Variety Evasive Sets'. Together they form a unique fingerprint.

  • Cite this