Search

We introduce FrontierMath, a benchmark of hundreds of original, exceptionally challenging mathematics problems crafted and vetted by expert mathematicians. The questions cover most major branches of modern mathematics -- from computationally intensive problems in number theory and real analysis to abstract questions in algebraic geometry and category theory. Solving a typical problem requires multiple hours of effort from a researcher in the relevant branch of mathematics, and for the upper end questions, multiple days. FrontierMath uses new, unpublished problems and automated verification to reliably evaluate models while minimizing risk of data contamination. Current state-of-the-art AI models solve under 2% of problems, revealing a vast gap between AI capabilities and the prowess of the mathematical community. As AI systems advance toward expert-level mathematical abilities, FrontierMath offers a rigorous testbed that quantifies their progress.

While traditional federated learning (FL) typically focuses on a star topology where clients are directly connected to a central server, real-world distributed systems often exhibit hierarchical architectures. Hierarchical FL (HFL) has emerged as a promising solution to bridge this gap, leveraging aggregation points at multiple levels of the system. However, existing algorithms for HFL encounter challenges in dealing with multi-timescale model drift, i.e., model drift occurring across hierarchical levels of data heterogeneity. In this paper, we propose a multi-timescale gradient correction (MTGC) methodology to resolve this issue. Our key idea is to introduce distinct control variables to (i) correct the client gradient towards the group gradient, i.e., to reduce client model drift caused by local updates based on individual datasets, and (ii) correct the group gradient towards the global gradient, i.e., to reduce group model drift caused by FL over clients within the group. We analytically characterize the convergence behavior of MTGC under general non-convex settings, overcoming challenges associated with couplings between correction terms. We show that our convergence bound is immune to the extent of data heterogeneity, confirming the stability of the proposed algorithm against multi-level non-i.i.d. data. Through extensive experiments on various datasets and models, we validate the effectiveness of MTGC in diverse HFL settings. The code for this project is available at \href{https://github.com/wenzhifang/MTGC}{https://github.com/wenzhifang/MTGC}., Comment: Accepted to NeurIPS 2024

Federated learning (FL) encounters scalability challenges when implemented over fog networks that do not follow FL's conventional star topology architecture. Semi-decentralized FL (SD-FL) has proposed a solution for device-to-device (D2D) enabled networks that divides model cooperation into two stages: at the lower stage, D2D communications is employed for local model aggregations within subnetworks (subnets), while the upper stage handles device-server (DS) communications for global model aggregations. However, existing SD-FL schemes are based on gradient diversity assumptions that become performance bottlenecks as data distributions become more heterogeneous. In this work, we develop semi-decentralized gradient tracking (SD-GT), the first SD-FL methodology that removes the need for such assumptions by incorporating tracking terms into device updates for each communication layer. Our analytical characterization of SD-GT reveals upper bounds on convergence for non-convex, convex, and strongly-convex problems. We show how the bounds enable the development of an optimization algorithm that navigates the performance-efficiency trade-off by tuning subnet sampling rate and D2D rounds for each global training interval. Our subsequent numerical evaluations demonstrate that SD-GT obtains substantial improvements in trained model quality and communication cost relative to baselines in SD-FL and gradient tracking on several datasets., Comment: This paper is under review in IEEE/ACM Transactions on Networking

We present the problems and solutions to the 12th Annual USA Junior Mathematical Olympiad., Comment: arXiv admin note: substantial text overlap with arXiv:2406.09518

We present the problems and solutions to the 61st Annual International Mathematical Olympiad

While federated learning (FL) eliminates the transmission of raw data over a network, it is still vulnerable to privacy breaches from the communicated model parameters. In this work, we propose Multi-Tier Federated Learning with Multi-Tier Differential Privacy (M^2FDP), a DP-enhanced FL methodology for jointly optimizing privacy and performance in hierarchical networks. One of the key concepts of M^2FDP is to extend the concept of HDP towards Multi-Tier Differential Privacy (MDP), while also adapting DP noise injection at different layers of an established FL hierarchy -- edge devices, edge servers, and cloud servers -- according to the trust models within particular subnetworks. We conduct a comprehensive analysis of the convergence behavior of M^2FDP, revealing conditions on parameter tuning under which the training process converges sublinearly to a finite stationarity gap that depends on the network hierarchy, trust model, and target privacy level. Subsequent numerical evaluations demonstrate that M^2FDP obtains substantial improvements in these metrics over baselines for different privacy budgets, and validate the impact of different system configurations.

Federated learning (FL) encounters scalability challenges when implemented over fog networks. Semi-decentralized FL (SD-FL) proposes a solution that divides model cooperation into two stages: at the lower stage, device-to-device (D2D) communications is employed for local model aggregations within subnetworks (subnets), while the upper stage handles device-server (DS) communications for global model aggregations. However, existing SD-FL schemes are based on gradient diversity assumptions that become performance bottlenecks as data distributions become more heterogeneous. In this work, we develop semi-decentralized gradient tracking (SD-GT), the first SD-FL methodology that removes the need for such assumptions by incorporating tracking terms into device updates for each communication layer. Analytical characterization of SD-GT reveals convergence upper bounds for both non-convex and strongly-convex problems, for a suitable choice of step size. We employ the resulting bounds in the development of a co-optimization algorithm for optimizing subnet sampling rates and D2D rounds according to a performance-efficiency trade-off. Our subsequent numerical evaluations demonstrate that SD-GT obtains substantial improvements in trained model quality and communication cost relative to baselines in SD-FL and gradient tracking on several datasets., Comment: This paper is accepted for publication in the proceedings of 2024 IEEE International Conference on Computer Communications (INFOCOM)

The demand of high-resolution video contents has grown over the years. However, the delivery of high-resolution video is constrained by either computational resources required for rendering or network bandwidth for remote transmission. To remedy this limitation, we leverage the eye trackers found alongside existing augmented and virtual reality headsets. We propose the application of video super-resolution (VSR) technique to fuse low-resolution context with regional high-resolution context for resource-constrained consumption of high-resolution content without perceivable drop in quality. Eye trackers provide us the gaze direction of a user, aiding us in the extraction of the regional high-resolution context. As only pixels that falls within the gaze region can be resolved by the human eye, a large amount of the delivered content is redundant as we can't perceive the difference in quality of the region beyond the observed region. To generate a visually pleasing frame from the fusion of high-resolution region and low-resolution region, we study the capability of a deep neural network of transferring the context of the observed region to other regions (low-resolution) of the current and future frames. We label this task a Foveated Video Super-Resolution (FVSR), as we need to super-resolve the low-resolution regions of current and future frames through the fusion of pixels from the gaze region. We propose Cross-Resolution Flow Propagation (CRFP) for FVSR. We train and evaluate CRFP on REDS dataset on the task of 8x FVSR, i.e. a combination of 8x VSR and the fusion of foveated region. Departing from the conventional evaluation of per frame quality using SSIM or PSNR, we propose the evaluation of past foveated region, measuring the capability of a model to leverage the noise present in eye trackers during FVSR. Code is made available at https://github.com/eugenelet/CRFP., Comment: 12 pages, 8 figures, to appear in IEEE/CVF Winter Conference on Applications of Computer Vision (WACV) 2023

Remote heart rate estimation is the measurement of heart rate without any physical contact with the subject and is accomplished using remote photoplethysmography (rPPG) in this work. rPPG signals are usually collected using a video camera with a limitation of being sensitive to multiple contributing factors, e.g. variation in skin tone, lighting condition and facial structure. End-to-end supervised learning approach performs well when training data is abundant, covering a distribution that doesn't deviate too much from the distribution of testing data or during deployment. To cope with the unforeseeable distributional changes during deployment, we propose a transductive meta-learner that takes unlabeled samples during testing (deployment) for a self-supervised weight adjustment (also known as transductive inference), providing fast adaptation to the distributional changes. Using this approach, we achieve state-of-the-art performance on MAHNOB-HCI and UBFC-rPPG., Comment: 26 pages, 10 figures, accepted by European Conference on Computer Vision (ECCV) 2020

An orthomorphism is a permutation $\sigma$ of $\{1, \dots, n-1\}$ for which $x + \sigma(x) \mod n$ is also a permutation on $\{1, \dots, n-1\}$. Eberhard, Manners, Mrazovi\'c, showed that the number of such orthomorphisms is $(\sqrt{e} + o(1)) \cdot \frac{n!^2}{n^n}$ for odd $n$ and zero otherwise. In this paper we prove two analogs of these results where $x+\sigma(x)$ is replaced by $x \sigma(x)$ (a "multiplicative orthomorphism") or with $x^{\sigma(x)}$ (an "exponential orthomorphism"). Namely, we show that no multiplicative orthomorphisms exist for $n > 2$ but that exponential orthomorphisms exist whenever $n$ is twice a prime $p$ such that $p-1$ is squarefree. In the latter case we then estimate the number of exponential orthomorphisms., Comment: 11 pages, 1 figure

Given a finite poset $\mathcal P$ and two distinct elements $x$ and $y$, we let $\operatorname{pr}_{\mathcal P}(x \prec y)$ denote the fraction of linear extensions of $\mathcal P$ in which $x$ precedes $y$. The balance constant $\delta(\mathcal P)$ of $\mathcal P$ is then defined by \[ \delta(\mathcal P) = \max_{x \neq y \in \mathcal P} \min \left\{ \operatorname{pr}_{\mathcal P}(x \prec y), \operatorname{pr}_{\mathcal P}(y \prec x) \right\}. \] The $1/3$-$2/3$ conjecture asserts that $\delta(\mathcal P) \ge \frac13$ whenever $\mathcal P$ is not a chain, but except from certain trivial examples it is not known when equality occurs, or even if balance constants can approach $1/3$. In this paper we make some progress on the conjecture by exhibiting a sequence of posets with balance constants approaching $\frac{1}{32}(93-\sqrt{6697}) \approx 0.3488999$, answering a question of Brightwell. These provide smaller balance constants than any other known nontrivial family., Comment: 11 pages, 4 figures. Latest version fixed a small typo reported by A Gudibanda in July 2017, and is otherwise unchanged

For integers $a_1, \dots, a_n \ge 0$ and $k \ge 1$, let $\mathcal L_{k+2}(a_1, \dots, a_n)$ denote the set of permutations of $\{1, \dots, a_1+\dots+a_n\}$ whose descent set is contained in $\{a_1, a_1+a_2, \dots, a_1+\dots+a_{n-1}\}$, and which avoids the pattern $12\dots(k+2)$. We exhibit some bijections between such sets, most notably showing that $\# \mathcal L_{k+2} (a_1, \dots, a_n)$ is symmetric in the $a_i$ and is in fact Schur-concave. This generalizes a set of equivalences observed by Mei and Wang., Comment: 11 pages, incorporated suggestions and corrections from anonymous referee

We present two families of Wilf-equivalences for consecutive and quasi-consecutive vincular patterns. These give new proofs of the classification of consecutive patterns of length $4$ and $5$. We then prove additional equivalences to explicitly classify all quasi-consecutive patterns of length $5$ into 26 Wilf-equivalence classes., Comment: 20 pages. Reformatted for DMTCS overlay journal

A coloring of the $\ell$-dimensional faces of $Q_n$ is called $d$-polychromatic if every embedded $Q_d$ has every color on at least one face. Denote by $p^\ell(d)$ the maximum number of colors such that any $Q_n$ can be colored in this way. We provide a new lower bound on $p^\ell(d)$ for $\ell > 1$., Comment: 10 pages

Let $k$ be a number field with cyclotomic closure $k^{\mathrm{cyc}}$, and let $h \in k^{\mathrm{cyc}}(x)$. For $A \ge 1$ a real number, we show that \[ \{ \alpha \in k^{\mathrm{cyc}} : h(\alpha) \in \overline{\mathbb Z} \text{ has house at most } A \} \] is finite for many $h$. We also show that for many such $h$ the same result holds if $h(\alpha)$ is replaced by orbits $h(h(\cdots h(\alpha)))$. This generalizes a result proved by Ostafe that concerns avoiding roots of unity, which is the case $A=1$., Comment: 10 pages

Let $E_1$ and $E_2$ be $\overline{\mathbb{Q}}$-nonisogenous, semistable elliptic curves over $\mathbb{Q}$, having respective conductors $N_{E_1}$ and $N_{E_2}$ and both without complex multiplication. For each prime $p$, denote by $a_{E_i}(p) := p+1-\#E_i(\mathbb{F}_p)$ the trace of Frobenius. Under the assumption of the Generalized Riemann Hypothesis (GRH) for the convolved symmetric power $L$-functions $L(s, \mathrm{Sym}^i E_1\otimes\mathrm{Sym}^j E_2)$ where $i,j\in\{0,1,2\}$, we prove an explicit result that can be stated succinctly as follows: there exists a prime $p\nmid N_{E_1}N_{E_2}$ such that $a_{E_1}(p)a_{E_2}(p)<0$ and \[ p < \big( (32+o(1))\cdot \log N_{E_1} N_{E_2}\big)^2. \] This improves and makes explicit a result of Bucur and Kedlaya. Now, if $I\subset[-1,1]$ is a subinterval with Sato-Tate measure $\mu$ and if the symmetric power $L$-functions $L(s, \mathrm{Sym}^k E_1)$ are functorial and satisfy GRH for all $k \le 8/\mu$, we employ similar techniques to prove an explicit result that can be stated succinctly as follows: there exists a prime $p\nmid N_{E_1}$ such that $a_{E_1}(p)/(2\sqrt{p})\in I$ and \[ p < \left((21+o(1)) \cdot \mu^{-2}\log (N_{E_1}/\mu)\right)^2. \], Comment: 30 pages

Let $\mathcal{I} \subset \mathbb{N}$ be an infinite subset, and let $\{a_i\}_{i \in \mathcal{I}}$ be a sequence of nonzero real numbers indexed by $\mathcal{I}$ such that there exist positive constants $m, C_1$ for which $|a_i| \leq C_1 \cdot i^m$ for all $i \in \mathcal{I}$. Furthermore, let $c_i \in [-1,1]$ be defined by $c_i = \frac{a_i}{C_1 \cdot i^m}$ for each $i \in \mathcal{I}$, and suppose the $c_i$'s are equidistributed in $[-1,1]$ with respect to a continuous, symmetric probability measure $\mu$. In this paper, we show that if $\mathcal{I} \subset \mathbb{N}$ is not too sparse, then the sequence $\{a_i\}_{i \in \mathcal{I}}$ fails to obey Benford's Law with respect to arithmetic density in any sufficiently large base, and in fact in any base when $\mu([0,t])$ is a strictly convex function of $t \in (0,1)$. Nonetheless, we also provide conditions on the density of $\mathcal{I} \subset \mathbb{N}$ under which the sequence $\{a_i\}_{i \in \mathcal{I}}$ satisfies Benford's Law with respect to logarithmic density in every base. As an application, we apply our general result to study Benford's Law-type behavior in the leading digits of Frobenius traces of newforms of positive, even weight. Our methods of proof build on the work of Jameson, Thorner, and Ye, who studied the particular case of newforms without complex multiplication., Comment: 10 pages

Let $E/\mathbb{Q}$ be an elliptic curve with complex multiplication (CM), and for each prime $p$ of good reduction, let $a_E(p) = p + 1 - \#E(\mathbb{F}_p)$ denote the trace of Frobenius. By the Hasse bound, $a_E(p) = 2\sqrt{p} \cos \theta_p$ for a unique $\theta_p \in [0, \pi]$. In this paper, we prove that the least prime $p$ such that $\theta_p \in [\alpha, \beta] \subset [0, \pi]$ satisfies \[ p \ll \left(\frac{N_E}{\beta - \alpha}\right)^A, \] where $N_E$ is the conductor of $E$ and the implied constant and exponent $A > 2$ are absolute and effectively computable. Our result is an analogue for CM elliptic curves of Linnik's Theorem for arithmetic progressions, which states that the least prime $p \equiv a \pmod q$ for $(a,q)=1$ satisfies $p \ll q^L$ for an absolute constant $L > 0$., Comment: 11 pages; made minor modifications