- September 23, 2013:
**Mirkó Visontai**, Royal Institute of Technology (KTH)

**Interlacing Families 1 by Marcus, Spielman, and Srivastava**

*Abstract:*

In this talk we review a recent result by Marcus, Spielman and Srivastava (http://arxiv.org/abs/1304.4132) which establishes the existence of infinite families of bipartite Ramanujan graphs for all degrees. We cover all the necessary background from Linear Algebra, Graph Theory and Theory of Stable polynomials.

- October 24, 2013:
**Nathan Lemons**, Center for Nonlinear Studies, Los Alamos National Laboratory

**Efficient generation of inhomogenous random graphs**

*Abstract:*

The last decade and a half has seen the introduction of a wide variety of random graph models. Random graph models allow for theoretical analysis of network properties as well as simulation on random instances of the model. Thus the most useful random graph models (a) capture the percieved important characteristics of real networks, (b) are mathematically tractible, and (c) allow for quick generation of random instances. We concentrate on this third point: fast generation. As real world networks are usually sparse and large, it is important for the running time of generation algorithms to scale linearly in the number of edges of the generated graph as opposed to quadratically in the number of vertices. Recently, Bollobas, Janson and Riordan introduced an extremely general random graph model, the random kernel graph. This model generalizes several well known models while remaining mathematically tractable. We describe an algorithm to randomly generate instances of this model which runs in time O(m+n) for many kernels of interest. (Here n is the number of vertices and m the expected number of edges in the graph.)

- November 21, 2013:
**Paul Bendich**, Duke University

**Persistent Homology: getting better algorithms by doing some math**

*Abstract:*

The field of topological data analysis (TDA) has been developed over the last decade, and has already found application in a wide variety of areas, from neuroscience to orthodontia. A key tool in TDA is the persistence diagram, which provides a compact picture of the multi-scale topoogical information carreid by a point cloud or other embedded object. The algorithm for computing this diagram takes an ordered list of simplices as input, and then reduces a matrix indexed by the simplices. Unfortunately, the number of simplices in practical applications is often extremely high, and so the algorithm is prohibitively expensive, especially when compared with other "big data" analysis methods. In this talk, we describe two ways to drastically reduce the number of input simplices, and hence reduce the overall running time of the algorithm. The first algorithm uses ideas from Discrete Morse Theory, returns a correct answer, and achieves large speedups in practice (despite no theoretical results to guarantee this). The second algorithm uses ideas from cover-trees, as well as the algebraic concept of a chain homotopy, to provide a family of approximate diagrams, of guaranteed quality, with theoretical bounds on running time that are achieved in practice. These algorithms, especially when used in tandem, allow for the computation of persistence diagrams on datasets of realistic size. This is joint work with John Harer, Jurgen Slaczedek, Mauro Maggionni, and Sam Gerber.

- February 5, 2014:
**Brian Dean**, Clemson University

**Recent Algorithmic Results in Stable Matching and Allocation Problems**

*Abstract:*

Matchings are a well-studied class of problems in algorithmic computer science, where we must find an assignment (e.g., jobs to machines) that is optimal in some sense, for example maximum cardinality or minimum cost. In this talk, I will discuss ordinal matching problems, where the input consists of ranked preference lists instead of explicit numeric costs (e.g., a job might prefer to be assigned to one machine over another). The best-known problem in this domain is the classical stable marriage problem, where we want to find a matching between N men and N women, such that there exists no unmatched (man, woman) pair preferring each-other to their partners in the matching. A natural generalization of this problem is the stable allocation problem, where we assign elements that are all potentially of different sizes; for example, we might assign jobs of varying size to machines of varying capacity. I’ll discuss several of our recent algorithmic results for problems in this general domain, focusing mainly on fast algorithms for solving stable allocation problems and “unsplittable” stable allocation problems.

- February 18, 2014:
**Erik D. Demaine**, Massachusetts Institute of Technology

**Replicators, Transformers, and Robot Swarms: Science Fiction through Geometric Algorithms**

*Abstract:*

Science fiction is a great inspiration for science. How can we build reconfigurable robots like Transformers or Terminator 2? How can we build Star Trek-style replicators that duplicate or mass-produce a given shape at the nano scale? How can we orchestrate the motion of a large swarm of robots? Recently we've been exploring possible answers to these questions through computational geometry.

Reconfigurable robots are made up of many components that can move/rotate around each other, enabling an overall shape change. What is the best way to transform such a robot from one shape (e.g. humanoid) into another (e.g. vehicle)? We will describe several algorithms developed for this problem for various models of geometric robots, both when the robots are independent units, and when they are connected together into a single robot, making either a self-folding origami sheet or hinged chain. Ultimately the goal is programmable matter: a single piece of material that can dynamically change its shape into anything desired, in principle allowing us to download and execute geometry in the same way we download and execute software.

Robot swarms are similar in that they involve many individual components, but different in the components are not attached to each other. How can a swarm of moving robots communicate locally and still measure its own shape? How can a swarm of simple particles be transformed from one configuration to another, given just a global signal like "everyone move left until hitting something", as might be provided by a strong external magnet. We will describe algorithms and hardness results developed for these problems.

Self-assembly is an exciting approach to constructing complex 3D objects out of simple, nano-scale such as DNA (each much less powerful than a typical robot). Staged assembly is a relatively new approach to self-assembly, which models not only the parts but also the experimenter who creates and combines the parts. This more algorithmic approach enables substantially more efficient and practical constructions of arbitrary desired shapes. Another surprising result is a general-purpose replicator, which takes an unknown physical object as input, and produces arbitrarily many copies of it using just a constant amount of experimental operations. Along the way, we show efficient ways to build nano-scale biological computers.

- February 18, 2014:
**Erik D. Demaine**, Massachusetts Institute of Technology

**Replicators, Transformers, and Robot Swarms: Science Fiction through Geometric Algorithms**

*Abstract:*

- April 14, 2014:
**Anant Godbole**, East Tennessee State University

**A potpourri of generalized De Bruijn sequences**

*Abstract:*

The sequence 11101000 codes the set of eight binary three letter strings in the most compact way possible, since, when written in a cycle, each three bit string can be seen to occur exactly once as a contiguous sequence. This is an example of a de Bruijn cycle. Generalizations of de Bruijn sequences often involve one or more of of the following:

(i) Changing the rules, e.g., allowing for non-consecutive windows (overlap-cycles) or introducing larger alphabets when smaller ones do not suffice;

(ii) Changing the customary coding, e.g., encoding subsets with their characteristic vectors rather than their elements;

(iii) Introducing non-standard objects for which to exhibit de Bruijn cycles, e.g., words with restrictions, lattice paths,subsets of sizes in a range; words with weights in a range; poset-allocations, etc.

This talk will focus on results that use standard methods to exhibit existence of de Bruijn cycles in each of the above three categories.

Return to main CS Theory Seminar page