Oded Schwartz

My Picture EECS Department, UC Berkeley
586-C Soda Hall
UC Berkeley
Berkeley, CA 94704-1776

odedsc@eecs.berkeley.edu


I am a postdoctoral researcher working with Prof. James Demmel (Math department and Electric Engineering and Computer Science Department) in the Parallel Computing Lab.
My current research interests include parallel computing, scientific computing, algorithmic linear algebra, high performance computing, and accelerating algorithms by reducing communication costs.
Before coming to Berkeley, I did my PhD at the School of Computer Science at Tel-Aviv University under the supervision of Prof. Muli Safra and Prof. Amnon Ta-Shma. I then conducted postdoctoral research at the Math department of TU-Berlin, working primarily with Prof. Olga Holtz, then at the department of Applied Math and Computer Science in Weizmann institute, hosted by Prof. Irit Dinur.

Curriculum Vitae


Honors & Awards

  • 2013 Communication of the ACM Research Highlights Recognition, for the paper
    Graph Expansion and Communication Costs of Fast Matrix Multiplication with Grey Ballard, James Demmel, and Olga Holtz.
  • 2013 IEEE International Parallel & Distributed Processing Symposium Best Paper Award, for
    Implementing a Blocked Aasen's Algorithm with a Dynamic Scheduler on Multicore Architectures with
    Grey Ballard, Dulceneia Becker, James Demmel, Jack Dongarra, Alex Druinsky, Inon Peled, Sivan Toledo, and Ichitaro Yamazaki.
  • 2012 SIAG/Linear Algebra Best Paper Prize (for the years 2009-2011), for
    Minimizing Communication in Numerical Linear Algebra with Grey Ballard, James Demmel, and Olga Holtz.
    Awarded at SIAM Conference on Applied Linear Algebra.
  • 2011 ACM Symposium on Parallelism in Algorithms and Architectures Best Paper Award, for
    Graph Expansion and Communication Costs of Fast Matrix Multiplication with Grey Ballard, James Demmel, and Olga Holtz.
  • 2001 - 2006 The School of Computer Science scholarship, Tel-Aviv University.
  • 2002 - 2006 The Vatat Scholarship for higher technology.
  • 2003 The Paul Viderman prize for Outstanding Teaching, Tel-Aviv University.
  • 2002 The Yeshayahu Lavi award for excellence in M.Sc. studies, Tel-Aviv University.
  • 2002 MSc summa cum laude, Tel-Aviv University.
  • 1995 Full Scholarship, The Adi Lautman Interdisciplinary program for outstanding students, Tel-Aviv University.

    • Professional activities

  • SIAM Conference on Computational Science & Engineering (2013), minisymposium organizer, with Aydin Buluç.
  • Parallel Processing for Scientific Computing (2012), minisymposium organizer, with Haim Avron.
  • SIAM Conference on Applied Linear Algebra (2012), minisymposium organizer, with Aydin Buluç.
  • International Workshop on Accurate Solution of Eigenvalue Problems IWASEP IX (2012), local committee, with James Demmel and Esmond G. NG.
  • AMS Joint Mathematics meetings (2010) special session organizer, with Shamgar Gurevich, Ronny Hadani, Olga Holtz, and Nir Sochen.

    • Teaching

    Partial list (for a complete list please see CV):
  • UC-Berkeley:
    Scientific Computing and Matrix Computations Seminar, Spring 2013, with James Demmel (Math 290, Section 25, CS 298, Section 6).
    Scientific Computing and Matrix Computations Seminar, Fall 2012, with James Demmel (Math 290, Section 25, CS 298, Section 6).
    Communication-Avoiding Algorithms, Fall 2011, with James Demmel (CS294-76).
  • Tel-Aviv University: Introduction to Algorithms and Data Structures (lectures and TA), Computational Complexity (lectures and TA), Advanced Computational Complexity (lectures and TA), Computational Neuroscience (TA), Analysis of Boolean Functions (TA).
  • Taught similar courses at The Academic College of Tel-Aviv-Yaffo and at The Open University.
  • Received the Paul Viderman Prize for Outstanding Teaching (at Tel-Aviv University).

    • Publications

    (bibtex)

    Journals

  • Communication Costs of Strassen's Matrix Multiplication
    Grey Ballard, James Demmel, Olga Holtz, and Oded Schwartz
    Invited to Research Highlights section of the Communications of the ACM, (to appear) 2013.

  • Graph Expansion and Communication Costs of Fast Matrix Multiplication
    Grey Ballard, James Demmel, Olga Holtz, and Oded Schwartz
    Journal of the ACM (JACM), 59(6) Article 32:1-23, 2012.

  • Minimizing Communication in Numerical Linear Algebra
    Grey Ballard, James Demmel, Olga Holtz, and Oded Schwartz
    SIAM Journal on Matrix Analysis and Applications (SIMAX). 32(3): 866-901, 2011.
    Awarded the 2012 SIAG/LA Best Paper Prize for the years 2009-2011.

  • Colorful Strips
    Greg Aloupis, Jean Cardinal, Sébastien Collette, Shinji Imahori, Matias Korman, Stefan Langerman, Oded Schwartz, Shakhar Smorodinsky, and Perouz Taslakian.
    Invited to Special Issue of Graphs and Combinatorics 27(3): 327-339, Springer, 2011.

  • Communication-Optimal Parallel and Sequential Cholesky Decomposition
    Grey Ballard, James Demmel, Olga Holtz, and Oded Schwartz
    SIAM Journal on Scientific Computing (SISC), 32(6): 3495-3523, 2010.

  • Quantum Expanders: Motivation and Constructions
    Avi Ben-Aroya, Oded Schwartz, and Amnon Ta-Shma.
    Theory of Computing, 6(1): 47-79, 2010.

  • Cooperative TSP
    Adi Avidor, Amitai Armon, and Oded Schwartz.
    Theoretical Computer Science, 411: 2847-2863, 2010.

  • An Elementary Construction of Constant Degree Expanders
    Noga Alon, Oded Schwartz, and Asaf Shapira.
    Combinatorics, Probability and Computing, 17: 319-327, 2008.

  • On the Complexity of Approximating k-Set-Packing
    Elad Hazan, Muli Safra, and Oded Schwartz.
    Computational Complexity, 15(1): 20-39, 2006.

  • On the Complexity of Approximating TSP with Neighborhoods and Related Problems
    Muli Safra and Oded Schwartz.
    Computational Complexity, 14(4): 281-307, 2006.

    • Refereed Conference Articles

  • Communication Efficient Gaussian Elimination with Partial Pivoting using a Shape Morphing Data Layout
    Grey Ballard, James Demmel, Ben Lipshitz, Oded Schwartz, and Sivan Toledo.
    In SPAA'13: Proceedings of the 25th ACM Symposium on Parallelism in Algorithms and Architectures, (to appear) 2013.

  • Communication Optimal Parallel Multiplication of Sparse Random Matrices
    Grey Ballard, Aydin Buluç, James Demmel, Laura Grigori, Ben Lipshitz, Oded Schwartz, and Sivan Toledo.
    In SPAA'13: Proceedings of the 25th ACM Symposium on Parallelism in Algorithms and Architectures, (to appear) 2013.

  • Implementing a Blocked Aasen's Algorithm with a Dynamic Scheduler on Multicore Architectures
    Grey Ballard, Dulceneia Becker, James Demmel, Jack Dongarra, Alex Druinsky, Inon Peled, Oded Schwartz, Sivan Toledo, and Ichitaro Yamazaki
    In IPDPS'13: Proceedings of the IEEE International Parallel & Distributed Processing Symposium, (to appear) 2013.
    (IPDPS'13 Best Paper Award).

  • Perfect Strong Scaling Using No Additional Energy
    James Demmel, Andrew Gerhart, Ben Lipshitz, and Oded Schwartz
    In IPDPS'13: Proceedings of the IEEE International Parallel & Distributed Processing Symposium, (to appear) 2013.

  • Communication-Optimal Parallel Recursive Rectangular Matrix Multiplication
    James Demmel, David Eliahu, Armando Fox, Shoaib Kamil, Ben Lipshitz, Oded Schwartz, and Omer Spillinger.
    In IPDPS'13: Proceedings of the IEEE International Parallel & Distributed Processing Symposium, (to appear) 2013.

  • Communication-Avoiding Parallel Strassen: Implementation and Performance
    Grey Ballard, James Demmel, Ben Lipshitz, and Oded Schwartz
    In SuperComputing'12: Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, 2012.

  • Delay-Doppler Channel Estimation in Almost Linear Complexity
    Alex Fish, Shamgar Gurevich, Ronny Hadani, Akbar Sayeed, and Oded Schwartz
    In ISIT'12: Proceedings of the IEEE International Symposium on Information Theory, pp. 2386-2390, 2012.

  • Communication-Optimal Parallel Algorithm for Strassen's Matrix Multiplication
    Grey Ballard, James Demmel, Olga Holtz, Ben Lipshitz, and Oded Schwartz
    In SPAA'12: Proceedings of the 24th ACM Symposium on Parallelism in Algorithms and Architectures, pp. 193-204, 2012.

  • Strong Scaling of Matrix Multiplication Algorithms and Memory-Independent Communication Lower Bounds (Brief Announcement)
    Grey Ballard, James Demmel, Olga Holtz, Ben Lipshitz, and Oded Schwartz
    In SPAA'12: Proceedings of the 24th ACM Symposium on Parallelism in Algorithms and Architectures, pp. 77-79, 2012.

  • Graph Expansion and Communication Costs of Fast Rectangular Matrix Multiplication
    Grey Ballard, James Demmel, Olga Holtz, Ben Lipshitz, and Oded Schwartz
    In MedAlg'12: Proceedings of the 1st Mediterranean Conference on Algorithms, pp. 13-36, 2012.

  • Graph Expansion and Communication Costs of Fast Matrix Multiplication
    Grey Ballard, James Demmel, Olga Holtz, and Oded Schwartz
    In SPAA'11: Proceedings of the 23th ACM Symposium on Parallelism in Algorithms and Architectures`, Pittsburgh, Pennsylvania, USA, pp. 1-12, 2011.
    (SPAA'11 Best Paper Award).

  • Colorful Strips
    Greg Aloupis, Jean Cardinal, Sébastien Collette, Shinji Imahori, Matias Korman, Stefan Langerman, Oded Schwartz, Shakhar Smorodinsky, and Perouz Taslakian.
    In LATIN'10: Proceedings of the 9th Latin American conference on Theoretical Informatics, Oaxaca, Mexico, pp. 2-13, 2010.

  • Communication-Optimal Parallel and Sequential Cholesky Decomposition
    Grey Ballard, James Demmel, Olga Holtz, and Oded Schwartz
    In SPAA'09: Proceedings of the 21st ACM Symposium on Parallelism in Algorithms and Architectures, pp. 245-252, Calgary, Canada, 2009.

  • Quantum Expanders: Motivation and Constructions
    Avi Ben-Aroya, Oded Schwartz, and Amnon Ta-Shma.
    In CCC'08: Proceedings of the 23rd IEEE Conference on Computational Complexity, pp. 292-303, College Park, Maryland, USA, 2008.

  • An Elementary Construction of Constant Degree Expanders
    Noga Alon, Oded Schwartz, and Asaf Shapira.
    In SODA'07: Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 319-327 , New Orleans, Louisiana, USA, 2007.

  • Cooperative TSP
    Adi Avidor, Amitai Armon, and Oded Schwartz.
    In ESA'06: Proceedings of the 14th Annual European Symposium on Algorithms, pp. 40-51, Zurich, Switzerland, 2006.

  • On the Complexity of Approximating k-Dimensional-Matching
    Elad Hazan, Muli Safra, and Oded Schwartz.
    In APPROX'03: Proceedings of the 6th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, pp. 59-70, Princeton, NY, USA, 2003.

  • On the Complexity of Approximating TSP with Neighborhoods and Related Problems
    Muli Safra and Oded Schwartz.
    In ESA'03: Proceedings of the 11th Annual European Symposium on Algorithms, pp. 446-458, Budapest, Hungary, 2003.

    • Submitted

  • Delay-Doppler Channel Estimation in Almost Linear Time (journal version)
    Alex Fish, Shamgar Gurevich, Ronny Hadani, Akbar Sayeed, and Oded Schwartz
    Submitted to IEEE Transactions on Information Theory, 2012.

    • Theses

  • Expansion and Approximability
    Advisors: Muli Safra and Amnon Ta-Shma.
    PhD thesis, Tel-Aviv University, June, 2008.

  • On the Hardness of Approximating TSP with Neighborhoods, Group TSP and Group Steiner Tree
    Advisor: Muli Safra.
    MSc thesis, Tel-Aviv University, 2002.


    • Work in Progress

  • Sequential Communication Bounds for Fast Linear Algebra
    Grey Ballard, James Demmel, Olga Holtz, and Oded Schwartz
    EECS Tech. Report No. UCB/EECS-2012-36, 2012.

  • Parallel Communication Bounds for Fast Linear Algebra
    Grey Ballard, James Demmel, Olga Holtz, Ben Lipshitz, and Oded Schwartz
    Work in progress, 2013.

  • Communication Efficient Gaussian Elimination with Partial Pivoting using a Shape Morphing Data Layout: Implementation and Performance
    Grey Ballard, James Demmel, Ben Lipshitz, Oded Schwartz, and Sivan Toledo.
    In preparation, 2013.

  • Communication Optimal Parallel Multiplication of Sparse Random Matrices: Implementation and Performance
    Grey Ballard, Aydin Buluç, James Demmel, Laura Grigori, Ben Lipshitz, Oded Schwartz, and Sivan Toledo.
    In preparation, 2013.

  • Communication-Avoiding Sparse Matrix-Matrix Multiplication
    Grey Ballard, Aydin Buluç, James Demmel, Laura Grigori, Ben Lipshitz, Oded Schwartz, and Sivan Toledo.
    Presented in SIAM-LA, 2012.

  • A Communication-Avoiding Symmetric-Indefinite Factorization
    Grey Ballard, Alex Druinsky, James Demmel, Inon Peled, Oded Schwartz and Sivan Toledo.
    Presented in SIAM-LA, 2012.

  • Stability Issues of Large-Scale Fast Matrix Multiplication
    Grey Ballard, James Demmel, Olga Holtz, Ben Lipshitz, and Oded Schwartz.
    Presented in IWASEP9, 2012.

  • On Finding the Sparsest Satisfying Solution
    Olga Holtz, Sadegh Jokar and Oded Schwartz.
    In preparation, 2013.

  • Communication Avoiding Sparse Fast Matrix Multiplication
    Grey Ballard, James Demmel, Olga Holtz, Ben Lipshitz, and Oded Schwartz.
    In preparation, 2013.

  • Colorful Strips in High Dimension
    Oded Schwartz and Shakhar Smorodinsky.
    In preparation, 2013.

  • Parallelizing Channel Estimation
    Alex Fish, Shamgar Gurevich, Ronny Hadani, Akbar Sayeed, and Oded Schwartz.
    In preparation, 2013.

  • Communication Costs of Schönhage-Strassen Fast Integer Multiplication
    Derrick Coetzee, James Demmel, and Oded Schwartz.
    In preparation, 2013.

    • Posters

  • Beating MKL and ScaLapack at Rectangular Matrix Multiplication Using the BFS/DFS Approach
    James Demmel, David Eliahu, Armando Fox, Shoaib Kamil, Ben Lipshitz, Oded Schwartz, and Omer Spillinger.
    SuperComputing'12: International Conference for High Performance Computing Networking, Storage and Analysis, Salt Lake City, Utah, USA, 2012.
    A preliminary version of this poster appeared in Parlab retreat, 2012 (next item).

  • Towards Automated Parallelization of Recursive Algorithms in SEJITS: Beating MKL's Matrix Multiplication Using the BFS/DFS Approach
    James Demmel, David Eliahu, Armando Fox, Ben Lipshitz, Oded Schwartz, and Omer Spillinger.
    Parlab retreat, 2012.

  • Communication-Avoiding Parallel Strassen: Implementation and Performance
    Grey Ballard, James Demmel, Ben Lipshitz, and and Oded Schwartz
    Parlab retreat, 2012.

  • Communication Costs of Schönhage-Strassen Fast Integer Multiplication
    Derrick Coetzee, James Demmel, and Oded Schwartz.
    Parlab retreat, 2011.

  • Communication-Optimal Parallel Algorithm for Strassen's Matrix Multiplication
    Grey Ballard, James Demmel, Ben Lipshitz, and Oded Schwartz.
    Parlab retreat, 2011.

  • Graph Expansion and Communication Costs of Fast Matrix Multiplication
    Grey Ballard, James Demmel, Olga Holtz, and Oded Schwartz
    Parlab retreat, 2011.