It is simple to see that every subset of a an affine space over a finite field is a variety - for example, it follows from the fact that finite subsets are closed in the Zariski Topology of every affine space.
My question is rather algorithmic - given a subset $S \subseteq \mathbb{F}_{q}^n$ for some prime power $q$ and positive $n$, how do I express it as the locus of some polynomial equations, as compactly as possible? By compactly I mean: minimizing the sum of degrees of the polynomials. I don't necessarily want an algorithm - lower\upper bounds will also be cool.
This is a useful question - for example, it has applications in algebraic combinatorics: when invoking the Chevalley-Warning theorem, one wants to write down polynomial equations with low degree in order to satisfy the theorem's conditions.