Roie Levin

Google Scholar | Semantic Scholar | DBLP

I am a first second third fourth fifth 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 uncertain environments (e.g. online/dynamic/streaming models). I also like pretty much 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.


Random Order Set Cover is as Easy as Offline

FOCS 2021 (to appear)
with Anupam Gupta and Gregory Kehne
arXiv, talk, slides

Streaming Submodular Matching Meets the Primal-Dual Method

SODA 2021
with David Wajc
arXiv, doi, talk

Fully-Dynamic Submodular Cover with Bounded Recourse

FOCS 2020
with Anupam Gupta
arXiv, doi, long talk, short talk

Finding Skewed Subcubes Under a Distribution

ITCS 2020
with Parikshit Gopalan, Udi Wieder
arXiv, doi

The Online Submodular Cover Problem

SODA 2020
with Anupam Gupta
doi, talk

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, doi

FigureSeer: Parsing Result-Figures in Research Papers

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

|||| |||



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

with Eli Fox-Epstein, David Meierfrankenfeld


Carnegie Mellon University

TA, Undergraduate Complexity Theory

Fall 2020, with Venkatesan Guruswami

TA, Graduate Algorithms (15-750)

Spring 2020, with Anupam Gupta

Brown University

Head TA, Models of Computation (CS 51)

Fall 2014, with Anna Lysyanskaya

TA, Models of Computation (CS 51)

Fall 2013, with John Savage

TA, Accelerated Intro to Computer Science (CS 19)

Fall 2012, with Shriram Krishnamurthi


Office: Gates 9219

Email: [my first name][the letter ell]