Roy Schwartz

I am a post doctoral researcher at the Theory Group at Microsoft Research.
I recently completed my PhD under the supervision of Prof. Joseph (Seffi) Naor at the Department of Computer Science at the Technion - Israel Institute of Technology.

Research Interests

I am broadly interested in the theory of algorithms. Specific areas are:

• Design and analysis of algorithms
• Approximation algorithms
• Metric methods and their algorithmic applications
• Submodular optimization
• Randomized algorithms

Publications

• Simplex Partitioning via Exponential Clocks and the Multiway-Cut Problem. [pdf]
  Niv Buchbinder, Joseph (Seffi) Naor and Roy Schwartz.
  Proceedings of the 45^th Annual ACM Symposium on Theory of Computing, STOC13, Palo Alto, CA, U.S.A, 2013.
  
  
• All-or-Nothing Generalized Assignment with Application to Scheduling Advertising Campaigns. [pdf]
  Ron Adany, Moran Feldman, Elad Haramaty, Rohit Khandekar, Baruch Schieber, Roy Schwartz, Hadas Shachnai and Tami Tamir.
  Proceedings of the 16^th Conference on Integer Programming and Combinatorial Optimization, IPCO13, Valparaíso, Chile, 2013.
  
  
• Rank Quantization. [pdf]
  Ravi Kumar, Ronny Lempel, Roy Schwartz and Sergei Vassilvitskii.
  Proceedings of the 6^th ACM International Conference on Web Search and Data Mining, WSDM13, Rome, Italy, 2013.
  
  
• A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization. [pdf]
  Niv Buchbinder, Moran Feldman, Joseph (Seffi) Naor and Roy Schwartz.
  Proceedings of the 53^rd Annual IEEE Symposium on Foundations of Computer Science, FOCS12, New Brunswick, New Jersey, U.S.A, 2012.
  Invited to SIAM Journal of Computing (SICOMP) FOCS12 Special Issue.
  
  
• Unsupervised SVMs: On the Complexity of the Furthest Hyperplane Problem. [pdf]
  Zohar S. Karnin, Edo Liberty, Shachar Lovett, Roy Schwartz and Omri Weinstein.
  Proceedings of the 25^th Conference on Learning Theory , COLT12, Edinburgh, Scotland, 2012.
  
  
• A Unified Continuous Greedy Algorithm for Submodular Maximization. [pdf]
  Moran Feldman, Joseph (Seffi) Naor and Roy Schwartz.
  Proceedings of the 52^nd Annual IEEE Symposium on Foundations of Computer Science, FOCS11, Palm Springs, California, U.S.A, 2011.
  
  
• Min-Max Graph Partitioning and Small Set Expansion. [pdf]
  Nikhil Bansal, Uriel Feige, Robert Krauthgamer, Konstantin Makarychev, Viswanath Nagarajan, Joseph (Seffi) Naor and Roy Schwartz.
  Proceedings of the 52^nd Annual IEEE Symposium on Foundations of Computer Science, FOCS11, Palm Springs, California, U.S.A, 2011.
  Invited to SIAM Journal of Computing (SICOMP) FOCS11 Special Issue.
  
  
• Improved Approximations for k-Exchange Systems. [pdf]
  Moran Feldman, Joseph (Seffi) Naor, Roy Schwartz and Justin Ward.
  Proceedings of the 19^th Annual European Symposium on Algorithms, ESA11, Saarbrücken, Germany, 2011.
  
  
• Improved Competitive Ratios for Submodular Secretary Problems. [pdf]
  Moran Feldman, Joseph (Seffi) Naor and Roy Schwartz.
  Proceedings of the 14^th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX11, Princeton University, U.S.A, 2011.
  
  
• Nonmonotone Submodular Maximization via a Structural Continuous Greedy Algorithm. [pdf]
  Moran Feldman, Joseph (Seffi) Naor and Roy Schwartz.
  Proceedings of the 38^th International Colloquium on Automata, Languages and Programming, ICALP11, Zürich, Switzerland, 2011.
  
  
• Partitioning Graphs into Balanced Components. [pdf]
  Robert Krauthgamer, Joseph (Seffi) Naor and Roy Schwartz.
  Proceedings of the 20^th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA09, New-York, NY, U.S.A, 2009.
  
  
• SDP Gaps and UGC Hardness for multiway cut, 0-extension, and metric labeling. [pdf]
  Rajsekar Manokaran, Joseph (Seffi) Naor, Prasad Raghavendra and Roy Schwartz.
  Proceedings of the 40^th Annual ACM Symposium on Theory of Computing, STOC08, Victoria, British Columbia, Canada, 2008.
  
  
• Balanced Metric Labeling. [pdf]
  Joseph (Seffi) Naor and Roy Schwartz.
  Proceedings of the 37^th Annual ACM Symposium on Theory of Computing, STOC05, Baltimore, MD, U.S.A, 2005.
  
  
• The Directed Circular Arrangement Problem. [pdf]
  Joseph (Seffi) Naor and Roy Schwartz.
  Proceedings of the 15^th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA04, New-Orleans, Louisiana, U.S.A, 2004.
  ACM Transactions on Algorithms (TALG), Volume 6 Issue 3, June 2010.
  
  

PhD Thesis

• Labelings and Partitions of Graphs.
  PhD Thesis, Department of Computer Science, Technion - Israel Institute of Technology, June 2012.
  Advisor: Prof. Joseph (Seffi) Naor.

MSc Thesis

• Circular Arrangements.
  MSc Thesis, Department of Computer Science, Technion - Israel Institute of Technology, July 2003.
  Advisor: Prof. Joseph (Seffi) Naor.

Teaching

For a few years I was a lecturer in the course:

• 234247 - Algorithms 1

In the past I was a teaching assistant in the following courses:

• Advanced Topics in Algorithms
• Algorithmic Game Theory
• Algorithms 1
• Graph Algorithms
• Stochastic Models in Operations Research
• Probability M

Contact Information

Theory Group, Microsoft Research
One Microsoft Way, Redmond, WA 98052

Office: Building 99/2935
Telephone: (425)707-8765
e-mail: roysch AT microsoft DOT com