Search

The bipartite matching problem is widely applied in the field of transportation; e.g., to find optimal matches between supply and demand over time and space. Recent efforts have been made on developing analytical formulas to estimate the expected matching distance in bipartite matching with randomly distributed vertices in two- or higher-dimensional spaces, but no accurate formulas currently exist for one-dimensional problems. This paper presents a set of closed-form formulas, without curve-fitting, that can provide accurate average distance estimates for one-dimensional random bipartite matching problems (RBMP). We first focus on one-dimensional space and propose a new method that relates the corresponding matching distance to the area size between a random walk path and the x-axis. This result directly leads to a straightforward closed-form formula for balanced RBMPs. For unbalanced RBMPs, we first analyze the properties of an unbalanced random walk that can be related to balanced RBPMs after optimally removing a subset of unmatched points, and then derive a set of approximate formulas. Additionally, we build upon an optimal point removal strategy to derive a set of recursive formulas that can provide more accurate estimates. Then, we shift our focus to regular discrete networks, and use the one-dimensional results as building blocks to derive RBMP formulas. To verify the accuracy of the proposed formulas, a set of Monte-Carlo simulations are generated for a variety of matching problems settings. Results indicate that our proposed formulas provide quite accurate distance estimations for one-dimensional line segments and discrete networks under a variety of conditions.

Although many well-known algorithms can solve the bipartite matching problem instance efficiently, it remains an open question how one could estimate the expected optimal matching distance for arbitrary numbers of randomly distributed vertices in a $D$-dimensional $L^p$ space (referred to as a random bipartite matching problem, or RBMP). This paper proposes an analytical model with closed-form formulas (without statistical curve-fitting) that estimate both the probability distribution and expectation of the optimal matching distance of RBMP. Simpler asymptotic approximations of the formulas are also developed for some special cases. A series of Monte-Carlo simulation experiments are conducted to verify the accuracy of the proposed formulas under varying conditions. These proposed distance estimates could be key for strategic performance evaluation and resource planning in a wide variety of application contexts. To illustrate their usefulness, we focus on mobility service systems where matches must be made between customers and service vehicles that are randomly distributed over time and space. We show how the proposed distance formulas provide a theoretical foundation for the empirically assumed Cobb-Douglas matching function for taxi systems, and reveal conditions under which the matching function can be suitable. Our formulas can also be easily incorporated into optimization models to select taxi operation strategies (e.g., whether newly arriving customers shall be instantly matched or pooled into a batch for matching). Agent-based simulations are conducted to verify the predicted performance of the demand pooling strategy for two types of e-hailing taxi systems. The results not only demonstrate the accuracy of the proposed model estimates under various service conditions, but also offer valuable managerial insights for service operators to optimize their strategies.

Domain generalization (DG) aims to train a model from limited source domains, allowing it to generalize to unknown target domains. Typically, DG models only employ large-scale pre-trained models during the initialization of fine-tuning. However, large-scale pre-trained models already possess the ability to resist domain shift. If we reference pre-trained models continuously during fine-tuning to maintain this ability, it could further enhance the generalization ability of the DG model. For this purpose, we introduce a new method called Fine-Tune with Large-scale pre-trained Priors (FT-LP), which incorporates the pre-trained model as a prior into the DG fine-tuning process, ensuring that the model refers to its pre-trained model at each optimization step. FT-LP comprises a theoretical framework and a simple implementation strategy. In theory, we verify the rationality of FT-LP by introducing a generalization error bound with the pre-trained priors for DG. In implementation, we utilize an encoder to simulate the model distribution, enabling the use of FT-LP when only pre-trained weights are available. In summary, we offer a new fine-tuning method for DG algorithms to utilize pre-trained models throughout the fine-tuning process. Through experiments on various datasets and DG models, our proposed method exhibits significant improvements, indicating its effectiveness.

Domain invariant learning aims to learn models that extract invariant features over various training domains, resulting in better generalization to unseen target domains. Recently, Bayesian Neural Networks have achieved promising results in domain invariant learning, but most works concentrate on aligning features distributions rather than parameter distributions. Inspired by the principle of Bayesian Neural Network, we attempt to directly learn the domain invariant posterior distribution of network parameters. We first propose a theorem to show that the invariant posterior of parameters can be implicitly inferred by aggregating posteriors on different training domains. Our assumption is more relaxed and allows us to extract more domain invariant information. We also propose a simple yet effective method, named PosTerior Generalization (PTG), that can be used to estimate the invariant parameter distribution. PTG fully exploits variational inference to approximate parameter distributions, including the invariant posterior and the posteriors on training domains. Furthermore, we develop a lite version of PTG for widespread applications. PTG shows competitive performance on various domain generalization benchmarks on DomainBed. Additionally, PTG can use any existing domain generalization methods as its prior, and combined with previous state-of-the-art method the performance can be further improved. Code will be made public.

Bayesian Neural Networks (BNNs) have become one of the promising approaches for uncertainty estimation due to the solid theorical foundations. However, the performance of BNNs is affected by the ability of catching uncertainty. Instead of only seeking the distribution of neural network weights by in-distribution (ID) data, in this paper, we propose a new Bayesian Neural Network with an Attached structure (ABNN) to catch more uncertainty from out-of-distribution (OOD) data. We first construct a mathematical description for the uncertainty of OOD data according to the prior distribution, and then develop an attached Bayesian structure to integrate the uncertainty of OOD data into the backbone network. ABNN is composed of an expectation module and several distribution modules. The expectation module is a backbone deep network which focuses on the original task, and the distribution modules are mini Bayesian structures which serve as attachments of the backbone. In particular, the distribution modules aim at extracting the uncertainty from both ID and OOD data. We further provide theoretical analysis for the convergence of ABNN, and experimentally validate its superiority by comparing with some state-of-the-art uncertainty estimation methods Code will be made available.

Applying the technique of $p$-adic integration, we prove the topological mirror symmetry conjecture of Hausel-Thaddeus for the moduli spaces of (strongly) parabolic Higgs bundles for the structure groups $\text{SL}_n$ and $\text{PGL}_n$, building on previous work of Groechenig-Wyss-Ziegler on the non-parabolic case. We also prove the $E$-polynomial of the smooth moduli space of parabolic $\text{GL}_n$-Higgs bundles is independent of the degree of the underlying vector bundles., Comment: 33 pages. Refereed version

We establish an isomorphism of complex $K$-theory of the moduli space $\check{\mathcal{M}}$ of $``SL_n"$-Higgs bundles of degree $d$ and rank $n$ (in the sense of Hausel--Thaddeus) and twisted complex $K$-theory of the orbifold $\hat{\mathcal{M}}$ of $PGL_n$-Higgs bundles of degree $e$, where $(n,d)=(n,e)=1$. Along the way we prove the vanishing of torsion for $H^*(\check{\mathcal{M}})$ and certain twisted complex $K$-theory groups of $\hat{\mathcal{M}}$. We also extend Arinkin's autoduality of compactified Jacobian to a derived equivalence between $SL_n$ and $PGL_n$-Hitchin systems over the elliptic locus. In the appendix we develop a formalism of $G$-sheaves of spectra, generalising equivariant homotopy theory to a relative setting., Comment: 49 pages, one appendix, comments welcome

Digital signatures are fundamental building blocks in various protocols to provide integrity and authenticity. The development of the quantum computing has raised concerns about the security guarantees afforded by classical signature schemes. CRYSTALS-Dilithium is an efficient post-quantum digital signature scheme based on lattice cryptography and has been selected as the primary algorithm for standardization by the National Institute of Standards and Technology. In this work, we present a high-throughput GPU implementation of Dilithium. For individual operations, we employ a range of computational and memory optimizations to overcome sequential constraints, reduce memory usage and IO latency, address bank conflicts, and mitigate pipeline stalls. This results in high and balanced compute throughput and memory throughput for each operation. In terms of concurrent task processing, we leverage task-level batching to fully utilize parallelism and implement a memory pool mechanism for rapid memory access. Considering the impact of varying repetition numbers in Dilithium on the overall execution time and hardware utilization, we propose a dynamic task scheduling mechanism to improve multiprocessor occupancy and significantly reduce execution time. Furthermore, we apply asynchronous computing and launch multiple streams to hide data transfer latencies and maximize the computing capabilities of both CPU and GPU. Across all three security levels, our GPU implementation can concurrently compute ten thousand tasks in less than 32 miliseconds for signing and 15 miliseconds for verification on both commercial and server-grade GPUs. This achieves microsecond-level amortized execution times for each task, offering a high-throughput and quantum-resistant solution suitable for a wide array of applications in real systems.

In this work, we make \emph{systematic} optimizations of key encapsulation mechanisms (KEM) based on module learning-with-errors (MLWE), covering algorithmic design, fundamental operation of number-theoretic transform (NTT), approaches to expanding encapsulated key size, and optimized implementation coding. We focus on Kyber (now in the Round-3 finalist of NIST PQC standardization) and Aigis (a variant of Kyber proposed at PKC 2020). By careful analysis, we first observe that the algorithmic design of Kyber and Aigis can be optimized by the mechanism of asymmetric key consensus with noise (AKCN) proposed in \cite{JZ16,JZ19}. Specifically, the decryption process can be simplified with AKCN, leading to a both faster and less error-prone decryption process. Moreover, the AKCN-based optimized version has perfect compatibility with the deployment of Kyber/Aigis in reality, as they can run on the same parameters, the same public key, and the same encryption process. We make a systematic study of the variants of NTT proposed in recent years for extending its applicability scope, make concrete analysis of their exact computational complexity, and in particular show their equivalence. We then present a new variant named hybrid-NTT (H-NTT), combining the advantages of existing NTT methods, and derive its optimality in computational complexity. The H-NTT technique not only has larger applicability scope but also allows for modular and unified implementation codes of NTT operations even with varying module dimensions. We analyze and compare the different approaches to expand the size of key to be encapsulated (specifically, 512-bit key for dimension of 1024), and conclude with the most economic approach. To mitigate the compatibility issue in implementations we adopt the proposed H-NTT method.

We prove a version of the tamely ramified geometric Langlands correspondence in positive characteristic for $GL_n(k)$. Let $k$ be an algebraically closed field of characteristic $p> n$. Let $X$ be a smooth projective curve over $k$ with marked points, and fix a parabolic subgroup of $GL_n(k)$ at each marked point. We denote by $\text{Bun}_{n,P}$ the moduli stack of (quasi-)parabolic vector bundles on $X$, and by $\mathcal{L}oc_{n,P}$ the moduli stack of parabolic flat connections such that the residue is nilpotent with respect to the parabolic reduction at each marked point. We construct an equivalence between the bounded derived category $D^{b}(\text{Qcoh}({\mathcal{L}oc_{n,P}^{0}}))$ of quasi-coherent sheaves on an open substack $\mathcal{L}oc_{n,P}^{0}\subset\mathcal{L}oc_{n,P}$, and the bounded derived category $D^{b}(\mathcal{D}^{0}_{{\text{Bun}}_{n,P}}\text{-mod})$ of $\mathcal{D}^{0}_{{\text{Bun}}_{n,P}}$-modules, where $\mathcal{D}^0_{\text{Bun}_{n,P}}$ is a localization of $\mathcal{D}_{\text{Bun}_{n,P}}$ the sheaf of crystalline differential operators on $\text{Bun}_{n,P}$. Thus we extend the work of Bezrukavnikov-Braverman to the tamely ramified case. We also prove a correspondence between flat connections on $X$ with regular singularities and meromorphic Higgs bundles on the Frobenius twist $X^{(1)}$ of $X$ with first order poles ., Comment: 37 pages. Final version

Let $C$ be a smooth complex projective curve and $G$ a connected complex reductive group. We prove that if the center $Z(G)$ of $G$ is disconnected, then the Kirwan map $H^*\big(\operatorname{Bun}(G,C),\mathbb{Q}\big)\rightarrow H^*\big(\mathcal{M}_{\operatorname{Higgs}}^{\operatorname{ss}},\mathbb{Q}\big)$ from the cohomology of the moduli stack of $G$-bundles to the moduli stack of semistable $G$-Higgs bundles, fails to be surjective: more precisely, the "variant cohomology" (and variant intersection cohomology) of the stack $\mathcal{M}_{\operatorname{Higgs}}^{\operatorname{ss}}$ of semistable $G$-Higgs bundles, is always nontrivial. We also show that the image of the pullback map $H^*\big(M_{\operatorname{Higgs}}^{\operatorname{ss}},\mathbb{Q}\big)\rightarrow H^*\big(\mathcal{M}_{\operatorname{Higgs}}^{\operatorname{ss}},\mathbb{Q}\big)$, from the cohomology of the moduli space of semistable $G$-Higgs bundles to the stack of semistable $G$-Higgs bundles, cannot be contained in the image of the Kirwan map. The proof uses a Borel-Quillen--style localization result for equivariant cohomology of stacks to reduce to an explicit construction and calculation.