Midwest Theory Day
Next Meeting: Dec. 6, 2008, 10am-5:00pm, Fine Barr Forum, Allen Center, Northwestern U., Evanston IL.
The 57th Midwest Theory Day will be hosted by the
Theory Group in
Electrical Engineering and
Computer Science Department and cosponsored by the Math
Center at the Kellogg
School of Management
at Northwestern University on Saturday, December 6th.
There will be a number of contributed talks and an invited talk
by Abraham Flaxman. Anyone interested in
theoretical computer science is welcome to attend. There is no
registration fee, lunch is provided, and the talks are scheduled so
that from many locations in the Midwest it is often possible to come,
attend all of the talks, and return home all in a day. For those
wishing to stay into the evening, arrangements for a banquet dinner
are made at a local restaurant, each person paying for his or her own
Next Meeting: Dec. 6, 2008, 10am-5:00pm, Fine Barr Forum, Allen Center, Northwestern U., Evanston IL.
The organizers thank you for
registering by sending email with your name and affiliation
to firstname.lastname@example.org by Dec. 3rd. There is no cost for attending.
Call for Participation
There are usually six or seven contributed talks and often an invited
talk. There is no program committee and there are no
proceedings. Anyone willing to talk may do so. The atmosphere is
relaxed and informal and so is an excellent forum for graduate
students to get experience giving a talk. If you would like to give a
talk, send email to email@example.com. Please include the title of your
talk and your affiliation in your email.
Speaker: Abraham Flaxman (Institute for Health Metrics and Evaluation, Seattle, WA.)
Title: Theoretical Computer Science for Global Health
Spanning Trees, Random Graphs, Markov Chains, and Solving Linear System
of Equations: these bread-and-butter concepts from CS theory all have
important roles to play in understanding global health. In this talk,
I'll give an overview of the Global Burden of Disease Study (GBD), and
describe some of its many algorithmic challenges. GBD is a systematic
effort to produce estimates of how 200+ diseases, injuries, and risk
factors impact people around the world. Naturally, there are a lot of
numbers to crunch. But you may be surprised to learn how many of the
relevant numbers are missing. And the numbers we do have often don't
add up. This is where we need computational tools, and I hope to
leverage research from probability theory, machine learning, and
possibly even combinatorial Hodge theory. I'll give you a quick tour of
the interdisciplinary area that is Health Metrics.
Bio: For the last 3 months, Abraham Flaxman has been working as
a post-doc at the Institute for Health Metrics and Evaluation,
which does global health research as part of the Public Health School
at the University of Washington. Before that, he was a graduate
student at CMU and a post-doc in the Microsoft Research Theory Group.
He maintains a weblog about Math, CS, and OR applications to Health
Metrics at http://healthyalgorithms.wordpress.com/.
Siddarth Barman (University of Wisconsin, Madison),
"Packing multiway cuts in capacitated graphs":
Louis Ibarra (DePaul U), "The clique-separator graph and developing a dynamic graph algorithm to recognize interval graphs":
We present a new representation of a chordal graph called the clique-separator graph, whose nodes are the maximal cliques and minimal vertex separators of the graph. We present structural properties of the clique-separator graph and additional properties when the chordal graph is an interval graph. This representation has been used to develop the first dynamic graph algorithm for interval graphs.
Nicole Immorlica (Northwestern U.), "The Role of Compatibility in Technology Diffusion on Social Networks" [paper.pdf]:
In many settings, competing technologies -- for example, operating
systems, instant messenger systems, or document formats -- can be seen
adopting a limited amount of compatibility with one another; in other
words, the difficulty in using multiple technologies is balanced
somewhere between the two extremes of impossibility and effortless
interoperability. There are a range of reasons why this phenomenon
occurs, many of which -- based on legal, social, or business
considerations -- seem to defy concise mathematical models. Despite
this, we show that the advantages of limited compatibility can arise
in a very simple model of diffusion in social networks, thus offering
a basic explanation for this phenomenon in purely strategic terms. Our
approach builds on work on the diffusion of innovations in the
economics literature, which seeks to model how a new technology A
might spread through a social network of individuals who are currently
users of technology B. We consider several ways of capturing the
compatibility of A and B, focusing primarily on a model in which users
can choose to adopt A, adopt B, or -- at an extra cost -- adopt both A
and B. We characterize how the ability of A to spread depends on both
its quality relative to B, and also this additional cost of adopting
both, and find some surprising non-monotonicity properties in the
dependence on these parameters: in some cases, for one technology to
survive the introduction of another, the cost of adopting both
technologies must be balanced within a narrow, intermediate range. We
also extend the framework to the case of multiple technologies, where
we find that a simple model captures the phenomenon of two firms
adopting a limited "strategic alliance" to defend against a new, third
Hemanta Maji (University of Illinois, Urbana-Champaign),
"Complexity of Multiparty Computation":
Joint work with J. Kleinberg, M. Mahdian, and T. Wexler.
In symmetric 2-party secure function evaluation, Alice has an input $x$, Bob has an input $y$, and both parties wish to compute $f(x,y)$ without revealing anything more about $x$ and $y$ to each other.
Xufei Mao (Illinois Institute of Technology), "Closing the Gap in the Multicast Capacity of Hybrid Networks"
Benjamin Moseley (University of Illinois, Urbana-Champaign),
"Online Scheduling to Minimize the Maximum Delay Factor":
It has been known that not all functions $f$ can be securely computed with computationally unbounded players (i.e., without computational assumptions).
We give a precise combinatorial characterization of functions that can
be securely computed with computationally unbounded players. Further
we show a hierarchy of functions of strictly increasing
``cryptographic complexity:'' given oracle access to computing a lower
complexity function, it is still impossible to compute the higher
Joint work with Manoj Prabhakaran and Mike Rosulek.
We consider two scheduling models: First is the standard model
(unicast) where requests (or jobs) are independent. The other is the
broadcast model where broadcasting a page can satisfy multiple
outstanding requests for that page. We consider online scheduling of
requests when they have deadlines. Unlike previous models, which
mainly consider the objective of maximizing throughput while
respecting deadlines, here we focus on scheduling all the given
requests with the goal of minimizing the maximum delay factor. The
delay factor of a schedule is defined to be the minimum alpha >= 1 such
that each request i is completed by time a_i + alpha(d_i - a_i ) where a_i
is the arrival time of request i and d_i is its deadline. Delay factor
generalizes the previously defined measure of maximum stretch which is
based only on the processing times of requests.
Saad Sheikh (U. of Illinois, Chicago),
"Qualitative methods for Sibling Reconstruction from genotyping data":
We prove strong lower bounds on the achievable competitive ratios for
delay factor scheduling even with unit-time requests. Motivated by
this, we consider resource augmentation analysis and prove the
following positive results. For the unicast model we give algorithms
that are (1 + \eps)- speed O(1/\eps)-competitive in both the single
machine and multiple machine settings. In the broadcast model we give
an algorithm for same-sized pages that is (2 + \eps)-speed
O(1/\eps^2)-competitive. For arbitrary page sizes we give an algorithm
that is (4 + \eps)-speed O(1/\eps^2)-competitive.
Joint work with
New technologies for collecting genotypic data from natural
populations open the possibilities of investigating many fundamental
biological phenomena, including behavior, mating systems,
heritabilities of adaptive traits, kin selection, and dispersal
patterns. The power and potential of genotypic information often
rests in the ability to reconstruct genealogical relationships among
individuals. These relationships include parentage, full and
half-sibships, and higher order aspects of pedigrees. Some areas of
genealogical inference, such as parentage, have been studied
extensively. Although methods for pedigree inference and kinship
analysis exist, most make assumptions that do not hold for wild
populations of animals and plants.
We present new combinatorial formulations and their complexity results,
including a link to Raz's Parallel Repetition Theorem.
Guangwu Xu (U. of Wisconsin, Milwaukee), "Restricted Isometry Properties and Compressed Sensing":
Xiaohua Xu (Illinois Institute of Technology),
"An Improved Approximation Algorithm for Data Aggregation in Multi-hop Wireless Sensor Networks":
Joint work with Tanya Berger-Wolf, Bhaskar DasGupta, and Ashfaq Khokhar.
Data aggregation is a key functionality for wireless sensor network
(WSN) applications. This paper focuses on data aggregation scheduling
problem to minimize the latency. We propose an efficient distributed
scheduling method that produces a collision-free schedule to perform
data aggregation in WSNs. We theoretically prove that the latency of
the aggregation schedule generated by our algorithm is at most
$13R+\Delta-12$. Here $R$ is the network radius and $\Delta$ is the
maximum node degree in the communication graph of the original
network. Our method significantly improves the previously known best
data aggregation algorithm which has a latency bound $24D+6\Delta+16$,
where $D$ is the network diameter. We conduct extensive simulations to
study the practical performances of our proposed data aggregation
methods. Our simulation results corroborate our theoretical results
and show that our algorithms perform better in practice.
If you are staying the night in Evanston, you may choose from one of the following hotels for discounted room rates. If you would like to share a room and want to be connected to a roommate, email firstname.lastname@example.org with "ROOMMATE MATCH" in the subject line.
1625 Hinman Ave,
Mention "Midwest Theory Day" when booking to get a room rate of $95
per night that includes: complimentary parking, complimentary continental
breakfast, wireless high speed Internet access, guest laundry, cable
TV, iron and ironing board.
Some double rooms are available at the same rate.
Best Western University Plaza [map it]
1501 Sherman Ave,
Mention "Midwest Theory Day" when booking to get a room rate of $89 per night that includes: complimentary wireless Internet, TV's with free Sho-time, coffee maker, iron, ironing board and hair dryers, and free shuttle ride to NU.
Double rooms are available at the same rate.
The 57th Midwest Theory Day will be held in the Fine Barr Forum of the
Allen Center at Northwestern U.
Dinner will be at Mt. Everest at 630 Church St.,
Evanston, IL 60201. See map, below.
View Larger Map
Parking on Northwestern's campus is free on weekends.