Source author record

Aaron Berger

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Data Structures and Algorithms Discrete Mathematics math.PR

Catalog footprint

Research overview

3works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2026arXiv

Anti-concentration with respect to random permutations

Classical anti-concentration results focus on the random sum $S := \sum _{i=1}^n ξ_i v_i$ , where $ξ_i$ are independent random variables and $v_i$ are real numbers. In this paper, we prove new concentration results concerning the random sum $S := \sum_{i=1}^n w_{π_i } v_i$ , where $w_i , v_i$ are real numbers and $π$ is a random permutation.

preprint2022arXiv

Memoryless Worker-Task Assignment with Polylogarithmic Switching Cost

We study the basic problem of assigning memoryless workers to tasks with dynamically changing demands. Given a set of $w$ workers and a multiset $T \subseteq[t]$ of $|T|=w$ tasks, a memoryless worker-task assignment function is any function $ϕ$ that assigns the workers $[w]$ to the tasks $T$ based only on the current value of $T$ . The assignment function $ϕ$ is said to have switching cost at most $k$ if, for every task multiset $T$ , changing the contents of $T$ by one task changes $ϕ(T)$ by at most $k$ worker assignments. The goal of memoryless worker task assignment is to construct an assignment function with the smallest possible switching cost. In past work, the problem of determining the optimal switching cost has been posed as an open question. There are no known sub-linear upper bounds, and after considerable effort, the best known lower bound remains 4 (ICALP 2020). We show that it is possible to achieve polylogarithmic switching cost. We give a construction via the probabilistic method that achieves switching cost $O(\log w \log (wt))$ and an explicit construction that achieves switching cost $\operatorname{polylog} (wt)$ . We also prove a super-constant lower bound on switching cost: we show that for any value of $w$ , there exists a value of $t$ for which the optimal switching cost is $w$ . Thus it is not possible to achieve a switching cost that is sublinear strictly as a function of $w$ . Finally, we present an application of the worker-task assignment problem to a metric embeddings problem. In particular, we use our results to give the first low-distortion embedding from sparse binary vectors into low-dimensional Hamming space.

preprint2021arXiv

Popular differences for matrix patterns

The following combinatorial conjecture arises naturally from recent ergodic-theoretic work of Ackelsberg, Bergelson, and Best. Let $M_1$ , $M_2$ be $k\times k$ integer matrices, $G$ be a finite abelian group of order $N$ , and $A\subseteq G^k$ with $|A|\geαN^k$ . If $M_1$ , $M_2$ , $M_1-M_2$ , and $M_1+M_2$ are automorphisms of $G^k$ , is it true that there exists a popular difference $d \in G^k\setminus\{0\}$ such that $\#\{x \in G^k: x, x+M_1d, x+M_2d, x+(M_1+M_2)d \in A\} \ge (α^4-o(1))N^k.$ We show that this conjecture is false in general, but holds for $G = \mathbb{F}_p^n$ with $p$ an odd prime given the additional spectral condition that no pair of eigenvalues of $M_1M_2^{-1}$ (over $\overline{\mathbb{F}}_p$ ) are negatives of each other. In particular, the "rotated squares" pattern does not satisfy this eigenvalue condition, and we give a construction of a set of positive density in $(\mathbb{F}_5^n)^2$ for which that pattern has no nonzero popular difference. This is in surprising contrast to three-point patterns, which we handle over all compact abelian groups and which do not require an additional spectral condition.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.