Georgia Institute of Technology College of Sciences

Given a graph H, the Turan graph problem asks to find the maximum number of edges in a n-vertex graph that does not contain any subgraph isomorphic to H. In recent years, Razborov's flag algebra methods have been applied to Turan hypergraph problems with great success. We show that these techniques embed naturally in standard symmetry-reduction methods for sum of squares representations of invariant polynomials. This connection gives an alternate computational framework for Turan problems with the potential to go further. Our results expose the rich combinatorics coming from the representation theory of the symmetric group present in flag algebra methods. This is joint work with James Saunderson, Mohit Singh and Rekha Thomas.

Recent breakthroughs in condensed matter physics are opening new directions in band engineering and wave manipulation. Specifically, challenging the notions of reciprocity, time-reversal symmetry and sensitivity to defects in wave propagation may disrupt ways in which mechanical and acoustic metamaterials are designed and employed, and may enable totally new functionalities. Non-reciprocity and topologically protected wave propagation will have profound implications on how stimuli and information are transmitted within materials, or how energy can be guided and steered so that its effects may be controlled or mitigated. The seminar will briefly introduce the state-of-the-art in this emerging field, and will present initial investigations on concepts exploiting electro-mechanical coupling and chiral and non-local interactions in mechanical lattices. Shunted piezo-electric patches are exploited to achieve time-modulated mechanical properties which lead to one-directional wave propagation in one-dimensional mechanical waveguides. A framework to realize helical edge states in two identical lattices with interlayer coupling is also presented. The methodology systematically leads to mechanical lattices that exhibit one-way, edge-bound, defect-immune, non-reciprocal wave motion. The presented concepts find potential application in vibration reduction, noise control or stress wave mitigation systems, and as part of surface acoustic wave devices capable of isolator, gyrator and circulator-like functions on compact acoustic platforms.

We examine a variant of the knapsack problem in which item sizes are random according to an arbitrary but known distribution. In each iteration, an item size is realized once the decision maker chooses and attempts to insert an item. With the aim of maximizing the expected profit, the process ends when either all items are successfully inserted or a failed insertion occurs. We investigate the strength of a particular dynamic programming based LP bound by examining its gap with the optimal adaptive policy. Our new relaxation is based on a quadratic value function approximation which introduces the notion of diminishing returns by encoding interactions between remaining items. We compare the bound to previous bounds in literature, including the best known pseudopolynomial bound, and contrast their corresponding policies with two natural greedy policies. Our main conclusion is that the quadratic bound is theoretically more efficient than the pseudopolyomial bound yet empirically comparable to it in both value and running time.