Mathematics
Seminar
|
|
|
Rocky Mountain Algebraic Combinatorics Seminar
Graph Traversal Edit Distance
Hamidreza Chitsaz
Colorado State University (CS)
Many problems in applied machine learning deal with graphs (also called
networks), including social networks, security, web data mining, protein
function prediction, and genome informatics. The kernel paradigm beautifully
decouples the learning algorithm from the underlying geometric space, which
renders graph kernels important for the aforementioned applications.
In this talk, we give a new graph kernel which we call graph traversal edit
distance (GTED). We introduce the GTED problem and give the first polynomial
time algorithm for it. Informally, the graph traversal edit distance is the
minimum edit distance between two strings formed by the edge labels of
respective Eulerian traversals of the two graphs. Also, GTED is motivated
by and provides the first mathematical formalism for sequence co-assembly
and de novo variation detection in bioinformatics.
We demonstrate that GTED admits a polynomial time algorithm using a linear
program (LP) in the graph product space. We prove the LP is unimodular;
hence, it is guaranteed to yield an integer solution. Our proof is based on
the homology of graph product spaces. In particular, we show that the
homology groups of graph product spaces are torsion free. A result of
Dey-Hirani-Krishnamoorthy then gives the result.
Semi-extraspecial Groups
Mark Lewis
Kent State University
Extraspecial groups play an important role in group theory. Particularly in
problems involving character degrees. We will show how how extraspecial
groups can be generalized to semi-extraspecial groups. We will present some
of the the basic results regarding semi-extraspecial groups. Then we focus
on semi-extraspecial groups that have an abelian subgroup of maximal
possible order and consider a connection with semifields.
Weber 223
4–6 pm
Friday, February 16, 2018
(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.
PDF version
Previous Seminars:
- February 2, 2018
- James B. Wilson,
Anton Betten
- November 10, 2017
- Michael Kinyon,
Petr Vojt\v{e}chovsk\'y
- October 20, 2017
- Eric Moorhouse,
William DeMeo
- October 6, 2017
- Spencer Gerhardt,
Joshua Grochow
- September 22, 2017
- Amanda Schaeffer Fry,
Henry Kvinge
- September 8, 2017
- Peter Mayr,
James B. Wilson
- May 5, 2017
- Ferdinand Ihringer,
Gavin King
- April 21, 2017
- Vladimir D. Tonchev,
Morgan Rodgers
- April 7, 2017
- Jason Williford,
Anton Betten
- March 24, 2017
- Isabella Novik,
Peter Brooksbank
- March 3, 2017
- Jintai Ding,
Curtis Bennett
- February 17, 2017
- Fatma Karaoglu,
Eric Moorhouse
- February 3, 2017
- Tim Penttila,
James B. Wilson
- December 2, 2016
- Jim Fowler,
Andrew Kelley
- November 11, 2016
- Joseph Gersch,
Joshua Maglione
- October 28, 2016
- John MacLaren Walsh,
Henry Adams
- 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
- Jason Cantarella,
Michal Adamaszek
- 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
- Ross McConnell,
Henry Adams
- September 11, 2015
- James B. Wilson,
Tim Penttila
- May 8, 2015
- Amanda Schaeffer Fry,
Peter Brooksbank
- April 24, 2015
- Heide Gluesing-Luerssen,
Phil DeOrsey
- 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
Fort Collins, Colorado 80523
|