Towards a Theory of Mixing Graphs: A Characterization of Perfect Mixability

Speaker:        Professor Marek Chrobak
                University of California at Riverside

Title:          "Towards a Theory of Mixing Graphs: A Characterization of
                 Perfect Mixability"

Date:           Monday, 26 November 2018

Time:           4:00pm - 5:00pm

Venue:          Lecture Theater F (near lift 25/26), HKUST

Abstract:

Some microfluidic lab-on-chip devices contain modules whose function is to
mix two fluids, called reactant and buffer, in desired proportions. In one
of the technologies for fluid mixing the process can be represented by a
directed acyclic graph whose nodes represent micro-mixers and edges
represent micro-channels. A micro-mixer has two input channels and two
output channels; it receives two fluid droplets, one from each input,
mixes them perfectly, and produces two droplets of the mixed fluid on its
output channels. Such a mixing graph converts a set I of input droplets
into a set T of output droplets, where the droplets are specified by their
reactant concentrations. The most fundamental algorithmic question related
to mixing graphs is to determine, given an input set I and a target set T,
whether there is a mixing graph that converts I into T. We refer to this
decision problem as mix-reachability. While the complexity of this problem
remains open, we provide a solution to its natural sub-problem, called
perfect mixability, in which we ask whether, given a collection C of
droplets, there is a mixing graph that mixes C perfectly, producing only
droplets whose concentration is the average concentration of C. We provide
a complete characterization of such perfectly mixable sets and an
efficient algorithm for testing perfect mixability. Further, we prove that
any perfectly mixable set has a perfect-mixing graph of polynomial size,
and that this graph can be computed in polynomial time.

This is joint work with Miguel Coviello Gonzalez (UCR).


*****************
Biography:

Marek Chrobak is currently a Professor of Computer Science at University
of California, Riverside. Born in Poland, he received his PhD from Warsaw
University in 1985, and soon afterwards moved to UCR and stayed there ever
since, enticed by its sunny weather, proximity to nature, and friendly
atmosphere. In his research, he is generally interested in theoretical
computer science, with his current research topics including offline and
online approximation algorithms, information dissemination in radio
networks, and job scheduling problems, although in the past he also tried
his luck in other areas, including automata theory and bioinformatics.