Variety evasive sets

DOI10.1007/S00037-013-0073-9MaRDI QIDQ475333zbMATH OpenOpenAlexFDO

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

Publication date 26 November 2014

Published in Computational Complexity (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1203.4532

zbMATH Keywords

finite fieldsaffine varietyexplicit constructionsde-randomization

Mathematics Subject Classification ID

Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Randomized algorithms (68W20) Symbolic computation and algebraic computation (68W30) Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Number-theoretic algorithms; complexity (11Y16)

Abstract: We give an explicit construction of a large subset of F^n, where F 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 (affine subspaces).

Recommendations

• Variety evasive subspace families
• Subspace evasive sets
• Going beyond variation of sets
• Evolving sets and mixing
• Evasion with weak superiority
• A variation on the game SET
• Uncovered sets
• Guessing more sets
• A certain evasion problem

Cites work

• scientific article; zbMATH DE number 4146160 (Why is no real title available?)
• scientific article; zbMATH DE number 125952 (Why is no real title available?)
• scientific article; zbMATH DE number 621806 (Why is no real title available?)
• scientific article; zbMATH DE number 1966201 (Why is no real title available?)
• A note on subspace evasive sets
• Definability and fast quantifier elimination in algebraically closed fields
• Deterministic extractors for affine sources over large fields
• Explicit Codes Achieving List Decoding Capacity: Error-Correction With Optimal Redundancy
• Norm-graphs and bipartite Turán numbers
• On the Noether-Lefschetz theorem and some remarks on codimension-two cycles
• On the construction of affine extractors
• Subspace evasive sets
• The Kakeya set and maximal conjectures for algebraic varieties over finite fields

Cited in

(11)

• scientific article; zbMATH DE number 7561763 (Why is no real title available?)
• Variety evasive subspace families
• Partition and analytic rank are equivalent over large fields
• Avoiding intersections of given size in finite affine spaces \(\operatorname{AG}(n,2)\)
• Furstenberg sets and Furstenberg schemes over finite fields
• Reductions modulo primes of systems of polynomial equations and algebraic dynamical systems
• Elements of large order on varieties over prime finite fields
• The automorphism group of projective norm graphs
• A promenade through correct test sequences. I: Degree of constructible sets, Bézout's inequality and density
• Subspace evasive sets
• A note on subspace evasive sets

This page was built for publication: Variety evasive sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q475333)