AFLB
From ResearchWiki
(→STOC 2010) |
(→Mar 4, 2010) |
||
| Line 80: | Line 80: | ||
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. | 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. | 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''': [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.98.9158&rep=rep1&type=pdf 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. | ||
== Papers for discussion == | == Papers for discussion == | ||
Revision as of 02:35, 11 March 2010
The Algorithms For Lunch Bunch
Thursdays at 12:30.
Contents |
Spring 2010
Jan 8, 2010
- Abstracts of papers accepted to ICS2010. Full versions of the papers is here.
- Suresh: Computational Complexity and Information Asymmetry in Financial Products. Sanjeev Arora, Boaz Barak, Markus Brunnermeier, Rong Ge
- Parasaran: Playing Games without Observing Payoffs (Adam Tauman Kalai, Michal Feldman, and Moshe Tennenholtz)
- Jeff: Local Algorithms for Finding Interesting Individuals in Large Networks (Mickey Brautbar and Michael Kearns)
- John: Pan-Private Streaming Algorithms (Cynthia Dwork Moni Naor Toni Pitassi Guy Rothblum Sergey Yekhanin)
Jan14, 2010
Jeff: Combinatorial view of Markov chain Monte Carlo.
Jan 21, 2010
SODA recaps Part I: Parasaran and Jeff
Parasaran
- Finding the Jaccard Median Flavio Chierichetti. Ravi Kumar. Sandeep Pandey. Sergei Vassilvitskii
- A Model of Computation for MapReduce Howard Karloff. Siddharth Suri. Sergei Vassilvitskii
Jeff
- Universal eps-Approximators for Integrals Michael Langberg and Leonard J. Shulman
- Deletion without Rebalancing in Balanced Binary Trees Siddhartha Sen and Robert E. Tarjan
- Self-improving Algorithms for Convex Hulls Kenneth L. Clarkson and Wolfgang Mulzer and C. Seshadrhi
Jan 28, 2010
SODA recaps Part II
Suresh (Poincare inequalities):
- Lower Bounds for Edit Distance and Product Metrics via Poincaré-Type Inequalities. Alexandr Andoni, T. S. Jayram, and Mihai Pătraşcu
- Towards a Calculus for Non-Linear Spectral Gaps. Manor Mendel and Assaf Naor
John:
- Convergence, Stability, and Discrete Approximation of Laplace Spectra Tamal K. Dey, Pawas Ranjan, and Yusu Wang
- Applications of Forbidden 0-1 Matrices to Search Tree and Path Compression-Based Data Structures Seth Pettie
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.
Papers for discussion
Recently Seen on Arxiv
- Constructive Algorithms for Discrepancy Minimization. Nikhil Bansal.
STOC 2010
Add papers here that you found interesting (and link to full version if available)
- Efficiently Learning Mixtures of Two Gaussians. Adam Tauman Kalai (Microsoft), Ankur Moitra (MIT), and Gregory Valiant (UC Berkeley)
- Measuring Independence of Datasets. Vladimir Braverman and Rafail Ostrovsky (UCLA)
- On the Geometry of Differential Privacy. Moritz Hardt (Princeton University) and Kunal Talwar (Microsoft Research)
- Weighted Geometric Set Cover via Quasi-Uniform Sampling. Kasturi Varadarajan (University of Iowa)
- A Sparse Johnson-Lindenstrauss Transform. Anirban Dasgupta and Ravi Kumar and Tamas Sarlos (Yahoo! Research)
Other Papers
- Natural Algorithms (this one might be easier to read) (Chazelle, SODA 09 Best paper)
- A constructive proof of the general Lovasz Local Lemma (Moser, earlier version STOC 09 Best Student Paper)
- Affiliation Networks (Lattanzi, Sivakumar, STOC 09)
- Quantum Proofs for Classical Theorems (Drucker, Wolf)
- Unique games survey (Harb)
- Sorting and Selection with Imprecise Comparisons (Ajtai, Feldman, Hassidim, Nelson, ICALP 09)
- Homology Flows, Cohomology Cuts (Chambers, Erickson and Nayyeri, STOC 09)
- A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0-1 Programming. Monique Laurent. Mathematics of Operations Research, Vol. 28, No. 3 (May, 2003), pp. 470-496
Previous Semesters
Contact
If you are interested in giving a talk at AFLB or have questions, please feel free to send a mail to moeller@cs.utah.edu, praman@cs.utah.edu or avishek@cs.utah.edu. If you are planning to give a talk, we would really appreciate if you have an abstract ready a week before the talk is scheduled.
