About Me
I am a researcher broadly interested in theoretical computer science. My specific research interests include fine-grained complexity and algorithm design, computational problems related to additive combinatorics, string algorithms, and algebraic methods.
Currently, I am a postdoc at INSAIT, Bulgaria. Before, I was a postdoc at Weizmann Institute of Science, where I was hosted by Amir Abboud. Before that, I have completed my undergrad and PhD at Saarland University and Max Planck Institute for Informatics, advised by Karl Bringmann.
Publications
Recognizing Sumsets is NP-Complete
Beating Bellman's Algorithm for Subset Sum
Sumsets, 3SUM, Subset Sum: Now for Real!
New Applications of 3SUM-Counting in Fine-Grained Complexity and Pattern Matching
A Simple Parallel Algorithm with Near-Linear Work for Negative-Weight Single-Source Shortest Paths
Minimizing Tardy Processing Time on a Single Machine in Near-Linear Time
New Graph Decompositions and Combinatorial Boolean Matrix Multiplication Algorithms
Deterministic 3SUM-Hardness
The Time Complexity of Fully Sparse Matrix Multiplication
Faster Sublinear-Time Edit Distance
Dynamic Dynamic Time Warping
The Effect of Sparsity on k-Dominating Set and Related First-Order Graph Properties
Deterministic Sparse Pattern Matching via the Baur-Strassen Theorem
Negative-Weight Single-Source Shortest Paths in Near-Linear Time: Now Faster!
Can You Solve Closest String Faster than Exhaustive Search?
Stronger 3-SUM Lower Bounds for Approximate Distance Oracles via Additive Combinatorics
Improved Sublinear-Time Edit Distance for Preprocessed Strings
A Structural Investigation of the Approximability of Polynomial-Time Problems
Almost-Optimal Sublinear-Time Edit Distance in the Low Distance Regime
Deterministic and Las Vegas Algorithms for Sparse Nonnegative Convolution
Fine-Grained Completeness for Optimization in P
Sparse Nonnegative Convolution Is Equivalent to Dense Nonnegative Convolution
Faster Minimization of Tardy Processing Time on a Single Machine
A Fine-Grained Analogue of Schaefer’s Theorem in P: Dichotomy of Exists^k-Forall-Quantified First-Order Graph Properties