Yuval Rabani
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Research Interests
Yuval Rabani has a total of 21 co-authors. Here are the top co-authors by number of shared publications:
- Rafail Ostrovsky
UCLA
3 shared publications - Alistair Sinclair
University of California, Berkeley, USA
2 shared publications - Allan Borodin
University of Toronto
2 shared publications - Yuri Rabinovich
Department of Mathematics and Computer Science, Ben Gurion University of the Negev, Beer Sheva 84105, Israel
2 shared publications - Allan Borodin
Department of Computer Science, University of Toronto, Toronto, Canada
1 shared publication Arman Yousefi
1 shared publication
Latest Publications
- 4 January 2017
- Published by Society for Industrial & Applied Mathematics (SIAM)
Matrix Balancing in Lp Norms: Bounding the Convergence Rate of Osborne's Iteration
We study an iterative matrix conditioning algorithm due to Osborne (1960). The goal of the algorithm is to convert a square matrix into a balanced matrix where every row and corresponding column have the same norm. The original algorithm was proposed for balancing rows and columns in the L2 norm, and it works by iterating over balancing a row-column pair in fixed round-robin order. Variants of the algorithm for other norms have been heavily studied and are implemented as standard preconditioners in many numerical linear algebra packages. Recently, Schulman and Sinclair (2015), in a first result of its kind for any norm, analyzed the rate of convergence of a variant of Osborne's algorithm that uses the L∞ norm and a different order of choosing row-column pairs. In this paper we study matrix balancing in the L1 norm and other Lp norms. We show the following results for any matrix , resolving in particular a main open problem mentioned by Schulman and Sinclair.
- 4 January 2017
- Published by Society for Industrial & Applied Mathematics (SIAM)
Matrix Balancing in Lp Norms: Bounding the Convergence Rate of Osborne's Iteration
We study an iterative matrix conditioning algorithm due to Osborne (1960). The goal of the algorithm is to convert a square matrix into a balanced matrix where every row and corresponding column have the same norm. The original algorithm was proposed for balancing rows and columns in the L2 norm, and it works by iterating over balancing a row-column pair in fixed round-robin order. Variants of the algorithm for other norms have been heavily studied and are implemented as standard preconditioners in many numerical linear algebra packages. Recently, Schulman and Sinclair (2015), in a first result of its kind for any norm, analyzed the rate of convergence of a variant of Osborne's algorithm that uses the L∞ norm and a different order of choosing row-column pairs. In this paper we study matrix balancing in the L1 norm and other Lp norms. We show the following results for any matrix , resolving in particular a main open problem mentioned by Schulman and Sinclair.
- 16 June 2009
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 55 (7) , 2931-2941
Error-Correcting Codes for Automatic Control
Systems with automatic feedback control may consist of several remote devices, connected only by unreliable communication channels. It is necessary in these conditions to have a method for accurate, real-time state estimation in the presence of channel noise. This problem is addressed, for the case of polynomial-growth-rate state spaces, through a new type of error-correcting code that is online and computationally efficient. This solution establishes a constructive analog, for some applications in estimation and control, of the Shannon coding theorem.
- 16 June 2009
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 55 (7) , 2931-2941
Error-Correcting Codes for Automatic Control
Systems with automatic feedback control may consist of several remote devices, connected only by unreliable communication channels. It is necessary in these conditions to have a method for accurate, real-time state estimation in the presence of channel noise. This problem is addressed, for the case of polynomial-growth-rate state spaces, through a new type of error-correcting code that is online and computationally efficient. This solution establishes a constructive analog, for some applications in estimation and control, of the Shannon coding theorem.
- Open Access
- 1 June 2006
- Published by Springer Nature in computational complexity
- Vol. 15 (2) , 94-114
ON THE HARDNESS OF APPROXIMATING MULTICUT AND SPARSEST-CUT
- 1 June 2006
- Published by Springer Nature in computational complexity
- Vol. 15 (2) , 94-114
Open AccessON THE HARDNESS OF APPROXIMATING MULTICUT AND SPARSEST-CUT
- 1 May 2005
- Published by Springer Nature in Combinatorica
- Vol. 25 (3) , 251-269
Approximating Directed Multicuts
- 1 May 2005
- Published by Springer Nature in Combinatorica
- Vol. 25 (3) , 251-269
Approximating Directed Multicuts
- 1 November 2004
- Published by Elsevier in Journal of Computer and System Sciences
- Vol. 69 (3) , 435-447
Cell-probe lower bounds for the partial match problem
- 1 November 2004
- Published by Elsevier in Journal of Computer and System Sciences
- Vol. 69 (3) , 435-447
Cell-probe lower bounds for the partial match problem
- 1 July 2004
- Published by Springer Nature in Machine Learning
- Vol. 56 (1-3) , 153-167
Subquadratic Approximation Algorithms for Clustering Problems in High Dimensional Spaces
- 1 July 2004
- Published by Springer Nature in Machine Learning
- Vol. 56 (1-3) , 153-167
Subquadratic Approximation Algorithms for Clustering Problems in High Dimensional Spaces
- 1 January 2003
- Published by Springer Nature
- p. 253-274
Lower Bounds for High Dimensional Nearest Neighbor Search and Related Problems
- 1 January 2003
- Published by Springer Nature
- p. 253-274
Lower Bounds for High Dimensional Nearest Neighbor Search and Related Problems
- 1 June 2002
- Published by Elsevier in Journal of Computer and System Sciences
- Vol. 64 (4) , 873-896
Tighter Lower Bounds for Nearest Neighbor Search and Related Problems in the Cell Probe Model
- 1 June 2002
- Published by Elsevier in Journal of Computer and System Sciences
- Vol. 64 (4) , 873-896
Tighter Lower Bounds for Nearest Neighbor Search and Related Problems in the Cell Probe Model
- 1 June 2000
- Published by Elsevier in Journal of Computer and System Sciences
- Vol. 60 (3) , 564-574
An Improved Approximation Algorithm for MULTIWAY CUT
- 1 June 2000
- Published by Elsevier in Journal of Computer and System Sciences
- Vol. 60 (3) , 564-574
An Improved Approximation Algorithm for MULTIWAY CUT
- 1 July 1998
- Published by Wiley in Random Structures & Algorithms
- Vol. 12 (4) , 313-334
A computational view of population genetics
- 1 July 1998
- Published by Wiley in Random Structures & Algorithms
- Vol. 12 (4) , 313-334
A computational view of population genetics