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:
 Lattices. In [Reis, R.
2023] we prove that the volumebased lower bound
to the covering radius for any lattice w.r.t. any convex
body is within a O(log^3 n) factor of the real
covering radius. This implies that integer programs with
n variables can be solved in time (log n)^O(n).
 Convex
geometry. Schechtman posed the question whether
the vector balancing constant of any ddimensional
zonotope is O(d^1/2). In [Heck, Reis,
R 2022] we prove a bound of O(d^1/2 * log log
log d) matching the conjectured bound up to a
miniscule triple log factor.
 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.:
 Victor Reis (2023)
 Yihao Zhang (2022)
 Sami Davies (2021).
 Harishandra Ramadas (2017)
 Rebecca Hoberg (2017)
Graduated Ms.:
Awards
 FOCS 2023 Best Paper Prize
 Gödel Prize 2023
 IPCO 2023 Best Paper Prize
 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 SMALL (20232026)
 NSF CAREER grant (20172022)
 Packard Foundation Fellowship
(20162021)
 Sloan Research Fellowship
(20152017)
 Feodor Lynen postdoctoral
fellowship (20112012)
