[LOGO] The Weizmann Institute of Science
Faculty of Mathematics and Computer Science

Robert Krauthgamer (רוברט קראוטגמר)

Faculty member
Faculty of Mathematics and Computer Science
The Weizmann Institute of Science

Jump to Research ~ Service ~ Teaching ~ Students ~ Links ~ Contact


Interests. I am mostly interested in Analysis of Algorithms. Some more specific areas are: Data Analysis and Massive Data Sets, Combinatorial Optimization, Approximation Algorithms and Hardness of Approximation Average-case Analysis and Heuristics, Embeddings of Finite Metrics, Routing and Peer to Peer networks. I also have a broad general interest in Discrete Mathematics and High-Dimensional Geometry.

Publications. Most of my papers are available online: Chronologically or by keyword.
It includes slides of additional talks (e.g. more introductory).


Journal Editorial.
SIAM Journal on Computing (SICOMP), Associate Editor (since 2012).
Theory of Computing, an open-access journal, Managing Editor (since 2007), and Editorial Board Member (2004-2007).

Conferences Program Committees. ESA 2017, IPDPS 2017, FOCS 2016, HALG 2016, SODA 2016 (PC chair), SIMBAD 2015, SODA 2015, ICALP 2014, SIMBAD 2013, STOC 2013, ICML 2012, ITCS 2012, SIMBAD 2011, APPROX 2011, SODA 2010, APPROX 2009, APPROX 2007, STOC 2007, RANDOM 2005, STOC 2004, APPROX 2003.

List of accepted papers to SODA 2016 and accepted papers with abstracts. Here is a version with with links to full papers (when available publicly).

Workshop Organization. Sublinear Algorithms (Johns Hopkins 2016), Sublinear Algorithms (Bertinoro 2014), Weizmann-Warwick Meeting 2012, Warwick-Weizmann 2011 workshop, Sublinear Algorithms (Bertinoro 2011), Weizmann-Warwick Meeting 2010.

Seminar Coordinator. Computer Science seminar, and (joint with Moni Naor) also Foundations of computer science (aka theory) seminar.

Other. Steering Committee member, Highlights of Algorithms conference (HALG 2016).
Organizer of the Reading Group in Algorithms (email me to join the mailing list). The relevant papers are accessible only from weizmann, due to copyright.
Organizer of TheoryLunch (email me to join the mailing list).
Coordinator of Ulpanot de Shalit in Mathematics and Computer Science (2011-2012, joint with Dmitry Novikov), a workshop for select undergraduate students.
Coordinator of Ulpanot de Shalit in Mathematics and Computer Science (2015, joint with Shahar Dobzinski and Dima Gourevitch), a workshop for select undergraduate students.
Treasurer of the Israel Mathematical Union (2009-2010).



MSc Students.
Yevgeny Levanzov, current.
Yosef Pogrow, current.
Otniel van Handel, 2016, Vertex Cover Approximation in Data Streams.
Chen Attias, 2016 (supervised jointly with Retsef Levi, MIT), Combinatorial Optimization Problems with Testing.
Noa Loewenthal, 2014, Exploiting temporal information for detecting communities in social networks.
Dmitry Kogan, 2014, Sketching Cuts in Graphs and Hypergraphs.
Inbal Rika, 2013, Mimicking Networks and Succinct Representations of Terminal Cuts.
Nimrod Talmon, 2012, Selection in the Presence of Memory Faults, With Applications to In-place Resilient Sorting.
Tamar Zondiner, 2012, Eliminating Steiner Vertices in Graph Metrics.

PhD Students.
Chen Attias, current (supervised jointly with Boaz Nadler).
Ohad Trabelsi, current (supervised jointly with Eden Chlamtac, BGU).
Inbal Rika, current.
Arnold Filtser, current (at BGU, supervised jointly with Ofer Neiman).
Lior Kamma, current.

Nimrod Talmon, 2015-today.
Bundit Laekhanukit, 2015-today (jointly with Uriel Feige).
Rajesh Chitnis, 2014-today (jointly with Uriel Feige).
Gilad Tsur, 2011-2013.
Tsvi Kopelowitz, 2011-2013.
Michael Dinitz, 2010-2013 (jointly with David Peleg).
Lee-Ad Gottlieb, 2008-2010.


Local events:

Local groups, seminars, etc.

Theoretical Computer Science Resources

Other links


Office: Ziskind Building #222
Phone: 08-9344281
Fax: 08-9344122 (to my attention)
Mailing Address: Faculty of Mathematics and Computer Science, The Weizmann Institute of Science, 234 Herzel St., P.O.B. 26, Rehovot 76100, ISRAEL.
Email: robert.krauthgamer@weizmann.ac.il