2 citations · 3 across the 16 of their papers we have counts for
10 papers · 1 filter
Optimal Sparsifiers for Minkowski Sums and Sums of Seminorms
Arpon Basu, Joshua Brakensiek, Yeyuan Chen +3
We extend the recent work of Reis and Rothvoss on sparsifying sums of norms to the more general task of sparsifying (Minkowski) sums of centrally symmetric, convex sets. A…
Weighted Equitability and Matroid-Constrained Discrepancy
Kristóf Bérczi, Siyue Liu, Victor Reis +1
We prove weighted matroid equitability. Let be a matroid whose ground set can be partitioned into bases, and assign a nonnegative weight to every element. T…
Weighted Chairman Assignment and Flow-Time Scheduling
Siyue Liu, Victor Reis
Given positive integers , a fractional assignment and weights , we show that there exists an assignment $y \in \{0,1\}^{m…
A Randomized Rounding Approach for DAG Edge Deletion
Sina Kalantarzadeh, Nathan Klein, Victor Reis
In the DAG Edge Deletion problem, we are given an edge-weighted directed acyclic graph and a parameter , and the goal is to delete the minimum weight set of edges so that the re…
Optimal Online Discrepancy Minimization
Janardhan Kulkarni, Victor Reis, Thomas Rothvoss
We prove that there exists an online algorithm that for any sequence of vectors with , arriving one at a time, decides random si…
Linear-Sized Sparsifiers via Near-Linear Time Discrepancy Theory
Arun Jambulapati, Victor Reis, Kevin Tian
Discrepancy theory provides powerful tools for producing higher-quality objects which "beat the union bound" in fundamental settings throughout combinatorics and computer science.…
A New Framework for Matrix Discrepancy: Partial Coloring Bounds via Mirror Descent
Daniel Dadush, Haotian Jiang, Victor Reis
Motivated by the Matrix Spencer conjecture, we study the problem of finding signed sums of matrices with a small matrix norm. A well-known strategy to obtain these signs is to prov…
A Tighter Relation Between Hereditary Discrepancy and Determinant Lower Bound
Haotian Jiang, Victor Reis
In seminal work, Lovász, Spencer, and Vesztergombi [European J. Combin., 1986] proved a lower bound for the hereditary discrepancy of a matrix in te…
Vector Balancing in Lebesgue Spaces
Victor Reis, Thomas Rothvoss
A tantalizing conjecture in discrete mathematics is the one of Komlós, suggesting that for any vectors there exist signs $x_1, \dots, x…
Linear Size Sparsifier and the Geometry of the Operator Norm Ball
Victor Reis, Thomas Rothvoss
The Matrix Spencer Conjecture asks whether given symmetric matrices in with eigenvalues in one can always find signs so that their signed sum…