Applied Math Colloquium

Abstract: Constraint satisfaction problems (CSPs in short) are among the most important computational problems studied in Theoretical Computer Science. This talk will focus on a recent line of study addressing the complexity of approximating satisfiable instances of CSPs, and connections of this study to multi-player parallel repetition theorems, property testing and combinatorics.

Based mostly on joint works with Amey Bhangale, Subhash Khot and Yang P. Liu.

Abstract: Pentamode materials are a class of materials that are useful for guiding stress. In particular, they have been proposed for acoustic cloaking by guiding stress around objects and have been physically constructed. A key feature of pentamode materials is that each vertex in the material is the junction of 4 double cone elements. Thus, the tension in one element determines the tension in the other elements, and by extension uniquely determines the stress in the entire metamaterial. Here we show how this key feature can be extended to discrete wire networks, supporting forces at the terminal nodes and which may have internal nodes where no forces are applied. In usual wire or cable networks, such as in a bridge or bicycle wheel, one distributes the forces by adjusting the tension in the wires. Here our discrete networks provide an alternative way of distributing the forces through the geometry of the network. In particular the network can be chosen so it is uniloadable, i.e. supports only one set of forces at the terminal nodes. Such uniloadable networks provide the natural generalization of pentamode materials to discrete networks. We extend such a problem to compression-only 'strut nets' subjected to fixed and reactive nodal loads. These systems provide discrete element models of masonry bodies. In particular, we solve the arch problem where one wants the strut net to avoid a given set of obstacles and also allow some of the forces to be reactive ones. This is joint work with Ada Amendola, Guy Bouchitte, Andrej Cherkaev, Antonio Fortunato, Fernando Fraternali, Ornella Mattei, and Pierre Seppecher.