Variety evasive sets

DOI10.1007/S00037-013-0073-9zbMATH Open1308.68166arXiv1203.4532OpenAlexW2027976532MaRDI QIDQ475333FDOQ475333

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

Publication date: 26 November 2014

Published in: Computational Complexity (Search for Journal in Brave)

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

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

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

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)

Cites Work

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

Cited In (11)

• Elements of large order on varieties over prime finite fields
• Variety evasive subspace families
• Title not available (Why is that?)
• Furstenberg sets and Furstenberg schemes over finite fields
• A promenade through correct test sequences. I: Degree of constructible sets, Bézout's inequality and density
• The automorphism group of projective norm graphs
• Avoiding intersections of given size in finite affine spaces \(\operatorname{AG}(n,2)\)
• Reductions modulo primes of systems of polynomial equations and algebraic dynamical systems
• Partition and analytic rank are equivalent over large fields
• 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)