This is joint with Gabe Conant. We give a structure theorem for finite subsets A of arbitrary groups G such that A has "small tripling" and "bounded VC dimension". Roughly, A will be a union of a bounded number of translates of a coset nilprogession of bounded rank and step (up to a small error).

   It is a long-standing open problem whether the ring of integers Z has an existential first-order definition in Q, the field of rational numbers. A few years ago, Jochen Koenigsmann proved that Z has a universal first-order definition in Q, building on earlier work by Bjorn Poonen. This result was later generalised to number fields by Jennifer Park and to global function fields of odd characteristic by Kirsten Eisenträger and Travis Morrison, who used classical machinery from number theory and class field theory related to the behaviour of quaternion algebras over global and local fields.

   In this talk, I will sketch a variation on the techniques used to obtain the aforementioned results. It allows for a relatively short and uniform treatment of global fields of all characteristics that is significantly less dependent on class field theory. Instead, a central role is played by Hilbert's Reciprocity Law for quaternion algebras. I will conclude with an example of a non-global set-up where the existence of a reciprocity law similarly yields universal definitions of certain subrings.

We consider the problem of global minimization with bound constraints. The problem is known to be intractable for large dimensions due to the exponential increase in the computational time for a linear increase in the dimension (also known as the “curse of dimensionality”). In this talk, we demonstrate that such challenges can be overcome for functions with low effective dimensionality — functions which are constant along certain linear subspaces. Such functions can often be found in applications, for example, in hyper-parameter optimization for neural networks, heuristic algorithms for combinatorial optimization problems and complex engineering simulations.

Extending the idea of random subspace embeddings in Wang et al. (2013), we introduce a new framework (called REGO) compatible with any global min- imization algorithm. Within REGO, a new low-dimensional problem is for- mulated with bound constraints in the reduced space. We provide probabilistic bounds for the success of REGO; these results indicate that the success is depen- dent upon the dimension of the embedded subspace and the intrinsic dimension of the function, but independent of the ambient dimension. Numerical results show that high success rates can be achieved with only one embedding and that rates are independent of the ambient dimension of the problem.