Roie Levin

I am a second third year PhD student at Carnegie Mellon University. I am in the Theory Group within the Computer Science Department, though nominally my degree is in Algorithms, Combinatorics and Optimization (ACO). I am very fortunate to be advised by Anupam Gupta. I am broadly interested in theoretical computer science, more specifically in approximation algorithms for graph and network design problems. I am also interested in online/dynamic/streaming algorithms, and anything involving submodular functions.

Previously I worked at the Allen Institute for Artificial Intelligence from 2015 to 2017. I was a research engineer on the Euclid team.

Before that I received a B.Sc. in Computer Science/Applied Mathematics, and a B.Sc. in Mathematics from Brown University, class of 2015.

Publications

Finding Skewed Subcubes Under a Distribution

ITCS 2020
with Parikshit Gopalan, Udi Wieder
(to appear), arXiv

The Online Submodular Cover Problem

SODA 2020
with Anupam Gupta
(to appear)

Robust Subspace Approximation in a Stream

NeurIPS 2018
with Anish Sevekari, David P. Woodruff
pdf, full version, talk

Beyond Sentential Semantic Parsing: Tackling the Math SAT with a Cascade of Tree Transducers

EMNLP 2017
with Mark Hopkins, Cristian Petrescu-Prahova, Ronan Le Bras, Alvaro Herrasti, Vidur Joshi
pdf

FigureSeer: Parsing Result-Figures in Research Papers

ECCV 2016
with Noah Siegel, Zachary Horvitz, Santosh Kumar Divvala, Ali Farhadi
pdf

||||

Papers

Preprints

PTAS for MAP Assignment on Pairwise Markov Random Fields in Planar Graphs

2015
with Eli Fox-Epstein, David Meierfrankenfeld
arXiv

Teaching

Brown University

Head TA, Models of Computation (CS 51)

Fall 2014, under Anna Lysyanskaya

TA, Models of Computation (CS 51)

Fall 2013, under John Savage

TA, Accelerated Intro to Computer Science (CS 19)

Fall 2012, under Shriram Krishnamurthi

Contact

Office: Gates 9219

Email: [my first name][the letter ell]@cs.cmu.edu