Georgia Institute of Technology College of Sciences

A 1986 article with this title, written by M. Zuker and published by the AMS, outlined several major challenges in the area. Stating the folding problem is simple; given an RNA sequence, predict the set of (canonical, nested) base pairs found in the native structure. Yet, despite significant advances over the past 25 years, it remains largely unsolved. A fundamental problem identified by Zuker was, and still is, the "ill-conditioning" of discrete optimization solution approaches. We revisit some of the questions this raises, and present recent advances in considering multiple (sub)optimal structures, in incorporating auxiliary experimental data into the optimization, and in understanding alternative models of RNA folding.

Algorithms and Randomness Center (ARC) Theory Day is an annual event that features hour-long lectures focusing on recent innovative results in theoretical computer science, spanning a wide array of topics several of which are inspired by practical problems. See the complete list of titles and times of talks.

A classical result of Aubry and Mather states that Hamiltonian twist maps have orbits of all rotation numbers. Analogously, one can show that certain ferromagnetic crystal models admit ground states of every possible mean lattice spacing. In this talk, I will show that these ground states generically form Cantor sets, if their mean lattice spacing is an irrational number that is easy to approximate by rational numbers. This is joint work with Blaz Mramor.

Pricing and allocating goods to buyers with complex preferences in order to maximize some desired objective (e.g., social welfare or profit) is a central problem in Algorithmic Mechanism Design. In this talk I will discuss some particularly simple algorithms that are able to achieve surprisingly strong guarantees for a range of problems of this type. As one example, for the problem of pricing resources, modeled as goods having an increasing marginal extraction cost to the seller, a simple approach of pricing the i-th unit of each good at a value equal to the anticipated extraction cost of the 2i-th unit gives a constant-factor approximation to social welfare for a wide range of cost curves and for arbitrary buyer valuation functions. I will also discuss simple algorithms with good approximation guarantees for revenue, as well as settings having an opposite character to resources, namely having economies of scale or decreasing marginal costs to the seller.