Seminar

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

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)

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.

Previous Seminars:

October 14, 2016
JM Landsberg, James B. Wilson
September 30, 2016
Alexander Hulpke, Oscar Levin
September 16, 2016
Delaram Kahrobaei, Amit Patel
June 23, 2016
April 29, 2016
Nick Loehr, Jason Williford
April 15, 2016
Alexander Hulpke, Klaus Lux
April 1, 2016
Eamonn O'Brien, Izabella Stuhl
February 19, 2015
James Wilson, Anton Betten
December 4, 2015
Maria Monks Gillespie, Dane Flannery
November 13, 2015
Richard Green, Tim Penttila
October 23, 2015
Christina Boucher, Sylvia Hobart
October 9, 2015
Josh Maglione, Ghodratollah Aalipour
September 25, 2015
September 11, 2015
James B. Wilson, Tim Penttila
May 8, 2015
Amanda Schaeffer Fry, Peter Brooksbank
April 24, 2015
March 6, 2015
Felice Manganiello, Eric Moorhouse
February 20, 2015
Anton Dzhamay, Anton Betten
February 6, 2015
Alexander Hulpke, Morgan Rodgers
December 5, 2014
Stefaan De Winter, Gretchen Matthews
November 14, 2014
Greg Coxson, Tom Dorsey
October 31, 2014
Octavio Paez Osuna, Sylvia Hobart
October 10, 2014
Takunari Miyazaki, Eric Moorhouse
September 26, 2014
Elissa Ross, Anton Betten
September 12, 2014
Petr Vojtěchovský, Alexander Hulpke
May 9, 2014
Philip DeOrsey, Tim Penttila
April 25, 2014
William J Martin, Jason Williford
April 11, 2014
Victor Pambuccian, George Shakan
March 7, 2014
Nathan Lindzey, Jens Harlander
February 21, 2014
Ross McConnell, Anton Betten
November 22, 2013
Justin Hughes, Josh Maglione

Department of Mathematics