Fall 2014 Calendar

Octo­ber 14
Annie Ray­mond, Depart­ment of Math­e­mat­ics, UW.
A New Con­jec­ture for Union-Closed Families

Octo­ber 28
Jonathan Hauen­stein, Depart­ment of Applied and Com­pu­ta­tional Math­e­mat­ics and Sta­tis­tics, Uni­ver­sity of Notre Dame.
Opti­miza­tion and Numer­i­cal Alge­braic Geometry

Novem­ber 18
Daniela Wit­ten, Depart­ment of Bio­sta­tis­tics, UW.

Novem­ber 20 (Thurs­day)
Henry Wolkow­icz, Depart­ment of Math­e­mat­ics, Uni­ver­sity of Water­loo.

Novem­ber 25
Emily Fox, Depart­ment of Sta­tis­tics, UW.

Decem­ber 2 [COREEEB125]
Peter Bür­gisser, Insti­tute for Math­e­mat­ics, TU Berlin.

Jan­u­ary 13 [CORE]
James Rene­gar, School of Oper­a­tions Research and Infor­ma­tion Engi­neer­ing, Cor­nell.

April 28 [CORE]
Joel Tropp, Depart­ment of Com­put­ing and Math­e­mat­i­cal Sci­ences, Cal­tech.

Click on the title or see below for the abstracts.

Annie Ray­mond; A New Conjecture for Union-Closed Families

Octo­ber 14, 2014, 4:00pm
GUG 204
Annie Ray­mond, Depart­ment of Math­e­mat­ics, Uni­ver­sity of Wash­ing­ton.
A New Con­jec­ture for Union-Closed Families

Abstract: The Frankl union-closed sets con­jec­ture states that there exists an ele­ment present in at least half of the sets form­ing a union-closed fam­ily. We refor­mu­late the con­jec­ture as an opti­miza­tion prob­lem and present an inte­ger pro­gram to model it. The com­pu­ta­tions done with this pro­gram lead to a new con­jec­ture: we claim that the max­i­mum num­ber of sets in a non-empty union-closed fam­ily in which each ele­ment is present at most a times is inde­pen­dent of the num­ber n of ele­ments spanned by the sets if n is greater or equal to log_2(a)+1. We prove that this is true when n is greater or equal to a. We also dis­cuss the impact that this new con­jec­ture would have on the Frankl con­jec­ture if it turns out to be true. This is joint work with Jonad Pulaj and Dirk Theis.

Elina Robeva; Fixed Points of the EM Algorithm and Nonnegative Rank Boundaries

May 27, 2014, 4:00pm
EEB 303
Elina Robeva, Depart­ment of Math­e­mat­ics, UC Berke­ley.
Fixed Points of the EM Algo­rithm and Non­neg­a­tive Rank Boundaries

Abstract: Matri­ces of non­neg­a­tive rank $r$ rep­re­sent mix­tures of $r$ inde­pen­dent dis­tri­b­u­tions for two ran­dom vari­ables. Like­li­hood infer­ence for this model leads to prob­lems in real alge­braic geom­e­try that we address in this paper. We char­ac­ter­ize the set of fixed points of Expec­ta­tion Max­i­miza­tion, and we study the bound­ary of the space of matri­ces with non­neg­a­tive rank at most $3$. Both of these cor­re­spond to alge­braic vari­eties with many irre­ducible components.

Michael Joswig; Long and Winding Central Paths

May 23, 2014, 3:30pm
LOW 112
Michael Joswig, Insti­tute of Math­e­mat­ics, TU Berlin.
Long and Wind­ing Cen­tral Paths

Abstract: We dis­prove a con­tin­u­ous ana­log of the Hirsch con­jec­ture pro­posed by Deza, Ter­laky and Zinchenko, by con­struct­ing a fam­ily of lin­ear pro­grams with $3r+4$ inequal­i­ties in dimen­sion $2r+2$ where the cen­tral path has a total cur­va­ture in $\Omega(2^r/r)$. Our method is to trop­i­cal­ize the cen­tral path in lin­ear pro­gram­ming. The trop­i­cal cen­tral path is the piecewise-linear limit of the cen­tral paths of para­me­ter­ized fam­i­lies of clas­si­cal lin­ear pro­grams viewed through log­a­rith­mic glasses. We show in par­tic­u­lar that the trop­i­cal ana­logue of the ana­lytic cen­ter is noth­ing but the trop­i­cal barycen­ter, that is, the max­i­mum of a trop­i­cal poly­he­dron. It fol­lows that unlike in the clas­si­cal case, the trop­i­cal cen­tral path may lie on the bound­ary of the trop­i­cal­iza­tion of the fea­si­ble set, and may even coin­cide with a path of the trop­i­cal sim­plex method. Finally, our counter-example is obtained as a defor­ma­tion of a fam­ily of trop­i­cal lin­ear pro­grams intro­duced by Bezem, Nieuwen­huis and Rodr\‘iguez-Carbonell.

This is joint work with Xavier Allami­geon, Pas­cal Benchi­mol and St\‘ephane Gaubert.

Noah Simon; Flexible Sparse Modeling

May 13, 2014, 4:00pm
EEB 303
Noah Simon, Depart­ment of Bio­sta­tis­tics, Uni­ver­sity of Wash­ing­ton.
Flex­i­ble Sparse Modeling

Abstract: Our abil­ity to col­lect data has exploded over recent years. Across sci­ence and busi­ness, we now col­lect thou­sands to mil­lions of mea­sure­ments on each per­son. It is often of inter­est to use these mea­sure­ments to pre­dict some response (eg. like­li­hood of get­ting a dis­ease, or prob­a­bil­ity of click­ing a link). Meth­ods for this prob­lem must bal­ance 3 objec­tives: they must be pre­dic­tive, they must be com­pu­ta­tion­ally tractable, and, in many appli­ca­tions, they must be inter­pretable. Many machine learn­ing meth­ods are highly suc­cess­ful at the first two, but are black boxes. In con­trast, the Lasso (l1 penal­ized regres­sion) is inter­pretable and com­pu­ta­tion­ally tractable, but assumes lin­ear­ity which lim­its its pre­dic­tive accuracy.

In this talk we will dis­cuss a class of sparse addi­tive mod­els induced by com­bin­ing spar­sity and struc­tural penal­ties. These are more flex­i­ble than the stan­dard lin­ear penal­ized model, but main­tain its inter­pretabil­ity and com­pu­ta­tional tractabil­ity. We will show when these penal­ties can and can­not be com­bined to induce the desired struc­ture and spar­sity. We will give an effi­cient algo­rithm for fit­ting a wide class of these mod­els. And we will show that some of these mod­els have desir­able the­o­ret­i­cal properties.

This is joint work with Ash­ley Petersen and Daniela Wit­ten (UW).

Dan Spielman; Spectral Sparsification of Graphs

May 8th, 2014, 3:30pm
EEB 105
Dan Spiel­man, Depart­ment of Com­puter Sci­ence, Yale.
Spec­tral Spar­si­fi­ca­tion of Graphs

Abstract: We intro­duce a notion of what it means for one graph to be a good spec­tral approx­i­ma­tion of another, and prove that every graph can be well-approximated by a graph with few edges.

We ask how well a given graph can be approx­i­mated by a sparse graph. Expander graphs can be viewed as sparse approx­i­ma­tions of com­plete graphs, with Ramanu­jan expanders pro­vid­ing the best pos­si­ble approx­i­ma­tions. We prove that every graph can be approx­i­mated by a sparse graph almost as well as the com­plete graphs are approx­i­mated by the Ramanu­jan expanders: our approx­i­ma­tions employ at most twice as many edges to achieve the same approx­i­ma­tion factor.

We also present an effi­cient ran­dom­ized algo­rithm for con­struct­ing sparse approx­i­ma­tions that only uses a log­a­rith­mic fac­tor more edges than optimal.

Our algo­rithms fol­low from the solu­tion of a prob­lem in lin­ear alge­bra. Given any expres­sion of a rank-n sym­met­ric matrix A as a sum of rank-1 sym­met­ric matri­ces, we show that A can be well approx­i­mated by a weighted sum of only O(n) of those rank-1 matrices.

This is joint work with Joshua Bat­son, Nikhil Sri­vas­tava and Shang-Hua Teng.

Bios­ketch: Daniel Alan Spiel­man received his B.A. in Math­e­mat­ics and Com­puter Sci­ence from Yale in 1992, and his Ph.D in Applied Math­e­mat­ics from M.I.T. in 1995. He spent a year as a NSF Math­e­mat­i­cal Sci­ences Post­doc in the Com­puter Sci­ence Depart­ment at U.C. Berke­ley, and then taught in the Applied Math­e­mat­ics Depart­ment at M.I.T. until 2005. Since 2006, he has been a Pro­fes­sor at Yale Uni­ver­sity. He is presently the Henry Ford II Pro­fes­sor of Com­puter Sci­ence, Math­e­mat­ics, and Applied Mathematics.

He has received many awards, includ­ing the 1995 ACM Doc­toral Dis­ser­ta­tion Award, the 2002 IEEE Infor­ma­tion The­ory Paper Award, the 2008 Godel Prize, the 2009 Fulk­er­son Prize, the 2010 Nevan­linna Prize, an inau­gural Simons Inves­ti­ga­tor Award, and a MacArthur Fel­low­ship. He is a Fel­low of the Asso­ci­a­tion for Com­put­ing Machin­ery and a mem­ber of the Con­necti­cut Acad­emy of Sci­ence and Engi­neer­ing. His main research inter­ests include the design and analy­sis of algo­rithms, graph the­ory, machine learn­ing, error-correcting codes and com­bi­na­to­r­ial sci­en­tific computing.