Given positive integers m, n, a fractional assignment x ∈ [0,1]^{m × n} and weights d ∈ ℝⁿ_{> 0}, we show that there exists an assignment y ∈ {0,1}^{m × n} so that for every i ∈ [m] and t ∈ [n], |∑_{j ∈ [t]} d_j (x_{ij} - y_{ij})| < max_{j ∈ [n]} d_j. This generalizes a result of Tijdeman (1973) on the unweighted version, known as the chairman assignment problem. This also confirms a special case of the single-source unsplittable flow conjecture with arc-wise lower and upper bounds due to Morell and Skutella (IPCO 2020). As an application, we consider a scheduling problem where jobs have release times and machines have closing times, and a job can only be scheduled on a machine if it is released before the machine closes. We give a 3-approximation algorithm for maximum flow-time minimization.

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 resulting graph has no paths of length k. This problem, which has applications to scheduling, was introduced in 2015 by Kenkre, Pandit, Purohit, and Saket. They gave a k-approximation and showed that it is UGC-Hard to approximate better than ⌊0.5k⌋ for any constant k ≥ 4 using a work of Svensson from 2012. The approximation ratio was improved to 2/3(k+1) by Klein and Wexler in 2016. In this work, we introduce a randomized rounding framework based on distributions over vertex labels in [0,1]. The most natural distribution is to sample labels independently from the uniform distribution over [0,1]. We show this leads to a (2-√2)(k+1) ≈ 0.585(k+1)-approximation. By using a modified (but still independent) label distribution, we obtain a 0.549(k+1)-approximation for the problem, as well as show that no independent distribution over labels can improve our analysis to below 0.542(k+1). Finally, we show a 0.5(k+1)-approximation for bipartite graphs and for instances with structured LP solutions. Whether this ratio can be obtained in general is open.

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. While much research literature has focused on generating private unstructured text and image data, in enterprise settings, structured data (e.g., tabular) is more common, often including natural language fields or components. Existing synthetic data evaluation techniques (e.g., FID) struggle to capture the structural properties and correlations of such datasets. In this work, we propose Struct-Bench, a framework and benchmark for evaluating synthetic datasets derived from structured datasets that contain natural language data. The Struct-Bench framework requires users to provide a representation of their dataset structure as a Context-Free Grammar (CFG). Our benchmark comprises 5 real-world and 2 synthetically generated datasets. We show that these datasets demonstrably present a great challenge even for state-of-the-art DP synthetic data generation methods. Struct-Bench provides reference implementations of different metrics and a leaderboard, offering a standardized platform to benchmark and investigate privacy-preserving synthetic data methods. We also present a case study showing how Struct-Bench improves the synthetic data quality of Private Evolution (PE) on structured data. The benchmark and the leaderboard have been publicly made available at https://struct-bench.github.io.

Discrepancy theory has provided powerful tools for producing higher-quality objects which “beat the union bound” in fundamental settings throughout combinatorics and computer science. However, this quality has often come at the price of more computationally-expensive algorithms. We introduce a new framework for bridging this gap, by allowing for the efficient implementation of discrepancy-theoretic primitives. Our framework repeatedly solves regularized optimization problems to low accuracy to approximate the partial coloring method of [Rot17], and simplifies and generalizes recent work of [JSS23] on fast algorithms for Spencer's theorem. In particular, our framework only requires that the discrepancy body of interest has exponentially large Gaussian measure and is expressible as a sublevel set of a symmetric, convex function. We combine this framework with new tools for proving Gaussian measure lower bounds to give improved algorithms for a variety of sparsification and coloring problems.

We prove that there exists an online algorithm that for any sequence of vectors v1,…,vT ∈ ℝn with ||vi||2 ≤ 1, arriving one at a time, decides random signs x1,…,xT ∈ { −1,1} so that for every t ≤ T, the prefix sum ∑i=1t xivi is 10-subgaussian. This improves over the work of Alweiss, Liu and Sawhney who kept prefix sums O(√log(nT))-subgaussian, and gives a O(√logT) bound on the discrepancy maxt ∈ T ||∑i=1t xi vi||∞. Our proof combines a generalization of Banaszczyk’s prefix balancing result to trees with a cloning argument to find distributions rather than single colorings. We also show a matching Ω(√logT) strategy for an oblivious adversary.

The vector balancing constant $\operatorname{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 scaling of Q. A question raised by Schechtman is whether for any zonotope $K \subseteq \mathbb{R}^{d}$ one has $\operatorname{vb}(K, K) \lesssim \sqrt{d}$. Intuitively, this asks whether a natural geometric generalization of Spencer’s Theorem (for which $K=B_{\infty}^{d}$) holds. We prove that for any zonotope $K \subseteq \mathbb{R}^{d}$ one has $\operatorname{vb}(K, K) \lesssim \sqrt{d} \log \log \log d$. Our main technical contribution is a tight lower bound on the Gaussian measure of any section of a normalized zonotope, generalizing Vaaler’s Theorem for cubes. We also prove that for two different normalized zonotopes K and Q one has $\operatorname{vb}(K, Q) \lesssim \sqrt{d \log d}$. All the bounds are constructive and the corresponding colorings can be computed in polynomial time.

In a seminal paper, Kannan and Lovász (1988) considered a quantity $\mu_{K L}(\Lambda, K)$ which denotes the best volume-based lower bound on the covering radius $\mu(\Lambda, K)$ of a convex body K with respect to a lattice $\Lambda$. Kannan and Lovász proved that $\mu(\Lambda, K) \leq n \cdot \mu_{K L}(\Lambda, K)$ and the Subspace Flatness Conjecture by Dadush (2012) claims a $O(\log (2 n))$ factor suffices, which would match the lower bound from the work of Kannan and Lovász. We settle this conjecture up to a constant in the exponent by proving that $\mu(\Lambda, K) \leq$ $O\left(\log ^{3}(2 n)\right) \cdot \mu_{K L}(\Lambda, K)$. Our proof is based on the Reverse Minkowski Theorem due to Regev and Stephens-Davidowitz (2017). Following the work of Dadush $(2012,2019)$, we obtain a $(\log (2 n))^{O(n)}$-time randomized algorithm to solve integer programs in n variables. Another implication of our main result is a near-optimal flatness constant of $O\left(n \log ^{3}(2 n)\right)$.

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 prove, given matrices A1, …, An ∈ ℝm × m, a Gaussian measure lower bound of 2−O(n) for a scaling of the discrepancy body {x ∈ ℝn: || ∑i=1n xi Ai|| ≤ 1}. We show this is equivalent to covering its polar with 2O(n) translates of the cube 1/n B∞n, and construct such a cover via mirror descent. As applications of our framework, we show:

The Matrix Spencer Conjecture asks whether given n symmetric matrices in ℝn×n with eigenvalues in [–1, 1] one can always find signs so that their signed sum has singular values bounded by . The standard approach in discrepancy requires proving that the convex body of all good fractional signings is large enough. However, this question has remained wide open due to the lack of tools to certify measure lower bounds for rather small non-polyhedral convex sets. A seminal result by Batson, Spielman and Srivastava from 2008 shows that any undirected graph admits a linear size spectral sparsifier. Again, one can define a convex body of all good fractional signings. We can indeed prove that this body is close to most of the Gaussian measure. This implies that a discrepancy algorithm by the second author can be used to sample a linear size sparsifer. In contrast to previous methods, we require only a logarithmic number of sampling phases.