Variety Evasive Sets

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

doi:10.1007/s00037-013-0073-9

Variety Evasive Sets

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

Research output: Contribution to journal › Article › peer-review

11 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 language	English (US)
Pages (from-to)	509-529
Number of pages	21
Journal	Computational Complexity
Volume	23
Issue number	4
DOIs	https://doi.org/10.1007/s00037-013-0073-9
State	Published - Dec 2014

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Mathematics
Computational Theory and Mathematics
Computational Mathematics

Keywords

Explicit constructions
de-randomization
finite fields

Access to Document

10.1007/s00037-013-0073-9

Cite this

@article{24c623e7d50f4aa58a791443020b586a,

title = "Variety Evasive Sets",

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).",

keywords = "Explicit constructions, de-randomization, finite fields",

author = "Zeev Dvir and J{\'a}nos Koll{\'a}r and Shachar Lovett",

note = "Publisher Copyright: {\textcopyright} 2013, Springer Basel.",

year = "2014",

month = dec,

doi = "10.1007/s00037-013-0073-9",

language = "English (US)",

volume = "23",

pages = "509--529",

journal = "Computational Complexity",

issn = "1016-3328",

publisher = "Birkhauser Verlag Basel",

number = "4",

}

TY - JOUR

T1 - Variety Evasive Sets

AU - Dvir, Zeev

AU - Kollár, János

AU - Lovett, Shachar

PY - 2014/12

Y1 - 2014/12

N2 - 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).

AB - 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).

KW - Explicit constructions

KW - de-randomization

KW - finite fields

UR - http://www.scopus.com/inward/record.url?scp=84919911053&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84919911053&partnerID=8YFLogxK

U2 - 10.1007/s00037-013-0073-9

DO - 10.1007/s00037-013-0073-9

M3 - Article

AN - SCOPUS:84919911053

SN - 1016-3328

VL - 23

SP - 509

EP - 529

JO - Computational Complexity

JF - Computational Complexity

IS - 4

ER -

Variety Evasive Sets

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this