AFLB/S10

From ResearchWiki

Jump to: navigation, search

AFLB: Spring 2010

Contents

Jan 8, 2010

Jan14, 2010

Jeff: Combinatorial view of Markov chain Monte Carlo.

Jan 21, 2010

SODA recaps Part I: Parasaran and Jeff

Parasaran

Jeff

Jan 28, 2010

SODA recaps Part II

Suresh (Poincare inequalities):

John:

Feb 4, 2010

John: Maximum Flows and Parametric Shortest Paths in Planar Graphs Jeff Erickson

Abstract: We observe that the classical maximum flow problem in any directed planar graph G can be reformulated as a parametric shortest path problem in the oriented dual graph G�. This reformulation immediately suggests an algorithm to compute maximum flows, which runs in O(n log n) time. As we continuously increase the parameter, each change in the shortest path tree can be effected in O(log n) time using standard dynamic tree data structures, and the special structure of the parametrization implies that each directed edge enters the evolving shortest path tree at most once. The resulting maximum-flow algorithm is identical to the recent algorithm of Borradaile and Klein [J. ACM 2009], but our new formulation allows a simpler presentation and analysis. On the other hand, we demonstrate that for a similarly structured parametric shortest path problem on the torus, the shortest path tree can change (n2) times in the worst case, suggesting that a different method may be required to efficiently compute maximum flows in higher-genus graphs.

This is a paper from SODA '10 that I thought was particularly interesting. It takes an older result and casts it in a topological setting.

Feb 11, 2010

Arvind: A Unified Algorithmic Framework for Multi-Dimensional Scaling

Abstract: In this paper, we propose a unified algorithmic framework for solving many known variants of MDS. Our algorithm is a simple iterative scheme with guaranteed convergence, and is modular; by changing the internals of a single subroutine in the algorithm, we can switch cost functions and target spaces easily. In addition to the formal guarantees of convergence, our algorithms are fast; in most cases, they converge to better quality solutions faster than existing methods. We expect that this framework will be useful for a number of MDS variants that have not yet been studied.

This is a joint work with Jeff Philips and Suresh Venkatasubramanian.

Feb 18, 2010

Josh: Road Network Reconstruction for Organizing Paths by Daniel Chen, Leo Guibas, John Hershberger, and Jian Sun

Abstract: We consider the problem of reconstructing a road network from a collection of path traces and provide guarantees to the accuracy of the reconstruction under reasonable assumptions. Our algorithm can be used to process a collection of polygonal paths in the plane so that shared structures (subpaths) among the paths in the collection can be discovered and the collection can be organized to allow efficient path similarity queries against new query paths on the same road network. This is a timely problem, as GPS or other location traces of both people and vehicles are becoming available in a large scale and there is a real need to create appropriate data structures and data bases for such data.

Feb 25, 2010

Jags

We will discuss the following paper Efficient Approximation for the Generalized Assignment Problem.

Generalized assignment problem is a generalization of the weighted bipartite matching problem. As input, we are given a set of M bins along with their sizes, a set of N items and for each item i and bin j, we are also given a size s(i,j) and a profit p(i,j). The problem is to find a subset of items that is consistent with size restrictions and also maximizes the profit.

This paper proposes a greedy algorithm. Given an α-approximation algorithm (ALG) to the Knapsack problem, greedily it finds an (1+α) approximation algorithm to the generalized assignment problem.

Mar 4, 2010

Suresh: Recognizing well-parenthesized expressions in the streaming model. F. Magniez, C. Mathieu, A. Nayak

Abstract: Motivated by a concrete problem and with the goal of understanding the sense in which the complexity of streaming algorithms is related to the complexity of formal languages, we investigate the problem Dyck(s) of checking matching parentheses, with $s$ different types of parenthesis. We present a one-pass randomized streaming algorithm for Dyck(2) with space $\Order(\sqrt{n}\log n)$, time per letter \log^c (n), and one-sided error. We prove that this one-pass algorithm is optimal, up to a $\polylog n$ factor, even when two-sided error is allowed. For the lower bound, we prove a direct sum result on hard instances by following the "information cost" approach, but with a few twists. Indeed, we play a subtle game between public and private coins. This mixture between public and private coins results from a balancing act between the direct sum result and a combinatorial lower bound for the base case. Surprisingly, the space requirement shrinks drastically if we have access to the input stream in reverse. We present a two-pass randomized streaming algorithm for Dyck(2) with space $\Order((\log n)^2)$, time $\polylog (n)$ and one-sided error, where the second pass is in the reverse direction. Both algorithms can be extended to Dyck(s) since this problem is reducible to Dyck(2) for a suitable notion of reduction in the streaming model.

Mar 11, 2010

Avishek: Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform. Nir Ailon, Bernard Chazelle

Abstract: We introduce a new low-distortion embedding of $l_2^d$ into $l_p^{O(log n)}$ $(p=1,2)$, called the Fast-Johnson-Linden-strauss-Transform. The FJLT is faster than standard random projections and just as easy to implement. It is based upon the preconditioning of a sparse projection matrix with a randomized Fourier transform. Sparse random projections are unsuitable for low-distortion embeddings. We overcome this handicap by exploiting the "Heisenberg principle" of the Fourier transform, ie, its local-global duality. The FJLT can be used to speed up search algorithms based on low-distortion embeddings in $l_1$ and $l_2$. We consider the case of approximate nearest neighbors in $l_2^d$. We provide a faster algorithm using classical projections, which we then further speed up by plugging in the FJLT. We also give a faster algorithm for searching over the hypercube.

Mar 18, 2010

Jeff: Sampling from Probe-Only Distributions.

I will talk about some preliminary work. Hopefully the audience can provide some feedback. The main object of interest will be "probe-only" distributions--continuous density functions m : |R^d -> |R^+ that can only be accessed by probes w(q) = c m(q) for q in |R^d and a fixed unknown constant c. These arise in measuring energy landscape and quite commonly in Bayesian statistics. Typically probes are expensive. The goal is to draw a set X of random samples distributed according to m. This is often accomplished using Markov chain Monte Carlo (MCMC), but we will examine disappointing properties of this approach. The main result will be an alternative to MCMC with different properties. We will also examine the relationships between kernel density estimates and eps-samples of range spaces.

Apr 1, 2010

All: Markets are efficient if and only if P = NP (Suresh: I'm suspicious about this, and so given the date, I thought it might be fun to ponder it. The plan is for the attendees to read it and then we discuss to see if we can find a bug, or if it actually makes sense)

Apr 8, 2010

Christopher: Push-down control-flow analysis of higher-order programs: Precise, polyvariant and polynomial-time

Abstract: We present push-down control-flow analysis, a novel method for analyzing higher-order control-flow. As its name suggests, push-down control-flow analysis replaces the finite-state machine underlying classical CFAs with a push-down system. The infinite state-space afforded by a push-down system makes it both more precise and more powerful than classical control-flow analysis. The push-down stack adds extra precision by perfectly matching returns to call sites. We discover push-down control-flow analysis as an abstract interpretation of a CESK machine with an unbounded stack. To prove computability, we transform the abstracted CESK machine into a push-down automaton (PDA), and then reduce control-flow analysis to deciding the non-emptiness of a language derived from the PDA's language. From there, we refine the algorithm, dropping its time-complexity from doubly exponential, to best-case exponential, to worst-case exponential, to polynomial. In the end, we are left with an efficient, polyvariant framework for control-flow analysis that can compute push-down generalizations of the classical finite-state control-flow analysis, e.g. push-down 0CFA, push-down $k$-CFA and push-down poly/CFA.

Apr 15, 2010

Jags:

I will discuss our recent attempts involving the graph laplacains to solve bilingual dictionary induction problem. This problem is only an application and I won't spend much time on it. Our approach builds on Canonical Correlation Analysis and Locality Preserving Projections

Jeff:

I will give a practice talk for LATIN 2010 on Lipschitz Unimodal and Isotonic Regression on Paths and Trees coauthored with Pankaj K. Agarwal and Bardia Sadri. Abstract:

We describe algorithms for finding the regression of t, a sequence of values, to the closest sequence s by mean squared error, so that s is always increasing (isotonicity) and so the values of two consecutive points do not increase by too much (Lipschitz). The isotonicity constraint can be replaced with a unimodular constraint, where there is exactly one local maximum in s. These algorithm are generalized from sequences of values to trees of values. For each scenario we describe near-linear time algorithms.

Apr 16, 2010

Special Utah Theory Day !

Time: 10-2 Place: MEB 3490 (the Flux conference room)

Agenda:

  • 10:15 Introductions
  • 10:20 Minghui Jiang: (LATIN 2010 talk) "Minimum-perimeter intersecting polygons"

Given a set \S of segments in the plane, a polygon P is an intersecting polygon of \S if every segment in \S intersects the interior or the boundary of P. The problem MPIP of computing a minimum-perimeter intersecting polygon of a given set of $n$ segments in the plane was first considered by Rappaport in 1995. This problem is not known to be polynomial, nor it is known to be NP-hard. Rappaport (1995) gave an exponential-time exact algorithm for MPIP. Hassanzadeh and Rappaport (2009) gave a polynomial-time approximation algorithm with ratio \pi/2 \approx 1.58.

In this paper, we present two improved approximation algorithms for MPIP: a 1.28-approximation algorithm bylinear programming, and a polynomial-time approximation scheme by discretization and enumeration. Our algorithms can be generalized for computing an approximate minimum-perimeter intersecting polygon of a set of convex polygons in the plane. From the other direction, we show that computing a minimum-perimeter intersecting polygon of a set of (not necessarily convex) simple polygons is NP-hard.

  • 11:00 Pedro Tejada: "On a dispersion problem in grid labeling"

Let $L_1$ and $L_2$ be two bijections from the cells of an $n \times n$ grid to a label set $S$ of $n2$ symbols. Each symbol in $S$ labels two cells, one in $L_1$ and one in $L_2$. Define the combined distance between two symbols $x$ and $y$ in $S$ as the distance between the two cells in $L_1$ plus the distance between the two cells in $L_2$ that are labeled by $x$ and $y$. How to arrange the symbols of the two labelings such that the minimum combined distance between any two symbols is maximized? In this paper, we give a partial answer to this question and study its natural generalizations. On the positive side, we present asymptotically tight bounds on the combined distance of $k$ labelings of a $d$-dimensional cubic grid, which lead to a very simple constant-factor approximation algorithm for the corresponding optimization problem. On the negative side, we show that deciding whether a graph has two labelings with combined distance at least $3$ is at least as hard as graph isomorphism.

  • 11:40: Lunch (I'll provide it)
  • 12:30: Brief 10 minute snippets (please email me if you'd like to be added to this list)
    • Avishek
    • John
    • Parasaran
    • Raj

May 6, 2010

Agenda:

  • Suraj Musuvathy: New Results on Medial Axis Segmentation
  • All: What shall we do this summer ?
Retrieved from "http://www.cs.utah.edu/~suresh/mediawiki/index.php/AFLB/S10"
Personal tools