  We study complexity measures on subsets of the boolean hypercube and exhibit
connections between algebra (the Hilbert function) and combinatorics (VC
theory). These connections yield results in both directions. Our main
complexity-theoretic result proves that most linear program feasibility
problems cannot be computed by polynomial-sized constant-depth circuits.
Moreover, our result applies to a stronger regime in which the hyperplanes are
fixed and only the directions of the inequalities are given as input to the
circuit. We derive this result by proving that a rich class of extremal
functions in VC theory cannot be approximated by low-degree polynomials. We
also present applications of algebra to combinatorics. We provide a new
algebraic proof of the Sandwich Theorem, which is a generalization of the
well-known Sauer-Perles-Shelah Lemma. Finally, we prove a structural result
about downward-closed sets, related to the Chv\'{a}tal conjecture in extremal
combinatorics.
