Cover Image

An Improved Construction of Variety-Evasive Subspace Families

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Andrews, Robert, Garg, Abhibhav
Format:	Preprint
Published:	2026
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Variety Evasive Subspace Families
by: Guo, Zeyu
Published: (2021)

Hilbert's Nullstellensatz is in the Counting Hierarchy
by: Andrews, Robert, et al.
Published: (2026)

Primes via Zeros: Interactive Proofs for Testing Primality of Natural Classes of Ideals
by: Garg, Abhibhav, et al.
Published: (2025)

Rank Bounds and PIT for $Σ^3 ΠΣΠ^d$ circuits via a non-linear Edelstein-Kelly theorem
by: Garg, Abhibhav, et al.
Published: (2025)

An exposition of recent list-size bounds of FRS Codes
by: Garg, Abhibhav, et al.
Published: (2025)

Algebraic Pseudorandomness in $VNC^0$
by: Andrews, Robert
Published: (2025)

On Matrix Multiplication and Polynomial Identity Testing
by: Andrews, Robert
Published: (2022)

Constant-Depth Arithmetic Circuits for Linear Algebra Problems
by: Andrews, Robert, et al.
Published: (2024)

Polynomial-Time PIT from (Almost) Necessary Assumptions
by: Andrews, Robert, et al.
Published: (2025)

Modular composition & polynomial GCD in the border of small, shallow circuits
by: Andrews, Robert, et al.
Published: (2025)

Explicit Constant-Alphabet Subspace Design Codes
by: Goyal, Rohan, et al.
Published: (2026)

Semi-Classical Subspaces, The No Synchronization Law, and More
by: Epstein, Samuel
Published: (2024)

Inapproximability of Finding Sparse Vectors in Codes, Subspaces, and Lattices
by: Bhattiprolu, Vijay, et al.
Published: (2024)

Query Lower Bounds for Correlation Clustering under Memory Constraints
by: Garg, Sumegha, et al.
Published: (2026)

Constructive Separations and Their Consequences
by: Chen, Lijie, et al.
Published: (2022)

Structure Theorems (and Fast Algorithms) for List Recovery of Subspace-Design Codes
by: Goyal, Rohan, et al.
Published: (2025)

Constructive Separations from Gate Elimination
by: Carmosino, Marco, et al.
Published: (2026)

Optimal Proximity Gap for Folded Reed--Solomon Codes via Subspace Designs
by: Jeronimo, Fernando Granha, et al.
Published: (2026)

Convergent Gate Elimination and Constructive Circuit Lower Bounds
by: Carmosino, Marco, et al.
Published: (2026)

New Techniques for Constructing Rare-Case Hard Functions
by: Nareddy, Tejas, et al.
Published: (2024)

Sublinear Time Algorithms for Abelian Group Isomorphism and Basis Construction
by: Bshouty, Nader H.
Published: (2025)

Black-Box Crypto is Useless for Pseudorandom Codes
by: Garg, Sanjam, et al.
Published: (2025)

Improving the Leading Constant of Matrix Multiplication
by: Alman, Josh, et al.
Published: (2024)

Improved Condensers for Chor-Goldreich Sources
by: Goodman, Jesse, et al.
Published: (2024)

Improved Bounds on the Space Complexity of Circuit Evaluation
by: Shalunov, Yakov
Published: (2025)

Systems of Discrete Differential Equations, Constructive Algebraicity of the Solutions
by: Notarantonio, Hadrien, et al.
Published: (2023)

Improved Parallel Repetition for GHZ-Supported Games via Spreadness
by: Liu, Yang P., et al.
Published: (2026)

Parks: A Doubly Infinite Family of NP-Complete Puzzles and Generalizations of A002464
by: Minevich, Igor, et al.
Published: (2024)

Gadgetless Lifting Beats Round Elimination: Improved Lower Bounds for Pointer Chasing
by: Mao, Xinyu, et al.
Published: (2024)

Improved Lower Bounds for Approximating Parameterized Nearest Codeword and Related Problems under ETH
by: Li, Shuangle, et al.
Published: (2024)

Low-Degree Method Fails to Predict Robust Subspace Recovery
by: Jia, He, et al.
Published: (2026)

Improved Small Set Expansion in High Dimensional Expanders
by: Kaufman, Tali, et al.
Published: (2025)

Construction of Event Graph for Ship Collision Accident Analysis to Improve Maritime Traffic Safety
by: Jun Ma, et al.
Published: (2024)

A Unified Approach to Memory-Sample Tradeoffs for Detecting Planted Structures
by: Garg, Sumegha, et al.
Published: (2026)

Improved Lower Bounds for all Odd-Query Locally Decodable Codes
by: Basu, Arpon, et al.
Published: (2024)

Explicit Directional Affine Extractors and Improved Hardness for Linear Branching Programs
by: Li, Xin, et al.
Published: (2023)

Lower Bounds for Approximate Sign Rank
by: Bindua, Riju, et al.
Published: (2026)

On Pigeonhole Principles and Ramsey in TFNP
by: Jain, Siddhartha, et al.
Published: (2024)

Improved quantum data analysis
by: Bădescu, Costin, et al.
Published: (2020)

Improved Debordering of Waring Rank
by: Shpilka, Amir
Published: (2025)