MathematicsSeminar |
|
Rocky Mountain Algebraic Combinatorics Seminar
A Computationally Enabled Theory of Network Coding
John MacLaren Walsh
Drexel University
The optimal design of critical engineering systems employing coding to aid the efficient caching of content, multimedia streaming, making the best use of a network of communication links, and deploy error-resilient massive distributed data storage systems, have all been shown to be variants of determining the capacity region of an associated abstracted network under network coding. This talk details a computationally enabled theory of network coding capacity regions. First we describe algorithms capable of computing outer bounds to the network coding capacity region via symmetry exploiting polyhedral projection. Next, we describe algorithms capable of generating inner bounds matched to these outer bounds, and codes that achieve them, as variants of a class of isomorph-free generation algorithms. Put together, these algorithms enable non-trivial capacity regions for small networks, and their proofs, to be generated rapidly with a computer. Harnessing a notion of problem minimality and symmetry to list all network coding problems up to a certain size, a massive database of solved network coding capacity regions is then generated by rapidly solving each of these problems with the inner and outer bound algorithms. In order to learn information about networks at scale from this massive database of small problems, a new theory, inspired by the notion of forbidden minors for families of graphs and matroids, is then devised by developing hierarchy between different network coding problem instances.
Cyclic polytopes and Cech complexes
Henry Adams
CSU
This talk will begin with an introduction to cyclic polytopes, which play an important role in polyhedral combinatorics. A cyclic polytope is a convex hull of points on a moment curve. The upper bound theorem by Peter McMullen and Richard Stanley states that among all simplicial spheres with the same number of vertices, the boundary of a cyclic polytope maximizes the number of faces. I will end by explaining how cyclic polytopes relate to Cech complexes, a geometric construction used in applied and computational topology.
Weber 223
4–6 pm
Friday, October 28, 2016
(Refreshments in Weber 117, 3:30–4 pm)
Colorado State University
This is a joint Denver U / UC Boulder / UC Denver / U of Wyoming / CSU seminar that meets biweekly. Anyone interested is welcome to join us at a local restaurant for dinner after the talks.
