Research
I work in the intersection of theoretical
computer science and discrete mathematics. In particular,
currently I am interested in approximation algorithms,
discrepancy theory and related questions in high
dimensional convex geometry.
Here is some recent work:
 Approximation algorithms.
For many problems, the naive linear programming
relaxation is too weak to find good approximations.
The SheraliAdams / Lasserre lift then provides a
systematic strengthening. For example in [Davies et
al. FOCS 2020] we can use this method to obtain
a O(log^2 n)approximation for scheduling with
precedence constraints and communication delays.
 Discrepancy theory. In the
geometric setting of discrepancy theory, one has a
concrete symmetric convex body K and asks for a
minimal scaling of s > 0, so that the body sK
contains a vector with {1,+1} entries. In [Reis, R.
SODA 2020], we considered the body K arising
from balancing matrices w.r.t. the operator norm and
prove that it must have high mean width. Then
this implies a new algorithm to find linearsize
spectral sparsifiers in graphs.
Lecture notes and expositions

Students
Current PhD advisees:
Graduated Ph.D.:
 Sami Davies (2021).
 Harishandra Ramadas (2017).
 Rebecca Hoberg (2017).
Graduated Ms.:
Awards
 Delbert Ray Fulkerson Prize
(2018)
 STOC 2014 Best Paper Prize
 SODA 2014 Best Paper Prize
 STOC 2010 Best Paper Prize
 Best Computer Science Graduate at
TU Dortmund (2007)
Selected Funding
 NSF CAREER grant (20172022)
 Packard Foundation Fellowship
(20162021)
 Sloan Research Fellowship
(20152017)
 Feodor Lynen postdoctoral
fellowship (20112012)
