ISU Mathematics, Electrical and computer engineering, Computer Science, Statistics (MECS) Interdisciplinary Seminar  

2013-2014

Time: Mondays 11:00 AM
      Place: 401 Carver (or listed room)


The goals of this colloquium and seminar series include: stimulating interdisciplinary research collaborations among the departments of Computer Science, Electrical and Computer Engineering, Mathematics, Statistics, and other interested departments; raising awareness of research going on in these departments, particularly highlighting interdisciplinary research that may be of interest to the other participating departments; hosting outside speakers who appeal to a broad audience.

Speakers will include both ISU faculty and outside speakers.  An ISU faculty member will normally give talks in two successive weeks.  The first is intended as a colloquium for a general audience, including an overview of problems s/he works on, and possible areas of expertise s/he can offer to others or is seeking in collaborators.  The second is a research seminar. 

If you have questions or to volunteer to speak in the seminar, please contact a member of the organizing committee.

Spring 2014 Seminars

Date  

     Speaker

Title 

Feb. 17
Ryan Martin in 223 Atanasoff Vertex Identifying Codes in Graphs
Feb. 24
Ryan Martin in 401 Carver Path Separation Number in Graphs
March 3
Tim McNicholl
Computability and complexity in discrete and continuous settings
March 10
Tim McNicholl Computable and incomputable boundary extensions of conformal maps
April 7
Leslie Hogben The maximum nullity of a complete subdivision graph is equal to its zero forcing number


Fall 2013 Seminars

Date  

     Speaker

Title 

Sept. 9   
  Namrata Vaswani
Recursive Sparse Recovery and Robust PCA: Performance Bounds and Experiments
Sept. 16 
  Namrata Vaswani Recursive Sparse Recovery and Robust PCA: Performance Bounds and Experiments
Sept. 23 
  David Weiss
Industrial Strength Software Measurement slides
Sept. 30 
  David Weiss
Chunking: An Empirical Evaluation of Software Architecture slides
Oct. 7  
  Leslie Hogben
Minimum Rank Problems
Oct. 14-15
  no seminar
Postponed: Nicholas Multari, Pacific Northwest National Lab 
 Tues  
Oct. 22
305 Carver
  Sondra Ashmore,
  IBM
IBM Watson
  Oct. 28
  James Ostrowski,
U Tennessee-Knoxville
Symmetry in Integer Programming
Tues  
Oct. 29
132 Carver
  William A. Massey,
  Princeton
Gaussian Skewness Approximation for Dynamic Rate Multi-Server Queues with Abandonment
  Nov. 4
  Fritz Keinert
Convex optimization based on the proximity operator
  Nov. 11
  Fritz Keinert Non-convex compressed sensing
November 25 - 29: Thanksgiving Break, No Seminar
Dec. 2 
  Derrrick Stolee
 Combinatorial Generation in the Presence of Symmetry
Dec. 9 
  Derrrick Stolee  Generating p-extremal graphs


Spring 2014 Seminars

Mon March 31
The maximum nullity of a complete subdivision graph is equal to its zero forcing number   Lelsie Hogben

A graph G=(V,E)  is a  set  of vertices V={1,...,n} and set  of edges E of two element sets of vertices.   A graph   describes the family  of  n x n real symmetric matrices A=[a_{ij}] by using the edges of the graph to describe the position of  nonzero off-diagonal entries of A with the edge {i,j} associated with the entry a_{ij} being nonzero.  The maximum nullity problem for graphs asks us to determine for any graph G the maximum  nullity among the matrices described by G.  Despite recent progress, the problem remains open, and there are specific graphs of not very large order for which there is no known method to find the maximum over the infinite family of matrices described by the graph.  The zero forcing number is a graph coloring game parameter that is an upper bound for maximum nullity.  Although in general zero forcing number is NP-hard to compute, it is still a finite computation, and if it is known that maximum nullity equals zero forcing number for a particular small graph, even brute force computation of zero forcing number allows the computation of maximum nullity; for some graphs there are better methods to find the zero forcing number.  An edge e={u,v} of G=(V,E) is subdivided by inserting a new vertex w into V, deleting the edge e and  inserting edges {u,w} and {w,v}.    The complete subdivision graph of a graph G is obtained from  G by subdividing each edge of G once. In 2009 it was asked whether the maximum nullity is equal to the zero forcing number for all complete subdivision graphs.  This talk will describe the ideas used in the proof that equality holds for complete subdivision graphs,  and show how to determine this common value.   


Fall 2013 Abstracts

Monday December 9
Generating p-extremal graphs    Prof. Derrick Stolee  slides
Let f(n,p) be the maximum number of edges in a graph on n vertices with exactly p perfect matchings. Dudek and Schmitt proved that there exist constants n_p and c_p such that for even n at least n_p, we have f(n,p) = n^2/4 + c_p; we say a graph is p-extremal if it has p perfect matchings and n^2/4 + c_p edges. In this talk, we discuss structural theorems in matching theory to study p-extremal graphs and use them in a new computational method. This method uses canonical deletion with a custom augmentation to work with the perfect matching restrictions. Using this method, we extend the known sizes of p-extremal graphs from p at most 10 to p at most 27 while providing a complete characterization. This information provides further evidence towards a conjectured upper bound for all values of p and shows the sequence c_p is not monotonic.

Monday December 2
Combinatorial Generation in the Presence of Symmetry    Prof. Derrick Stolee  slides
Many interesting problems are easily described using combinatorial terminology that does not translate well into linear or convex optimization problems. While the combinatorial problems are difficult, being aware of combinatorial structure can lead to significant improvements in computation time. In particular, being aware of the symmetries of a combinatorial system is extremely important. We will discuss some of the ways to formulate a problem in a combinatorial setting and how to exploit that structure in an improved algorithm. In particular, we will discuss the canonical deletion method at a high level before discussing it in more detail the following week.

Monday October 28
Symmetry in Integer Programming    Prof. James Ostrowski
This talk will focus on solving integer programs whose feasible
regions are highly symmetric. Symmetry has long been recognized as a
curse for solving integer programs, and auxiliary (often extended)
formulations are sought to reduce the amount of symmetry in an
Integer Programming (IP) formulation. If not properly addressed,
branch-and-bound trees for highly symmetric problems can contain many
thousands of nodes representing equivalent subproblems. Solving each
of these subproblems results in a tremendous waste of computational
resources and can make what should be very simple problems impossible to solve.

Tuesday October 29
Gaussian Skewness Approximation for Dynamic Rate Multi-Server Queues with Abandonment   Prof. William Massey
    The multi-server queue with non-homogeneous Poisson arrivals and
customer abandonment is a fundamental queueing model with dynamic rates. It arises in
large scale service systems such as call centers and hospitals. Moreover, understanding their
stochastic evolution is key to the analysis of fork-join systems that model the coordination
of such queues.
    Scaling the arrival rates and number of servers in the QED regime gives
us the fluid and diffusion limits for Markovian service networks.These scaling
asymptotics are also the Halfin-Whitt scaling for multi-server queues.
    These fluid and diffusion limits suggests a Gaussian approximation for
this queueing process. The mean and variance are easily computed from a two-dimensional
dynamical system for the limiting processes. Recent work by Ko and Gautum found
that a modified version of these differential equations yield better
Gaussian estimates of the original queueing system distribution.
    We introduce here a new closure approximation method where the fluid
limit is a one-dimensional version of the method and Ko and Gautum's work is a two-dimensional
version. This broader view yields a new three-dimensional version of this method that constructs a
quadratic function of a Gaussian random variable to estimates the mean, variance, and third
cumulative moment.
*This is based on a paper that will appear in QUESTA and is joint work with
Jamol Pender of Princeton University.

Tuesday October 22
IBM Watson    Dr. Sondra Ashmore, IBM

IBM celebrated 100 years of technology leadership in 2011 by taking on one of the biggest technical challenges yet - creating a computer that could beat the grand champions in Jeopardy.  They succeeded with their Watson computer, and now they are putting Watson to work to help with some of the world's biggest challenges.  This talk will discuss Watson's future and how we all may be impacted by this ground-breaking technology.

Organizing Committee