Search

In this paper, we study vanishing of Fourier coefficients of holomorphic $\eta$-quotients. We investigate examples of two different types: the first one involves integral weight CM newforms, while the second one involves half-integral weight $\eta$-quotients associated with sums of squares and Hurwitz class numbers.

Dark matter is a fundamental constituent of the universe, which is needed to explain a wide variety of astrophysical and cosmological observations. Although the existence of dark matter was first postulated nearly a century ago and its abundance is precisely measured, approximately five times larger than that of ordinary matter, its underlying identity remains a mystery. A leading hypothesis is that it is composed of new elementary particles, which are predicted to exist in many extensions of the Standard Model of particle physics. In this article we review the basic evidence for dark matter and the role it plays in cosmology and astrophysics, and discuss experimental searches and potential candidates. Rather than targeting researchers in the field, we aim to provide an accessible and concise summary of the most important ideas and results, which can serve as a first entry point for advanced undergraduate students of physics or astronomy., Comment: 15 pages, 5 figures. Preprint of a chapter for the 'Encyclopedia of Astrophysics' (Editor-in-Chief Ilya Mandel, Section Editor Cullan Howlett) to be published by Elsevier as a Reference Module

Bellman's algorithm for Subset Sum is one of the earliest and simplest examples of dynamic programming, dating back to 1957. For a given set of $n$ integers $X$ and a target $t$, it computes the set of subset sums $\mathcal S(X, t)$ (i.e., the set of integers $s \in [0\ldots t]$ for which there is a subset of $X$ summing to $s$) in time $O(|\mathcal S(X, t)| \cdot n)$. Since then, it has been an important question whether Bellman's seminal algorithm can be improved. This question is addressed in many recent works. And yet, while some algorithms improve upon Bellman's algorithm in specific parameter regimes, such as Bringmann's $\tilde O(t + n)$-time algorithm [SODA '17] and Bringmann and Nakos' $\tilde O(|\mathcal S(X, t)|^{4/3})$-time algorithm [STOC '20], none of the known algorithms beats Bellman's algorithm in all regimes. In particular, it remained open whether Subset Sum is in time $\tilde O(|\mathcal S(X, t)| \cdot n^{1-\epsilon})$ (for some $\epsilon > 0$). In this work we positively resolve this question and design an algorithm that outperforms Bellman's algorithm in all regimes. Our algorithm runs in time $\tilde O(|\mathcal S(X, t)| \cdot \sqrt{n})$, thus improving the time complexity by a factor of nearly $\sqrt n$. Our key innovation is the use of a result from additive combinatorics, which has not been applied in an algorithmic context before and which we believe to be of further independent interest for algorithm design. To demonstrate the broader applicability of our approach, we extend our ideas to a variant of Subset Sum on vectors as well as to Unbounded Subset Sum., Comment: To appear at SODA25

We prove the global well-posedness of the dynamical sine-Gordon model up to the third threshold, i.e., for parameters $\beta^2 < 6\pi$. The key novelty in our approach is the introduction of the so-called resonant equation, whose solution is entirely deterministic and completely captures the size of the solution to the dynamical sine-Gordon model. The probabilistic fluctuations in the dynamical sine-Gordon model are then controlled using uniform estimates for modified stochastic objects., Comment: 37 pages

In this paper we study sign changes of an infinite class of $\eta$-quotients which are holomorphic modular forms. There is also a relation to Hurwitz class numbers.

Anonymization plays a key role in protecting sensible information of individuals in real world datasets. Self-driving cars for example need high resolution facial features to track people and their viewing direction to predict future behaviour and react accordingly. In order to protect people's privacy whilst keeping important features in the dataset, it is important to replace the full body of a person with a highly detailed anonymized one. In contrast to doing face anonymization, full body replacement decreases the ability of recognizing people by their hairstyle or clothes. In this paper, we propose a workflow for full body person anonymization utilizing Stable Diffusion as a generative backend. Text-to-image diffusion models, like Stable Diffusion, OpenAI's DALL-E or Midjourney, have become very popular in recent time, being able to create photorealistic images from a single text prompt. We show that our method outperforms state-of-the art anonymization pipelines with respect to image quality, resolution, Inception Score (IS) and Frechet Inception Distance (FID). Additionally, our method is invariant with respect to the image generator and thus able to be used with the latest models available.

Recently, Amderberhan, Griffin, Ono, and Singh started the study of "traces of partition Eisenstein series" and used it to give explicit formulas for many interesting functions. In this note we determine the precise spaces in which they lie, find modular completions, and show how they are related via operators., Comment: 15 pages, comments welcome

Union volume estimation is a classical algorithmic problem. Given a family of objects $O_1,\ldots,O_n \subseteq \mathbb{R}^d$, we want to approximate the volume of their union. In the special case where all objects are boxes (also known as hyperrectangles) this is known as Klee's measure problem. The state-of-the-art algorithm [Karp, Luby, Madras '89] for union volume estimation and Klee's measure problem in constant dimension $d$ computes a $(1+\varepsilon)$-approximation with constant success probability by using a total of $O(n/\varepsilon^2)$ queries of the form (i) ask for the volume of $O_i$, (ii) sample a point uniformly at random from $O_i$, and (iii) query whether a given point is contained in $O_i$. We show that if one can only interact with the objects via the aforementioned three queries, the query complexity of [Karp, Luby, Madras '89] is indeed optimal, i.e., $\Omega(n/\varepsilon^2)$ queries are necessary. Our lower bound already holds for estimating the union of equiponderous axis-aligned polygons in $\mathbb{R}^2$, and even if the algorithm is allowed to inspect the coordinates of the points sampled from the polygons, and still holds when a containment query can ask containment of an arbitrary (not sampled) point. Guided by the insights of the lower bound, we provide a more efficient approximation algorithm for Klee's measure problem improving the $O(n/\varepsilon^2)$ time to $O((n+\frac{1}{\varepsilon^2}) \cdot \log^{O(d)}n)$. We achieve this improvement by exploiting the geometry of Klee's measure problem in various ways: (1) Since we have access to the boxes' coordinates, we can split the boxes into classes of boxes of similar shape. (2) Within each class, we show how to sample from the union of all boxes, by using orthogonal range searching. And (3) we exploit that boxes of different classes have small intersection, for most pairs of classes.

Andrews-Dyson-Hickerson, Cohen build a striking relation between q-hypergeometric series, real quadratic fields, and Maass forms. Thanks to the works of Lewis-Zagier and Zwegers we have a complete understanding on the part of these relations pertaining to Maass forms and false-indefinite theta functions. In particular, we can systematically distinguish and study the class of false-indefinite theta functions related to Maass forms. A crucial component here is the framework of mock Maass theta functions built by Zwegers in analogy with his earlier work on indefinite theta functions and their application to Ramanujan's mock theta functions. Given this understanding, a natural question is to what extent one can utilize modular properties to investigate the asymptotic behavior of the associated Fourier coefficients, especially in view of their relevance to combinatorial objects. In this paper, we develop the relevant methods to study such a question and show that quite detailed results can be obtained on the asymptotic development, which also enable Hardy-Ramanujan-Rademacher type exact formulas under the right conditions. We develop these techniques by concentrating on a concrete example involving partitions with parts separated by parity and derive an asymptotic expansion that includes all the exponentially growing terms., Comment: 37 pages

Implementing Deep Neural Networks (DNNs) on resource-constrained edge devices is a challenging task that requires tailored hardware accelerator architectures and a clear understanding of their performance characteristics when executing the intended AI workload. To facilitate this, we present an automated generation approach for fast performance models to accurately estimate the latency of a DNN mapped onto systematically modeled and concisely described accelerator architectures. Using our accelerator architecture description method, we modeled representative DNN accelerators such as Gemmini, UltraTrail, Plasticine-derived, and a parameterizable systolic array. Together with DNN mappings for those modeled architectures, we perform a combined DNN/hardware dependency graph analysis, which enables us, in the best case, to evaluate only 154 loop kernel iterations to estimate the performance for 4.19 billion instructions achieving a significant speedup. We outperform regression and analytical models in terms of mean absolute percentage error (MAPE) compared to simulation results, while being several magnitudes faster than an RTL simulation., Comment: Accepted version for: ACM Transactions on Embedded Computing Systems

In this paper, we study sign changes of weakly holomorphic modular forms which are given as $\eta$-quotients. We give representative examples for forms of negative weight, weight zero, and positive weight.

The growing concerns regarding energy consumption and privacy have prompted the development of AI solutions deployable on the edge, circumventing the substantial CO2 emissions associated with cloud servers and mitigating risks related to sharing sensitive data. But deploying Convolutional Neural Networks (CNNs) on non-off-the-shelf edge devices remains a complex and labor-intensive task. In this paper, we present and end-to-end workflow for deployment of CNNs on Field Programmable Gate Arrays (FPGAs) using the Gemmini accelerator, which we modified for efficient implementation on FPGAs. We describe how we leverage the use of open source software on each optimization step of the deployment process, the customizations we added to them and its impact on the final system's performance. We were able to achieve real-time performance by deploying a YOLOv7 model on a Xilinx ZCU102 FPGA with an energy efficiency of 36.5 GOP/s/W. Our FPGA-based solution demonstrates superior power efficiency compared with other embedded hardware devices, and even outperforms other FPGA reference implementations. Finally, we present how this kind of solution can be integrated into a wider system, by testing our proposed platform in a traffic monitoring scenario., Comment: 8 pages, 9 figures, accepted at the 27th Euromicro Conference Series on Digital System Design (DSD) 2024

The safe operation of automated vehicles depends on their ability to perceive the environment comprehensively. However, occlusion, sensor range, and environmental factors limit their perception capabilities. To overcome these limitations, collective perception enables vehicles to exchange information. However, fusing this exchanged information is a challenging task. Early fusion approaches require large amounts of bandwidth, while intermediate fusion approaches face interchangeability issues. Late fusion of shared detections is currently the only feasible approach. However, it often results in inferior performance due to information loss. To address this issue, we propose MR3D-Net, a dynamic multi-resolution 3D sparse voxel grid fusion backbone architecture for LiDAR-based collective perception. We show that sparse voxel grids at varying resolutions provide a meaningful and compact environment representation that can adapt to the communication bandwidth. MR3D-Net achieves state-of-the-art performance on the OPV2V 3D object detection benchmark while reducing the required bandwidth by up to 94% compared to early fusion. Code is available at https://github.com/ekut-es/MR3D-Net, Comment: Accepted at IEEE ITSC 2024

Collective perception has received considerable attention as a promising approach to overcome occlusions and limited sensing ranges of vehicle-local perception in autonomous driving. In order to develop and test novel collective perception technologies, appropriate datasets are required. These datasets must include not only different environmental conditions, as they strongly influence the perception capabilities, but also a wide range of scenarios with different road users as well as realistic sensor models. Therefore, we propose the Synthetic COllective PErception (SCOPE) dataset. SCOPE is the first synthetic multi-modal dataset that incorporates realistic camera and LiDAR models as well as parameterized and physically accurate weather simulations for both sensor types. The dataset contains 17,600 frames from over 40 diverse scenarios with up to 24 collaborative agents, infrastructure sensors, and passive traffic, including cyclists and pedestrians. In addition, recordings from two novel digital-twin maps from Karlsruhe and T\"ubingen are included. The dataset is available at https://ekut-es.github.io/scope

Comprehensive perception of the vehicle's environment and correct interpretation of the environment are crucial for the safe operation of autonomous vehicles. The perception of surrounding objects is the main component for further tasks such as trajectory planning. However, safe trajectory planning requires not only object detection, but also the detection of drivable areas and lane corridors. While first approaches consider an advanced safety evaluation of object detection, the evaluation of lane detection still lacks sufficient safety metrics. Similar to the safety metrics for object detection, additional factors such as the semantics of the scene with road type and road width, the detection range as well as the potential causes of missing detections, incorporated by vehicle speed, should be considered for the evaluation of lane detection. Therefore, we propose the Lane Safety Metric (LSM), which takes these factors into account and allows to evaluate the safety of lane detection systems by determining an easily interpretable safety score. We evaluate our offline safety metric on various virtual scenarios using different lane detection approaches and compare it with state-of-the-art performance metrics.

Previous theoretical work on contrastive learning (CL) with InfoNCE showed that, under certain assumptions, the learned representations uncover the ground-truth latent factors. We argue these theories overlook crucial aspects of how CL is deployed in practice. Specifically, they assume that within a positive pair, all latent factors either vary to a similar extent, or that some do not vary at all. However, in practice, positive pairs are often generated using augmentations such as strong cropping to just a few pixels. Hence, a more realistic assumption is that all latent factors change, with a continuum of variability across these factors. We introduce AnInfoNCE, a generalization of InfoNCE that can provably uncover the latent factors in this anisotropic setting, broadly generalizing previous identifiability results in CL. We validate our identifiability results in controlled experiments and show that AnInfoNCE increases the recovery of previously collapsed information in CIFAR10 and ImageNet, albeit at the cost of downstream accuracy. Additionally, we explore and discuss further mismatches between theoretical assumptions and practical implementations, including extensions to hard negative mining and loss ensembles.

Epilepsy is the most common, chronic, neurological disease worldwide and is typically accompanied by reoccurring seizures. Neuro implants can be used for effective treatment by suppressing an upcoming seizure upon detection. Due to the restricted size and limited battery lifetime of those medical devices, the employed approach also needs to be limited in size and have low energy requirements. We present an energy-efficient seizure detection approach involving a TC-ResNet and time-series analysis which is suitable for low-power edge devices. The presented approach allows for accurate seizure detection without preceding feature extraction while considering the stringent hardware requirements of neural implants. The approach is validated using the CHB-MIT Scalp EEG Database with a 32-bit floating point model and a hardware suitable 4-bit fixed point model. The presented method achieves an accuracy of 95.28%, a sensitivity of 92.34% and an AUC score of 0.9384 on this dataset with 4-bit fixed point representation. Furthermore, the power consumption of the model is measured with the low-power AI accelerator UltraTrail, which only requires 495 nW on average. Due to this low-power consumption this classification approach is suitable for real-time seizure detection on low-power wearable devices such as neural implants., Comment: Accepted at IJCNN 2024 (Preprint)

Statistical models are widely used to estimate the performance of commercial off-the-shelf (COTS) AI hardware accelerators. However, training of statistical performance models often requires vast amounts of data, leading to a significant time investment and can be difficult in case of limited hardware availability. To alleviate this problem, we propose a novel performance modeling methodology that significantly reduces the number of training samples while maintaining good accuracy. Our approach leverages knowledge of the target hardware architecture and initial parameter sweeps to identify a set of Performance Representatives (PR) for deep neural network (DNN) layers. These PRs are then used for benchmarking, building a statistical performance model, and making estimations. This targeted approach drastically reduces the number of training samples needed, opposed to random sampling, to achieve a better estimation accuracy. We achieve a Mean Absolute Percentage Error (MAPE) of as low as 0.02% for single-layer estimations and 0.68% for whole DNN estimations with less than 10000 training samples. The results demonstrate the superiority of our method for single-layer estimations compared to models trained with randomly sampled datasets of the same size., Comment: Accepted version for: SAMOS'24

In this paper, we investigate the signs changes of Fourier coefficients of infinite products of $q$-series of Rogers--Ramanujan type. In particular, we prove a conjecture made by Schlosser--Zhou pertaining to such sign changes for products of modulus $10$.

To ensure safe operation of autonomous vehicles in complex urban environments, complete perception of the environment is necessary. However, due to environmental conditions, sensor limitations, and occlusions, this is not always possible from a single point of view. To address this issue, collective perception is an effective method. Realistic and large-scale datasets are essential for training and evaluating collective perception methods. This paper provides the first comprehensive technical review of collective perception datasets in the context of autonomous driving. The survey analyzes existing V2V and V2X datasets, categorizing them based on different criteria such as sensor modalities, environmental conditions, and scenario variety. The focus is on their applicability for the development of connected automated vehicles. This study aims to identify the key criteria of all datasets and to present their strengths, weaknesses, and anomalies. Finally, this survey concludes by making recommendations regarding which dataset is most suitable for collective 3D object detection, tracking, and semantic segmentation., Comment: Accepted at IEEE IV 2024

Sub-GeV dark matter (DM) particles produced via thermal freeze-out evade many of the strong constraints on heavier DM candidates but at the same time face a multitude of new constraints from laboratory experiments, astrophysical observations and cosmological data. In this work we combine all of these constraints in order to perform frequentist and Bayesian global analyses of fermionic and scalar sub-GeV DM coupled to a dark photon with kinetic mixing. For fermionic DM, we find viable parameter regions close to the dark photon resonance, which expand significantly when including a particle-antiparticle asymmetry. For scalar DM, the velocity-dependent annihilation cross section evades the strongest constraints even in the symmetric case. Using Bayesian model comparison, we show that both asymmetric fermionic DM and symmetric scalar DM are preferred over symmetric fermionic DM due to the reduced fine-tuning penalty. Finally, we explore the discovery prospects of near-future experiments both in the full parameter space and for specific benchmark points. We find that the most commonly used benchmark scenarios are already in tension with existing constraints and propose a new benchmark point that can be targeted with future searches., Comment: 59 pages, 5 tables, 24 figures

Embedded distributed inference of Neural Networks has emerged as a promising approach for deploying machine-learning models on resource-constrained devices in an efficient and scalable manner. The inference task is distributed across a network of embedded devices, with each device contributing to the overall computation by performing a portion of the workload. In some cases, more powerful devices such as edge or cloud servers can be part of the system to be responsible of the most demanding layers of the network. As the demand for intelligent systems and the complexity of the deployed neural network models increases, this approach is becoming more relevant in a variety of applications such as robotics, autonomous vehicles, smart cities, Industry 4.0 and smart health. We present a systematic review of papers published during the last six years which describe techniques and methods to distribute Neural Networks across these kind of systems. We provide an overview of the current state-of-the-art by analysing more than 100 papers, present a new taxonomy to characterize them, and discuss trends and challenges in the field., Comment: 32 pages, 12 tables, 11 figures

As machine learning applications continue to evolve, the demand for efficient hardware accelerators, specifically tailored for deep neural networks (DNNs), becomes increasingly vital. In this paper, we propose a configurable memory hierarchy framework tailored for per layer adaptive memory access patterns of DNNs. The hierarchy requests data on-demand from the off-chip memory to provide it to the accelerator's compute units. The objective is to strike an optimized balance between minimizing the required memory capacity and maintaining high accelerator performance. The framework is characterized by its configurability, allowing the creation of a tailored memory hierarchy with up to five levels. Furthermore, the framework incorporates an optional shift register as final level to increase the flexibility of the memory management process. A comprehensive loop-nest analysis of DNN layers shows that the framework can efficiently execute the access patterns of most loop unrolls. Synthesis results and a case study of the DNN accelerator UltraTrail indicate a possible reduction in chip area of up to 62.2% as smaller memory modules can be used. At the same time, the performance loss can be minimized to 2.4%., Comment: accepted at MBMV 2024 - 27. Workshop "Methoden und Beschreibungssprachen zur Modellierung und Verifikation von Schaltungen und Systemen"

This chapter provides an overview of state-of-the-art adaptive finite element methods (AFEMs) for the numerical solution of second-order elliptic partial differential equations (PDEs), where the primary focus is on the optimal interplay of local mesh refinement and iterative solution of the arising discrete systems. Particular emphasis is placed on the thorough description of the essential ingredients necessary to design adaptive algorithms of optimal complexity, i.e., algorithms that mathematically guarantee the optimal rate of convergence with respect to the overall computational cost and, hence, time. Crucially, adaptivity induces reliability of the computed numerical approximations by means of a-posteriori error control. This ensures that the error committed by the numerical scheme is bounded from above by computable quantities. The analysis of the adaptive algorithms is based on the study of appropriate quasi-error quantities that include and balance different components of the overall error. Importantly, the quasi-errors stemming from an adaptive algorithm with contractive iterative solver satisfy a centerpiece concept, namely, full R-linear convergence. This guarantees that the adaptive algorithm is essentially contracting this quasi-error at each step and it turns out to be the cornerstone for the optimal complexity of AFEM. The unified analysis of the adaptive algorithms is presented in the context of symmetric linear PDEs. Extensions to goal-oriented, non-symmetric, as well as non-linear PDEs are presented with suitable nested iterative solvers fitting into the general analytical framework of the linear symmetric case. Numerical experiments highlight the theoretical results and emphasize the practical relevance and gain of adaptivity with iterative solvers for numerical simulations with optimal complexity.

Ensuring the safety of road vehicles at an acceptable level requires the absence of any unreasonable risk arising from all potential hazards linked to the intended au-tomated driving function and its implementation. The assurance that there are no unreasonable risks stemming from hazardous behaviours associated to functional insufficiencies is denoted as safety of intended functionality (SOTIF), a concept outlined in the ISO 21448 standard. In this context, the acquisition of real driving data is considered essential for the verification and validation. For this purpose, we are currently developing a method with which data collect-ed representatively from production vehicles can be modelled into a knowledge-based system in the future. A system that represents the probabilities of occur-rence of concrete driving scenarios over the statistical population of road traffic and makes them usable. The method includes the qualitative and quantitative ab-straction of the drives recorded by the sensors in the vehicles, the possibility of subsequent wireless transmission of the abstracted data from the vehicles and the derivation of the distributions and correlations of scenario parameters. This paper provides a summary of the research project and outlines its central idea. To this end, among other things, the needs for statistical information and da-ta from road traffic are elaborated from ISO 21448, the current state of research is addressed, and methodical aspects are discussed., Comment: 12 pages, 4 figures, the article has been accepted for publication and presentation during the 9th International ATZ Conference on Automated Driving 2024

We present a pseudopolynomial-time algorithm for the Knapsack problem that has running time $\widetilde{O}(n + t\sqrt{p_{\max}})$, where $n$ is the number of items, $t$ is the knapsack capacity, and $p_{\max}$ is the maximum item profit. This improves over the $\widetilde{O}(n + t \, p_{\max})$-time algorithm based on the convolution and prediction technique by Bateni et al.~(STOC 2018). Moreover, we give some evidence, based on a strengthening of the Min-Plus Convolution Hypothesis, that our running time might be optimal. Our algorithm uses two new technical tools, which might be of independent interest. First, we generalize the $\widetilde{O}(n^{1.5})$-time algorithm for bounded monotone min-plus convolution by Chi et al.~(STOC 2022) to the \emph{rectangular} case where the range of entries can be different from the sequence length. Second, we give a reduction from general knapsack instances to \emph{balanced} instances, where all items have nearly the same profit-to-weight ratio, up to a constant factor. Using these techniques, we can also obtain algorithms that run in time $\widetilde{O}(n + OPT\sqrt{w_{\max}})$, $\widetilde{O}(n + (nw_{\max}p_{\max})^{1/3}t^{2/3})$, and $\widetilde{O}(n + (nw_{\max}p_{\max})^{1/3} OPT^{2/3})$, where $OPT$ is the optimal total profit and $w_{\max}$ is the maximum item weight.

In an $m$-edge host graph $G$, all triangles can be listed in time $O(m^{1.5})$ [Itai, Rodeh '78], and all $k$-cycles can be listed in time $O(m^{2-1/{\lceil k/2 \rceil}} + t)$ where $t$ is the output size [Alon, Yuster, Zwick '97]. These classic results also hold for the colored problem variant, where the nodes of the host graph $G$ are colored by nodes in the pattern graph $H$, and we are only interested in subgraphs of $G$ that are isomorphic to the pattern $H$ and respect the colors. We study the problem of listing all $H$-subgraphs in the colored setting, for fixed pattern graphs $H$. As our main result, we determine all pattern graphs $H$ such that all $H$-subgraphs can be listed in subquadratic time $O(m^{2-\varepsilon} + t)$, where $t$ is the output size. Moreover, for each such subquadratic pattern $H$ we determine the smallest exponent $c(H)$ such that all $H$-subgraphs can be listed in time $O(m^{c(H)} + t)$. This is a vast generalization of the classic results on triangles and cycles. To prove this result, we design new listing algorithms and prove conditional lower bounds based on standard hypotheses from fine-grained complexity theory. In our algorithms, we use a new ingredient that we call hyper-degree splitting, where we split tuples of nodes into high degree and low degree depending on their number of common neighbors. We also show the same results for two related problems: finding an $H$-subgraph of minimum total edge-weight in time $O(m^{c(H)})$, and enumerating all $H$-subgraphs in $O(m^{c(H)})$ preprocessing time and constant delay. Again we determine all pattern graphs $H$ that have complexity $c(H) < 2$, and for each such subquadratic pattern we determine the optimal complexity $c(H)$.

We prove the global well-posedness of the stochastic Abelian-Higgs equations in two dimensions. The proof is based on a new covariant approach, which consists of two parts: First, we introduce covariant stochastic objects. The covariant stochastic objects and their multi-linear interactions are controlled using covariant heat kernel estimates. Second, we control nonlinear remainders using a covariant monotonicity formula, which is inspired by earlier work of Hamilton., Comment: 103 pages, fixed several minor errors

The Earth Mover's Distance is a popular similarity measure in several branches of computer science. It measures the minimum total edge length of a perfect matching between two point sets. The Earth Mover's Distance under Translation ($\mathrm{EMDuT}$) is a translation-invariant version thereof. It minimizes the Earth Mover's Distance over all translations of one point set. For $\mathrm{EMDuT}$ in $\mathbb{R}^1$, we present an $\widetilde{\mathcal{O}}(n^2)$-time algorithm. We also show that this algorithm is nearly optimal by presenting a matching conditional lower bound based on the Orthogonal Vectors Hypothesis. For $\mathrm{EMDuT}$ in $\mathbb{R}^d$, we present an $\widetilde{\mathcal{O}}(n^{2d+2})$-time algorithm for the $L_1$ and $L_\infty$ metric. We show that this dependence on $d$ is asymptotically tight, as an $n^{o(d)}$-time algorithm for $L_1$ or $L_\infty$ would contradict the Exponential Time Hypothesis (ETH). Prior to our work, only approximation algorithms were known for these problems., Comment: Full version of the paper "Fine-Grained Complexity of Earth Mover's Distance under Translation" accepted for SoCG 2024

Monochromatic gamma-ray signals constitute a potential smoking gun signature for annihilating or decaying dark matter particles that could relatively easily be distinguished from astrophysical or instrumental backgrounds. We provide an updated assessment of the sensitivity of the Cherenkov Telescope Array (CTA) to such signals, based on observations of the Galactic centre region as well as of selected dwarf spheroidal galaxies. We find that current limits and detection prospects for dark matter masses above 300 GeV will be significantly improved, by up to an order of magnitude in the multi-TeV range. This demonstrates that CTA will set a new standard for gamma-ray astronomy also in this respect, as the world's largest and most sensitive high-energy gamma-ray observatory, in particular due to its exquisite energy resolution at TeV energies and the adopted observational strategy focussing on regions with large dark matter densities. Throughout our analysis, we use up-to-date instrument response functions, and we thoroughly model the effect of instrumental systematic uncertainties in our statistical treatment. We further present results for other potential signatures with sharp spectral features, e.g.~box-shaped spectra, that would likewise very clearly point to a particle dark matter origin., Comment: 44 pages JCAP style (excluding author list and references), 19 figures; minor changes to match published version

The study of partitions with parts separated by parity was initiated by Andrews in connection with Ramanujan's mock theta functions, and his variations on this theme have produced generating functions with a large variety of different modular properties. In this paper, we use Ingham's Tauberian theorem to compute the asymptotic main term for each of the eight functions studied by Andrews.

Recently, MacMahon's generalized sum-of-divisor functions were shown to link partitions, quasimodular forms, and q-multiple zeta values. In this paper, we explore many further properties and extensions of these. Firstly, we address a question of Ono by producing infinite families of MacMahon-like functions that approximate the colored partition functions (and indeed other eta quotients). We further explore the MacMahon-like functions and discover new and suggestive arithmetic structure and modular completions., Comment: 22 pages; several new results were added

This literature review gives an overview of current approaches to perform domain adaptation in a low-resource and approaches to perform multilingual semantic search in a low-resource setting. We developed a new typology to cluster domain adaptation approaches based on the part of dense textual information retrieval systems, which they adapt, focusing on how to combine them efficiently. We also explore the possibilities of combining multilingual semantic search with domain adaptation approaches for dense retrievers in a low-resource setting.

Artificial Intelligence (AI) has witnessed remarkable growth, particularly through the proliferation of Deep Neural Networks (DNNs). These powerful models drive technological advancements across various domains. However, to harness their potential in real-world applications, specialized hardware accelerators are essential. This demand has sparked a market for parameterizable AI hardware accelerators offered by different vendors. Manufacturers of AI-integrated products face a critical challenge: selecting an accelerator that aligns with their product's performance requirements. The decision involves choosing the right hardware and configuring a suitable set of parameters. However, comparing different accelerator design alternatives remains a complex task. Often, engineers rely on data sheets, spreadsheet calculations, or slow black-box simulators, which only offer a coarse understanding of the performance characteristics. The Abstract Computer Architecture Description Language (ACADL) is a concise formalization of computer architecture block diagrams, which helps to communicate computer architecture on different abstraction levels and allows for inferring performance characteristics. In this paper, we demonstrate how to use the ACADL to model AI hardware accelerators, use their ACADL description to map DNNs onto them, and explain the timing simulation semantics to gather performance results., Comment: Accepted Version for: MBMV'24

Denote by $N_{\ell}(n)$ the number of $\ell$-tuples of elements in the symmetric group $S_n$ with commuting components, normalized by the order of $S_n$. In this paper, we prove asymptotic formulas for $N_\ell(n)$. In addition, general criteria for log-concavity are shown, which can be applied to $N_\ell(n)$ among other examples. Moreover, we obtain a Bessenrodt-Ono type theorem which gives an inequality of the form $c(a)c(b) > c(a+b)$ for certain families of sequences $c(n)$.

We study certain algebras of theta-like functions on partitions, for which the corresponding generating functions give rise to theta functions, quasi-Jacobi forms, Appell-Lerch sums, and false theta functions., Comment: 20 pages

We study the fundamental problem of approximating the edit distance of two strings. After an extensive line of research led to the development of a constant-factor approximation algorithm in almost-linear time, recent years have witnessed a notable shift in focus towards sublinear-time algorithms. Here, the task is typically formalized as the $(k, K)$-gap edit distance problem: Distinguish whether the edit distance of two strings is at most $k$ or more than $K$. Surprisingly, it is still possible to compute meaningful approximations in this challenging regime. Nevertheless, in almost all previous work, truly sublinear running time of $O(n^{1-\varepsilon})$ (for a constant $\varepsilon > 0$) comes at the price of at least polynomial gap $K \ge k \cdot n^{\Omega(\varepsilon)}$. Only recently, [Bringmann, Cassis, Fischer, and Nakos; STOC'22] broke through this barrier and solved the sub-polynomial $(k, k^{1+o(1)})$-gap edit distance problem in time $O(n/k + k^{4+o(1)})$, which is truly sublinear if $n^{\Omega(1)} \le k \le n^{\frac14-\Omega(1)}$.The $n/k$ term is inevitable (already for Hamming distance), but it remains an important task to optimize the $\mathrm{poly}(k)$ term and, in general, solve the $(k, k^{1+o(1)})$-gap edit distance problem in sublinear-time for larger values of $k$. In this work, we design an improved algorithm for the $(k, k^{1+o(1)})$-gap edit distance problem in sublinear time $O(n/k + k^{2+o(1)})$, yielding a significant quadratic speed-up over the previous $O(n/k + k^{4+o(1)})$-time algorithm. Notably, our algorithm is unconditionally almost-optimal (up to subpolynomial factors) in the regime where $k \leq n^{\frac13}$ and improves upon the state of the art for $k \leq n^{\frac12-o(1)}$., Comment: To appear in SODA'24. Shortened abstract for arXiv

We analyze a goal-oriented adaptive algorithm that aims to efficiently compute the quantity of interest $G(u^\star)$ with a linear goal functional $G$ and the solution $u^\star$ to a general second-order nonsymmetric linear elliptic partial differential equation. The current state of the analysis of iterative algebraic solvers for nonsymmetric systems lacks the contraction property in the norms that are prescribed by the functional analytic setting. This seemingly prevents their application in the optimality analysis of goal-oriented adaptivity. As a remedy, this paper proposes a goal-oriented adaptive iteratively symmetrized finite element method (GOAISFEM). It employs a nested loop with a contractive symmetrization procedure, e.g., the Zarantonello iteration, and a contractive algebraic solver, e.g., an optimal multigrid solver. The various iterative procedures require well-designed stopping criteria such that the adaptive algorithm can effectively steer the local mesh refinement and the computation of the inexact discrete approximations. The main results consist of full linear convergence of the proposed adaptive algorithm and the proof of optimal convergence rates with respect to both degrees of freedom and total computational cost (i.e., optimal complexity). Numerical experiments confirm the theoretical results and investigate the selection of the parameters.

The ultimate goal of any numerical scheme for partial differential equations (PDEs) is to compute an approximation of user-prescribed accuracy at quasi-minimal computational time. To this end, algorithmically, the standard adaptive finite element method (AFEM) integrates an inexact solver and nested iterations with discerning stopping criteria balancing the different error components. The analysis ensuring optimal convergence order of AFEM with respect to the overall computational cost critically hinges on the concept of R-linear convergence of a suitable quasi-error quantity. This work tackles several shortcomings of previous approaches by introducing a new proof strategy. First, the algorithm requires several fine-tuned parameters in order to make the underlying analysis work. A redesign of the standard line of reasoning and the introduction of a summability criterion for R-linear convergence allows us to remove restrictions on those parameters. Second, the usual assumption of a (quasi-)Pythagorean identity is replaced by the generalized notion of quasi-orthogonality from [Feischl, Math. Comp., 91 (2022)]. Importantly, this paves the way towards extending the analysis to general inf-sup stable problems beyond the energy minimization setting. Numerical experiments investigate the choice of the adaptivity parameters.

We prove an asymptotic formula for the number of $d$-fold partition diamonds of $n$ and their Schmidt-type counterparts. In order to do so, we study the asymptotic behavior of certain infinite products. We also remark on interesting potential connections with mathematical physics and Bloch groups., Comment: 20 pages, comments welcome

We pose the fine-grained hardness hypothesis that the textbook algorithm for the NFA Acceptance problem is optimal up to subpolynomial factors, even for dense NFAs and fixed alphabets. We show that this barrier appears in many variations throughout the algorithmic literature by introducing a framework of Colored Walk problems. These yield fine-grained equivalent formulations of the NFA Acceptance problem as problems concerning detection of an $s$-$t$-walk with a prescribed color sequence in a given edge- or node-colored graph. For NFA Acceptance on sparse NFAs (or equivalently, Colored Walk in sparse graphs), a tight lower bound under the Strong Exponential Time Hypothesis has been rediscovered several times in recent years. We show that our hardness hypothesis, which concerns dense NFAs, has several interesting implications: - It gives a tight lower bound for Context-Free Language Reachability. This proves conditional optimality for the class of 2NPDA-complete problems, explaining the cubic bottleneck of interprocedural program analysis. - It gives a tight $(n+nm^{1/3})^{1-o(1)}$ lower bound for the Word Break problem on strings of length $n$ and dictionaries of total size $m$. - It implies the popular OMv hypothesis. Since the NFA acceptance problem is a static (i.e., non-dynamic) problem, this provides a static reason for the hardness of many dynamic problems. Thus, a proof of the NFA Acceptance hypothesis would resolve several interesting barriers. Conversely, a refutation of the NFA Acceptance hypothesis may lead the way to attacking the current barriers observed for Context-Free Language Reachability, the Word Break problem and the growing list of dynamic problems proven hard under the OMv hypothesis., Comment: 35 pages, TheoretiCS journal version

The thermal freeze-out mechanism in its classical form is tightly connected to physics beyond the Standard Model around the electroweak scale, which has been the target of enormous experimental efforts. In this work we study a dark matter model in which freeze-out is triggered by a strong first-order phase transition in a dark sector, and show that this phase transition must also happen close to the electroweak scale, i.e. in the temperature range relevant for gravitational wave searches with the LISA mission. Specifically, we consider the spontaneous breaking of a $U(1)^\prime$ gauge symmetry through the vacuum expectation value of a scalar field, which generates the mass of a fermionic dark matter candidate that subsequently annihilates into dark Higgs and gauge bosons. In this set-up the peak frequency of the gravitational wave background is tightly correlated with the dark matter relic abundance, and imposing the observed value for the latter implies that the former must lie in the milli-Hertz range. A peculiar feature of our set-up is that the dark sector is not necessarily in thermal equilibrium with the Standard Model during the phase transition, and hence the temperatures of the two sectors evolve independently. Nevertheless, the requirement that the universe does not enter an extended period of matter domination after the phase transition, which would strongly dilute any gravitational wave signal, places a lower bound on the portal coupling that governs the entropy transfer between the two sectors. As a result, the predictions for the peak frequency of gravitational waves in the LISA band are robust, while the amplitude can change depending on the initial dark sector temperature., Comment: 29 pages, 12 figures + appendices

A convincing feature of least-squares finite element methods is the built-in a posteriori error estimator for any conforming discretization. In order to generalize this property to discontinuous finite element ansatz functions, this paper introduces a least-squares principle on piecewise Sobolev functions for the solution of the Poisson model problem in 2D with mixed boundary conditions. It allows for fairly general discretizations including standard piecewise polynomial ansatz spaces on triangular and polygonal meshes. The presented scheme enforces the interelement continuity of the piecewise polynomials by additional least-squares residuals. A side condition on the normal jumps of the flux variable requires a vanishing integral mean and enables a natural weighting of the jump in the least-squares functional in terms of the mesh size. This avoids over-penalization with additional regularity assumptions on the exact solution as usually present in the literature on discontinuous LSFEM. The proof of the built-in a posteriori error estimation for the over-penalized scheme is presented as well. All results in this paper are robust with respect to the size of the domain guaranteed by a suitable weighting of the residuals in the least-squares functional. Numerical experiments exhibit optimal convergence rates of the adaptive mesh-refining algorithm for various polynomial degrees.

The Dynamic Time Warping (DTW) distance is a popular similarity measure for polygonal curves (i.e., sequences of points). It finds many theoretical and practical applications, especially for temporal data, and is known to be a robust, outlier-insensitive alternative to the \frechet distance. For static curves of at most $n$ points, the DTW distance can be computed in $O(n^2)$ time in constant dimension. This tightly matches a SETH-based lower bound, even for curves in $\mathbb{R}^1$. In this work, we study \emph{dynamic} algorithms for the DTW distance. Here, the goal is to design a data structure that can be efficiently updated to accommodate local changes to one or both curves, such as inserting or deleting vertices and, after each operation, reports the updated DTW distance. We give such a data structure with update and query time $O(n^{1.5} \log n)$, where $n$ is the maximum length of the curves. As our main result, we prove that our data structure is conditionally \emph{optimal}, up to subpolynomial factors. More precisely, we prove that, already for curves in $\mathbb{R}^1$, there is no dynamic algorithm to maintain the DTW distance with update and query time~\makebox{$O(n^{1.5 - \delta})$} for any constant $\delta > 0$, unless the Negative-$k$-Clique Hypothesis fails. In fact, we give matching upper and lower bounds for various trade-offs between update and query time, even in cases where the lengths of the curves differ., Comment: To appear at SODA24