Abstract We introduce the problem of constructing explicit variety evasive subspace families . Given a family $$\mathcal{F}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>F</mml:mi> </mml:math> of subvarieties of a projective or affine space, a collection $$\mathcal{H}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>H</mml:mi> </mml:math> of projective or affine $$k$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>k</mml:mi> </mml:math> -subspaces is $$(\mathcal{F},\epsilon)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>F</mml:mi> <mml:mo>,</mml:mo> <mml:mi>ϵ</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> -evasive if for every $$\mathcal{V}\in\mathcal{F}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>V</mml:mi> <mml:mo>∈</mml:mo> <mml:mi>F</mml:mi> </mml:mrow> </mml:math> , all but at most $$\epsilon$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>ϵ</mml:mi> </mml:math> -fraction of $$W\in\mathcal{H}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>W</mml:mi> <mml:mo>∈</mml:mo> <mml:mi>H</mml:mi> </mml:mrow> </mml:math> intersect every irreducible component of $$\mathcal{V}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>V</mml:mi> </mml:math> with (at most) the expected dimension. The problem of constructing such an explicit subspace family generalizes both deterministic black-box polynomial identity testing (PIT) and the problem of constructing explicit (weak) lossless rank condensers. Using Chow forms, we construct explicit $$k$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>k</mml:mi> </mml:math> -subspace families of polynomial size that are evasive for all varieties of bounded degree in a projective or affine $$n$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>n</mml:mi> </mml:math> -space. As one application, we obtain a complete derandomization of Noether’s normalization lemma for varieties of low degree in a projective or affine $$n$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>n</mml:mi> </mml:math> -space. In another application, we obtain a simple polynomial-time black-box PIT algorithm for depth-4 arithmetic circuits with bounded top fan-in and bottom fan-in that are not in the Sylvester–Gallai configuration, improving and simplifying a result of Gupta (ECCC TR 14-130). As a complement of our explicit construction, we prove a tight lower bound for the size of $$k$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>k</mml:mi> </mml:math> -subspace families that are evasive for degree- $$d$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>d</mml:mi> </mml:math> varieties in a projective $$n$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>n</mml:mi> </mml:math> -space. When $$n-k=n^{\Omega(1)}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>-</mml:mo> <mml:mi>k</mml:mi> <mml:mo>=</mml:mo> <mml:msup> <mml:mi>n</mml:mi> <mml:mrow> <mml:mi>Ω</mml:mi> <mml:mo>(</mml:mo> <mml:mn>1</mml:mn> <mml:mo>)</mml:mo> </mml:mrow> </mml:msup> </mml:mrow> </mml:math> , the lower bound is superpolynomial unless $$d$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>d</mml:mi> </mml:math> is bounded. The proof uses a dimension counting argument on Chow varieties that parametrize projective subvarieties.

Zeyu Guo

Computational Complexity

计算复杂性提出了计算复杂性方面的杰出研究。它的主题是数学和理论计算机科学之间的接口，具有清晰的数学轮廓和严格的数学格式。中心主题是：计算模型、复杂性界限（特别强调下界）、复杂性类别、权衡结果用于确定性、概率性和非确定性计算的“一般”（布尔）和“结构化”计算（例如决策树、算术电路）的顺序和并行计算最坏情况和平均情况的具体重点领域包括：复杂性类别的结构（简化、相对化问题、度，去随机化）代数复杂性（双线性复杂性，多项式、组、代数和表示的计算）交互式证明、伪随机生成和随机性提取复杂性问题：密码学学习理论数论逻辑（逻辑理论的复杂性，决策过程的成本）组合优化和近似解分布式计算性能测试。

The journal 'Computational Complexity' is dedicated to outstanding research in the field of computational complexity, focusing on the interface between mathematics and theoretical computer science, characterized by clear mathematical outlines and rigorous mathematical formats. The central themes include computational models, complexity bounds (with a particular emphasis on lower bounds), complexity classes, and trade-off results for deterministic, probabilistic, and non-deterministic computations. Specific areas of focus include: the structure of complexity classes (simplification, relativization problems, degrees, derandomization), algebraic complexity (bilinear complexity, computations of polynomials, groups, algebras, and representations), interactive proofs, pseudorandom generation, and randomness extraction. Complexity issues encompass cryptography, learning theory, number theory, logic (the complexity of logical theories, costs of decision processes), combinatorial optimization and approximate solutions, as well as performance testing in distributed computing.

《Computational Complexity》期刊致力于计算复杂性领域的杰出研究，涵盖数学与理论计算机科学之间的接口，具有清晰的数学轮廓和严格的数学格式。其核心主题包括计算模型、复杂性界限（特别是下界）、复杂性类别，以及用于确定性、概率性和非确定性计算的权衡结果。具体重点领域包括：复杂性类别的结构（简化、相对化问题、度，去随机化）、代数复杂性（双线性复杂性、多项式、组、代数和表示的计算）、交互式证明、伪随机生成和随机性提取。复杂性问题涉及密码学、学习理论、数论、逻辑（逻辑理论的复杂性、决策过程的成本）、组合优化和近似解，以及分布式计算性能测试。

Category	Quartile
计算机科学	3
计算机科学, 计算机理论方法	3
计算机科学, 数学	3

Variety Evasive Subspace Families

ivySCI AI Smartly Parses PDF, Answers Researchers' Questions, and Helps You Understand Papers in Seconds

Journal Info