A shallow (one–hidden layer) neural network is trained using gradient flow (a continuous version of gradient descent) on data that perfectly fits a single ReLU neuron. We find sufficient conditions for convergence to zero loss. The limit network has minimum rank and, depending on the geometry of data, may or may not have minimum norm.

A decision procedure for Presburger arithmetic based on semilinear sets runs in triply exponential time. Also, the VC dimension of Presburger formulas is at most doubly exponential in their length.

We extend linear integer arithmetic with quantifiers of the form “there exists at least c values of x” and similar. It turns out such theories still support efficient quantifier elimination, even relative to alternation depth.

The decision problem for linear arithmetic over Z with just equality (no inequalities) is as hard as for standard linear integer arithmetic. To prove this, we define and study the complexity of a quantified version of SAT that supports higher-order Boolean functions.

For while loops of the form “while x in S do x:=A*x” (where x is initialized to a rational vector, A is a rational matrix, and S is a nice set), minimal invariants look like truncated cones.

We look at a probabilistic puzzle on the sphere which has applications to quantum information theory (Bell inequalities).

Given a formula of linear arithmetic, can we decide if the same set can be defined by another formula that uses just equality, without inequalities?

We find a matrix for which the nonnegative rank over the reals and over the rationals are different.

Relying on ideas of Sipser and Stockmeyer, existing SMT solvers can do approximate model counting (discrete counting or volume estimation) for logical theories of arithmetic.

If some variables in integer programs are quantified universally instead of existentially, then the decision problem becomes complete for the k-th level of the polynomial hierarchy, assuming k quantifier blocks.

We find a matrix for which the nonnegative rank over the reals and over the rationals are different. Consequently, state minimization of hidden Markov models may require irrational probabilities.

There exists a pair of 3D polytopes with rational vertices, one inside the other, such that every intermediate polytope with 5 vertices must have a vertex with an irrational coordinate.

To measure how semilinear sets “grow” under Boolean operations, we keep track of the maximum norm of generators.