Search

We study the differentially private top-$k$ selection problem, aiming to identify a sequence of $k$ items with approximately the highest scores from $d$ items. Recent work by Gillenwater et al. (ICML '22) employs a direct sampling approach from the vast collection of $d^{\,\Theta(k)}$ possible length-$k$ sequences, showing superior empirical accuracy compared to previous pure or approximate differentially private methods. Their algorithm has a time and space complexity of $\tilde{O}(dk)$. In this paper, we present an improved algorithm with time and space complexity $O(d + k^2 / \epsilon \cdot \ln d)$, where $\epsilon$ denotes the privacy parameter. Experimental results show that our algorithm runs orders of magnitude faster than their approach, while achieving similar empirical accuracy., Comment: NeurIPS 2024

Next generation communications demand for better spectrum management, lower latency, and guaranteed quality-of-service (QoS). Recently, Artificial intelligence (AI) has been widely introduced to advance these aspects in next generation wireless systems. However, such AI applications suffer from limited training data, low robustness, and poor generalization capabilities. To address these issues, a model-driven deep unfolding (DU) algorithm is introduced in this paper to bridge the gap between traditional model-driven communication algorithms and data-driven deep learning. Focusing on the QoS-aware rate-splitting multiple access (RSMA) resource allocation problem in multi-user communications, a conventional fractional programming (FP) algorithm is first applied as a benchmark. The solution is then refined by the application of projection gradient descent (PGD). DU is employed to further speed up convergence procedure, hence improving the efficiency of PGD. Moreover, the feasibility of results is guaranteed by designing a low-complexity projection based on scale factors, plus adding violation control mechanisms into the loss function that minimizes error rates. Finally, we provide a detailed analysis of the computational complexity and analysis design of the proposed DU algorithm. Extensive simulations are conducted and the results demonstrate that the proposed DU algorithm can reach the optimal communication efficiency with a mere $0.024\%$ violation rate for 4 layers DU. The DU algorithm also exhibits robustness in out-of-distribution tests and can be effectively trained with as few as 50 samples., Comment: This work has been submitted to the IEEE for possible publication

With the advancements of generative artificial intelligence (GenAI) models, their capabilities are expanding significantly beyond content generation and the models are increasingly being used across diverse applications. Particularly, GenAI shows great potential in addressing challenges in the electric vehicle (EV) ecosystem ranging from charging management to cyber-attack prevention. In this paper, we specifically consider Internet of electric vehicles (IoEV) and we categorize GenAI for IoEV into four different layers namely, EV's battery layer, individual EV layer, smart grid layer, and security layer. We introduce various GenAI techniques used in each layer of IoEV applications. Subsequently, public datasets available for training the GenAI models are summarized. Finally, we provide recommendations for future directions. This survey not only categorizes the applications of GenAI in IoEV across different layers but also serves as a valuable resource for researchers and practitioners by highlighting the design and implementation challenges within each layer. Furthermore, it provides a roadmap for future research directions, enabling the development of more robust and efficient IoEV systems through the integration of advanced GenAI techniques., Comment: 25 Pages

A standard task in solid state physics and quantum chemistry is the computation of localized molecular orbitals known as Wannier functions. In this manuscript, we propose a new procedure for computing Wannier functions in one-dimensional crystalline materials. Our approach proceeds by first performing parallel transport of the Bloch functions using numerical integration. Then a simple analytically computable correction is introduced to yield the optimally localized Wannier function. The resulting scheme is rapidly convergent and proven to produce globally optimal Wannier functions. The analysis in this manuscript can also be viewed as a proof of the existence of exponentially localized Wannier functions in one dimension. We illustrate the performance of the scheme by a number of numerical experiments.

Rate-splitting multiple access (RSMA) has been proven as an effective communication scheme for 5G and beyond. However, current approaches to RSMA resource management require complicated iterative algorithms, which cannot meet the stringent latency requirement by users with limited resources. Recently, data-driven methods are explored to alleviate this issue. However, they suffer from poor generalizability and scarce training data to achieve satisfactory performance. In this paper, we propose a fractional programming (FP) based deep unfolding (DU) approach to address resource allocation problem for a weighted sum rate optimization in RSMA. By carefully designing the penalty function, we couple the variable update with projected gradient descent algorithm (PGD). Following the structure of PGD, we embed a few learnable parameters in each layer of the DU network. Through extensive simulation, we have shown that the proposed model-based neural networks can yield similar results compared to the traditional optimization algorithm for RSMA resource management but with much lower computational complexity, less training data, and higher resilience to out-of-distribution (OOD) data., Comment: submitted to IEEE conference

Correlation Clustering is a classic clustering objective arising in numerous machine learning and data mining applications. Given a graph $G=(V,E)$, the goal is to partition the vertex set into clusters so as to minimize the number of edges between clusters plus the number of edges missing within clusters. The problem is APX-hard and the best known polynomial time approximation factor is 1.73 by Cohen-Addad, Lee, Li, and Newman [FOCS'23]. They use an LP with $|V|^{1/\epsilon^{\Theta(1)}}$ variables for some small $\epsilon$. However, due to the practical relevance of correlation clustering, there has also been great interest in getting more efficient sequential and parallel algorithms. The classic combinatorial \emph{pivot} algorithm of Ailon, Charikar and Newman [JACM'08] provides a 3-approximation in linear time. Like most other algorithms discussed here, this uses randomization. Recently, Behnezhad, Charikar, Ma and Tan [FOCS'22] presented a $3+\epsilon$-approximate solution for solving problem in a constant number of rounds in the Massively Parallel Computation (MPC) setting. Very recently, Cao, Huang, Su [SODA'24] provided a 2.4-approximation in a polylogarithmic number of rounds in the MPC model and in $\tilde{O} (|E|^{1.5})$ time in the classic sequential setting. They asked whether it is possible to get a better than 3-approximation in near-linear time? We resolve this problem with an efficient combinatorial algorithm providing a drastically better approximation factor. It achieves a $\sim 2-2/13 < 1.847$-approximation in sub-linear ($\tilde O(|V|)$) sequential time or in sub-linear ($\tilde O(|V|)$) space in the streaming setting. In the MPC model, we give an algorithm using only a constant number of rounds that achieves a $\sim 2-1/8 < 1.876$-approximation.

As public awareness of environmental protection continues to grow, the trend of integrating more electric vehicles (EVs) into the transportation sector is rising. Unlike conventional internal combustion engine (ICE) vehicles, EVs can minimize carbon emissions and potentially achieve autonomous driving. However, several obstacles hinder the widespread adoption of EVs, such as their constrained driving range and the extended time required for charging. One alternative solution to address these challenges is implementing dynamic wireless power transfer (DWPT), charging EVs in motion on the road. Moreover, charging stations with static wireless power transfer (SWPT) infrastructure can replace existing gas stations, enabling users to charge EVs in parking lots or at home. This paper surveys the communication infrastructure for static and dynamic wireless charging in electric vehicles. It encompasses all communication aspects involved in the wireless charging process. The architecture and communication requirements for static and dynamic wireless charging are presented separately. Additionally, a comprehensive comparison of existing communication standards is provided. The communication with the grid is also explored in detail. The survey gives attention to security and privacy issues arising during communications. In summary, the paper addresses the challenges and outlines upcoming trends in communication for EV wireless charging., Comment: submitted to IET Communication as a survey paper

Privacy-preserving computing is crucial for multi-center machine learning in many applications such as healthcare and finance. In this paper a Multi-center Privacy Computing framework with Predictions Aggregation (MPCPA) based on denoising diffusion probabilistic model (DDPM) is proposed, in which conditional diffusion model training, DDPM data generation, a classifier, and strategy of prediction aggregation are included. Compared to federated learning, this framework necessitates fewer communications and leverages high-quality generated data to support robust privacy computing. Experimental validation across multiple datasets demonstrates that the proposed framework outperforms classic federated learning and approaches the performance of centralized learning with original data. Moreover, our approach demonstrates robust security, effectively addressing challenges such as image memorization and membership inference attacks. Our experiments underscore the efficacy of the proposed framework in the realm of privacy computing, with the code set to be released soon.

Table-based Fact Verification (TFV) aims to extract the entailment relation between statements and structured tables. Existing TFV methods based on small-scaled models suffer from insufficient labeled data and weak zero-shot ability. Recently, the appearance of Large Language Models (LLMs) has gained lots of attraction in research fields. They have shown powerful zero-shot and in-context learning abilities on several NLP tasks, but their potential on TFV is still unknown. In this work, we implement a preliminary study about whether LLMs are table-based fact-checkers. In detail, we design diverse prompts to explore how the in-context learning can help LLMs in TFV, i.e., zero-shot and few-shot TFV capability. Besides, we carefully design and construct TFV instructions to study the performance gain brought by the instruction tuning of LLMs. Experimental results demonstrate that LLMs can achieve acceptable results on zero-shot and few-shot TFV with prompt engineering, while instruction-tuning can stimulate the TFV capability significantly. We also make some valuable findings about the format of zero-shot prompts and the number of in-context examples. Finally, we analyze some possible directions to promote the accuracy of TFV via LLMs, which is beneficial to further research of table reasoning., Comment: CSCWD 2024

We devise a polynomial-time algorithm for partitioning a simple polygon $P$ into a minimum number of star-shaped polygons. The question of whether such an algorithm exists has been open for more than four decades [Avis and Toussaint, Pattern Recognit., 1981] and it has been repeated frequently, for example in O'Rourke's famous book [Art Gallery Theorems and Algorithms, 1987]. In addition to its strong theoretical motivation, the problem is also motivated by practical domains such as CNC pocket milling, motion planning, and shape parameterization. The only previously known algorithm for a non-trivial special case is for $P$ being both monotone and rectilinear [Liu and Ntafos, Algorithmica, 1991]. For general polygons, an algorithm was only known for the restricted version in which Steiner points are disallowed [Keil, SIAM J. Comput., 1985], meaning that each corner of a piece in the partition must also be a corner of $P$. Interestingly, the solution size for the restricted version may be linear for instances where the unrestricted solution has constant size. The covering variant in which the pieces are star-shaped but allowed to overlap--known as the Art Gallery Problem--was recently shown to be $\exists\mathbb R$-complete and is thus likely not in NP [Abrahamsen, Adamaszek and Miltzow, STOC 2018 & J. ACM 2022]; this is in stark contrast to our result. Arguably the most related work to ours is the polynomial-time algorithm to partition a simple polygon into a minimum number of convex pieces by Chazelle and Dobkin~[STOC, 1979 & Comp. Geom., 1985].

Drainage of supraglacial lakes to the ice-sheet bed can occur when a hydrofracture propagates downward, driven by the weight of the water in the lake. For supraglacial lakes in the grounding zones of Antarctic glaciers, the mechanics of drainage is complicated by their proximity to the grounding line. Recently, a series of supraglacial lake-drainage events through hydrofractures was observed in the Amery Ice Shelf grounding zone, East Antarctica. The lake depth at drainage varied considerably between events, raising questions about the mechanisms that induce hydrofracture, even at low lake depths. Here we use a modelling approach to investigate the contribution of tidally driven flexure to hydrofracture propagation. We model the viscoelastic response of a marine ice sheet to tides, the stresses that are induced, and the contribution of tidal stresses to hydrofracture propagation. Our results show that ocean tides and lake-water pressure together control supraglacial lake drainage through hydrofractures in the grounding zone. We give a model-based criterion that predicts supraglacial lake drainage as a function of daily maximum tidal amplitude and lake depth. Our model-based criterion agrees with remotely sensed data, indicating the importance of tidal flexure to processes associated with hydrofracturing such as supraglacial lake drainage, rifting and calving., Comment: 23 pages, 10 figures

This paper investigates robust beamforming for system-centric energy efficiency (EE) optimization in the vehicular integrated sensing and communication (ISAC) system, where the mobility of vehicles poses significant challenges to channel estimation. To obtain the optimal beamforming under channel uncertainty, we first formulate an optimization problem for maximizing the system EE under bounded channel estimation errors. Next, fractional programming and semidefinite relaxation (SDR) are utilized to relax the rank-1 constraints. We further use Schur complement and S-Procedure to transform Cramer-Rao bound (CRB) and channel estimation error constraints into convex forms, respectively. Based on the Lagrangian dual function and Karush-Kuhn-Tucker (KKT) conditions, it is proved that the optimal beamforming solution is rank-1. Finally, we present comprehensive simulation results to demonstrate two key findings: 1) the proposed algorithm exhibits a favorable convergence rate, and 2) the approach effectively mitigates the impact of channel estimation errors., Comment: Submitted to IEEE for future publication

Distributed Artificial Intelligence (AI) model training over mobile edge networks encounters significant challenges due to the data and resource heterogeneity of edge devices. The former hampers the convergence rate of the global model, while the latter diminishes the devices' resource utilization efficiency. In this paper, we propose a generative AI-empowered federated learning to address these challenges by leveraging the idea of FIlling the MIssing (FIMI) portion of local data. Specifically, FIMI can be considered as a resource-aware data augmentation method that effectively mitigates the data heterogeneity while ensuring efficient FL training. We first quantify the relationship between the training data amount and the learning performance. We then study the FIMI optimization problem with the objective of minimizing the device-side overall energy consumption subject to required learning performance constraints. The decomposition-based analysis and the cross-entropy searching method are leveraged to derive the solution, where each device is assigned suitable AI-synthesized data and resource utilization policy. Experiment results demonstrate that FIMI can save up to 50% of the device-side energy to achieve the target global test accuracy in comparison with the existing methods. Meanwhile, FIMI can significantly enhance the converged global accuracy under the non-independently-and-identically distribution (non-IID) data., Comment: 13 pages, 5 figures. Submitted to IEEE for possible publication

We study the optimal order (or sequence) of contracting a tensor network with a minimal computational cost. We conclude 2 different versions of this optimal sequence: that minimize the operation number (OMS) and that minimize the time complexity (CMS). Existing results only shows that OMS is NP-hard, but no conclusion on CMS problem. In this work, we firstly reduce CMS to CMS-0, which is a sub-problem of CMS with no free indices. Then we prove that CMS is easier than OMS, both in general and in tree cases. Last but not least, we prove that CMS is still NP-hard. Based on our results, we have built up relationships of hardness of different tensor network contraction problems., Comment: Jianyu Xu and Hanwen Zhang are equal contributors. 10 pages (reference and appendix excluded), 20 pages in total, 6 figures

We develop a efficient, easy-to-implement, and strictly monotone numerical integration method for Mean-Variance (MV) portfolio optimization in realistic contexts, which involve jump-diffusion dynamics of the underlying controlled processes, discrete rebalancing, and the application of investment constraints, namely no-bankruptcy and leverage. A crucial element of the MV portfolio optimization formulation over each rebalancing interval is a convolution integral, which involves a conditional density of the logarithm of the amount invested in the risky asset. Using a known closed-form expression for the Fourier transform of this density, we derive an infinite series representation for the conditional density where each term is strictly positive and explicitly computable. As a result, the convolution integral can be readily approximated through a monotone integration scheme, such as a composite quadrature rule typically available in most programming languages. The computational complexity of our method is an order of magnitude lower than that of existing monotone finite difference methods. To further enhance efficiency, we propose an implementation of the scheme via Fast Fourier Transforms, exploiting the Toeplitz matrix structure. The proposed monotone scheme is proven to be both $\ell_{\infty}$-stable and pointwise consistent, and we rigorously establish its pointwise convergence to the unique solution of the MV portfolio optimization problem. We also intuitively demonstrate that, as the rebalancing time interval approaches zero, the proposed scheme converges to a continuously observed impulse control formulation for MV optimization expressed as a Hamilton-Jacobi-Bellman Quasi-Variational Inequality. Numerical results show remarkable agreement with benchmark solutions obtained through finite differences and Monte Carlo simulation, underscoring the effectiveness of our approach., Comment: 38 pages, 2 figures

Large-scale metasurfaces promise nanophotonic performance improvements to macroscopic optics functionality, for applications from imaging to analog computing. Yet the size scale mismatch of centimeter-scale chips versus micron-scale wavelengths prohibits use of conventional full-wave simulation techniques, and has necessitated dramatic approximations. Here, we show that tailoring "fast direct" integral-equation simulation techniques to the form factor of metasurfaces offers the possibility for accurate and efficient full-wave, large-scale metasurface simulations. For cylindrical (two-dimensional) metasurfaces, we demonstrate accurate simulations whose solution time scales \emph{linearly} with the metasurface diameter. Moreover, the solver stores compressed information about the simulation domain that is reusable over many design iterations. We demonstrate the capabilities of our solver through two designs: first, a high-efficiency, high-numerical-aperture metalens that is 20,000 wavelengths in diameter. Second, a high-efficiency, large-beam-width grating coupler. The latter corresponds to millimeter-scale beam design at standard telecommunications wavelengths, while the former, at a visible wavelength of 500 nm, corresponds to a design diameter of 1 cm, created through full simulations of Maxwell's equations., Comment: 11 pages, 6 figures

We present a scheme for finding all roots of an analytic function in a square domain in the complex plane. The scheme can be viewed as a generalization of the classical approach to finding roots of a function on the real line, by first approximating it by a polynomial in the Chebyshev basis, followed by diagonalizing the so-called ''colleague matrices''. Our extension of the classical approach is based on several observations that enable the construction of polynomial bases in compact domains that satisfy three-term recurrences and are reasonably well-conditioned. This class of polynomial bases gives rise to ''generalized colleague matrices'', whose eigenvalues are roots of functions expressed in these bases. In this paper, we also introduce a special-purpose QR algorithm for finding the eigenvalues of generalized colleague matrices, which is a straightforward extension of the recently introduced componentwise stable QR algorithm for the classical cases (See [Serkh]). The performance of the schemes is illustrated with several numerical examples.

Constructing a high-quality dense map in real-time is essential for robotics, AR/VR, and digital twins applications. As Neural Radiance Field (NeRF) greatly improves the mapping performance, in this paper, we propose a NeRF-based mapping method that enables higher-quality reconstruction and real-time capability even on edge computers. Specifically, we propose a novel hierarchical hybrid representation that leverages implicit multiresolution hash encoding aided by explicit octree SDF priors, describing the scene at different levels of detail. This representation allows for fast scene geometry initialization and makes scene geometry easier to learn. Besides, we present a coverage-maximizing keyframe selection strategy to address the forgetting issue and enhance mapping quality, particularly in marginal areas. To the best of our knowledge, our method is the first to achieve high-quality NeRF-based mapping on edge computers of handheld devices and quadrotors in real-time. Experiments demonstrate that our method outperforms existing NeRF-based mapping methods in geometry accuracy, texture realism, and time consumption. The code will be released at: https://github.com/SYSU-STAR/H2-Mapping, Comment: Accepted by IEEE Robotics and Automation Letters

This paper proposes a methodology to obtain estimates in small domains when the target is a composite indicator. These indicators are of utmost importance for studying multidimensional phenomena, but little research has been done on how to obtain estimates of these indicators under the small area context. Composite indicators are particularly complex for this purpose since their construction requires different data sources, aggregation procedures, and weighting which makes challenging not only the estimation for small domains but also obtaining uncertainty measures. As case study of our proposal, we estimate the incidence of multidimensional poverty at the municipality level in Colombia. Furthermore, we provide uncertainty measures based on a parametric bootstrap algorithm., Comment: 24 pages, 9 figures

Large curated datasets are necessary, but annotating medical images is a time-consuming, laborious, and expensive process. Therefore, recent supervised methods are focusing on utilizing a large amount of unlabeled data. However, to do so, is a challenging task. To address this problem, we propose a new 3D Cross-Pseudo Supervision (3D-CPS) method, a semi-supervised network architecture based on nnU-Net with the Cross-Pseudo Supervision method. We design a new nnU-Net based preprocessing. In addition, we set the semi-supervised loss weights to expand linearity with each epoch to prevent the model from low-quality pseudo-labels in the early training process. Our proposed method achieves an average dice similarity coefficient (DSC) of 0.881 and an average normalized surface distance (NSD) of 0.913 on the MICCAI FLARE2022 validation set (20 cases)., Comment: 14 pages, 5 figures

The deterministic $k$-server conjecture states that there is a $k$-competitive deterministic algorithm for the $k$-server problem for any metric space. We show that the work function algorithm is $3$-competitive for the $3$-server problem on circle metrics, a case left open by Coester and Koutsoupias (2021). Our analysis follows the existing framework but introduces a new potential function which may be viewed as a relaxation of the counterpart by Coester and Koutsoupias (2021). We further notice that the new potential function and many existing ones can be rewritten in a canonical form. Through a computer-aided verification, however, we find that no such canonical potential function can resolve the deterministic $3$-server conjecture for general metric spaces under the current analysis framework.

Basal crevasses are macroscopic structural discontinuities at the base of ice sheets and glaciers. Motivated by observations and the mechanics of elastic fracture, we hypothesise that in the presence of basal water pressure, spatial variations in basal stress can promote and localise basal crevassing. We quantify this process in the theoretical context of linear elastic fracture mechanics. We develop a model evaluating the effect of shear stress variation on the growth of basal crevasses. Our results indicate that sticky patches promote the initiation of basal crevasses, increase their length of propagation into the ice and, under some conditions, give them curved trajectories that incline upstream. A detailed exploration of the parameter space is conducted to gain a better understanding of the conditions under which sticky-patch-induced basal crevassing likely occurs beneath ice sheets and glaciers., Comment: 29 pages, 9 figures