Resume

• 2002

  Doctor of Philosophy - PhD

  Algorithms

  Combinatorics

  and Optimization

  Georgia Institute of Technology

• William T. Trotter

  Mitchel T. Keller

  Csaba Biro

  We resolve a conjecture of Herzog

  Vladiou

  and Zheng and prove that the Stanley depth of the maximal ideal over 2k-1 or 2k indeterminates is k. The proof uses a novel partition of the subset lattice and has become to the basis for several results in the combinatorial calculation of Stanley depth.

  Interval partitions and Stanley Depth

  Katie Nowak

  Similarity measures are used extensively in machine learning and data science algorithms. The newly proposed graph Relative Hausdorff (RH) distance is a lightweight yet nuanced similarity measure for quantifying the closeness of two graphs. In this work we study the effectiveness of RH distance as a tool for detecting anomalies in time-evolving graph sequences. We apply RH to cyber data with given red team events

  as well to synthetically generated sequences of graphs with planted attacks. In our experiments

  the performance of RH distance is at times comparable

  and sometimes superior

  to graph edit distance in detecting anomalous phenomena. Our results suggest that in appropriate contexts

  RH distance has advantages over more computationally intensive similarity measures.

  Relative Hausdorff distance for network analysis

  Noah Streib

  Yi-Huang Shen

  Mitchel T. Keller

  We build on the constructions of the previous paper

  calculating the Stanley depth of the degree d squarefree Veronese ideals on n indeterminates when d ≤ n ≤ 5d+4.

  On the Stanley depth of squarefree Veronese ideals

  Graeme Kemkes

  Jozsef Balogh

  Choongbum Lee

  We considered the question of how large the weighted minimum degree of a complete graph must be to ensure that there was a partition of the graph into sets of size r such that every set contains at has weight at least t. We provide an upper and lower bound for this quantity. The linked version is an expanded version of the journal article.

  Towards a weighted version of the Hajnal-Szemeredi Theorem

  Fan Chung

  Braess's paradox is supposedly rare phenomenon by which removing links from a network can improve the overall selfish routing time for the entire network. Extending the results of Valiant and Roughgarden

  we show Braess's paradox occurs with high probability in connected Erdos-Renyi random graphs with random linear latency functions.

  Braess' Paradox in Large Sparse Graphs

  Katie Nowak

  Graph similarity metrics serve far-ranging purposes across many domains in data science. As graph datasets grow in size

  scientists need comparative tools that capture meaningful differences

  yet are lightweight and scalable. Graph Relative Hausdorff (RH) distance is a promising

  recently proposed measure for quantifying degree distribution similarity. In spite of recent interest in RH distance

  little is known about its properties. Here

  we conduct an algorithmic and analytic study of RH distance. In particular

  we provide the first linear-time algorithm for computing RH distance

  analyze examples of RH distance between families of graphs

  and prove several analytic results concerning the range

  density

  and extremal behavior of RH distance values.\n\n

  A linear-time algorithm and analysis of graph relative hausdorff distance.

  Henry Huang

  Mallik Vallem

  Mahantesh Halappanavar

  Research communities

  vendors

  and utilities need access to realistic power system models

  however

  there are confidentiality concerns that prevent their access to real world data. Similar concerns apply to the exchange of power system models between different organizations. This DOE-sponsored work is part of a broader effort to address these issues by creating tools for automatic generation of realistic publicly available power system models. In particular

  this work presents a novel methodology for rapidly generating synthetic AC OPF power system models based on real-world topologies

  power system parameters

  \"realism\" metrics

  and the desired complexity of the synthetic models. Our technique relies on recent insights into the topological statistics of real-world power systems. \n\nSelected as Prize Conference Paper

  Synthetic power grids from real world models

  Edward R. Scheinerman

  This is an expanded version of the WAW 2007 paper. We additionally consider a spherical directed random dot product graphs

  where the in- and out-vectors are scaled version of the same vector.

  Directed Random Dot Product Graphs

  Wenbo Zhao

  Fan Chung

  Extending the work which appeared in WINE 2010

  we show that the paradox occurs in sufficiently good expanders where the latency functions are random convex functions.

  Braess's Paradox in Expanders

  Mitchel T. Keller

  We prove a Brooks-type theorem for the linear discrepancy interval orders

  showing that if every interval intersects at most Δ other intervals

  then the linear discrepancy is at most Δ

  with equality if and only if the interval order contains a antichain of size Δ+1.

  Degree bounds for Linear Discrepancy of Interval Orders and Disconnected Posets

  Noah Streib

  Joel Sokol

  Every year approximately 1200 amateur baseball players are drafted in the Major League Baseball Draft. In order to determine which players to draft a major league team relies primarily on in-person scouting by their scouting department

  however

  because of cost constraints most scouts see only a small fraction of the players likely to be drafted. We helped a MLB team develop a tool to assist in aggregating the individual scouts evaluations to a consensus ordering of players.

  A Major League Baseball Team Uses Operations Research to Improve Draft Preparation

  Mitchel T. Keller

  Csaba Biro

  Joret

  Micek

  Milans

  Trotter

  Walczak

  and Wang recently asked if there is a bound on the dimension of a poset whose cover graph has pathwidth at most two. We answer this question in the affirmative. We also show that any planar embedding of a large standard example has treewidth at least 3.

  Posets with cover graph of pathdwidth two have bounded dimeanion

  Yanhua Tian

  Paweł Prałat

  Dieter Mitsche

  Myunghwan Kim

  David F. Gleich

  Anthony Bonato

  The log-dimension hypothesis conjectures that social networks exist in some underlying

  but hidden

  geometric space that grows logarithmically with the size of the network. Using parameters derived from snapshots of the Facebook and LinkedIn networks

  we use simulate a modification of the Geometric Protean Graphs with a variety of dimension parameters. The analysis of this simulation data provides some evidence for the log-dimension hypothesis.

  Dimensionality of social networks using motifs and eigenvalues

  Mitchel T. Keller

  We develop combinatorial tools to study the relationship between the Stanley depth of a monomial ideal I and the Stanley depth of its compliment

  S/I. Using these results we are able to prove that if S is a polynomial ring with at most 5 indeterminates and I is a square-free monomial ideal

  then the Stanley depth of S/I is strictly larger than the Stanley depth of I. Using a computer search

  we are able to extend this strict inequality up to polynomial rings with at most 7 indeterminates. This partially answers questions asked by Propescu and Qureshi as well as Herzog.

  Combinatorial reductions for the Stanley depth of I and S/I

  Kristina Lerman

  Jacob Hunter

  Nathan O. Hodas

  Model of cognitive dynamics predicts performance on standardized tests

  Henry Huang

  Mallik Vallem

  Mahantesh Halappanavar

  In this work we provide novel tools to evaluate the \"realism\" of a power system topology based combining ideas from the study of complex networks with electrical system parameters. Specifically

  we show that the recent network-of-networks approach of Halappanavar

  et al. can be used to gain insight into reasonable ranges for topological properties of a power system such as

  diameter

  average shortest path length

  core size

  and clustering.

  Topological power grid statistics from a network-of-networks perspective

  Stochastic Kronecker graphs are a recent model for complex networks such as the internet where each edge is independent

  but the probability of occurence is based on the Kronecker product of a fixed matrix. Mulitplicative attribute graphs are the natural generalization of the stochastic Kronecker graphs formed by allowing duplication of vertices before randomly generating the edges. Using properties of the Kronecker product and matrix spectrum concetentration techniques we provide asymptotic control of the spectrum of the adjacency matrix and normalized Laplacian for both graph models.

  The spectra of multiplicative attribute graphs

  A weak extension of a poset is a order preserving injection onto the natural numbers and thus the weak discrepancy of a poset is the least k such that there is a weak extension where incomparable elements are mapped to numbers of distance at most k. We show that determining whether the weak and linear discrepancy are equal is NP-complete and provide a complete characterization of when the weak and linear discrepancy are equal.

  When Linear and Weak Discrepancy are Equal

  Using the correspondence between Stanley depth and poset partition discovered by Herzog

  Vladiou

  and Zheng we show that the Stanley depth of a monomial ideal in n indeterminates with 2k or 2k+1 generators is at least n-m.

  Stanley depth of square-free monomial ideals

  Stochastic Kronecker graphs are a recent model for complex networks such as the internet where each edge is independent

  but the probability of occurence is based on the Kronecker product of a fixed matrix. We use a novel understanding of the adjancency structure of stochastic Kronecker graphs to completely characterize the emmergence of giant component and connectivity in terms of generating matrix.

  Connectivity and giant component of stochastic Kronecker graphs

  Young

  University of Louisville

  Pacific Northwest National Laboratory - PNNL

  Richland/Kennewick/Pasco

  Washington Area

  Senior Research Mathematician

  Pacific Northwest National Laboratory - PNNL

  University of Louisville