Georgia Institute of Technology College of Sciences

In this talk, my goal is to give an introduction to some of the mathematics behind quasicrystals. Quasicrystals were discovered in 1982, when Dan Schechtmann observed a material which produced a diffraction pattern made of sharp peaks, but with a 10-fold rotational symmetry. This indicated that the material was highly ordered, but the atoms were nevertheless arranged in a non-periodic way. These quasicrystals can be defined by certain aperiodic tilings, amongst which the famous Penrose tiling. What makes aperiodic tilings so interesting--besides their aesthetic appeal--is that they can be studied using tools from many areas of mathematics: combinatorics, topology, dynamics, operator algebras... While the study of tilings borrows from various areas of mathematics, it doesn't go just one way: tiling techniques were used by Giordano, Matui, Putnam and Skau to prove a purely dynamical statement: any Z^d free minimal action on a Cantor set is orbit equivalent to an action of Z.

To any compact Hausdorff space we can assign the ring of (classes of) vector bundles under the operations of direct sum and tensor product. This assignment allows the construction of an extraordinary cohomology theory for which the long exact sequence of a pair is 6-periodic.

Although production is an integral part of the Arrow-Debreu market model, most of the work in theoretical computer science has so far concentrated on markets without production, i.e., the exchange economy. In this work, we take a significant step towards understanding computational aspects of markets with production. We first define the notion of separable, piecewise-linear concave (SPLC) production by analogy with SPLC utility functions. We then obtain a linear complementarity problem (LCP) formulation that captures exactly the set of equilibria for Arrow-Debreu markets with SPLC utilities and SPLC production, and we give a complementary pivot algorithm for finding an equilibrium. This settles a question asked by Eaves in 1975. Since this is a path-following algorithm, we obtain a proof of membership of this problem in PPAD, using Todd, 1976. We also obtain an elementary proof of existence of equilibrium (i.e., without using a fixed point theorem), rationality, and oddness of the number of equilibria. Experiments show that our algorithm runs fast on randomly chosen examples, and unlike previous approaches, it does not suffer from issues of numerical instability. Additionally, it is strongly polynomial when the number of goods or the number of agents and firms is constant. This extends the result of Devanur and Kannan (2008) to markets with production. Based on a joint work with Vijay V. Vazirani.