|
|||||
[PDF]
- TANYA BERGER-WOLF, U. Illinois at Chicago
Dynamic Networks in Behavioral Ecology: Baboons and Zebras as Mobile Social Users. [PDF]
-
From gene interactions and brain activity to cellphone calls and zebras grazing together, large, noisy, and highly dynamic networks of interactions are everywhere. My application domain of choice, ecology, being the science of connections among living organisms and their environment, among different biological scales, from organisms to the planet, is particularly well positioned to take advantage of the network paradigm. Unfortunately, in this domain as in many others, our ability to analyze data lags substantially behind our ability to collect it.
In this talk I will show how some of the big questions in animal ecology can be answered using network analysis. I will show how abstract questions about dynamic interaction networks -- what is a representative sample? is there an inherent time scale? what are the most parsimonious, significant, and meaningful patterns? -- can be formulated as combinatorial or graph optimization problems and used to gain insight into and suggest hypotheses about individual and collective behavior of zebras, baboons, humans, and other animals.
- PETER KEEVASH, Oxford
Hypergraph matchings [PDF]
-
Matching theory is a large field with many directions of research, both in practical algorithms and combinatorial theory. I will aim to show some of the breadth of the subject, and survey some recent advances in techniques for hypergraphs, such as a geometric theory of matchings in dense hypergraphs (joint work with Richard Mycroft), and the existence of designs (by my method of Randomised Algebraic Constructions and by the Iterative Absorption method as recently applied by Glock, Kuhn, Lo and Osthus).
- ROBERT KLEINBERG, Cornell
Recharging Bandits [PDF]
-
Experimenting with different alternatives and learning from experience are quintessentially human behaviors that, until recently, were largely missing from the realm of computing. Online systems that self-improve by sequential experimentation are now becoming increasingly common. The theoretical foundation for studying such systems is furnished by the so-called multi-armed bandit problem, first formulated by statisticians in the middle of the 20th century.
Traditional multi-armed bandit models posit that the payoff distribution of each action (or "arm") is stationary over time, and hence that the goal of learning is to identify the arm with the highest expected payoff and choose that one forever after. However, in many applications the efficacy of an action depends on the amount of time that has elapsed since it was last performed. Examples arise in regulatory enforcement, online education, and music recommendations. In this talk we introduce a generalization of the multi-armed bandit problem that models such applications. In the course of analyzing algorithms for this problem, we will encounter some interesting questions about coloring the integers subject to constraints on the sizes of gaps between consecutive elements in a given color class.
This talk is based on joint work with Nicole Immorlica.
- BOJAN MOHAR, Simon Fraser
Totally odd immersions of graphs [PDF]
-
Graph immersions are a close relative to graph minors. It has been proved rather recently that graphs in which a fixed graph K cannot be immersed are sparse and their rough structure can be described by using small edge-cuts. The corresponding problem of totally odd immersions will be discussed in the talk.
- SHUBHANGI SARAF, Rutgers
High rate locally-correctable and locally-testable codes [PDF]
-
We study local algorithms for error correcting codes in the high rate regime. The tradeoff between the rate of a code and the locality/efficiency of its decoding and testing algorithms has been studied extensively in the past decade, with numerous applications to theoretical computer science.
In this talk I will discuss some recent results giving efficient sub-polynomial query decoding and testing algorithms for high rate error correcting codes. I will also highlight some of the most interesting challenges that remain.
Based on joint work with Swastik Kopparty, Or Meir and Noga Ron-Zewi
- ANDREW SUK, U Illinois at Chicago
On the Erdos-Szekeres convex polygon problem [PDF]
-
The classic 1935 paper of Erdos and Szekeres entitled "A combinatorial problem in geometry" was a starting point of a very rich discipline within combinatorics: Ramsey theory. In that paper, Erdos and Szekeres studied the following geometric problem. For every integer $n \geq 3$, determine the smallest integer $ES(n)$ such that any set of $ES(n)$ points in the plane in general position contains $n$ members in convex position, that is, $n$ points that form the vertex set of a convex polygon. Their main result showed that $ES(n) \leq {2n - 4\choose n-2} + 1 = 4^{n -o(n)}$. In 1960, they showed that $ES(n) \geq 2^{n-2} + 1$ and conjectured this to be optimal. In this talk, we will sketch a proof showing that $ES(n) =2^{n +o(n)}$.
- LAUREN WILLIAMS, Berkeley
Tableaux combinatorics of hopping particles and Koornwinder polynomials [PDF]
-
The asymmetric simple exclusion process (ASEP) is a Markov
chain describing particles hopping on a 1-dimensional finite lattice.
Particles can enter and exit the lattice at the left and right
boundaries, and particles can hop left and right in the lattice, subject
to the condition that there is at most one particle per site. The
ASEP has been cited as a model for traffic flow, protein synthesis, the
nuclear pore complex, etc. In my talk I will discuss joint work with
Corteel and with Corteel-Mandelshtam, in which we describe the
stationary distribution of the ASEP and the 2-species ASEP using
staircase tableaux and rhombic tilings. We also link
these models to Askey Wilson polynomials and
Macdonald-Koornwinder polynomials, which allows us to give
combinatorial formulas for their moments.
- JULIA WOLF, Bristol
Counting monochromatic structures in finite abelian groups [PDF]
-
It is well known (and a result of Goodman) that a random 2-colouring of the edges of the complete graph $K_n$ contains asymptotically the minimum number of monochromatic triangles ($K_3$s). Erdős conjectured that this was also true of monochromatic copies of $K_4$, but his conjecture was disproved by Thomason in 1989. The question of determining for which small graphs Goodman's result holds true remains wide open. In this talk we explore an arithmetic analogue of this question: what can be said about the number of monochromatic additive configurations in 2-colourings of finite abelian groups?
