Title:
Weighted Matching on General Graphs: Faster and Simpler
Abstract :
We present a new scaling algorithm for maximum (or minimum) weight perfect matching on general, edge weighted graphs. The algorithm runs in O(mn^{1/2}log(nW)) time, where m, n, and W are the numbers of edges, vertices and maximum integer edge weight. This bound matches the fastest algorithm for bipartite graphs and comes within a log(nW) factor of the Micali-Vazirani cardinality matching algorithm. In terms of running time our algorithm is just slightly faster than the previous best (Gabow and Tarjan, 1991) by a roughly (log n)^{1/2} factor. However, it is dramatically simpler to describe and analyze.
Joint work with Ran Duan (IIIS, Tsinghua) and Hsin-Hao Su (University of Michigan). Manuscript available at http://arxiv.org/abs/1411.1919v2.
Bio:
Seth Pettie received his Ph.D. in Computer Science from the University of Texas at Austin, in 2003. From 2003-2006 he was an Alexander von Humboldt Postdoctoral Fellow at the Max Planck Institute for Computer Science, in Saarbruecken, Germany. Since 2006 he has been a professor of Electrical Engineering and Computer Science at the University of Michigan, in Ann Arbor.
Seth Pettie, Assoc. Prof. in Computer Science and Engineering University of Michigan, Ann Arbor http://web.eecs.umich.edu/~pettie
Title:
Approximately Stable, School Optimal, and Student-Truthful Many-to-One Matchings (via Differential Privacy)
Abstract:
We present a mechanism for computing asymptotically stable school optimal matchings, while guaranteeing that it is an asymptotic dominant strategy for every student to report their true preferences to the mechanism. Our main tool in this endeavor is differential privacy: we give an algorithm that coordinates a stable matching using differentially private signals, which lead to our truthfulness guarantee. This is the first setting in which it is known how to achieve nontrivial truthfulness guarantees for students when computing school-optimal matchings, assuming worst-case preferences (for schools and students) in large markets.
Joint work with Sampath Kannan, Aaron Roth and Zhiwei Steven Wu: SODA 2015.
This workshop will be held at the Georgia Institute of Technology, Klaus Building room 1116, 266 Ferst Drive, NW, Atlanta, GA 30332-0765.
This workshop will bring together researchers from a variety of fields to highlight new results broadly related to the use of randomization in algorithm design.
Talks will highlight new results in the area of randomized algorithms and probabilistic tools for algorithm design. The workshop will also include recent successes in derandomization and problems where there are efficient deterministic algorithms but not yet randomized versions, such as Weitz's approximate counting approach and recent extensions of it.
The workshop will attempt to bring various experts interested in this general theme and identify challenging open problems and discuss ways to approach and attack them.
Preserving Statistical Validity in Adaptive Data Analysis
Abstract:
A great deal of effort has been devoted to reducing the risk of spurious scientific discoveries resulting from misapplication of statistical data analysis. Existing approaches to ensuring validity of inferences drawn from data assume a fixed collection of hypotheses to be tested, or analysis to be applied, selected non-adaptively before the data are examined. In contrast, the practice of data analysis in scientific research is by its nature an adaptive process, in which new hypotheses are generated and new analyses are performed on the basis of data exploration and observed outcomes on the same data. We demonstrate a new approach for addressing the challenges of adaptivity based on insights from private data analysis. As an application we show how to safely reuse a holdout set a great many times without undermining its validation power, even when hypotheses, models, and algorithms are chosen adaptively.
Joint work with Cynthia Dwork, Moritz Hardt, Toni Pitassi, Omer Reingold and Aaron Roth.
]]>Title:
Looking for Structure in Real-World Networks
Abstract:
Graphs offer a natural representation of relationships within data -- for example, edges can be defined based on any user-defined measure of similarity (e.g. word frequencies, geographic proximity of observation, gene expression levels, or overlap in sample populations) or interaction (e.g. social friendship, communication, chemical bonds/protein bindings, or migration). As such, network analysis is playing an increasingly important role in understanding the data collected in a wide variety of social, scientific, and engineering settings. Unfortunately, efficient graph algorithms with guaranteed performance and solution quality are impossible in general networks (according to computational complexity).
One tantalizing approach to increasing scalability without sacrificing accuracy is to employ a suite of powerful (parameterized) algorithms developed by the theoretical computer science community which exploit specific forms of sparse graph structure to drastically reduce running time. The applicability of these algorithms, however, is unclear, since the (extensive) research effort in network science to characterize the structure of real-world graphs has been primarily focused on either coarse, global properties (e.g., diameter) or very localized measurements (e.g., clustering coefficient) -- metrics which are insufficient for ensuring efficient algorithms.
We discuss recent work on bridging the gap between network analysis and structural graph algorithms, answering questions like: Do real-world networks exhibit structural properties that enable efficient algorithms? Is it observable empirically? Can sparse structure be proven for popular random graph models? How does such a framework help? Are the efficient algorithms associated with this structure relevant for common tasks such as evaluating communities, clustering and motifs? Can we reduce the (often super-exponential) dependence of these approaches on their structural parameters?
Joint work with E. Demaine, M. Farrell, T. Goodrich, N. Lemons, F. Reidl, P. Rossmanith, F. Sanchez Villaamil & S. Sikdar.
]]>
Title:
Pursuit on a Graph
Abstract:
Pursuit games---motivated historically by military tactics – are a natural for graphical settings, and take many forms. We will present some recent results involving (among other things) drunks, Kakeya sets and a ``ketchup graph.'' Lastly, we describe what we think is the most important open problem in the field.
Bio:
Peter Winkler is William Morrill Professor of Mathematics and Computer Science at Dartmouth College. He is the author of about 150 research papers and holds a dozen patents in marine navigation, cryptolography, holography, gaming, optical networking, and distributed computing. His research is primarily in combinatorics, probability, and the theory of computing, with forays into statistical physics. He is a winner of the Mathematical Association of America's Lester R. Ford and David P. Robbins prizes.
Dr. Winkler has also written two collections of mathematical puzzles, a book on cryptography in the game of bridge, and a portfolio of compositions for ragtime piano. He's working on a new puzzle book.
ARC: http://www.arc.gatech.edu/
]]>
denton at cc dot gatech dot edu
]]>Title:
Projection-free Optimization and Online Learning
Abstract:
Modern large data sets prohibit any super-linear time operations. This motivates the study of iterative optimization algorithms with low complexity per iteration. The computational bottleneck in applying state-of-the-art iterative methods is many times the so-called "projection step".
We consider projection-free optimization/learning that replaces projections by more efficient linear optimization steps. We describe the first linearly-converging algorithm of this type for polyhedral sets and how it gives rise to optimal-rate stochastic optimization and online learning algorithms.
]]>
denton at cc dot gatech dot edu
]]>Title:
Online Advertisements and Online Algorithms
Abstract:
Capacity or budget planning is an important component of any online ad serving platform. This has given rise to a rich and exciting line of work in online algorithms, and one of the most successful marriages of theory and practice. The practical aspects have directly influenced the theory and the theory has had significant impact on the design of modern advertising systems. The talk will give an overview of this interaction and some recent results on a very general problem called the online convex programming problem.
Bio:
Nikhil R. Devanur is a researcher in the Theory group at Microsoft Research, Redmond. He is interested in designing algorithms that are faster, simpler, work online or in a distributed fashion, for some of the fundamental combinatorial optimization problem and in "Automated Economics", which studies the question of how technology can be used to improve the efficiency of economic systems. Prior to joining Microsoft Research, Nikhil got his PhD from Georgia Tech and spent a year at the Toyota Technological Institute at Chicago as a Research Assistant Professor.
]]>denton at cc dot gatech dot edu
]]>Title:
Algorithms for Lipschitz Learning on Graphs
Abstract:
We develop fast algorithms for solving regression problems on graphs where one is given the value of a function at some vertices, and must find its smoothest possible extension to all vertices. The extension we compute is the absolutely minimal Lipschitz extension, and is the limit for large p of p-Laplacian regularization. We present an algorithm that computes a minimal Lipschitz extension in expected linear time, and an algorithm that computes an absolutely minimal Lipschitz extension in expected time O(mn). The latter algorithm has variants that seem to run much faster in practice. These extensions are particularly amenable to regularization: we can perform l_0 regularization on the given values in polynomial time and l_1 regularization on the graph edge weights in time O(m^(3/2)). Our algorithms naturally extend to directed graphs. This is a joint work with Rasmus Kyng, Sushant Sachdeva and Daniel Spielman.
denton at cc dot gatech dot edu
]]>9:00 - 9:05 Introduction
9:05 - 10:35 Talks by Srinivas Aluru (CSE), Santosh Vempala (CS), and Natashia Boland (ISyE) (30 minutes each)
10:35 - 11:00 Break and light snacks
11:00 - 12:00 Keynote by Christos Papadimitriou (U.C.- Berkeley)
(see titles and abstracts below)
————————
Srinivas Aluru, (CSE)
Title: Parallel machine learning approaches for reverse engineering genome-scale networks
Abstract: Reverse engineering whole-genome networks from large-scale gene expression measurements and analyzing them to extract biologically valid hypotheses are important challenges in systems biology. While simpler models easily scale to large number of genes and gene expression datasets, more accurate models are compute intensive limiting their scale of applicability. In this talk, I will present our research on the development of parallel mutual information and Bayesian network based structure learning methods to eliminate such bottlenecks and facilitate genome-scale network structure learning.
————————
Santosh Vempala, (CS)
Title: Safe and Easy: Humanly Usable Password Generation Methods
Abstract: On a typical day, humans brush teeth, read, eat, converse ... and type passwords. This last task seems to be overly time-consuming (multiple attempts, frequent resets) and insecure --- passwords are often compromised. We desire passwords that are HUMANLY USABLE, i.e., easy to generate when needed, and SECURE, i.e., any single password is hard to crack, but even knowing several passwords doesn't allow an adversary infer others. Is this possible? How? How to even measure human effort? These questions lead us to ask what (protocols and algorithms) humans can compute and cannot compute. We present a model for measuring the complexity of human computation, and apply it in a rigorous framework for password generation.
This is joint work with Manuel Blum.
————————
Natashia L Boland, (ISyE)
Title: Alternating Projection Algorithms and Integer Programming
Abstract: Alternating projection algorithms have been independently discovered, and have made a significant impact, in diverse areas of science and engineering. They remain of great interest and current activity in convex optimization, and were independently discovered for general-purpose integer programming (IP) in 2005. Their use has been one component of the major advances in IP technology that now make IP a valuable and practical tool for solution of large-scale industrial problems. An essential element of the success of these methods is the application of randomization within the alternating projection framework. Since their first discovery for IP, the methods have been improved and extended in a number of directions. In this talk, we will give an overview of recent activity in these methods, including two new ideas for improving their performance.
————————
Keynote Speaker
Christos H Papadimitriou, UC-Berkeley
Title: Life under the lens
Abstract: Applying the algorithmic point of view to the natural, life, and social sciences often results in unexpected insights and progress in central problems, a mode of research that has been described as ``the lens of computation.'' I will focus on examples in the life sciences, from joint work with Erick Chastain, Costis Daskalakis, Adi Livnat, Umesh Vazirani, Santosh Vempala, and Albert Wu: Evolution of a population through sexual reproduction can be rethought of as a repeated game between genes played through the multiplicative weight updates algorithm. In an infinite population, when selection acts not on genes alone but on pairs of genes, fixation can take exponentially many generations. And unsupervised learning of patterns can be achieved spontaneously and with high probability through a simple and neurally plausible primitive.
Bio: Christos H. Papadimitriou is the C. Lester Hogan Professor of Computer Science at UC-Berkeley. Before joining Berkeley in 1996, he taught at Harvard, MIT, NTU Athens, Stanford, and UCSD. He has written five textbooks and many articles on algorithms and complexity, and their applications to optimization, databases, control, AI, robotics, economics, game theory, the Internet, evolution, and brain science. He holds a PhD from Princeton, and seven honorary doctorates. He is a member of the National Academy of Sciences of the US, the American Academy of Arts and Sciences, and the National Academy of Engineering. He has also written three novels: “Turing”, “Logicomix” (with Apostolos Doxiadis) and “Independence” (in Greek).
Wednesday, August 26, 2015
Klaus 2447 - 2:00 pm
Title:
Swendsen-Wang Algorithm on the Mean-Field Potts Model
Abstract:
This talk will focus on the q-state ferromagnetic Potts model on the n-vertex complete graph known as the mean-field (Curie-Weiss) model. We analyze the Swendsen-Wang algorithm which is a Markov chain that utilizes the random cluster representation for the ferromagnetic Potts model to recolor large sets of vertices in one step and potentially overcomes obstacles that inhibit single-site Glauber dynamics.
The case q=2 (the Swendsen-Wang algorithm for the ferromagnetic Ising model) undergoes a slow-down at a critical temperature beta=betac (Long et al., 2014), but yet still has polynomial mixing time at all (inverse) temperatures beta>0 (Cooper et al., 2000).
In contrast, for q>=3 there are two critical temperatures 0<betau<betarc that are relevant (these correspond to phase transitions on the infinite tree). We prove that the mixing time of the Swendsen-Wang algorithm for the ferromagnetic Potts model on the n-vertex complete graph satisfies:
(i) O(log n) for beta<betau, (ii) O(n^{1/3}) for beta=betau, (iii) exp(n^(Omega(1))) for betau<beta<betarc, and (iv) O(log n) for beta>=betarc. These results complement refined results of Cuff et al. (2012) on the mixing time of the Glauber dynamics for the ferromagnetic Potts model.
The most interesting aspect of our analysis is at the critical temperature beta=betau, which requires a delicate choice of a potential function to balance the conflating factors for the slow drift away from a fixed point (which is repulsive but not Jacobian repulsive): close to the fixed point the variance from the percolation step dominates and sufficiently far from the fixed point the dynamics of the size of the dominant color class takes over.
Joint work with Daniel Stefankovic and Eric Vigoda.
]]>denton at cc dot gatech dot edu
]]>Monday, August 31, 2015
Klaus 1116 East & West - 1:00 pm
(Refreshments will be served in Klaus 2222 at 2 pm)
Title:
Algorithm Frameworks Based on Structure Preserving Sampling
Abstract:
Sampling is a widely used algorithmic tool: running routines on a small representative subset of the data often leads to speedups while preserving accuracy. Recent works on algorithmic frameworks that relied on sampling graphs and matrices highlighted several connections between graph theory, statistics, optimization, and functional analysis. This talk will describe some key ideas that emerged from these connections:
* Sampling as a generalized divide-and-conquer paradigm.
* Implicit sampling without constructing the larger data set, and its algorithmic applications.
* What does sampling need to preserve? What can sampling preserve?
These ideas have applications in solvers for structured linear systems, network flow algorithms, input-sparsity time numerical routines, coresets, and dictionary learning.
]]>denton at cc dot gatech dot edu
]]>(Refreshments will be served in Klaus 2222 at 2 pm)
Title:
Reconstruction thresholds for the random colourings of G(n,m)
Abstract:
In this talk we consider the reconstruction problem for the random colourings of a random graph G(n,m) of degree d.
For some k-colourable graph G, the reconstruction problem studies the correlation between the assignment of a single vertex in G and that of its neighbours at distance r, under the uniform measure over the k-colourings of G. This is point to set correlation.
When the correlation persists as r grows, then we have reconstruction, otherwise we have non-reconstruction.
It has been conjecture from statistical physics that for typical instances of G(n,m) the transition from non-reconstruction to reconstruction exhibits a threshold behavior. That is, there is a critical value k_0, which depends on the expected degree d, such that the following is true: When k>k_0 there is non-reconstruction while when k<k_0 there is reconstruction.
The aforementioned phase transition has been related to the performance of local search algorithms as well as the shattering phenomenon in the solution space of the k-colourings.
In this talk I discuss our recent results which show that the phase transition from statistical physics is indeed correct. Moreover, the point where this phase transition occurs, up to smaller order terms, is exactly at the point where it has been conjectured to be.
The first step in our approach is to show that the Gibbs distribution over the k-colouring of G(n,m) converges locally to the Gibbs distribution over the k-colourings of a Poisson(d) Galton-Watson tree T(d), for a wide range of k. This allows to reduce our initial problem to studying the reconstruction on T(d). The second step is to establish the reconstruction threshold for the colourings of T(d).
This talk is based on 2 recent works of mine. One of them is a joint work with Amin Coja-Oghlan and Nor Jaafari.
]]>
]]>
Monday, September 21, 2015
Klaus 1116 W - 1:00 pm
(Refreshments will be served in Klaus 2222 at 2 pm)
Title:
Strings, Trees, and RNA Folding
Abstract:
An RNA molecule is a linear biochemical chain which folds into a three dimensional structure via a set of 2D base pairings known as a nested secondary structure. Reliably determining a secondary structure for large RNA molecules, such as the genomes of most viruses, is an important open problem in molecular biology. Using strings and (plane) trees as a combinatorial model of RNA folding, we give mathematical results which yield insights into RNA branching configurations and suggest new directions in understanding the structure of RNA viruses. We also demonstrate that, under a suitable abstraction, complex biological problems can reveal surprising mathematical structure.
]]>]]>
Monday, November 2, 2015
Klaus 1116 West – 1:00 pm
(Refreshments will be served in Klaus 2222 at 2 pm)
Title:
The Emergent Structure of Simple Behaviors in Complex Networks
Abstract:
Many games of social significance are played in a networked context. In these settings, agents often exhibit simple behaviors, shaped by local preferences and social norms. The interplay of these behaviors and the underlying network give rise to emergent structures with global impact. In this talk, we explore the impact of networked behavior on social capital, segregation, and learning.
First we study the emergence of social capital in dynamic, anonymous social networks, such as online communities. We find that, despite the lack of punitive strategies, (partial) cooperation is sustainable at an intuitive and simple equilibrium as cooperation allows an individual to interact with an increasing number of other cooperators, resulting in the formation of valuable social capital.
Next we examine the emergence of segregation in geographical networks. In 1969, Schelling introduced a model of racial segregation in which individuals move out of neighborhoods where their ethnicity constitutes a minority and suggested that this local behavior can cause global segregation effects. Our rigorous analysis shows that, in contrast to prior interpretations, the outcome exhibits local but not global segregation.
Finally, we study learning outcomes in social networks. Individuals with independent opinions asynchronously update their declared opinion to match the majority report of their neighbors. We show that the population will converge to the majority opinion with high probability if the underlying network is large, sparse, and expansive, properties reflected by realistic social networks.
Based on joint works with Christie Brandt, Michal Feldman, Gautam Kamath, Robert Kleinberg, Brendan Lucier, Brian Rogers and Matt Weinberg.
]]>]]>
Algorithms & Randomness Center (ARC)
Wednesday, September 9, 2015
Klaus 1116 West - 4:00 pm
(Refreshments will be served in 1116W at 4 pm)
Title:
Phylogenetics Through the Lens of Chordal Graph Theory
Abstract:
The evolutionary history of a set of species is generally described by a hylogenetic tree. The combinatorial structure of phylogenetic trees is very well understood when biological characters can only take on two states. But, when characters can take on more than two states, the combinatorial structure is much less understood. The Multi-State Perfect Phylogeny (MPP) problem addresses the case of non-binary states.
The MPP problem was initially defined (using different terminology) in a 1975 paper by Peter Buneman that establishes a deep relationship between the MPP problem and the class of graphs called chordal graphs. It showed a how to view the multi-state perfect phylogeny problem as a problem of triangulating non-chordal graphs. While that result has been used in mathematical results, it was not widely exploited as a computational tool.
In this talk, I discuss our work on exploiting the chordal graph approach to solve and study multi-state perfect phylogeny and related problems. I will discuss how the problem relates to minimal triangulation, 2-SAT, integer linear programming, and undirected tree compatibility. I will also discuss generalizations of the classic four-gametes condition, which characterizes a binary (perfect) phylogeny, to conditions that characterize multi-state perfect phylogenies, and I will identify open questions in this field.
]]>Algorithms & Randomness Center (ARC)
Wednesday, September 23, 2015
Klaus 1116 E - 11:00 am
(Refreshments will be served in Klaus 2222 at Noon)
Title:
Title: Probabilistic analysis of some combinatorial optimization problems.
Abstract:
We consider the following probabilistic model. The edges of a (complete) graph have unknown random edge weights. We want to build a minimum cost structure. We can ask for the weight of an edge and then accept or reject the edge. Once rejected, the edge cannot be accepted later. We must accept enough edges to support a structure and we are charged for all the edges accepted, even if not used. We give results in this model for minimum spanning tree, perfect matching and shortest path.
Joint work with Colin Cooper and Wesley Pegden.
]]>
Monday, October 26, 2015
Klaus 1116 West – 1:00 pm
(Refreshments will be served in Klaus 2222 at 2 pm)
Title:
The Stochastic Block Model and Communities in Sparse Random Graphs: Detection at Optimal Rate
Abstract:
We consider the problem of communities detection in sparse random graphs. Our model is the so-called Stochastic Block Model, which has been immensely popular in the recent statistics literature. Let X1,...Xk be vertex sets of size n each (where k is fixed and n is large). One draws random edges inside each Xi with probability a/n, and between Xi and Xj with probability b/n, for some constants a and b. Given one instance of this sparse random graph, our goal is to recover the sets Xi as correctly as possible. We are going to present a fast spectral algorithm which does this job at the optimal rate (namely the relation between a,b and the number of mistakes in the recovery is optimal). Our algorithm is based on spectral properties of random sparse matrices and is easy to implement. We will also discuss some related works with spectral algorithms and an open question concerning random matrices.
]]>]]>
Monday, September 28, 2015
Klaus 1116 West - 1:00 pm
(Refreshments will be served in Klaus 2222 at 2 pm)
Title:
Counting hypergraph matchings up to uniqueness threshold
Abstract:
We study the problem of approximately counting hypergraph matchings with an activity parameter $\lambda$ in hypergraphs of bounded maximum degree and bounded maximum size of hyperedges. This problem unifies two important statistical physics models in approximate counting: the hardcore model (graph independent sets) and the monomer-dimer model (graph matchings).
We show for this model the critical activity $\lambda_c= \frac{d^d}{k (d-1)^{d+1}}$ is the threshold for the uniqueness of Gibbs measures on the infinite $(d+1)$-uniform $(k+1)$-regular hypertree. And we show that when $\lambda<\lambda_c$ the model exhibits strong spatial mixing at an exponential rate and there is an FPTAS for the partition function of the model on all hypergraphs of maximum degree at most $k+1$ and maximum edge size at most $d+1$. Assuming NP$\neq$RP, there is no FPRAS for the partition function of the model when $\lambda > 2\lambda_c$ on above family of hypergraphs .
Towards closing this gap and obtaining a tight transition of approximability, we study the local weak convergence from an infinite sequence of random finite hypergraphs to the infinite uniform regular hypertree with specified symmetry, and prove a surprising result: the existence of such local convergence is fully characterized by the reversibility of the uniform random walk on the infinite hypertree projected on the symmetry classes. We also give explicit constructions sequence of random finite hypergraphs with proper local convergence property when the reversibility condition is satisfied.
]]>]]>
Monday, November 9, 2015
Klaus 1116 West – 1:00 pm
(Refreshments will be served in Klaus 2222 at 2 pm)
Title:
Input Sparsity Time Algorithms for Robust Regression and Robust Low Rank Approximation
Abstract:
We give near optimal algorithms for regression and low rank approximation in the robust case. For regression, we give algorithms generalizing l_p regression to M-Estimator loss functions, such as the Huber measure, which enjoys the robustness properties of l_1 as well as the smoothness properties of l_2. For low rank approximation, we give new algorithms generalizing the singular value decomposition to sum of p-th powers of distances, and M-estimator loss functions applied to the distances. Some problems here are arguably even more fundamental than the SVD itself, such as given a set of points, find a line which minimizes the sum of distances of the points to the line, rather than the sum of squared distances. These measures are less sensitive to outliers and we show they can be computed approximately in time proportional to the number of non-zeros of the input matrix. We also discuss hardness results in the low rank approximation setting.
]]>]]>
James Saunderson - University of Washington
Monday, November 23, 2015
Klaus 1116 West – 1:00 pm
(Refreshments will be served in Klaus 2222 at 2 pm)
Title:
Semidefinite descriptions of regular polygons (and beyond)
Abstract:
Semidefinite programs are a family of convex optimization problems that generalize linear programs and can model a wide range of problems from areas as diverse as statistics, robotics, and combinatorial optimization. Despite this, understanding the expressive power and limitations of (small) semidefinite programs remains a significant challenge.
This talk is centered on new efficient descriptions of regular polygons (and related polytopes) in terms of the feasible regions of semidefinite programs. These constructions, for instance, give the first known family of polytopes with semidefinite programming descriptions that are asymptotically smaller than the best linear programming descriptions.
Based on joint work with Hamza Fawzi (MIT) and Pablo Parrilo (MIT).
Host is Greg Blekherman (greg@math.gatech.edu).
]]>]]>
Friday, October 9, 2015
Klaus 1116 East – 11:00 am
Title:
Programmable Matter: Self-organizing Particle Systems
Abstract:
From the level of chemical reaction networks within cells to the social structures of higher organisms, biological systems take advantage of distributed computation to perform a myriad of complex functions. Computer scientists and engineers have investigated biological and physical systems in order to understand how these systems can provide us with the necessary insight to realize self-organizing systems of artificial, programmable particles. Those investigations led to the notion of programmable matter. The impact of programmable matter will be seen across all areas, from improved drugs and assistance in nano surgery, to increased productivity, greater capabilities in automation, etc. Fully distributed computation, self-organization and self-stabilization are key for the scalability and robustness of such systems. In this talk, we present a general abstract model for programmable matter consisting of systems of simple, computationally-limited particles. We present self-organizing algorithms for the problems of leader election, coating, and shape formation.
This work has been done in collaboration with Zahra Derakhshandeh (ASU), Christian Scheideler, Robert Gmyr and Thim Strothmann (U. of Paderborn, Germany), and others.
Bio:
Andrea W. Richa is an Associate Professor in Computer Science at Arizona State University (ASU), Tempe, AZ. She is also affiliated with the Biomimicry Center at ASU. She received her M.S. and Ph.D. degrees from the School of Computer Science at Carnegie Mellon University, in 1995 and 1998, respectively. Prof. Richa's work on distributed algorithms has been widely cited, and includes work on self-organizing particle systems, wireless network modeling and topology control, wireless jamming, data mule networks, underwater optical networking, distributed load balancing, and distributed hash tables (DHTs). Dr. Richa was the recipient of an NSF CAREER Award in 1999, is currently an Associate Editor of IEEE Transactions on Mobile Computing, and has served as keynote speaker and program\general chair of several prestigious conferences. Dr. Richa is also a founding member of UON Technologies. For a selected list of her publications and other accomplishments, and current research projects, please visit www.public.asu.edu/~aricha .
]]>
]]>