{"id":"arxiv/2611.14909","url":"https://arxiv.org/abs/2611.14909","tags":["cs.DM","cs.IT","math.CO"],"score":0,"title":"Explicit Subspace Evasive Sets via Subspace Designs","domain":"cs.DM","source":"arxiv","authors":["Joshua Brakensiek","Yeyuan Chen","Mahdi Cheraghchi","Rohan Goyal","Venkatesan Guruswami","Aaron Putterman","Zihan Zhang"],"reviews":0,"subject":"cs.DM","summary":"Given a finite field $\\mathbb F_q$, we say that a set $A\\subseteq \\mathbb F^n_q$ is an $(r,c)$ subspace evasive set if and only if for any affine subspace $U\\subseteq \\mathbb F^n_q$ with bounded dimension $\\dim(U)\\leq r$, the intersection size $|A\\cap U|$ is at most $c$. The probabilistic method shows the existence of $(r,c)$ subspace evasive sets with $|A| = q^{(1-ε) n}$ with $c = O(r/ε)$. However, the best explicit constructions by Dvir--Lovett (STOC 2012) and Ben-Aroya--Shinkar (CJTCS 2013) have $c$ growing as an exponential function of $r$. Here, we give an explicit construction of such…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-11-11","reactions":{}}