Roy Schwartz

I am a postdoctoral research associate in the Department of Computer Science at Princeton University.

Previously I was a postdoctoral researcher in the Theory Group at Microsoft Research.

I completed my thesis under the supervision of Prof. Joseph (Seffi) Naor in the Department of Computer Science at the Technion - Israel Institute of Technology.

Research Interests

I am broadly interested in algorithms and combinatorial optimization, including:

- Design and analysis of algorithms
- Approximation algorithms and coping with NP-hardness
- The geometry of metric spaces and its applications
- Submodular optimization
- Randomized algorithms
- Practical applications

Publications

- Comparing Apples and Oranges: Query Tradeoff in Submodular Maximization.

Niv Buchbinder, Moran Feldman and Roy Schwartz.

Proceedings of the 26^{th}Annual ACM-SIAM Symposium on Discrete Algorithms, SODA15, San Diego, CA, USA, 2015.

- Online Submodular Maximization with Preemption.

Niv Buchbinder, Moran Feldman and Roy Schwartz.

Proceedings of the 26^{th}Annual ACM-SIAM Symposium on Discrete Algorithms, SODA15, San Diego, CA, USA, 2015.

- Discrepancy Without Partial Colorings. [pdf]

Nicholas J. A. Harvey, Roy Schwartz and Mohit Singh.

Proceedings of the 17^{th}International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX14, Barcelona, Spain, 2014.

- Calendaring for Wide Area Networks. [pdf]

Srikanth Kandula, Ishai Menache, Roy Schwartz and Spandana R. Babbula.

Proceedings of the Annual ACM Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, SIGCOMM14, Chicago, IL, USA, 2014.

- Non-Uniform Graph Partitioning. [pdf]

Robert Krauthgamer, Joseph (Seffi) Naor, Roy Schwartz and Kunal Talwar.

Proceedings of the 25^{th}Annual ACM-SIAM Symposium on Discrete Algorithms, SODA14, Portland, OR, USA, 2014.

- Submodular Maximization with Cardinality Constraints. [pdf]

Niv Buchbinder, Moran Feldman, Joseph (Seffi) Naor and Roy Schwartz.

Proceedings of the 25^{th}Annual ACM-SIAM Symposium on Discrete Algorithms, SODA14, Portland, OR, USA, 2014.

- On the Approximation of Submodular Functions. [pdf]

Nikhil R. Devanur, Shaddin Dughmi, Roy Schwartz, Ankit Sharma and Mohit Singh.

Arxiv, 2013.

- 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, USA, 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, NJ, USA, 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, CA, USA, 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, CA, USA, 2011.**Invited to SIAM Journal of Computing (SICOMP) FOCS11 Special Issue.**

SIAM Journal of Computing (SICOMP), Volume 43 Number 2, April 2014.

- 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, NJ, USA, 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, USA, 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, BC, 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, USA, 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, LA, USA, 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

Department of Computer Science

Princeton University

35 Olden Street, Princeton, NJ 08540-5233

e-mail: roysch AT cs DOT princeton DOT edu