Delphi.science

Explicit Subspace Evasive Sets via Subspace Designs

Source: arxiv.org/abs/2611.14909

Joshua Brakensiek, Yeyuan Chen, Mahdi Cheraghchi, Rohan Goyal, Venkatesan Guruswami, Aaron Putterman, Zihan Zhang

arXivarxiv/2611.14909Nov 11, 2026cs.DMscore 0

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…

JSONText

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2611.14909
curl -X POST /api/v1/records/arxiv/2611.14909/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.14909/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'