- Friday, August 25 @ noon, at the theory lounge (3rd floor SC)
- Organizational meeting to determine our regular meeting time. If you can't come, please write your name and the times you absolutely cannot attend on one of the whiteboards in the theory lounge (or email Mike).
- Thursday, August 31 @ 3:00 pm, 3405 Siebel Center
- Chandra Chekuri will give a talk entitled Algorithms for Path and Walk Problems in Directed Graphs (abstract).
Algorithms for Path and Walk Problems in Directed Graphs
We consider algorithms for some problems related
to finding a path or walk between two given nodes s,t in
a directed graph G. Although closely related to the classical
traveling salesman problem (TSP), these problems have,
surprisingly, not received much attention in the literature.
We discuss simple algorithmic ideas that yield new results and
suggest interesting open problems.
Joint work with Martin Pal
- Thursday, September 7 @ 3:00 pm, 3405 Siebel Center
- John Fischer will give a talk entitled Coreset results for clustering and related problems (abstract).
Coreset results for clustering and related problems
We present a variety of approximation results for clustering and related problems in Euclidean space. These results use the concept of coresets -- given a dataset, extracting a small representative set for this dataset that captures certain properties of the original dataset.
Joint work with Sariel Har-Peled.
- Thursday, September 14 @ 3:00 pm, 3405 Siebel Center
- Mike Rosulek will give a talk entitled The State Of The Art In Program Obfuscation (abstract).
The State Of The Art In Program Obfuscation
An obfuscated computer program is one whose source code reveals no information other than the program's input-output functionality. The study of obfuscation is still in its infancy, only being given a formal foundation in cryptography by Barak et al. in 2001. Still, several possibility and impossibility results are known. In this talk, we will present the major results and open problems in this new field.
- Thursday, September 21 @ 3:00 pm, 3405 Siebel Center
- Jeff Erickson will give a talk entitled Delaunay triangulations of random points on cylinders.
- Thursday, September 28 @ 3:00 pm, 3405 Siebel Center
- Lisa Fleischer will visit UIUC and give a talk entitled Finding Equilibria through Natural Play: Tatonnement and the Market Problem (abstract).
Finding Equilibria through Natural Play: Tatonnement and the Market Problem
While much recent attention has focussed on the computational
tractability of computing equilibria in various game-theoretic settings,
less attention has been paid to how the players themselves
might converge to an equilibrium while making individually
rational decisions.
We consider this question in the context of the classical market
problem as put forth by Walras: There
is a market consisting of a set of infinitely divisible goods;
and a set of agents with an initial allocation
of the goods and a utility function over combinations of goods. Trade is
driven by the prices of the goods. Each agent can buy at most the worth
of their initial allocation. Prices provide an equilibrium if, in addition,
the demand for each good is bounded by the supply.
In 1874, Walras hypothesized that some form natural price adjustment
should lead to equilibrium prices for the market problem.
Much later, Arrow et al. showed that
a differential process specified by Samuelson did indeed converge
to equilibrium in markets of gross substitutes. Shortly afterward,
Uzawa described a discrete process that also converges. However,
Uzawa's process depends on global knowledge of the market --- information
that market players are unlikely to consistently share.
We describe a discrete and distributed process in which player actions
depend on reasonable local knowledge only. We show not only
that this converges in many markets of gross substitutes,
but also that it does so quickly --- in polynomial time.
This is joint work with Richard Cole of NYU.
- Thursday, October 12 @ 3:00 pm, 3405 Siebel Center
- Erin Wolf Chambers will give a talk entitled Multiple Source Shortest Paths in a Genus $g$ Graph (abstract).
Multiple Source Shortest Paths in a Genus $g$ Graph
We give an $O(g^2 n \log n)$ algorithm to represent the shortest path
tree from all the vertices on a single specified face $f$ in a genus
$g$ graph. From this representation, any query distance from a vertex
in $f$ can be obtained in $O(\log n)$ time. The algorithm uses a
kinetic data structure, where the source of the
tree iteratively moves across edges in $f$. In addition, we give
applications using these shortest path trees in order to compute the
shortest non-contractible cycle and the shortest non-separating cycle
embedded on an orientable 2-manifold in $O(g^3 n \log n)$ time.
- Thursday, October 19 @ 3:00 pm, 3405 Siebel Center
- Tracy Grauman will give a talk entitled The Difficulty (and Fun) of Paper Folding
(abstract).
The Difficulty (and Fun) of Paper Folding
There has been a new wave of research on folding and unfolding problems,
that is, problems which try to characterize how objects can be reconfigured
subject to given constraints. One class of these problems deals with
origami flat-foldability, where one is given a crease pattern on a piece of
paper and is asked to determine if it is foldable into a flat origami using
exactly those creases. One can think of this as receiving a map which has
been opened and being asked to fold it back up again. This talk will cover
the hardness of folding a map flat, and it will touch on a few other fun
ideas regarding flat-foldability.
- Thursday, October 26 @ 3:00 pm, 3405 Siebel Center
- Pratik Worah will give a talk entitled Derandomization and epsilon approximations.
- Thursday, November 2 @ 3:00 pm, 3405 Siebel Center
- Nitish Korula will give a talk entitled Partial results for the Domatic Partition and Connected Domatic Partition Problems
(abstract).
Partial results for the Domatic Partition and Connected Domatic Partition Problems
The Domatic partition problem requires us to find as many disjoint dominating sets of a graph as possible. In the connected version, we have the additional requirement that each dominating set is connected. We present a O(\log n) approximation algorithm (due to Feige, Halldorsson and Kortsarz) for the domatic partition problem; this is optimal. For the connected domatic partition problem, the connectivity k of the graph is an easy upper bound. We conjecture that there always exist \Omega(k / \log n) connected dominating sets, and prove that for every graph, we can find \Omega(\sqrt{k / \log n}) connected dominating sets.
- Thursday, November 9 @ 3:00 pm, 3405 Siebel Center
- Harald Raecke will visit us and give a talk entitled Algorithms for Sorting Buffers in HST's
(abstract).
Algorithms for Sorting Buffers in HST's
In the sorting buffer problem we are given an input sequence of points
in a metric space. The task is to visit all points while minimizing
the total distance that is traveled. For this, a sorting buffer can
be used to rearrrange/reorder the input sequence into an output sequence
with improved travel distance. At each step the sorting buffer holds the
first $k$ yet unvisited points of the input sequence. An
online algorithm has to decide which of these points should be visited
next; and upon this decision the corresponding point is removed from the
buffer and the slot is filled with the next point from the input sequence.
We present an online algorithm that obtains a competitive ratio of
$O(\log n \log^2 k)$ for arbitrary metric spaces and $O(\log^2\Delta\log
k)$ for metric spaces of aspect ratio $\Delta$.
This is joint work with Matthias Englert and Matthias Westermann.
- Thursday, November 16 @ 3:00 pm, 3405 Siebel Center
- Ke Chen will give a talk entitled Approximation algorithms for outlier k-median problem (abstract).
Approximation algorithms for outlier k-median problem
We consider approximation algorithms for the outlier
k-median problem. We are given a set of n data points in
a metric space, and we want to remove m points (called
outliers) from the data, such that the cost of the
k-median clustering of the remaining points is minimized.
We present an algorithm for computing a constant-factor
approximation solution for this problem, using at most k+1
centers.
- Thursday, November 30 @ 3:00 pm, 3405 Siebel Center
- Feida Zhu will give a talk on two subjects (abstract).
Mining Colossal Frequent Patterns by Core Pattern Fusion
Extensive research for frequent-pattern mining in the past decade has brought forth a number of pattern mining algorithms that are both effective and efficient. However, the existing frequent-pattern mining algorithms encounter challenges at mining rather large patterns, called \emph{colossal} frequent patterns, in the presence of an explosive number of frequent patterns. Colossal patterns are
critical to many applications, especially in domains like
bioinformatics. In this study, we investigate a novel mining
approach called \emph{Pattern-Fusion} to efficiently find a good approximation to the colossal patterns. With Pattern-Fusion, a colossal pattern is discovered by fusing its small \emph{core patterns} in one step, whereas the incremental pattern-growth mining strategies, such as those adopted in Apriori and FP-growth, have to examine a large number of mid-sized ones. This property distinguishes Pattern-Fusion from all the existing frequent pattern
mining approaches and draws a new mining methodology. Our empirical studies show that, in cases where current mining algorithms cannot proceed, Pattern-Fusion is able to mine a result set which is a close enough approximation to the complete set of the colossal patterns, under a quality evaluation model proposed in this paper.
A Cooperative Filter Overlay for Consistency reserving Stream Data Dissemination
The increasingly large size of the data dissemination network in today's stream-data oriented applications poses serious challenges for available stream data management systems due to their significant dissemination costs. Aimed at large-scale data dissemination network in particular, we propose a Multilevel Cooperative Filter (MCF) overlay for consistency preserving data dissemination. Based on our classification of the total dissemination cost into the maintenance cost and the delivery cost,we show that MCF is able to significantly reduce the maintenance cost by the idea of \emph{cooperative filter}. MCF is the first known system to decompose user-specified consistency thresholds into \emph{cooperating} filters and construct them in a pyramid"-like structure for overall dissemination cost saving. We also prove that MCF gives the optimal delivery cost for all online deterministic algorithms. Extensive experiments on both real and synthetic financial data streams
demonstrate that MCF gives performance superior to available approaches and exhibits high scalability.