Search

Sumsets are central objects in additive combinatorics. In 2007, Granville asked whether one can efficiently recognize whether a given set $S$ is a sumset, i.e. whether there is a set $A$ such that $A+A=S$. Granville suggested an algorithm that takes exponential time in the size of the given set, but can we do polynomial or even linear time? This basic computational question is indirectly asking a fundamental structural question: do the special characteristics of sumsets allow them to be efficiently recognizable? In this paper, we answer this question negatively by proving that the problem is NP-complete. Specifically, our results hold for integer sets and over any finite field. Assuming the Exponential Time Hypothesis, our lower bound becomes $2^{\Omega(n^{1/4})}$., Comment: Corrected a reference. To appear at SODA 2025

A tournament is an orientation of a complete graph. A vertex that can reach every other vertex within two steps is called a \emph{king}. We study the complexity of finding $k$ kings in a tournament graph. We show that the randomized query complexity of finding $k \le 3$ kings is $O(n)$, and for the deterministic case it takes the same amount of queries (up to a constant) as finding a single king (the best known deterministic algorithm makes $O(n^{3/2})$ queries). On the other hand, we show that finding $k \ge 4$ kings requires $\Omega(n^2)$ queries, even in the randomized case. We consider the RAM model for $k \geq 4$. We show an algorithm that finds $k$ kings in time $O(kn^2)$, which is optimal for constant values of $k$. Alternatively, one can also find $k \ge 4$ kings in time $n^{\omega}$ (the time for matrix multiplication). We provide evidence that this is optimal for large $k$ by suggesting a fine-grained reduction from a variant of the triangle detection problem.

This paper presents an integrated approach to Visual SLAM, merging online sequential photometric calibration within a Hybrid direct-indirect visual SLAM (H-SLAM). Photometric calibration helps normalize pixel intensity values under different lighting conditions, and thereby improves the direct component of our H-SLAM. A tangential benefit also results to the indirect component of H-SLAM given that the detected features are more stable across variable lighting conditions. Our proposed photometrically calibrated H-SLAM is tested on several datasets, including the TUM monoVO as well as on a dataset we created. Calibrated H-SLAM outperforms other state of the art direct, indirect, and hybrid Visual SLAM systems in all the experiments. Furthermore, in online SLAM tested at our site, it also significantly outperformed the other SLAM Systems.

Real-time SLAM with dense 3D mapping is computationally challenging, especially on resource-limited devices. The recent development of 3D Gaussian Splatting (3DGS) offers a promising approach for real-time dense 3D reconstruction. However, existing 3DGS-based SLAM systems struggle to balance hardware simplicity, speed, and map quality. Most systems excel in one or two of the aforementioned aspects but rarely achieve all. A key issue is the difficulty of initializing 3D Gaussians while concurrently conducting SLAM. To address these challenges, we present Monocular GSO (MGSO), a novel real-time SLAM system that integrates photometric SLAM with 3DGS. Photometric SLAM provides dense structured point clouds for 3DGS initialization, accelerating optimization and producing more efficient maps with fewer Gaussians. As a result, experiments show that our system generates reconstructions with a balance of quality, memory efficiency, and speed that outperforms the state-of-the-art. Furthermore, our system achieves all results using RGB inputs. We evaluate the Replica, TUM-RGBD, and EuRoC datasets against current live dense reconstruction systems. Not only do we surpass contemporary systems, but experiments also show that we maintain our performance on laptop hardware, making it a practical solution for robotics, A/R, and other real-time applications., Comment: Paper Contribution to the ICRA 2025 Conference. Currently being reviewed

We show the following result: If $X_0$ is an affine surface over a field $K$ and $f, g$ are two loxodromic automorphisms with an orbit meeting infinitely many times, then $f$ and $g$ must share a common iterate. The proof uses the preliminary work of the author in [Abb23] on the dynamics of endomorphisms of affine surfaces and arguments from arithmetic dynamics. We then show a dynamical Mordell-Lang type result for surfaces in $X_0 \times X_0$.

We show that two automorphisms of an affine surface with dynamical degree strictly larger than 1 share a Zariski dense set of periodic points if and only if they have the same periodic points. We construct canonical heights for these automorphisms and use arithmetic equidistribution for adelic line bundles over quasiprojective varieties following the work of Yuan and Zhang. Finally, we extend the local arithmetic Hodge index theorem to a certain class of vertical adelic line bundles over quasiprojective varieties to conclude the proof.

Efficiently quantifying predictive uncertainty in medical images remains a challenge. While Bayesian neural networks (BNN) offer predictive uncertainty, they require substantial computational resources to train. Although Bayesian approximations such as ensembles have shown promise, they still suffer from high training and inference costs. Existing approaches mainly address the costs of BNN inference post-training, with little focus on improving training efficiency and reducing parameter complexity. This study introduces a training procedure for a sparse (partial) Bayesian network. Our method selectively assigns a subset of parameters as Bayesian by assessing their deterministic saliency through gradient sensitivity analysis. The resulting network combines deterministic and Bayesian parameters, exploiting the advantages of both representations to achieve high task-specific performance and minimize predictive uncertainty. Demonstrated on multi-label ChestMNIST for classification and ISIC, LIDC-IDRI for segmentation, our approach achieves competitive performance and predictive uncertainty estimation by reducing Bayesian parameters by over 95\%, significantly reducing computational expenses compared to fully Bayesian and ensemble methods.

Federated Learning (FL) is an emerging machine learning paradigm that enables the collaborative training of a shared global model across distributed clients while keeping the data decentralized. Recent works on designing systems for efficient FL have shown that utilizing serverless computing technologies, particularly Function-as-a-Service (FaaS) for FL, can enhance resource efficiency, reduce training costs, and alleviate the complex infrastructure management burden on data holders. However, current serverless FL systems still suffer from the presence of stragglers, i.e., slow clients that impede the collaborative training process. While strategies aimed at mitigating stragglers in these systems have been proposed, they overlook the diverse hardware resource configurations among FL clients. To this end, we present Apodotiko, a novel asynchronous training strategy designed for serverless FL. Our strategy incorporates a scoring mechanism that evaluates each client's hardware capacity and dataset size to intelligently prioritize and select clients for each training round, thereby minimizing the effects of stragglers on system performance. We comprehensively evaluate Apodotiko across diverse datasets, considering a mix of CPU and GPU clients, and compare its performance against five other FL training strategies. Results from our experiments demonstrate that Apodotiko outperforms other FL training strategies, achieving an average speedup of 2.75x and a maximum speedup of 7.03x. Furthermore, our strategy significantly reduces cold starts by a factor of four on average, demonstrating suitability in serverless environments., Comment: Accepted at IEEE/ACM CCGrid'24

A recent paper by Abboud and Wallheimer [ITCS 2023] presents self-reductions for various fundamental graph problems, which transform worst-case instances to expanders, thus proving that the complexity remains unchanged if the input is assumed to be an expander. An interesting corollary of their self-reductions is that if some problem admits such reduction, then the popular algorithmic paradigm based on expander-decompositions is useless against it. In this paper, we improve their core gadget, which augments a graph to make it an expander while retaining its important structure. Our new core construction has the benefit of being simple to analyze and generalize while obtaining the following results: 1. A derandomization of the self-reductions, showing that the equivalence between worst-case and expander-case holds even for deterministic algorithms, and ruling out the use of expander-decompositions as a derandomization tool. 2. An extension of the results to other models of computation, such as the Fully Dynamic model and the Congested Clique model. In the former, we either improve or provide an alternative approach to some recent hardness results for dynamic expander graphs by Henzinger, Paz, and Sricharan [ESA 2022]. In addition, we continue this line of research by designing new self-reductions for more problems, such as Max-Cut and dynamic Densest Subgraph, and demonstrating that the core gadget can be utilized to lift lower bounds based on the OMv Conjecture to expanders., Comment: Full version of a paper to appear at ESA 2024

Federated Learning (FL) is an emerging machine learning paradigm that enables the collaborative training of a shared global model across distributed clients while keeping the data decentralized. Recent works on designing systems for efficient FL have shown that utilizing serverless computing technologies, particularly Function-as-a-Service (FaaS) for FL, can enhance resource efficiency, reduce training costs, and alleviate the complex infrastructure management burden on data holders. However, existing serverless FL systems implicitly assume a uniform global model architecture across all participating clients during training. This assumption fails to address fundamental challenges in practical FL due to the resource and statistical data heterogeneity among FL clients. To address these challenges and enable heterogeneous client models in serverless FL, we utilize Knowledge Distillation (KD) in this paper. Towards this, we propose novel optimized serverless workflows for two popular conventional federated KD techniques, i.e., FedMD and FedDF. We implement these workflows by introducing several extensions to an open-source serverless FL system called FedLess. Moreover, we comprehensively evaluate the two strategies on multiple datasets across varying levels of client data heterogeneity using heterogeneous client models with respect to accuracy, fine-grained training times, and costs. Results from our experiments demonstrate that serverless FedDF is more robust to extreme non-IID data distributions, is faster, and leads to lower costs than serverless FedMD. In addition, compared to the original implementation, our optimizations for particular steps in FedMD and FedDF lead to an average speedup of 3.5x and 1.76x across all datasets., Comment: ACM/SIGAPP Symposium on Applied Computing 2024

Graph-based environments pose unique challenges to multi-agent reinforcement learning. In decentralized approaches, agents operate within a given graph and make decisions based on partial or outdated observations. The size of the observed neighborhood limits the generalizability to different graphs and affects the reactivity of agents, the quality of the selected actions, and the communication overhead. This work focuses on generalizability and resolves the trade-off in observed neighborhood size with a continuous information flow in the whole graph. We propose a recurrent message-passing model that iterates with the environment's steps and allows nodes to create a global representation of the graph by exchanging messages with their neighbors. Agents receive the resulting learned graph observations based on their location in the graph. Our approach can be used in a decentralized manner at runtime and in combination with a reinforcement learning algorithm of choice. We evaluate our method across 1000 diverse graphs in the context of routing in communication networks and find that it enables agents to generalize and adapt to changes in the graph., Comment: Accepted at AAMAS 2024, version with appendix; corrected typo in equation (1)

We show that it is possible to define a timelike future-directed information current within relativistic first-order hydrodynamics. This constitutes the first step toward a covariantly stable and causal formulation of first-order fluctuating hydrodynamics based on thermodynamic principles. We provide several explicit examples of first-order theories with an information current, covering many physical phenomena, ranging from electric conduction to viscosity and elasticity. We use these information currents to compute the corresponding equal-time correlation functions, and we find that the physically relevant (equal-time) correlators do not depend on the choice of the hydrodynamic frame as long as the frame leads to causal and stable dynamics. In the example of chiral hydrodynamics, we find that circularly polarized shear waves have different probabilities of being excited depending on their handedness, generating net helicity in chiral fluids., Comment: 23 pages, Published on Physical Review D, see https://journals.aps.org/prd/abstract/10.1103/PhysRevD.109.085013

Detecting if a graph contains a $k$-Clique is one of the most fundamental problems in computer science. The asymptotically fastest algorithm runs in time $O(n^{\omega k/3})$, where $\omega$ is the exponent of Boolean matrix multiplication. To date, this is the only technique capable of beating the trivial $O(n^k)$ bound by a polynomial factor. Due to this technique's various limitations, much effort has gone into designing "combinatorial" algorithms that improve over exhaustive search via other techniques. The first contribution of this work is a faster combinatorial algorithm for $k$-Clique, improving Vassilevska's bound of $O(n^{k}/\log^{k-1}{n})$ by two log factors. Technically, our main result is a new reduction from $k$-Clique to Triangle detection that exploits the same divide-and-conquer at the core of recent combinatorial algorithms by Chan (SODA'15) and Yu (ICALP'15). Our second contribution is exploiting combinatorial techniques to improve the state-of-the-art (even of non-combinatorial algorithms) for generalizations of the $k$-Clique problem. In particular, we give the first $o(n^k)$ algorithm for $k$-clique in hypergraphs and an $O(n^3/\log^{2.25}{n} + t)$ algorithm for listing $t$ triangles in a graph., Comment: Revised abstract and introduction to acknowledge a prior result by Nagle for hyperclique detection that we've improved upon. All else is unchanged

We study the problem of unlikely intersections for automorphisms of Markov surfaces of positive entropy. We show for certain parameters that two automorphisms with positive entropy share a Zariski dense set of periodic points if and only if they share a common iterate. Our proof uses arithmetic equidistribution for adelic line bundles over quasiprojective varieties, the theory of laminar currents and quasi-Fuchsian representation theory.

We construct the general theory of first-order relativistic hydrodynamics for a fluid exhibiting a chiral anomaly, including all possible viscous terms allowed by symmetry. Using standard techniques, we compute the necessary and sufficient conditions for this theory to be relativistically causal in the nonlinear regime and for thermal equilibria to be linearly stable. This is the first theory of first-order chiral hydrodynamics suitable for numerical simulations., Comment: 4 pages. Contribution to the Quark Matter 2023 conference proceedings

In [FJ07], Favre and Jonsson developed tools from valuative theory to study the dynamics of a dominant endomorphism of the complex affine plane. We extend this theory to the case of any affine surface, over any field. We give a new method to construct an eigenvaluation of an endomorphism. We generalize the result of Favre and Jonsson and show that the first dynamical degree of a dominant endomorphism of anormal affine surface is an algebraic integer of degree at most 2. Plus, we obtain a new result of rigidity. The set of first dynamical degrees of loxodromic automorphisms of a given affine surface must be contained in the set of integers or in the set of algebraic numbers of degree 2.

We revisit the fundamental Boolean Matrix Multiplication (BMM) problem. With the invention of algebraic fast matrix multiplication over 50 years ago, it also became known that BMM can be solved in truly subcubic $O(n^\omega)$ time, where $\omega<3$; much work has gone into bringing $\omega$ closer to $2$. Since then, a parallel line of work has sought comparably fast combinatorial algorithms but with limited success. The naive $O(n^3)$-time algorithm was initially improved by a $\log^2{n}$ factor [Arlazarov et al.; RAS'70], then by $\log^{2.25}{n}$ [Bansal and Williams; FOCS'09], then by $\log^3{n}$ [Chan; SODA'15], and finally by $\log^4{n}$ [Yu; ICALP'15]. We design a combinatorial algorithm for BMM running in time $n^3 / 2^{\Omega(\sqrt[7]{\log n})}$ -- a speed-up over cubic time that is stronger than any poly-log factor. This comes tantalizingly close to refuting the conjecture from the 90s that truly subcubic combinatorial algorithms for BMM are impossible. This popular conjecture is the basis for dozens of fine-grained hardness results. Our main technical contribution is a new regularity decomposition theorem for Boolean matrices (or equivalently, bipartite graphs) under a notion of regularity that was recently introduced and analyzed analytically in the context of communication complexity [Kelley, Lovett, Meka; arXiv'23], and is related to a similar notion from the recent work on $3$-term arithmetic progression free sets [Kelley, Meka; FOCS'23]., Comment: To appear at STOC 2024

We investigate the relation between $\delta$ and $\epsilon$ required for obtaining a $(1+\delta)$-approximation in time $N^{2-\epsilon}$ for closest pair problems under various distance metrics, and for other related problems in fine-grained complexity. Specifically, our main result shows that if it is impossible to (exactly) solve the (bichromatic) inner product (IP) problem for vectors of dimension $c \log N$ in time $N^{2-\epsilon}$, then there is no $(1+\delta)$-approximation algorithm for (bichromatic) Euclidean Closest Pair running in time $N^{2-2\epsilon}$, where $\delta \approx (\epsilon/c)^2$ (where $\approx$ hides $\polylog$ factors). This improves on the prior result due to Chen and Williams (SODA 2019) which gave a smaller polynomial dependence of $\delta$ on $\epsilon$, on the order of $\delta \approx (\epsilon/c)^6$. Our result implies in turn that no $(1+\delta)$-approximation algorithm exists for Euclidean closest pair for $\delta \approx \epsilon^4$, unless an algorithmic improvement for IP is obtained. This in turn is very close to the approximation guarantee of $\delta \approx \epsilon^3$ for Euclidean closest pair, given by the best known algorithm of Almam, Chan, and Williams (FOCS 2016). By known reductions, a similar result follows for a host of other related problems in fine-grained hardness of approximation. Our reduction combines the hardness of approximation framework of Chen and Williams, together with an MA communication protocol for IP over a small alphabet, that is inspired by the MA protocol of Chen (Theory of Computing, 2020).

This paper presents GreenCourier, a novel scheduling framework that enables the runtime scheduling of serverless functions across geographically distributed regions based on their carbon efficiencies. Our framework incorporates an intelligent scheduling strategy for Kubernetes and supports Knative as the serverless platform. To obtain real-time carbon information for different geographical regions, our framework supports multiple marginal carbon emissions sources such as WattTime and the Carbon-aware SDK. We comprehensively evaluate the performance of our framework using the Google Kubernetes Engine and production serverless function traces for scheduling functions across Spain, France, Belgium, and the Netherlands. Results from our experiments show that compared to other approaches, GreenCourier reduces carbon emissions per function invocation by an average of 13.25%., Comment: Accepted at the ACM 9th International Workshop on Serverless Computing (WoSC@Middleware'23)

The ability to automatically generate accurate protocols for scientific experiments would represent a major step towards the automation of science. Large Language Models (LLMs) have impressive capabilities on a wide range of tasks, such as question answering and the generation of coherent text and code. However, LLMs can struggle with multi-step problems and long-term planning, which are crucial for designing scientific experiments. Moreover, evaluation of the accuracy of scientific protocols is challenging, because experiments can be described correctly in many different ways, require expert knowledge to evaluate, and cannot usually be executed automatically. Here we present an automatic evaluation framework for the task of planning experimental protocols, and we introduce BioProt: a dataset of biology protocols with corresponding pseudocode representations. To measure performance on generating scientific protocols, we use an LLM to convert a natural language protocol into pseudocode, and then evaluate an LLM's ability to reconstruct the pseudocode from a high-level description and a list of admissible pseudocode functions. We evaluate GPT-3 and GPT-4 on this task and explore their robustness. We externally validate the utility of pseudocode representations of text by generating accurate novel protocols using retrieved pseudocode, and we run a generated protocol successfully in our biological laboratory. Our framework is extensible to the evaluation and improvement of language model planning abilities in other areas of science or other areas that lack automatic evaluation., Comment: EMNLP 2023. Dataset and code: https://github.com/bioplanner/bioplanner

What is the time complexity of matrix multiplication of sparse integer matrices with $m_{in}$ nonzeros in the input and $m_{out}$ nonzeros in the output? This paper provides improved upper bounds for this question for almost any choice of $m_{in}$ vs. $m_{out}$, and provides evidence that these new bounds might be optimal up to further progress on fast matrix multiplication. Our main contribution is a new algorithm that reduces sparse matrix multiplication to dense (but smaller) rectangular matrix multiplication. Our running time thus depends on the optimal exponent $\omega(a,b,c)$ of multiplying dense $n^a\times n^b$ by $n^b\times n^c$ matrices. We discover that when $m_{out}=\Theta(m_{in}^r)$ the time complexity of sparse matrix multiplication is $O(m_{in}^{\sigma+\epsilon})$, for all $\epsilon > 0$, where $\sigma$ is the solution to the equation $\omega(\sigma-1,2-\sigma,1+r-\sigma)=\sigma$. No matter what $\omega(\cdot,\cdot,\cdot)$ turns out to be, and for all $r\in(0,2)$, the new bound beats the state of the art, and we provide evidence that it is optimal based on the complexity of the all-edge triangle problem. In particular, in terms of the input plus output size $m = m_{in} + m_{out}$ our algorithm runs in time $O(m^{1.3459})$. Even for Boolean matrices, this improves over the previous $m^{\frac{2\omega}{\omega+1}+\epsilon}=O(m^{1.4071})$ bound [Amossen, Pagh; 2009], which was a natural barrier since it coincides with the longstanding bound of all-edge triangle in sparse graphs [Alon, Yuster, Zwick; 1994]. We find it interesting that matrix multiplication can be solved faster than triangle detection in this natural setting. In fact, we establish an equivalence to a special case of the all-edge triangle problem.