Title: VC-dimension of short Presburger formulas,
Abstract: We study VC-dimension of short formulas in Presburger Arithmetic, defined to
have a bounded number of variables, quantifiers and atoms. We give both lower
and upper bounds, which are tight up to a polynomial factor in the bit length
of the formula.