Sivan Toledo

ICML Conference 2013 Conference Paper

Efficient Dimensionality Reduction for Canonical Correlation Analysis

• Haim Avron
• Christos Boutsidis
• Sivan Toledo
• Anastasios Zouzias

We present a fast algorithm for approximate Canonical Correlation Analysis (CCA). Given a pair of tall-and-thin matrices, the proposed algorithm first employs a randomized dimensionality reduction transform to reduce the size of the input matrices, and then applies any standard CCA algorithm to the new pair of matrices. The algorithm computes an approximate CCA to the original pair of matrices with provable guarantees, while requiring asymptotically less operations than the state-of-the-art exact algorithms.

AIJ Journal 2002 Journal Article

Parallel Randomized Best-First Minimax Search

• Yaron Shoham
• Sivan Toledo

FOCS Conference 1993 Conference Paper

Efficient Out-of-Core Algorithms for Linear Relaxation Using Blocking Covers (Extended Abstract)

• Charles E. Leiserson
• Satish Rao
• Sivan Toledo

When a numerical computation fails to fit in the primary memory of a serial or parallel computer, a so-called "out-of-core" algorithm must be used which moves data between primary and secondary memories. In this paper, we study out-of-core algorithms for sparse linear relaxation problems in which each iteration of the algorithm updates the state of every vertex in a graph with a linear combination of the states of its neighbors. We give a general method that can save substantially on the I/O traffic for many problems. For example, our technique allows a computer with M words of primary memory to perform T=/spl Omega/(M/sup 1/5/) cycles of a multigrid algorithm for a two-dimensional elliptic solver over an n-point domain using only /spl Theta/(nT/M/sup 1/5/) I/O transfers, as compared with the naive algorithm which requires /spl Omega/(nT) I/O's. >

SODA Conference 1992 Conference Paper

Applications of Parametric Searching in Geometric Optimization

• Pankaj K. Agarwal
• Micha Sharir
• Sivan Toledo

FOCS Conference 1992 Conference Paper

Maximizing Non-Linear Concave Functions in Fixed Dimension

• Sivan Toledo

Consider a convex set P in R/sup d/ and a piece wise polynomial concave function F: P to R. Let A be an algorithm that given a point x in IR/sup d/ computes F(x) if x in P, or returns a concave polynomial p such that p(x) or= 0. The author assumes that d is fixed and that all comparisons in A depend on the sign of polynomial functions of the input point. He shows that under these conditions, one can find max/sub P/ F in time which is polynomial in the number of arithmetic operations of A. Using this method he gives the first strongly polynomial algorithms for many nonlinear parametric problems in fixed dimension, such as the parametric max flow problem, the parametric minimum s-t distance, the parametric spanning tree problem and other problems. In addition he shows that in one dimension, the same result holds even if one only knows how to approximate the value of F. Specifically, if one can obtain an alpha -approximation for F(x) then one can alpha -approximate the value of maxF. He thus obtains the first polynomial approximation algorithms for many NP-hard problems such as the parametric Euclidean traveling salesman problem. >