Victor Reis

activity

20192026

most citedTight bounds on the Fourier growth of bounded functions on the hypercube

2 citations · 3 across the 16 of their papers we have counts for

collaborators

22 papers

math.MG2026

Strongly log-concave measures and lattices

Brayden Letwin, Victor Reis, Thomas Rothvoss

Let $Λ \subset R^{n}$ be a full rank lattice with the property that $det Γ \geq 1$ for all sublattices $Γ \subseteq Λ^{*}$ . We prove that there exists a symmetric random vector $…

math.CO2026

Three Standard Deviations Suffice While One Does Not

Victor Reis, Zhao Song

Spencer's 1985 ``six standard deviations suffice'' theorem shows that every $A \in [- 1, 1]^{n \times n}$ has a sign vector $x \in {- 1, 1}^{n}$ with $∥ A x ∥_{\infty} \leq 6 n$ . We…

cs.DS2026

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 $ℓ_{1}$ norms to the more general task of sparsifying (Minkowski) sums of centrally symmetric, convex sets. A…

cs.DS2026

Weighted Equitability and Matroid-Constrained Discrepancy

Kristóf Bérczi, Siyue Liu, Victor Reis +1

We prove weighted matroid equitability. Let $M = (E, I)$ be a matroid whose ground set can be partitioned into $k$ bases, and assign a nonnegative weight to every element. T…

math.MG2026

Linear-size $ℓ_{1}$ sparsifiers

Victor Reis, Thomas Rothvoss

We prove that for any matrix $A \in R^{m \times n}$ and any $ε > 0$ there is a diagonal matrix $D \in R_{\geq 0}^{m \times m}$ with at most $O(\frac{n}{…

cs.LG2026

Differentially Private Synthetic Data via APIs 4: Tabular Data

Toan Tran, Arturs Backurs, Zinan Lin +3

This paper investigates the problem of generating synthetic tabular data with differential privacy (DP) guarantees, enabling data sharing in sensitive domains. Despite extensive st…

math.MG2026

Optimal Vector Balancing for Zonotopes

Victor Reis

A zonotope is a linear image of the cube $[- 1, 1]^{m}$ for some $m \in N$ . We show that there is a universal constant $C$ such that, for every zonotope $Z\subset \mathbb{R}^d…

cs.DS2025

Weighted Chairman Assignment and Flow-Time Scheduling

Siyue Liu, Victor Reis

Given positive integers $m, n$ , a fractional assignment $x \in [0, 1]^{m \times n}$ and weights $d \in R_{> 0}^{n}$ , we show that there exists an assignment $y \in \{0,1\}^{m…

cs.CL2025

Struct-Bench: A Benchmark for Differentially Private Structured Text Generation

Shuaiqi Wang, Vikas Raunak, Arturs Backurs +7

Differentially private (DP) synthetic data generation is a promising technique for utilizing private datasets that otherwise cannot be exposed for model training or other analytics…

cs.DS2025

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 $k$ , and the goal is to delete the minimum weight set of edges so that the re…

cs.DS2023

Optimal Online Discrepancy Minimization

Janardhan Kulkarni, Victor Reis, Thomas Rothvoss

We prove that there exists an online algorithm that for any sequence of vectors $v_{1}, \dots, v_{T} \in R^{n}$ with $∥ v_{i} ∥_{2} \leq 1$ , arriving one at a time, decides random si…

cs.DS2023

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.…

math.OC2023★ 1 cited

The Subspace Flatness Conjecture and Faster Integer Programming

Victor Reis, Thomas Rothvoss

In a seminal paper, Kannan and Lovász (1988) considered a quantity $μ_{K L} (Λ, K)$ which denotes the best volume-based lower bound on the covering radius $μ (Λ, K)$ of a convex body $K…

math.MG2022

The Vector Balancing Constant for Zonotopes

Laurel Heck, Victor Reis, Thomas Rothvoss

The vector balancing constant $vb (K, Q)$ of two symmetric convex bodies $K, Q$ is the minimum $r \geq 0$ so that any number of vectors from $K$ can be balanced into an $r$ -s…

math.MG2022

Approximate Carathéodory bounds via Discrepancy Theory

Victor Reis, Thomas Rothvoss

The approximate Carathéodory problem in general form is as follows: Given two symmetric convex bodies $P, Q \subseteq R^{m}$ , a parameter $k \in N$ and $\mathbf{z} \…

cs.DS2021

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…

cs.DS2021

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 $A \in R^{m \times n}$ in te…

cs.CC2021★ 2 cited

Tight bounds on the Fourier growth of bounded functions on the hypercube

Siddharth Iyer, Anup Rao, Victor Reis +2

We give tight bounds on the degree $ℓ$ homogenous parts $f_{ℓ}$ of a bounded function $f$ on the cube. We show that if $f : {\pm 1}^{n} \to [- 1, 1]$ has degree $d$ , then…

math.CA2020

Balancing Polynomials in the Chebyshev Norm

Victor Reis

Given $n$ polynomials $p_{1}, \dots, p_{n}$ of degree at most $n$ with $∥ p_{i} ∥_{\infty} \leq 1$ for $i \in [n]$ , we show there exist signs $x_{1}, \dots, x_{n} \in {- 1, 1}$ so that \[\Big\|…

math.FA2020

An Elementary Exposition of Pisier's Inequality

Siddharth Iyer, Anup Rao, Victor Reis +2

Pisier's inequality is central in the study of normed spaces and has important applications in geometry. We provide an elementary proof of this inequality, which avoids some non-co…

cs.DS2020

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 $a_{1}, \dots, a_{n} \in B_{2}^{m}$ there exist signs $x_1, \dots, x…

cs.DS2019

Linear Size Sparsifier and the Geometry of the Operator Norm Ball

Victor Reis, Thomas Rothvoss

The Matrix Spencer Conjecture asks whether given $n$ symmetric matrices in $R^{n \times n}$ with eigenvalues in $[- 1, 1]$ one can always find signs so that their signed sum…

Strongly log-concave measures and lattices

Three Standard Deviations Suffice While One Does Not

Optimal Sparsifiers for Minkowski Sums and Sums of Seminorms

Weighted Equitability and Matroid-Constrained Discrepancy

Linear-size ℓ1​ sparsifiers

Differentially Private Synthetic Data via APIs 4: Tabular Data

Optimal Vector Balancing for Zonotopes

Weighted Chairman Assignment and Flow-Time Scheduling

Struct-Bench: A Benchmark for Differentially Private Structured Text Generation

A Randomized Rounding Approach for DAG Edge Deletion

Optimal Online Discrepancy Minimization

Linear-Sized Sparsifiers via Near-Linear Time Discrepancy Theory

The Subspace Flatness Conjecture and Faster Integer Programming

The Vector Balancing Constant for Zonotopes

Approximate Carathéodory bounds via Discrepancy Theory

A New Framework for Matrix Discrepancy: Partial Coloring Bounds via Mirror Descent

A Tighter Relation Between Hereditary Discrepancy and Determinant Lower Bound

Tight bounds on the Fourier growth of bounded functions on the hypercube

Balancing Polynomials in the Chebyshev Norm

An Elementary Exposition of Pisier's Inequality

Vector Balancing in Lebesgue Spaces

Linear Size Sparsifier and the Geometry of the Operator Norm Ball

Linear-size $ℓ_{1}$ sparsifiers