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 volume-based 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 d-dimensional
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 Sherali-Adams / 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 linear-size
spectral sparsifiers in graphs.
Lecture notes and expositions
|
Students
Current PhD advisees:
- Rainie Heck
- Mathews Boban
Graduated Ph.D.:
- Sally Dong (2024; co-advised with Yin Tat Lee)
- 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 (2023-2026)
- NSF CAREER grant (2017-2022)
- Packard Foundation Fellowship
(2016-2021)
- Sloan Research Fellowship
(2015-2017)
- Feodor Lynen post-doctoral
fellowship (2011-2012)
|
