Search

This paper addresses the behavior of the Lov\'asz number for dense random circulant graphs. The Lov\'asz number is a well-known semidefinite programming upper bound on the independence number. Circulant graphs, an example of a Cayley graph, are highly structured vertex-transitive graphs on integers modulo $n$, where the connectivity of pairs of vertices depends only on the difference between their labels. While for random circulant graphs the asymptotics of fundamental quantities such as the clique and the chromatic number are well-understood, characterizing the exact behavior of the Lov\'asz number remains open. In this work, we provide upper and lower bounds on the expected value of the Lov\'asz number and show that it scales as the square root of the number of vertices, up to a log log factor. Our proof relies on a reduction of the semidefinite program formulation of the Lov\'asz number to a linear program with random objective and constraints via diagonalization of the adjacency matrix of a circulant graph by the discrete Fourier transform (DFT). This leads to a problem about controlling the norms of vectors with sparse Fourier coefficients, which we study using results on the restricted isometry property of subsampled DFT matrices.

Artificial intelligence (AI) is transforming scientific research, including proteomics. Advances in mass spectrometry (MS)-based proteomics data quality, diversity, and scale, combined with groundbreaking AI techniques, are unlocking new challenges and opportunities in biological discovery. Here, we highlight key areas where AI is driving innovation, from data analysis to new biological insights. These include developing an AI-friendly ecosystem for proteomics data generation, sharing, and analysis; improving peptide and protein identification and quantification; characterizing protein-protein interactions and protein complexes; advancing spatial and perturbation proteomics; integrating multi-omics data; and ultimately enabling AI-empowered virtual cells., Comment: 28 pages, 2 figures, perspective in AI proteomics

The Abstraction and Reasoning Corpus challenges AI systems to perform abstract reasoning with minimal training data, a task intuitive for humans but demanding for machine learning models. Using CodeT5+ as a case study, we demonstrate how limitations in positional encoding hinder reasoning and impact performance. This work further examines the role of positional encoding across transformer architectures, highlighting its critical influence on models of varying sizes and configurations. Comparing several strategies, we find that while 2D positional encoding and Rotary Position Embedding offer competitive performance, 2D encoding excels in data-constrained scenarios, emphasizing its effectiveness for ARC tasks

Matrix concentration inequalities and their recently discovered sharp counterparts provide powerful tools to bound the spectrum of random matrices whose entries are linear functions of independent random variables. However, in many applications in theoretical computer science and in other areas one encounters more general random matrix models, called matrix chaoses, whose entries are polynomials of independent random variables. Such models have often been studied on a case-by-case basis using ad-hoc methods that can yield suboptimal dimensional factors. In this paper we provide general matrix concentration inequalities for matrix chaoses, which enable the treatment of such models in a systematic manner. These inequalities are expressed in terms of flattenings of the coefficients of the matrix chaos. We further identify a special family of matrix chaoses of combinatorial type for which the flattening parameters can be computed mechanically by a simple rule. This allows us to provide a unified treatment of and improved bounds for matrix chaoses that arise in a variety of applications, including graph matrices, Khatri-Rao matrices, and matrices that arise in average case analysis of the sum-of-squares hierarchy., Comment: 28 pages

The cross-section for the associated production of a jet with an electroweak gauge boson ($G = W^{\pm}, Z^0, \gamma$) at forward rapidities in $pp$ and $pA$ collisions is derived within the color - dipole $S$ - matrix framework. We present the full expressions for the differential cross-section of the $q p \rightarrow G q X$ process in the transverse momentum space, considering the longitudinal and transverse polarizations of the gauge boson. We demonstrate that the final formulae can be expressed in terms of the unintegrated gluon distribution and reproduce previous results for the associated jet + $\gamma$ and jet + $Z^0$ production, derived using other frameworks. Moreover, we derive the back - to - back correlation limit of the spectra and show that it can be expressed in terms of the unpolarized and linearly polarized transverse momentum gluon distributions. Our results improve the description of the inclusive jet plus color neutral particle production at forward rapidities, not far from the proton fragmentation region, in $pp$ or $pA$ collisions, and are the main ingredient to study the impact of nonlinear QCD effects in two - particle correlations., Comment: 11 pages, 1 figure. arXiv admin note: text overlap with arXiv:2405.10265

The exponential growth of text-based data in domains such as healthcare, education, and social sciences has outpaced the capacity of traditional qualitative analysis methods, which are time-intensive and prone to subjectivity. Large Language Models (LLMs), powered by advanced generative AI, have emerged as transformative tools capable of automating and enhancing qualitative analysis. This study systematically maps the literature on the use of LLMs for qualitative research, exploring their application contexts, configurations, methodologies, and evaluation metrics. Findings reveal that LLMs are utilized across diverse fields, demonstrating the potential to automate processes traditionally requiring extensive human input. However, challenges such as reliance on prompt engineering, occasional inaccuracies, and contextual limitations remain significant barriers. This research highlights opportunities for integrating LLMs with human expertise, improving model robustness, and refining evaluation methodologies. By synthesizing trends and identifying research gaps, this study aims to guide future innovations in the application of LLMs for qualitative analysis., Comment: 8 pages, includes 1 figures and 3 tables. Submitted and Accepted to the WSESE 2025 ICSE Workshop

Matrix concentration inequalities, intimately connected to the Non-Commutative Khintchine inequality, have been an important tool in both applied and pure mathematics. We study tensor versions of these inequalities, and establish non-asymptotic inequalities for the $\ell_p$ injective norm of random tensors with correlated entries. In certain regimes of $p$ and the tensor order, our tensor concentration inequalities are nearly optimal in their dimension dependencies. We illustrate our result with applications to problems including structured models of random tensors and matrices, tensor PCA, and connections to lower bounds in coding theory. Our techniques are based on covering number estimates as opposed to operator theoretic tools, which also provide a geometric proof of a weaker version of the Non-Commutative Khintchine inequality, motivated by a question of Talagrand.

We present a systematic study of the energy levels of twisted bilayer graphene (tBLG) quantum dots (QD) and rings (QR) under an external perpendicular magnetic field. The confinement structures are modeled by a circular dot-like- and ring-like-shaped site-dependent staggered potential, which prevents edge effects and leads to an energy gap between the electron and hole states. Results are obtained within the tight-binding model with interlayer hopping parameters defined by the Slater-Koster form for different interlayer twist angles $\theta$. Our findings show that, for $\theta$ around 0$^\circ$ or $60^\circ$, the energy spectra exhibit features resulting from the interplay between characteristics of the AA and AB/BA stacking orders that compose the moir\'e pattern of such tBLG, while the low-energy levels are shown to be nearly independent on the rotation angle for $10^\circ\lesssim \theta\lesssim 50^\circ$. In the absence of a magnetic field, the energy levels of the QR scale with its width $W$ according to a power law $W^{-\alpha}$, whose exponent $1 \lessapprox\alpha\lessapprox 2$ depends on the twist angle. Most interestingly, the lowest energy states of tBLG QRs oscillate as a function of its average radius, with the oscillation period matching half of the moir\'e period. In the presence of an intense magnetic field, the lowest energy levels for the tBLG QDs and QRs match almost perfectly, regardless of whether the external radius of the quantum confinement structure is smaller or on the order of the moir\'e period, which is due to the interplay of the trigonal warping effect and the preferential localization of the eigenstates. Our results reveal relevant information about the moir\'e pattern in tBLG and its role in charge particle confinement., Comment: 16 pages, 12 figures

We study the optimization landscape of a smooth nonconvex program arising from synchronization over the two-element group $\mathbf{Z}_2$, that is, recovering $z_1, \dots, z_n \in \{\pm 1\}$ from (noisy) relative measurements $R_{ij} \approx z_i z_j$. Starting from a max-cut--like combinatorial problem, for integer parameter $r \geq 2$, the nonconvex problem we study can be viewed both as a rank-$r$ Burer--Monteiro factorization of the standard max-cut semidefinite relaxation and as a relaxation of $\{ \pm 1 \}$ to the unit sphere in $\mathbf{R}^r$. First, we present deterministic, non-asymptotic conditions on the measurement graph and noise under which every second-order critical point of the nonconvex problem yields exact recovery of the ground truth. Then, via probabilistic analysis, we obtain asymptotic guarantees for three benchmark problems: (1) synchronization with a complete graph and Gaussian noise, (2) synchronization with an Erd\H{o}s--R\'enyi random graph and Bernoulli noise, and (3) graph clustering under the binary symmetric stochastic block model. In each case, we have, asymptotically as the problem size goes to infinity, a benign nonconvex landscape near a previously-established optimal threshold for exact recovery; we can approach this threshold to arbitrary precision with large enough (but finite) rank parameter $r$. In addition, our results are robust to monotone adversaries.

The first paper in this series introduced a new family of nonasymptotic matrix concentration inequalities that sharply capture the spectral properties of very general Gaussian (as well as non-Gaussian) random matrices in terms of an associated noncommutative model. These methods achieved matching upper and lower bounds for smooth spectral statistics, but only provided upper bounds for the spectral edges. Here we obtain matching lower bounds for the spectral edges, completing the theory initiated in the first paper. The resulting two-sided bounds enable the study of applications that require an exact determination of the spectral edges to leading order, which is fundamentally beyond the reach of classical matrix concentration inequalities. To illustrate their utility, we undertake a detailed study of phase transition phenomena for spectral outliers of nonhomogeneous random matrices., Comment: 47 pages, 5 figures; part II of series (part I is arXiv:2108.06312)

We consider a group synchronization problem with multiple frequencies which involves observing pairwise relative measurements of group elements on multiple frequency channels, corrupted by Gaussian noise. We study the computational phase transition in the problem of detecting whether a structured signal is present in such observations by analyzing low-degree polynomial algorithms. We show that, assuming the low-degree conjecture, in synchronization models over arbitrary finite groups as well as over the circle group $SO(2)$, a simple spectral algorithm is optimal among algorithms of runtime $\exp(\tilde{\Omega}(n^{1/3}))$ for detection from an observation including a constant number of frequencies. Combined with an upper bound for the statistical threshold shown in Perry et al., our results indicate the presence of a statistical-to-computational gap in such models with a sufficiently large number of frequencies.

The cross-section for the production of an electroweak gauge boson ($G = W^{\pm}, Z^0, \gamma$) at forward rapidities in $pp$ collisions is derived within the color - dipole $S$ - matrix framework. We present the full expressions for the differential cross-section of the $q p \rightarrow G X$ process in the impact parameter and transverse momentum spaces, considering the longitudinal and transverse polarizations of the gauge boson. The particular cases associated with the Drell - Yan process and real photon production are discussed. We demonstrate that the final formulae are expressed in terms of the dipole - proton cross-section or the unintegrated gluon distribution, and can be used to estimate the impact of the saturation effects in the gauge boson production at the LHC and future colliders., Comment: 18 pages, 2 figures, 1 table

We prove the existence of a positive semidefinite matrix $A \in \mathbb{R}^{n \times n}$ such that any decomposition into rank-1 matrices has to have factors with a large $\ell^1-$norm, more precisely $$ \sum_{k} x_k x_k^*=A \quad \implies \quad \sum_k \|x_k\|^2_{1} \geq c \sqrt{n} \|A\|_{1},$$ where $c$ is independent of $n$. This provides a lower bound for the Balan--Jiang matrix problem. The construction is probabilistic.