Minimizing Communication in Linear Algebra (2009)
Ballard, Grey, Demmel, James, Holtz, Olga, Schwartz, Oded
In 1981 Hong and Kung proved a lower bound on the amount of communication needed to perform dense, matrix-multiplication using the conventional $O(n^3)$ algorithm, where the input matrices were too...
Communication-optimal Parallel and Sequential Cholesky Decomposition (2009)
Ballard, Grey, Demmel, James, Holtz, Olga, Schwartz, Oded
Numerical algorithms have two kinds of costs: arithmetic and communication, by which we mean either moving data between levels of a memory hierarchy (in the sequential case) or over a network...
Beverly Sackler, Oded Schwartz
2007 To all my parents, sisters and brothers. Thank you thank you thank you... Expanders are graphs that are sparse, yet highly connected. In this thesis, we consider an elementary algorithm for...
An Explicit Construction of Quantum Expanders (2007)
Ben-Aroya, Avraham, Schwartz, Oded, Ta-Shma, Amnon
Quantum expanders are a natural generalization of classical expanders. These objects were introduced and studied by Ben-Aroya and Ta-Shma and by Hastings. In this note we show how to construct...
An elementary construction of constant-degree expanders (2007)
Noga Alon, Oded Schwartz, Asaf Shapira
We describe a short and easy to analyze construction of constant-degree expanders. The construction relies on the replacement product, applied by [14] to give an iterative construction of...
An elementary construction of constant-degree expanders (2007)
Noga Alon, Oded Schwartz, Asaf Shapira
We describe a short and easy to analyze construction of constant-degree expanders. The construction relies on the replacement product, applied by [14] to give an iterative construction of...
Amitai Armon, Adi Avidor, Oded Schwartz
Abstract. In this paper we introduce and study cooperative variants of the Traveling Salesperson Problem. In these problems a salesperson has to make deliveries to customers who are willing to help...
On the complexity of approximating k-set packing (2003)
Elad Hazan, Shmuel Safra, Oded Schwartz
Given a k-uniform hypergraph, the Maximum k-Set Packing problem is to find the maximum disjoint set of edges. We prove that this problem cannot be efficiently approximated to within a factor of Ω (...
On the complexity of approximating k-set packing (2003)
Elad Hazan, Shmuel Safra, Oded Schwartz
Abstract. We study the complexity of bounded packing problems, mainly the problem of k-Set Packing (k-SP), We prove that k-SP cannot be efficiently approximated to within a factor of O ( k ln k)...
An Explicit Construction of Quantum Expanders
Avraham Ben-aroya, Oded Schwartz, Amnon Ta-shma
Quantum expanders are a natural generalization of classical expanders. These objects were introduced and studied by [1, 3, 4]. In this note we show how to construct explicit, constant-degree quantum...