Georgia Institute of Technology College of Sciences

Motivated by neurally feasible computation, we study Boolean functions of an arbitrary number of input variables that can be realized by recursively applying a small set of functions with a constant number of inputs each. This restricted type of construction is neurally feasible since it uses little global coordination or control. Valiant’s construction of a majority function can be realized in this manner and, as we show, can be generalized to any uniform threshold function. We study the rate of convergence, finding that while linear convergence to the correct function can be achieved for any threshold using a fixed set of primitives, for quadratic convergence, the size of the primitives must grow as the threshold approaches 0 or 1. We also study finite realizations of this process, and show that the constructions realized are accurate outside a small interval near the target threshold, where the size of the construction at each level grows as the inverse square of the interval width. This phenomenon, that errors are higher closer to thresholds (and thresholds closer to the boundary are harder to represent), is also a well-known cognitive finding. Finally, we give a neurally feasible algorithm that uses recursive constructions to learn threshold functions. This is joint work with Christos Papadimitriou and Santosh Vempala.

Let G be a 5-connected nonplanar graph. To show the Kelmans-Seymour conjecture, we keep contracting a connected subgraph on a special vertex z until the following happens: H does not contain K_4^-, and for any subgraph T of H such that z is a vertex in T and T is K_2 or K_3, H/T is not 5-connected. In this talk, we prove a lemma using the characterization of three paths with designated ends, which will be used in the proof of the Kelmans-Seymour conjecture.

The subject of this talk is wave equations that arise from geometric considerations. Prime examples include the wave map equation and the Yang-Mills equation on the Minkowski space. On one hand, these are fundamental field theories arising in physics; on the other hand, they may be thought of as the hyperbolic analogues of the harmonic map and the elliptic Yang-Mills equations, which are interesting geometric PDEs on their own. I will discuss the recent progress on the problem of global regularity and asymptotic behavior of solutions to these PDEs.

We define a variant of tropical varieties for exponential sums. These polyhedral complexes can be used to approximate, within an explicit distance bound, the real parts of complex zeroes of exponential sums. We also discuss the algorithmic efficiency of tropical varieties in relation to the computational hardness of algebraic sets. This is joint work with Maurice Rojas and Grigoris Paouris.