Search

Every known communication problem whose randomized communication cost is constant (independent of the input size) can be reduced to $k$-Hamming Distance, that is, solved with a constant number of deterministic queries to some $k$-Hamming Distance oracle. We exhibit the first examples of constant-cost problems which cannot be reduced to $k$-Hamming Distance. To prove this separation, we relate it to a natural coding-theoretic question. For $f : \{2, 4, 6\} \to \mathbb{N}$, we say an encoding function $E : \{0, 1\}^n \to \{0, 1\}^m$ is an $f$-code if it transforms Hamming distances according to $\mathrm{dist}(E(x), E(y)) = f(\mathrm{dist}(x, y))$ whenever $f$ is defined. We prove that, if there exist $f$-codes for infinitely many $n$, then $f$ must be affine: $f(4) = (f(2) + f(6))/2$.

In the field of single image super-resolution (SISR), transformer-based models, have demonstrated significant advancements. However, the potential and efficiency of these models in applied fields such as real-world image super-resolution have been less noticed and there are substantial opportunities for improvement. Recently, composite fusion attention transformer (CFAT), outperformed previous state-of-the-art (SOTA) models in classic image super-resolution. This paper extends the CFAT model to an improved GAN-based model called IG-CFAT to effectively exploit the performance of transformers in real-world image super-resolution. IG-CFAT incorporates a semantic-aware discriminator to reconstruct fine details more accurately. Moreover, our model utilizes an adaptive degradation model to better simulate real-world degradations. Our methodology adds wavelet loss to conventional loss functions of GAN-based super-resolution models to recover high-frequency details more efficiently. Empirical results demonstrate that IG-CFAT sets new benchmarks in real-world image super-resolution, outperforming SOTA models in quantitative and qualitative metrics.

Materials subjected to neutron irradiation experience damage due to displacement cascades triggered by nuclear reactions. This paper presents a practical method to calculate primary atomic recoil events (PKAs), which lead to cascade damage, based on energy and recoiling species. We developed a custom code to identify PKAs and extract their properties using MCNPX and SRIM. This code determines the specifications of recoil atoms from the data provided by the PTRAC card in MCNPX. Consequently, the energy spectrum of PKAs generated through various reaction channels, including elastic/inelastic scattering and transmutations such as (n, {\alpha}), (n, p), and (n, {\gamma}), is calculated. This PKA spectrum is then input into SRIM, which calculates the total number of atomic displacements using the binary collision approximation (BCA) and provides crucial information about the spatial distribution of defects within the irradiated material. Our results indicate that elastic scattering is the predominant reaction, producing most PKAs with energies in the range of several keV. In contrast, inelastic scattering becomes the dominant interaction for generating high-energy PKAs (~EPKA>1 MeV). Additionally, we observed that the number of Frenkel pairs versus ion energy curves for light particle ion implantation (such as H and He) is significantly smaller than for heavier ions.

Sequence modeling plays a vital role across various domains, with recurrent neural networks being historically the predominant method of performing these tasks. However, the emergence of transformers has altered this paradigm due to their superior performance. Built upon these advances, transformers have conjoined CNNs as two leading foundational models for learning visual representations. However, transformers are hindered by the $\mathcal{O}(N^2)$ complexity of their attention mechanisms, while CNNs lack global receptive fields and dynamic weight allocation. State Space Models (SSMs), specifically the \textit{\textbf{Mamba}} model with selection mechanisms and hardware-aware architecture, have garnered immense interest lately in sequential modeling and visual representation learning, challenging the dominance of transformers by providing infinite context lengths and offering substantial efficiency maintaining linear complexity in the input sequence. Capitalizing on the advances in computer vision, medical imaging has heralded a new epoch with Mamba models. Intending to help researchers navigate the surge, this survey seeks to offer an encyclopedic review of Mamba models in medical imaging. Specifically, we start with a comprehensive theoretical review forming the basis of SSMs, including Mamba architecture and its alternatives for sequence modeling paradigms in this context. Next, we offer a structured classification of Mamba models in the medical field and introduce a diverse categorization scheme based on their application, imaging modalities, and targeted organs. Finally, we summarize key challenges, discuss different future research directions of the SSMs in the medical domain, and propose several directions to fulfill the demands of this field. In addition, we have compiled the studies discussed in this paper along with their open-source implementations on our GitHub repository., Comment: This is the first version of our survey, and the paper is currently under review

For $S\subseteq \mathbb{F}^n$, consider the linear space of restrictions of degree-$d$ polynomials to $S$. The Hilbert function of $S$, denoted $\mathrm{h}_S(d,\mathbb{F})$, is the dimension of this space. We obtain a tight lower bound on the smallest value of the Hilbert function of subsets $S$ of arbitrary finite grids in $\mathbb{F}^n$ with a fixed size $|S|$. We achieve this by proving that this value coincides with a combinatorial quantity, namely the smallest number of low Hamming weight points in a down-closed set of size $|S|$. Understanding the smallest values of Hilbert functions is closely related to the study of degree-$d$ closure of sets, a notion introduced by Nie and Wang (Journal of Combinatorial Theory, Series A, 2015). We use bounds on the Hilbert function to obtain a tight bound on the size of degree-$d$ closures of subsets of $\mathbb{F}_q^n$, which answers a question posed by Doron, Ta-Shma, and Tell (Computational Complexity, 2022). We use the bounds on the Hilbert function and degree-$d$ closure of sets to prove that a random low-degree polynomial is an extractor for samplable randomness sources. Most notably, we prove the existence of low-degree extractors and dispersers for sources generated by constant-degree polynomials and polynomial-size circuits. Until recently, even the existence of arbitrary deterministic extractors for such sources was not known.

Several theorems and conjectures in communication complexity state or speculate that the complexity of a matrix in a given communication model is controlled by a related analytic or algebraic matrix parameter, e.g., rank, sign-rank, discrepancy, etc. The forward direction is typically easy as the structural implications of small complexity often imply a bound on some matrix parameter. The challenge lies in establishing the reverse direction, which requires understanding the structure of Boolean matrices for which a given matrix parameter is small or large. We will discuss several research directions that align with this overarching theme., Comment: This is a column to be published in the complexity theory column of SIGACT News

We prove that the class of communication problems with public-coin randomized constant-cost protocols, called $BPP^0$, does not contain a complete problem. In other words, there is no randomized constant-cost problem $Q \in BPP^0$, such that all other problems $P \in BPP^0$ can be computed by a constant-cost deterministic protocol with access to an oracle for $Q$. We also show that the $k$-Hamming Distance problems form an infinite hierarchy within $BPP^0$. Previously, it was known only that Equality is not complete for $BPP^0$. We introduce a new technique, using Ramsey theory, that can prove lower bounds against arbitrary oracles in $BPP^0$, and more generally, we show that $k$-Hamming Distance matrices cannot be expressed as a Boolean combination of any constant number of matrices which forbid large Greater-Than subproblems., Comment: 24 pages

Diffusion-weighted MRI (DWI) is essential for stroke diagnosis, treatment decisions, and prognosis. However, image and disease variability hinder the development of generalizable AI algorithms with clinical value. We address this gap by presenting a novel ensemble algorithm derived from the 2022 Ischemic Stroke Lesion Segmentation (ISLES) challenge. ISLES'22 provided 400 patient scans with ischemic stroke from various medical centers, facilitating the development of a wide range of cutting-edge segmentation algorithms by the research community. Through collaboration with leading teams, we combined top-performing algorithms into an ensemble model that overcomes the limitations of individual solutions. Our ensemble model achieved superior ischemic lesion detection and segmentation accuracy on our internal test set compared to individual algorithms. This accuracy generalized well across diverse image and disease variables. Furthermore, the model excelled in extracting clinical biomarkers. Notably, in a Turing-like test, neuroradiologists consistently preferred the algorithm's segmentations over manual expert efforts, highlighting increased comprehensiveness and precision. Validation using a real-world external dataset (N=1686) confirmed the model's generalizability. The algorithm's outputs also demonstrated strong correlations with clinical scores (admission NIHSS and 90-day mRS) on par with or exceeding expert-derived results, underlining its clinical relevance. This study offers two key findings. First, we present an ensemble algorithm (https://github.com/Tabrisrei/ISLES22_Ensemble) that detects and segments ischemic stroke lesions on DWI across diverse scenarios on par with expert (neuro)radiologists. Second, we show the potential for biomedical challenge outputs to extend beyond the challenge's initial objectives, demonstrating their real-world clinical applicability.

As societal interactions increasingly involve both intentional and unintentional agents, understanding their effects on human cognition becomes paramount. This study investigates the neural correlates of interacting with intentional versus artificial agents in a simulated tennis game scenario. Employing functional near-infrared spectroscopy (fNIRS), brain activity in 50 male participants during gameplay against both types of opponents was analyzed. The used methodological approach ensures ecological validity by simulating real-world decision-making scenarios while participants undergo fNIRS scanning, avoiding the constraints of traditional neuroimaging methods. Six prefrontal cortex channels are focused on, leveraging the 10-20 system, to capture nuanced differences in brain activity. Wavelet analysis was utilized to dissect the data into frequency-specific differences, revealing subtle variations across different channels and frequency bands. Moreover, activity was quantified by comparing average data signals between rest and play modes across all points using Generalized Linear Model (GLM). The findings unveil significant differences in neural activation patterns, particularly in one specific channel and frequency range, suggesting distinct cognitive processing when interacting with intentional agents. These results align with previous neuroimaging studies and contribute to understanding the neural underpinnings of human-agent interactions in naturalistic settings. While acknowledging study limitations, including sample homogeneity and spatial accuracy constraints, the study's findings underscore the potential of fNIRS in exploring complex cognitive phenomena beyond laboratory confines.

Polar codes are the first class of structured channel codes that achieve the symmetric capacity of binary channels with efficient encoding and decoding. In 2019, Arikan proposed a new polar coding scheme referred to as polarization-adjusted convolutional (PAC)} codes. In contrast to polar codes, PAC codes precode the information word using a convolutional code prior to polar encoding. This results in material coding gain over polar code under Fano sequential decoding as well as successive cancellation list (SCL) decoding. Given the advantages of SCL decoding over Fano decoding in certain scenarios such as low-SNR regime or where a constraint on the worst case decoding latency exists, in this paper, we focus on SCL decoding and present a simplified SCL (SSCL) decoding algorithm for PAC codes. SSCL decoding of PAC codes reduces the decoding latency by identifying special nodes in the decoding tree and processing them at the intermediate stages of the graph. Our simulation results show that the performance of PAC codes under SSCL decoding is almost similar to the SCL decoding while having lower decoding latency., Comment: 7 pages, 3 figures

The log-rank conjecture, a longstanding problem in communication complexity, has persistently eluded resolution for decades. Consequently, some recent efforts have focused on potential approaches for establishing the conjecture in the special case of XOR functions, where the communication matrix is lifted from a boolean function, and the rank of the matrix equals the Fourier sparsity of the function, which is the number of its nonzero Fourier coefficients. In this note, we refute two conjectures. The first has origins in Montanaro and Osborne (arXiv'09) and is considered in Tsang et al. (FOCS'13), and the second one is due to Mande and Sanyal (FSTTCS'20). These conjectures were proposed in order to improve the best-known bound of Lovett (STOC'14) regarding the log-rank conjecture in the special case of XOR functions. Both conjectures speculate that the set of nonzero Fourier coefficients of the boolean function has some strong additive structure. We refute these conjectures by constructing two specific boolean functions tailored to each., Comment: Added additional background and intuition

In a recent breakthrough, Kelley and Meka (FOCS 2023) obtained a strong upper bound on the density of sets of integers without nontrivial three-term arithmetic progressions. In this work, we extend their result, establishing similar bounds for all linear patterns defined by binary systems of linear forms, where "binary" indicates that every linear form depends on exactly two variables. Prior to our work, no strong bounds were known for such systems even in the finite field model setting. A key ingredient in our proof is a graph counting lemma. The classical graph counting lemma, developed by Thomason (Random Graphs 1985) and Chung, Graham, and Wilson (Combinatorica 1989), is a fundamental tool in combinatorics. For a fixed graph $H$, it states that the number of copies of $H$ in a pseudorandom graph $G$ is similar to the number of copies of $H$ in a purely random graph with the same edge density as $G$. However, this lemma is only non-trivial when $G$ is a dense graph. In this work, we prove a graph counting lemma that is also effective when $G$ is sparse. Moreover, our lemma is well-suited for density increment arguments in additive number theory. As an immediate application, we obtain a strong bound for the Tur\'an problem in abelian Cayley sum graphs: let $\Gamma$ be a finite abelian group with odd order. If a Cayley sum graph on $\Gamma$ does not contain any $r$-clique as a subgraph, it must have at most $2^{-\Omega_r(\log^{1/16}|\Gamma|)}\cdot |\Gamma|^2$ edges. These results hinge on the technology developed by Kelley and Meka and the follow-up work by Kelley, Lovett, and Meka (STOC 2024)., Comment: [v3] This version proves the Kelley-Meka type bounds for all Binary systems of linear forms over any finite abelian group. [v4] This revised version includes a correction to Corollary 1.6, which is now stated for the Cayley sum graph

Tri-n-butyl phosphate (TBP) is a solvent that is commonly used in a variety of industries, including the nuclear and chemical industries, for its ability to dissolve and purify various inorganic acids and metals. It is often used in hydrometallurgical processes to separate and purify these substances. Machine learning models offer a promising alternative to traditional methods for predicting the viscosity of TBP mixtures. By training machine learning models on a dataset of viscosity measurements, it is possible to accurately predict the viscosity of TBP mixtures at different compositions, densities, and temperatures, which can save time and resources and reduce the risk of exposure to toxic solvents. This paper aimed at proposing Machine Learning (ML) techniques to automatically predict the viscosity of TBP mixtures using experimental data. For comparison peruses, we trained five different ML algorithms including Support Vector Regressor (SVR), Random Forest (RF), Logistic Regression (LR), Gradient Boosted Decision Trees (XGBoost), and Neural Network (NN). We collected a total of 511 measurements for TBP mixtures with temperature-based density, at different compositions, containing hexane, dodecane, cyclohexane, n-heptane, toluene, and ethylbenzene measured at temperatures of T= (288.15, 293.15, 298.15, 303.15, 308.15, 313.15, 318.15, 323.15, and 328.15) K. The results revealed that the NN model with 25 and 50 neurons in the hidden layers could achieve the best viscosity predictions for a system of TBP mixtures. The NN model outperformed other regular ML models in terms of Mean Square Error (MSE) of 0.157 % and adjusted R2 of 99.72 % on the test data set. This paper demonstrated that the NN model can be an appropriate option to accurately predict the viscosity of TBP + Ethylbenzene with a margin of deviation as low as 0.049 %.

Efficiently counting or detecting defective items is a crucial task in various fields ranging from biological testing to quality control to streaming algorithms. The \emph{group testing estimation problem} concerns estimating the number of defective elements $d$ in a collection of $n$ total within a given factor. We primarily consider the classical query model, in which a query reveals whether the selected group of elements contains a defective one. We show that any non-adaptive randomized algorithm that estimates the value of $d$ within a constant factor requires $\Omega(\log n)$ queries. This confirms that a known $O(\log n)$ upper bound by Bshouty (2019) is tight and resolves a conjecture by Damaschke and Sheikh Muhammad (2010). Additionally, we prove similar matching upper and lower bounds in the threshold query model., Comment: This work is a merger of arXiv:2309.09613 and arXiv:2309.10286

UAV-based intelligent data acquisition for 3D reconstruction and monitoring of infrastructure has experienced an increasing surge of interest due to recent advancements in image processing and deep learning-based techniques. View planning is an essential part of this task that dictates the information capture strategy and heavily impacts the quality of the 3D model generated from the captured data. Recent methods have used prior knowledge or partial reconstruction of the target to accomplish view planning for active reconstruction; the former approach poses a challenge for complex or newly identified targets while the latter is computationally expensive. In this work, we present Bag-of-Views (BoV), a fully appearance-based model used to assign utility to the captured views for both offline dataset refinement and online next-best-view (NBV) planning applications targeting the task of 3D reconstruction. With this contribution, we also developed the View Planning Toolbox (VPT), a lightweight package for training and testing machine learning-based view planning frameworks, custom view dataset generation of arbitrary 3D scenes, and 3D reconstruction. Through experiments which pair a BoV-based reinforcement learning model with VPT, we demonstrate the efficacy of our model in reducing the number of required views for high-quality reconstructions in dataset refinement and NBV planning., Comment: Published in IEEE Robotics and Automation Letters (RA-L)

In a recent article, Alon, Hanneke, Holzman, and Moran (FOCS '21) introduced a unifying framework to study the learnability of classes of partial concepts. One of the central questions studied in their work is whether the learnability of a partial concept class is always inherited from the learnability of some ``extension'' of it to a total concept class. They showed this is not the case for PAC learning but left the problem open for the stronger notion of online learnability. We resolve this problem by constructing a class of partial concepts that is online learnable, but no extension of it to a class of total concepts is online learnable (or even PAC learnable).

The issue of Automatic License Plate Recognition (ALPR) has been one of the most challenging issues in recent years. Weather conditions, camera angle of view, lighting conditions, different characters written on license plates, and many other factors are among the challenges for the issue of ALPR. Given the advances that have been made in recent years in the field of deep neural networks, some types of neural networks and models based on them can be used to perform the task of Iranian license plate recognition. In the proposed method presented in this paper, the license plate recognition is done in two steps. The first step is to detect the rectangles of the license plates from the input image. In the second step, these license plates are cropped from the image and their characters are recognized. For the first step, 3065 images including license plates and for the second step, 3364 images including characters of license plates have been prepared and considered as the desired datasets. In the first step, license plates are detected using the YOLOv4-tiny model, which is based on Convolutional Neural Network (CNN). In the next step, the characters of these license plates are recognized using Convolutional Recurrent Neural Network (CRNN), and Connectionist Temporal Classification (CTC). In the second step, there is no need to segment and label the characters separately, only one string of numbers and letters is enough for the labels., Comment: Under Review in Scientia Iranica Journal

During the COVID-19 pandemic, wearing a face mask has been known to be an effective way to prevent the spread of COVID-19. In lots of monitoring tasks, humans have been replaced with computers thanks to the outstanding performance of the deep learning models. Monitoring the wearing of a face mask is another task that can be done by deep learning models with acceptable accuracy. The main challenge of this task is the limited amount of data because of the quarantine. In this paper, we did an investigation on the capability of three state-of-the-art object detection neural networks on face mask detection for real-time applications. As mentioned, here are three models used, Single Shot Detector (SSD), two versions of You Only Look Once (YOLO) i.e., YOLOv4-tiny, and YOLOv4-tiny-3l from which the best was selected. In the proposed method, according to the performance of different models, the best model that can be suitable for use in real-world and mobile device applications in comparison to other recent studies was the YOLOv4-tiny model, with 85.31% and 50.66 for mean Average Precision (mAP) and Frames Per Second (FPS), respectively. These acceptable values were achieved using two datasets with only 1531 images in three separate classes., Comment: Accepted to Scientia Iranica Journal

Depth completion and object detection are two crucial tasks often used for aerial 3D mapping, path planning, and collision avoidance of Uncrewed Aerial Vehicles (UAVs). Common solutions include using measurements from a LiDAR sensor; however, the generated point cloud is often sparse and irregular and limits the system's capabilities in 3D rendering and safety-critical decision-making. To mitigate this challenge, information from other sensors on the UAV (viz., a camera used for object detection) is utilized to help the depth completion process generate denser 3D models. Performing both aerial depth completion and object detection tasks while fusing the data from the two sensors poses a challenge to resource efficiency. We address this challenge by proposing a novel approach to jointly execute the two tasks in a single pass. The proposed method is based on an encoder-focused multi-task learning model that exposes the two tasks to jointly learned features. We demonstrate how semantic expectations of the objects in the scene learned by the object detection pathway can boost the performance of the depth completion pathway while placing the missing depth values. Experimental results show that the proposed multi-task network outperforms its single-task counterpart, particularly when exposed to defective inputs., Comment: 6 pages, 7 figures, submitted to IEEE SMC 2023