Search

We present a new improvement on the laser method for designing fast matrix multiplication algorithms. The new method further develops the recent advances by [Duan, Wu, Zhou FOCS 2023] and [Vassilevska Williams, Xu, Xu, Zhou SODA 2024]. Surprisingly the new improvement is achieved by incorporating more asymmetry in the analysis, circumventing a fundamental tool of prior work that requires two of the three dimensions to be treated identically. The method yields a new bound on the square matrix multiplication exponent $$\omega<2.371339,$$ improved from the previous bound of $\omega<2.371552$. We also improve the bounds of the exponents for multiplying rectangular matrices of various shapes., Comment: 44 pages. arXiv admin note: text overlap with arXiv:2307.07970

This paper delves into the realm of ChatGPT, an AI-powered chatbot that utilizes topic modeling and reinforcement learning to generate natural responses. Although ChatGPT holds immense promise across various industries, such as customer service, education, mental health treatment, personal productivity, and content creation, it is essential to address its security, privacy, and ethical implications. By exploring the upgrade path from GPT-1 to GPT-4, discussing the model's features, limitations, and potential applications, this study aims to shed light on the potential risks of integrating ChatGPT into our daily lives. Focusing on security, privacy, and ethics issues, we highlight the challenges these concerns pose for widespread adoption. Finally, we analyze the open problems in these areas, calling for concerted efforts to ensure the development of secure and ethically sound large language models.

In undirected graphs with real non-negative weights, we give a new randomized algorithm for the single-source shortest path (SSSP) problem with running time $O(m\sqrt{\log n \cdot \log\log n})$ in the comparison-addition model. This is the first algorithm to break the $O(m+n\log n)$ time bound for real-weighted sparse graphs by Dijkstra's algorithm with Fibonacci heaps. Previous undirected non-negative SSSP algorithms give time bound of $O(m\alpha(m,n)+\min\{n\log n, n\log\log r\})$ in comparison-addition model, where $\alpha$ is the inverse-Ackermann function and $r$ is the ratio of the maximum-to-minimum edge weight [Pettie & Ramachandran 2005], and linear time for integer edge weights in RAM model [Thorup 1999]. Note that there is a proposed complexity lower bound of $\Omega(m+\min\{n\log n, n\log\log r\})$ for hierarchy-based algorithms for undirected real-weighted SSSP [Pettie & Ramachandran 2005], but our algorithm does not obey the properties required for that lower bound. As a non-hierarchy-based approach, our algorithm shows great advantage with much simpler structure, and is much easier to implement., Comment: 17 pages

One-shot segmentation of brain tissues is typically a dual-model iterative learning: a registration model (reg-model) warps a carefully-labeled atlas onto unlabeled images to initialize their pseudo masks for training a segmentation model (seg-model); the seg-model revises the pseudo masks to enhance the reg-model for a better warping in the next iteration. However, there is a key weakness in such dual-model iteration that the spatial misalignment inevitably caused by the reg-model could misguide the seg-model, which makes it converge on an inferior segmentation performance eventually. In this paper, we propose a novel image-aligned style transformation to reinforce the dual-model iterative learning for robust one-shot segmentation of brain tissues. Specifically, we first utilize the reg-model to warp the atlas onto an unlabeled image, and then employ the Fourier-based amplitude exchange with perturbation to transplant the style of the unlabeled image into the aligned atlas. This allows the subsequent seg-model to learn on the aligned and style-transferred copies of the atlas instead of unlabeled images, which naturally guarantees the correct spatial correspondence of an image-mask training pair, without sacrificing the diversity of intensity patterns carried by the unlabeled images. Furthermore, we introduce a feature-aware content consistency in addition to the image-level similarity to constrain the reg-model for a promising initialization, which avoids the collapse of image-aligned style transformation in the first iteration. Experimental results on two public datasets demonstrate 1) a competitive segmentation performance of our method compared to the fully-supervised method, and 2) a superior performance over other state-of-the-art with an increase of average Dice by up to 4.67%. The source code is available at: https://github.com/JinxLv/One-shot-segmentation-via-IST., Comment: Accepted by AAAI-2023

Video super-resolution is one of the most popular tasks on mobile devices, being widely used for an automatic improvement of low-bitrate and low-resolution video streams. While numerous solutions have been proposed for this problem, they are usually quite computationally demanding, demonstrating low FPS rates and power efficiency on mobile devices. In this Mobile AI challenge, we address this problem and propose the participants to design an end-to-end real-time video super-resolution solution for mobile NPUs optimized for low energy consumption. The participants were provided with the REDS training dataset containing video sequences for a 4X video upscaling task. The runtime and power efficiency of all models was evaluated on the powerful MediaTek Dimensity 9000 platform with a dedicated AI processing unit capable of accelerating floating-point and quantized neural networks. All proposed solutions are fully compatible with the above NPU, demonstrating an up to 500 FPS rate and 0.2 [Watt / 30 FPS] power consumption. A detailed description of all models developed in the challenge is provided in this paper., Comment: arXiv admin note: text overlap with arXiv:2105.08826, arXiv:2105.07809, arXiv:2211.04470, arXiv:2211.03885

Image super-resolution is a common task on mobile and IoT devices, where one often needs to upscale and enhance low-resolution images and video frames. While numerous solutions have been proposed for this problem in the past, they are usually not compatible with low-power mobile NPUs having many computational and memory constraints. In this Mobile AI challenge, we address this problem and propose the participants to design an efficient quantized image super-resolution solution that can demonstrate a real-time performance on mobile NPUs. The participants were provided with the DIV2K dataset and trained INT8 models to do a high-quality 3X image upscaling. The runtime of all models was evaluated on the Synaptics VS680 Smart Home board with a dedicated edge NPU capable of accelerating quantized neural networks. All proposed solutions are fully compatible with the above NPU, demonstrating an up to 60 FPS rate when reconstructing Full HD resolution images. A detailed description of all models developed in the challenge is provided in this paper., Comment: arXiv admin note: text overlap with arXiv:2105.07825, arXiv:2105.08826, arXiv:2211.04470, arXiv:2211.03885, arXiv:2211.05256

Fast matrix multiplication is one of the most fundamental problems in algorithm research. The exponent of the optimal time complexity of matrix multiplication is usually denoted by $\omega$. This paper discusses new ideas for improving the laser method for fast matrix multiplication. We observe that the analysis of higher powers of the Coppersmith-Winograd tensor [Coppersmith & Winograd 1990] incurs a "combination loss", and we partially compensate for it using an asymmetric version of CW's hashing method. By analyzing the eighth power of the CW tensor, we give a new bound of $\omega<2.371866$, which improves the previous best bound of $\omega<2.372860$ [Alman & Vassilevska Williams 2020]. Our result breaks the lower bound of $2.3725$ in [Ambainis, Filmus & Le Gall 2015] because of the new method for analyzing component (constituent) tensors., Comment: 86 pages

Kinetic inductance detectors (KID) have great potential in astronomical observation, such as searching for exoplanets, because of their low noise, fast response and photon counting characteristics. In this paper, we present the design process and simulation results of a microstrip line coupled KIDs array for near-infrared astronomical observation. Compared with coplanar waveguide (CPW) feedlines, microstrip feedlines do not require air bridges, which simplify fabrication process. In the design part, we mainly focus on the impedance transforming networks, the KID structure, and the frequency crosstalk simulations. The test array has a total of 104 resonators with 8 rows and 13 columns, which ranges from 4.899~GHz to 6.194~GHz. The pitch size is about 200~$\mu$m and the frequency crosstalk is less than 50~kHz in simulation.

As a major approach to looking for life beyond the Earth, the search for extraterrestrial intelligence (SETI) is committed to detecting technosignatures such as engineered radio signals that are indicative of technologically capable life. In this paper, we report a targeted SETI campaign employing an observation strategy named multi-beam coincidence matching (MBCM) at the Five-hundred-meter Aperture Spherical radio Telescope (FAST) towards 33 known exoplanet systems, searching for ETI narrow-band drifting signals across 1.05-1.45 GHz in two orthogonal linear polarization directions separately. A signal at 1140.604 MHz detected from the observation towards Kepler-438 originally peaked our interest because its features are roughly consistent with assumed ETI technosignatures. However, evidences such as its polarization characteristics are almost able to eliminate the possibility of an extraterrestrial origin. Our observations achieve an unprecedented sensitivity since the minimum equivalent isotropic radiated power (EIRP) we are able to detect reaches 1.48 x10^9 W., Comment: 17 pages, 12 figures, matches the published version

In this paper, we show that the time complexity of monotone min-plus product of two $n\times n$ matrices is $\tilde{O}(n^{(3+\omega)/2})=\tilde{O}(n^{2.687})$, where $\omega < 2.373$ is the fast matrix multiplication exponent [Alman and Vassilevska Williams 2021]. That is, when $A$ is an arbitrary integer matrix and $B$ is either row-monotone or column-monotone with integer elements bounded by $O(n)$, computing the min-plus product $C$ where $C_{i,j}=\min_k\{A_{i,k}+B_{k,j}\}$ takes $\tilde{O}(n^{(3+\omega)/2})$ time, which greatly improves the previous time bound of $\tilde{O}(n^{(12+\omega)/5})=\tilde{O}(n^{2.875})$ [Gu, Polak, Vassilevska Williams and Xu 2021]. Then by simple reductions, this means the following problems also have $\tilde{O}(n^{(3+\omega)/2})$ time algorithms: (1) $A$ and $B$ are both bounded-difference, that is, the difference between any two adjacent entries is a constant. The previous results give time complexities of $\tilde{O}(n^{2.824})$ [Bringmann, Grandoni, Saha and Vassilevska Williams 2016] and $\tilde{O}(n^{2.779})$ [Chi, Duan and Xie 2022]. (2) $A$ is arbitrary and the columns or rows of $B$ are bounded-difference. Previous result gives time complexity of $\tilde{O}(n^{2.922})$ [Bringmann, Grandoni, Saha and Vassilevska Williams 2016]. (3) The problems reducible to these problems, such as language edit distance, RNA-folding, scored parsing problem on BD grammars. [Bringmann, Grandoni, Saha and Vassilevska Williams 2016]. Finally, we also consider the problem of min-plus convolution between two integral sequences which are monotone and bounded by $O(n)$, and achieve a running time upper bound of $\tilde{O}(n^{1.5})$. Previously, this task requires running time $\tilde{O}(n^{(9+\sqrt{177})/12}) = O(n^{1.859})$ [Chan and Lewenstein 2015]., Comment: Add acknowledgment

Fast radio bursts (FRBs) are brief, intense flashes of radio waves from unidentified extragalactic sources. Polarized FRBs originate in highly magnetized environments. We report observations of the repeating FRB 20190520B spanning seventeen months , which show its amount of Faraday rotation is highly variable and twice changes its sign. The FRB also depolarizes below radio frequencies around 1 to 3 GHz. We interpret these properties as due to change in the parallel component of the integrated magnetic field along the line-of-sight, including reversals. This could result from propagation through a turbulent, magnetized screen of plasma located between $10^{-5}$ to 100 parsecs of the FRB source. This is consistent with the bursts passing through the stellar wind of a binary companion of the FRB source., Comment: arXiv:2203.08151 has been merged into this

We present the first compact distance oracle that tolerates multiple failures and maintains exact distances. Given an undirected weighted graph $G = (V, E)$ and an arbitrarily large constant $d$, we construct an oracle that given vertices $u, v \in V$ and a set of $d$ edge failures $D$, outputs the exact distance between $u$ and $v$ in $G - D$ (that is, $G$ with edges in $D$ removed). Our oracle has space complexity $O(d n^4)$ and query time $d^{O(d)}$. Previously, there were compact approximate distance oracles under multiple failures [Chechik, Cohen, Fiat, and Kaplan, SODA'17; Duan, Gu, and Ren, SODA'21], but the best exact distance oracles under $d$ failures require essentially $\Omega(n^d)$ space [Duan and Pettie, SODA'09]. Our distance oracle seems to require $n^{\Omega(d)}$ time to preprocess; we leave it as an open question to improve this preprocessing time.

Min-plus product of two $n\times n$ matrices is a fundamental problem in algorithm research. It is known to be equivalent to APSP, and in general it has no truly subcubic algorithms. In this paper, we focus on the min-plus product on a special class of matrices, called $\delta$-bounded-difference matrices, in which the difference between any two adjacent entries is bounded by $\delta=O(1)$. Our algorithm runs in randomized time $O(n^{2.779})$ by the fast rectangular matrix multiplication algorithm [Le Gall \& Urrutia 18], better than $\tilde{O}(n^{2+\omega/3})=O(n^{2.791})$ ($\omega<2.373$ [Alman \& V.V.Williams 20]). This improves previous result of $\tilde{O}(n^{2.824})$ [Bringmann et al. 16]. When $\omega=2$ in the ideal case, our complexity is $\tilde{O}(n^{2+2/3})$, improving Bringmann et al.'s result of $\tilde{O}(n^{2.755})$., Comment: 13 pages

We consider the energy complexity of the leader election problem in the single-hop radio network model, where each device has a unique identifier in $\{1, 2, \ldots, N\}$. Energy is a scarce resource for small battery-powered devices. For such devices, most of the energy is often spent on communication, not on computation. To approximate the actual energy cost, the energy complexity of an algorithm is defined as the maximum over all devices of the number of time slots where the device transmits or listens. Much progress has been made in understanding the energy complexity of leader election in radio networks, but very little is known about the trade-off between time and energy. $\textbf{Time-energy trade-off:}$ For any $k \geq \log \log N$, we show that a leader among at most $n$ devices can be elected deterministically in $O(k \cdot n^{1+\epsilon}) + O(k \cdot N^{1/k})$ time and $O(k)$ energy if each device can simultaneously transmit and listen, where $\epsilon > 0$ is any small constant. This improves upon the previous $O(N)$-time $O(\log \log N)$-energy algorithm by Chang et al. [STOC 2017]. We provide lower bounds to show that the time-energy trade-off of our algorithm is near-optimal. $\textbf{Dense instances:}$ For the dense instances where the number of devices is $n = \Theta(N)$, we design a deterministic leader election algorithm using only $O(1)$ energy. This improves upon the $O(\log^* N)$-energy algorithm by Jurdzi\'{n}ski et al. [PODC 2002] and the $O(\alpha(N))$-energy algorithm by Chang et al. [STOC 2017]. More specifically, we show that the optimal deterministic energy complexity of leader election is $\Theta\left(\max\left\{1, \log \frac{N}{n}\right\}\right)$ if the devices cannot simultaneously transmit and listen, and it is $\Theta\left(\max\left\{1, \log \log \frac{N}{n}\right\}\right)$ if they can.