Search

We introduce $k$-local quasi-quantum states: a superset of the regular quantum states, defined by relaxing the positivity constraint. We show that a $k$-local quasi-quantum state on $n$ qubits can be 1-1 mapped to a distribution of assignments over $n$ variables with an alphabet of size $4$, which is subject to non-linear constraints over its $k$-local marginals. Therefore, solving the $k$-local Hamiltonian over the quasi-quantum states is equivalent to optimizing a distribution of assignment over a classical $k$-local CSP. We show that this optimization problem is essentially classical by proving it is NP-complete. Crucially, just as ordinary quantum states, these distributions lack a simple tensor-product structure and are therefore not determined straightforwardly by their local marginals. Consequently, our classical optimization problem shares some unique aspects of Hamiltonian complexity: it lacks an easy search-to-decision reduction, and it is not clear that its 1D version can be solved with dynamical programming (i.e., it could remain NP-hard). Our main result is a PCP theorem for the $k$-local Hamiltonian over the quasi-quantum states in the form of a hardness-of-approximation result. The proof suggests the existence of a subtle promise-gap amplification procedure in a model that shares many similarities with the quantum local Hamiltonian problem, thereby providing insights on the quantum PCP conjecture., Comment: 48 pages, 18 figures, comments are welcome

Tokenization is associated with many poorly understood shortcomings in language models (LMs), yet remains an important component for long sequence scaling purposes. This work studies how tokenization impacts model performance by analyzing and comparing the stochastic behavior of tokenized models with their byte-level, or token-free, counterparts. We discover that, even when the two models are statistically equivalent, their predictive distributions over the next byte can be substantially different, a phenomenon we term as "tokenization bias''. To fully characterize this phenomenon, we introduce the Byte-Token Representation Lemma, a framework that establishes a mapping between the learned token distribution and its equivalent byte-level distribution. From this result, we develop a next-byte sampling algorithm that eliminates tokenization bias without requiring further training or optimization. In other words, this enables zero-shot conversion of tokenized LMs into statistically equivalent token-free ones. We demonstrate its broad applicability with two use cases: fill-in-the-middle (FIM) tasks and model ensembles. In FIM tasks where input prompts may terminate mid-token, leading to out-of-distribution tokenization, our method mitigates performance degradation and achieves an approximately 18% improvement in FIM coding benchmarks, consistently outperforming the standard token healing fix. For model ensembles where each model employs a distinct vocabulary, our approach enables seamless integration, resulting in improved performance (up to 3.7%) over individual models across various standard baselines in reasoning, knowledge, and coding.

Periodic collisions between a star on an inclined orbit around a supermassive black hole and its accretion disk offers a promising explanation for X-ray "quasi-periodic eruptions" (QPEs). Each passage through the disk shocks and compresses gas ahead of the star, which subsequently re-expands above the disk as a quasi-spherical cloud. We present spherically symmetric Monte Carlo radiation transport simulations which follow the production of photons behind the radiation-mediated shock, Comptonization by hot electrons, and the eventual escape of the radiation through the expanding debris. Such one-dimension calculations are approximately justified for thin disks, through which the star of radius $R_{\star}$ passes faster than the shocked gas can flow around the star. For collision speeds $v_{\rm coll} \gtrsim 0.15 c$ and disk surface densities $\Sigma \sim 10^{3}$ g cm$^{-2}$ characteristic of those encountered by stellar orbits consistent with QPE recurrence times, the predicted transient light curves exhibit peak luminosities $\gtrsim 10^{42}$ erg s$^{-1}$ and Comptonized quasi-thermal (Wien-like) spectra which peak at energies $h\nu \sim 100$ eV, broadly consistent with QPE properties. For these conditions, gas and radiation are out of equilibrium and the emission temperature is harder than the blackbody value due to inefficient photon production behind the shock. Alternatively, for higher disk densities and/or lower shock velocities, QPE emission could instead represent the comparatively brief phase shortly after shock break-out, though in this case the bulk of the radiation is thermalized and occurs in the ultraviolet instead of the X-ray band. In either scenario, reproducing the observed eruption properties (duration, luminosity, temperature) requires a large radius $R_{\star} \gtrsim 10R_{\odot}$, which may point to inflation of the star's atmosphere from repeated collisions., Comment: 34 pages, 20 figures. Submitted to ApJ

We present our analysis of supernovae serendipitously found to be radio-bright several years after their optical discovery. We used recent observations from the Australian SKA Pathfinder taken as part of the pilot Variables and Slow Transients and Rapid ASKAP Continuum Survey programs. We identified 29 objects by cross-matching sources from these ASKAP observations with known core-collapse supernovae below a declination of $+40^{\circ}$ and with a redshift of $z\leq0.15$. Our results focus on eight cases that show potential late-time radio emission. These supernovae exhibit significantly greater amounts of radio emission than expected from the standard model of a single shockwave propagating through a spherical circumstellar medium, with a constant density structure produced by regular stellar mass-loss. We also discuss how we can learn from future ASKAP surveys about the circumstellar environments and emission mechanisms of supernovae that undergo late-time radio re-brightening. This pilot work tested and confirmed the potential of the Variables and Slow Transients survey to discover and study late-time supernova emission., Comment: Accepted for publication in MNRAS

The LK-99 hype came and went but the great potential of the apatite class of materials as platform for flat bands research must not be swept away in the process. A heuristic reinterpretation of the atomic structure of LK-99 is offered, including electronic signatures from the fully oxidized to the fully reduced. Here, copper is proposed to reside in the apatite channel rather than doping the Lead sublattice. Contact is made with the experimental x-ray powder diffractogram. The electronic signatures are found to reflect those of local [O-Cu-O] and [O-Cu-Vo**] molecular ions, where Vo** is a 2+ charged vacant oxygen site in the apatite channel. The local nature warrants flat bands. Charge carrier concentration is controlled by the oxygen content. Fully reduced LK-99 is a wide band gap insulator with a well-developed intermediate band. Fully oxidized LK-99 is a magnetic insulator, while the partially reduced LK-99 allows for hopping of holes between anti bonding pi orbitals of non-magnetic and magnetic [O-Cu-O] moieties. The findings are extended to include the case where half of the Cu atoms are replaced by Ni and half by Zn. For [O-Ni-O] +[O-Zn-Vo**] inter-site accidental near degeneracy among states at EF is reported, while for [O-Zn-O] + [O-Ni-Vo**] the near-degeneracy at EF on hole doping is among intra-site valence states exclusively on [O-Ni-Vo**]. The apatite platform is ideal for the study of flat bands associated phenomena. The reinterpreted fully reduced LK-99 system invites intrinsic intermediate band solar cells applications. Sites with variable oxygen occupation allow for holes doping, the consequences of which include strong correlations between electrons and lattice that suggest the emergence of (rebuilt) phonons mediated intra- as well as inter- bands (virtual) electron transfer-based phenomena, feeding the quest for ambient conditions superconductivity., Comment: 10 pages, 6 figures

There is growing evidence of the effectiveness of Shampoo, a higher-order preconditioning method, over Adam in deep learning optimization tasks. However, Shampoo's drawbacks include additional hyperparameters and computational overhead when compared to Adam, which only updates running averages of first- and second-moment quantities. This work establishes a formal connection between Shampoo (implemented with the 1/2 power) and Adafactor -- a memory-efficient approximation of Adam -- showing that Shampoo is equivalent to running Adafactor in the eigenbasis of Shampoo's preconditioner. This insight leads to the design of a simpler and computationally efficient algorithm: $\textbf{S}$hampo$\textbf{O}$ with $\textbf{A}$dam in the $\textbf{P}$reconditioner's eigenbasis (SOAP). With regards to improving Shampoo's computational efficiency, the most straightforward approach would be to simply compute Shampoo's eigendecomposition less frequently. Unfortunately, as our empirical results show, this leads to performance degradation that worsens with this frequency. SOAP mitigates this degradation by continually updating the running average of the second moment, just as Adam does, but in the current (slowly changing) coordinate basis. Furthermore, since SOAP is equivalent to running Adam in a rotated space, it introduces only one additional hyperparameter (the preconditioning frequency) compared to Adam. We empirically evaluate SOAP on language model pre-training with 360m and 660m sized models. In the large batch regime, SOAP reduces the number of iterations by over 40% and wall clock time by over 35% compared to AdamW, with approximately 20% improvements in both metrics compared to Shampoo. An implementation of SOAP is available at https://github.com/nikhilvyas/SOAP.

The sum of the absolute values of the Fourier coefficients of a function $f:\mathbb{F}_2^n \to \mathbb{R}$ is called the spectral norm of $f$. Green and Sanders' quantitative version of Cohen's idempotent theorem states that if the spectral norm of $f:\mathbb{F}_2^n \to \{0,1\}$ is at most $M$, then the support of $f$ belongs to the ring of sets generated by at most $\ell(M)$ cosets, where $\ell(M)$ is a constant that only depends on $M$. We prove that the above statement can be generalized to \emph{approximate} spectral norms if and only if the support of $f$ and its complement satisfy a certain arithmetic connectivity condition. In particular, our theorem provides a new proof of the quantitative Cohen's theorem for $\mathbb{F}_2^n$.

We study how the rigidity transition in a triangular lattice changes as a function of anisotropy by preferentially filling bonds on the lattice in one direction. We discover that the onset of rigidity in anisotropic spring networks arises in at least two steps, reminiscent of the two-step melting transition in two dimensional crystals. In particular, our simulations demonstrate that the percolation of stress-supporting bonds happens at different critical volume fractions along different directions. By examining each independent component of the elasticity tensor, we determine universal exponents and develop universal scaling functions to analyze isotropic rigidity percolation as a multicritical point. We expect that these results will be important for elucidating the underlying mechanical phase transitions governing the properties of biological materials ranging from the cytoskeletons of cells to the extracellular networks of tissues such as tendon where the networks are often preferentially aligned., Comment: 13 pages, 17 figures

We present foundations of globally valued fields, i.e., of a class of fields with an extra structure, capturing some aspects of the geometry of global fields, based on the product formula. We provide a dictionary between various data defining such extra structure: syntactic (models of some unbounded continuous logic theory), Arakelov theoretic, and measure theoretic. In particular we obtain a representation theorem relating globally valued fields and adelic curves defined by Chen and Moriwaki., Comment: 51 pages

We describe an efficient algorithm to compute finite type invariants of type $k$ by first creating, for a given knot $K$ with $n$ crossings, a look-up table for all subdiagrams of $K$ of size $\lceil \frac{k}{2}\rceil$ indexed by dyadic intervals in $[0,2n-1]$. Using this algorithm, any such finite type invariant can be computed on an $n$-crossing knot in time $\sim n^{\lceil \frac{k}{2}\rceil}$, a lot faster than the previously best published bound of $\sim n^k$.

We propose MeshUp, a technique that deforms a 3D mesh towards multiple target concepts, and intuitively controls the region where each concept is expressed. Conveniently, the concepts can be defined as either text queries, e.g., "a dog" and "a turtle," or inspirational images, and the local regions can be selected as any number of vertices on the mesh. We can effectively control the influence of the concepts and mix them together using a novel score distillation approach, referred to as the Blended Score Distillation (BSD). BSD operates on each attention layer of the denoising U-Net of a diffusion model as it extracts and injects the per-objective activations into a unified denoising pipeline from which the deformation gradients are calculated. To localize the expression of these activations, we create a probabilistic Region of Interest (ROI) map on the surface of the mesh, and turn it into 3D-consistent masks that we use to control the expression of these activations. We demonstrate the effectiveness of BSD empirically and show that it can deform various meshes towards multiple objectives. Our project page is at https://threedle.github.io/MeshUp., Comment: Project page: https://threedle.github.io/MeshUp

A leading family of algorithms for state estimation in dynamic systems with multiple sub-states is based on particle filters (PFs). PFs often struggle when operating under complex or approximated modelling (necessitating many particles) with low latency requirements (limiting the number of particles), as is typically the case in multi target tracking (MTT). In this work, we introduce a deep neural network (DNN) augmentation for PFs termed learning flock (LF). LF learns to correct a particles-weights set, which we coin flock, based on the relationships between all sub-particles in the set itself, while disregarding the set acquisition procedure. Our proposed LF, which can be readily incorporated into different PFs flow, is designed to facilitate rapid operation by maintaining accuracy with a reduced number of particles. We introduce a dedicated training algorithm, allowing both supervised and unsupervised training, and yielding a module that supports a varying number of sub-states and particles without necessitating re-training. We experimentally show the improvements in performance, robustness, and latency of LF augmentation for radar multi-target tracking, as well its ability to mitigate the effect of a mismatched observation modelling. We also compare and illustrate the advantages of LF over a state-of-the-art DNN-aided PF, and demonstrate that LF enhances both classic PFs as well as DNN-based filters., Comment: Under review for publication in the IEEE

We study the steady-state properties of quantum channels with local Kraus operators. We consider a large family that consists of general ergodic 1-local (non-interacting) terms and general 2-local (interacting) terms. Physically, a repeated application of these channels can be seen as a simple model for the thermalization process of a many-body system. We study its steady state perturbatively by interpolating between the 1-local and 2-local channels with a perturbation parameter $\epsilon$. We prove that under very general conditions, these states are Gibbs states of a quasi-local Hamiltonian. Expanding this Hamiltonian as a series in $\epsilon$, we show that the $k$'th order term corresponds to a $(k+1)$-local interaction term in the Hamiltonian, which follows the same interaction graph as the Kraus channel. We also prove a complementary result suggesting the existence of an interaction strength threshold, under which the total weight of the high-order terms in the Hamiltonian decays exponentially fast. This result also implies a quasi-polynomial classical algorithm for computing the expectation value of local observables in such steady states. Finally, we also present numerical simulations of various channels that support our theoretical claims., Comment: 26 pages

Modern artificial intelligence (AI) systems are powered by foundation models. This paper presents a new set of foundation models, called Llama 3. It is a herd of language models that natively support multilinguality, coding, reasoning, and tool usage. Our largest model is a dense Transformer with 405B parameters and a context window of up to 128K tokens. This paper presents an extensive empirical evaluation of Llama 3. We find that Llama 3 delivers comparable quality to leading language models such as GPT-4 on a plethora of tasks. We publicly release Llama 3, including pre-trained and post-trained versions of the 405B parameter language model and our Llama Guard 3 model for input and output safety. The paper also presents the results of experiments in which we integrate image, video, and speech capabilities into Llama 3 via a compositional approach. We observe this approach performs competitively with the state-of-the-art on image, video, and speech recognition tasks. The resulting models are not yet being broadly released as they are still under development.

Several proposals aiming to demonstrate quantum advantage on near-term quantum computers rely on the optimization of variational circuits. These approaches include, for example, variational quantum eigensolvers and many-body quantum simulators and their realization with limited computational techniques critically depends on the development of efficient optimization techniques. In this paper, we introduce a new optimization strategy for dense quantum circuits, leveraging tensor network optimization principles. Our approach focuses on optimizing one gate at a time by fully characterizing the dependency of the cost function on the gate through environment tensor tomography, obtained via noisy measurements on a quantum device. We compute the minimal number of measurements needed to perform a full tensor tomography and relate this number to unitary 2-design. We then describe a general framework for landscape tomography based on linear regression and compare two different implementations based on shadow tomography and Clifford tableaux, respectively. Finally, we compare our strategy with both gradient-free optimization and gradient-based optimization based on the parameter-shift rule, highlighting potential benefits of our algorithm for the development of quantum algorithms in noisy devices.

The origin of warm ions in the circum-galactic medium (CGM) surrounding massive galaxies remains a mystery. In this paper, we argue that a significant fraction of the observed warm-ion columns may arise in the intergalactic medium (IGM) surrounding galactic halos. We use a simple spherical collapse model of the dark matter (DM) halos and their baryonic content to compute the evolving ion fractions within and outside virial halos. We show that the photoionized IGM may produce a thick blanket of warm ions around the CGM, thereby contaminating CGM observations. We find that the IGM contributes $> 75\%$ of the total \ion{O}{6} column densities in halos with virial masses exceeding a few times $10^{11}~M_\odot$, and that it may dominate the \ion{O}{6} absorption even for lower mass-halos, depending on the impact parameter. We compare our results with observations and find that our simplified model reproduces the overall \ion{O}{6} columns as well as their trend with the impact parameter and halo mass. We show that observed warm ion columns may be completely dominated by the IGM envelopes, consistent with CGM$^2$ data. We, therefore, suggest that theoretical interpretations of CGM-survey observations must consider the possible contribution of the surrounding IGM. Although our simplified model suggests that it may be possible to kinematically distinguish between CGM and IGM origins through the absorption line profiles, this distinction is likely unfeasible in realistic astrophysical halos, due to the complex velocity structure in the multi-phased CGM., Comment: 12 pages, 6 figures

Despite Flow Matching and diffusion models having emerged as powerful generative paradigms for continuous variables such as images and videos, their application to high-dimensional discrete data, such as language, is still limited. In this work, we present Discrete Flow Matching, a novel discrete flow paradigm designed specifically for generating discrete data. Discrete Flow Matching offers several key contributions: (i) it works with a general family of probability paths interpolating between source and target distributions; (ii) it allows for a generic formula for sampling from these probability paths using learned posteriors such as the probability denoiser ($x$-prediction) and noise-prediction ($\epsilon$-prediction); (iii) practically, focusing on specific probability paths defined with different schedulers considerably improves generative perplexity compared to previous discrete diffusion and flow models; and (iv) by scaling Discrete Flow Matching models up to 1.7B parameters, we reach 6.7% Pass@1 and 13.4% Pass@10 on HumanEval and 6.7% Pass@1 and 20.6% Pass@10 on 1-shot MBPP coding benchmarks. Our approach is capable of generating high-quality discrete data in a non-autoregressive fashion, significantly closing the gap between autoregressive models and discrete flow models.

Current methods for reconstructing training data from trained classifiers are restricted to very small models, limited training set sizes, and low-resolution images. Such restrictions hinder their applicability to real-world scenarios. In this paper, we present a novel approach enabling data reconstruction in realistic settings for models trained on high-resolution images. Our method adapts the reconstruction scheme of arXiv:2206.07758 to real-world scenarios -- specifically, targeting models trained via transfer learning over image embeddings of large pre-trained models like DINO-ViT and CLIP. Our work employs data reconstruction in the embedding space rather than in the image space, showcasing its applicability beyond visual data. Moreover, we introduce a novel clustering-based method to identify good reconstructions from thousands of candidates. This significantly improves on previous works that relied on knowledge of the training set to identify good reconstructed images. Our findings shed light on a potential privacy risk for data leakage from models trained using transfer learning.

Rigidity transitions induced by the formation of system-spanning disordered rigid clusters, like the jamming transition, can be well-described in most physically relevant dimensions by mean-field theories. A dynamical mean-field theory commonly used to study these transitions, the coherent potential approximation (CPA), shows logarithmic corrections in $2$ dimensions. By solving the theory in arbitrary dimensions and extracting the universal scaling predictions, we show that these logarithmic corrections are a symptom of an upper critical dimension $d_{u}=2$, below which the critical exponents are modified. We recapitulate Ken Wilson's phenomenology of the $(4-\epsilon)$-dimensional Ising model, but with the upper critical dimension reduced to $2$. We interpret this using normal form theory as a transcritical bifurcation in the RG flows and extract the universal nonlinear coefficients to make explicit predictions for the behavior near $2$ dimensions. This bifurcation is driven by a variable that is dangerously irrelevant in all dimensions $d>2$ which incorporates the physics of long-wavelength phonons and low-frequency elastic dissipation. We derive universal scaling functions from the CPA sufficient to predict all linear response in randomly diluted isotropic elastic systems in all dimensions., Comment: 22 pages, 6 figures. Revised abstract, added references

Affine logic is a fragment of continuous logic, introduced by Bagheri, in which only affine functions are allowed as connectives. This has the effect of endowing type spaces with the structure of compact convex sets. We study extremal models of affine theories (those that only realize extreme types), and the ways and conditions under which all models can be described from the extremal ones. We introduce and develop the general theory of measurable fields of metric structures and their direct integrals. One of our main results is an extremal decomposition theorem for models of simplicial theories, that is, affine theories whose type spaces form Choquet simplices. We prove that every model of a simplicial theory can be (uniquely) decomposed as a direct integral of extremal models. This generalizes known decomposition results (ergodic decomposition, tracial von Neumann factor decomposition), and moreover, holds without any separability hypothesis. Two extreme kinds of simplicial theories are Bauer theories, whose extreme types form a closed set, and Poulsen theories, whose extreme types form a dense set. We show that Keisler randomizations of continuous theories are, essentially, the same thing as affine Bauer theories. We establish a dichotomy result: a complete simplicial theory is either Bauer or Poulsen. As part of our analysis, we adapt many results and tools from continuous logic to the affine or extremal contexts (definability, saturation, type isolation, categoricity, etc.). We also provide a detailed study of the relations between continuous logic and affine logic. Finally, we present several examples of simplicial theories arising from theories in discrete logic, Hilbert spaces, probability measure-preserving systems, and tracial von Neumann algebras., Comment: 133 pages

We propose a dynamic product adoption persuasion model involving an impatient partially informed sender who gradually learns the state. In this model, the sender gathers information over time, and hence her posteriors' sequence forms a discrete-time martingale. The sender commits to a dynamic revelation policy to persuade the agent to adopt a product. We demonstrate that under the assumption that the sender's martingale possesses Blackwell-preserving kernels, the family of optimal strategies for the sender takes an interval form; namely, in every period the set of martingale realizations in which adoption occurs is an interval. Utilizing this, we prove that if the sender is sufficiently impatient, then under a random walk martingale, the optimal policy is fully transparent up to the moment of adoption; namely, the sender reveals the entire information she privately holds in every period.

In recent years, variational quantum algorithms (VQAs) have gained significant attention due to their adaptability and efficiency on near-term quantum hardware. They have shown potential in a variety of tasks, including linear algebra, search problems, Gibbs and ground state preparation. Nevertheless, the presence of noise in current day quantum hardware, severely limits their performance. In this work, we introduce dissipative variational quantum algorithms (D-VQAs) by incorporating dissipative operations, such as qubit RESET and stochastic gates, as an intrinsic part of a variational quantum circuit. We argue that such dissipative variational algorithms posses some natural resilience to dissipative noise. We demonstrate how such algorithms can prepare Gibbs states over a wide range of quantum many-body Hamiltonians and temperatures, while significantly reducing errors due to both coherent and non-coherent noise. An additional advantage of our approach is that no ancilla qubits are need. Our results highlight the potential of D-VQAs to enhance the robustness and accuracy of variational quantum computations on NISQ devices., Comment: 9 + 3 pages, 6 figures, comments are welcome

In this paper, we present and study the \emph{Hamming distance oracle problem}. In this problem, the task is to preprocess two strings $S$ and $T$ of lengths $n$ and $m$, respectively, to obtain a data-structure that is able to answer queries regarding the Hamming distance between a substring of $S$ and a substring of $T$. For a constant size alphabet strings, we show that for every $x\le nm$ there is a data structure with $\tilde{O}(nm/x)$ preprocess time and $O(x)$ query time. We also provide a combinatorial conditional lower bound, showing that for every $\varepsilon > 0$ and $x \le nm$ there is no data structure with query time $O(x)$ and preprocess time $O((\frac{nm}{x})^{1-\varepsilon})$ unless combinatorial fast matrix multiplication is possible. For strings over general alphabet, we present a data structure with $\tilde{O}(nm/\sqrt{x})$ preprocess time and $O(x)$ query time for every $x \le nm$.

We consider Roche lobe overflow (RLO) from a low-mass star on a nearly circular orbit, onto a supermassive black hole (SMBH). If mass transfer is unstable, its rate accelerates in a runaway process, resulting in highly super-Eddington mass accretion rates, accompanied by an optically-thick outflow emanating from the SMBH vicinity. This produces a week-month long, bright optical/Ultraviolet flare, accompanied by a year-decade long X-ray precursor and post-cursor emitted from the accretion flow onto the SMBH. Such ``Circular Tidal Disruption Events (TDEs)" represent a new class of nuclear transients, occurring at up to $1-10\%$ of the canonical parabolic tidal disruption event rate. Near breakup rotation and strong tidal deformation of the star prior to disruption could lead to strong magnetic fields, making circular-TDEs possible progenitors of jetted TDEs. Outflows prior to the final stellar disruption produce a circum-nuclear environment (CNM) with $\sim \rm 10^{-2} \, M_\odot$ at distances of $\sim 0.01-0.1 \, \rm pc$, likely leading to bright radio emission, and also similar to the CNM inferred for jetted TDEs. We discuss broader connections between circular TDEs and other recently identified classes of transients associated with galactic nuclei, such as repeating-TDEs and Quasi-Periodic X-ray Eruptions, as well as possible connections to luminous fast blue optical transients such as AT2018cow. We also discuss observational signatures of the analogous RLO of a white dwarf around an intermediate mass BH, which may be a multi-messenger source in the LISA era., Comment: 22 pages, 7 figures. Submitted to ApJ. Comments are welcome

Supermassive black holes and their surrounding dense stellar environments nourish a variety of astrophysical phenomena. We focus on the distribution of stellar-mass black holes around the supermassive black hole and the consequent formation of extreme mass-ratio inspirals (EMRIs). We derive a steady-state distribution, considering the effects of two-body scatterings and gravitational wave emission, and calculate the EMRI formation rate, eccentricity distribution and EMRI-to-plunge ratio. Our model predicts: (I) A stronger segregation than previously estimated at the outskirts of the sphere of influence (at $\sim0.01\rm pc$ to $2\rm pc$ for a Milky Way-like galaxy). (II) An increased EMRI-to-plunge ratio, favoring EMRIs at galaxies where stellar-mass black holes are scarce. (III) A detection of about $2\times10^3$ resolvable EMRIs, with a signal-to-noise ratio above $20$, along a $4$ year LISA mission time. (IV) A confusion noise, induced by a cosmological population of unresolved EMRIs, reducing LISA sensitivity in the $1-5\ \rm mHz$ frequency range by up to a factor of $\approx2$, relative to the instrumental noise., Comment: 15 pages, 6 figures. Submitted to ApJ

Shampoo, a second-order optimization algorithm which uses a Kronecker product preconditioner, has recently garnered increasing attention from the machine learning community. The preconditioner used by Shampoo can be viewed either as an approximation of the Gauss--Newton component of the Hessian or the covariance matrix of the gradients maintained by Adagrad. We provide an explicit and novel connection between the $\textit{optimal}$ Kronecker product approximation of these matrices and the approximation made by Shampoo. Our connection highlights a subtle but common misconception about Shampoo's approximation. In particular, the $\textit{square}$ of the approximation used by the Shampoo optimizer is equivalent to a single step of the power iteration algorithm for computing the aforementioned optimal Kronecker product approximation. Across a variety of datasets and architectures we empirically demonstrate that this is close to the optimal Kronecker product approximation. Additionally, for the Hessian approximation viewpoint, we empirically study the impact of various practical tricks to make Shampoo more computationally efficient (such as using the batch gradient and the empirical Fisher) on the quality of Hessian approximation.

We present JASCO, a temporally controlled text-to-music generation model utilizing both symbolic and audio-based conditions. JASCO can generate high-quality music samples conditioned on global text descriptions along with fine-grained local controls. JASCO is based on the Flow Matching modeling paradigm together with a novel conditioning method. This allows music generation controlled both locally (e.g., chords) and globally (text description). Specifically, we apply information bottleneck layers in conjunction with temporal blurring to extract relevant information with respect to specific controls. This allows the incorporation of both symbolic and audio-based conditions in the same text-to-music model. We experiment with various symbolic control signals (e.g., chords, melody), as well as with audio representations (e.g., separated drum tracks, full-mix). We evaluate JASCO considering both generation quality and condition adherence, using both objective metrics and human studies. Results suggest that JASCO is comparable to the evaluated baselines considering generation quality while allowing significantly better and more versatile controls over the generated music. Samples are available on our demo page https://pages.cs.huji.ac.il/adiyoss-lab/JASCO.

While large language models (LLMs) excel in various natural language tasks in English, their performance in lower-resourced languages like Hebrew, especially for generative tasks such as abstractive summarization, remains unclear. The high morphological richness in Hebrew adds further challenges due to the ambiguity in sentence comprehension and the complexities in meaning construction. In this paper, we address this resource and evaluation gap by introducing HeSum, a novel benchmark specifically designed for abstractive text summarization in Modern Hebrew. HeSum consists of 10,000 article-summary pairs sourced from Hebrew news websites written by professionals. Linguistic analysis confirms HeSum's high abstractness and unique morphological challenges. We show that HeSum presents distinct difficulties for contemporary state-of-the-art LLMs, establishing it as a valuable testbed for generative language technology in Hebrew, and MRLs generative challenges in general.

We tackle the task of learning dynamic 3D semantic radiance fields given a single monocular video as input. Our learned semantic radiance field captures per-point semantics as well as color and geometric properties for a dynamic 3D scene, enabling the generation of novel views and their corresponding semantics. This enables the segmentation and tracking of a diverse set of 3D semantic entities, specified using a simple and intuitive interface that includes a user click or a text prompt. To this end, we present DGD, a unified 3D representation for both the appearance and semantics of a dynamic 3D scene, building upon the recently proposed dynamic 3D Gaussians representation. Our representation is optimized over time with both color and semantic information. Key to our method is the joint optimization of the appearance and semantic attributes, which jointly affect the geometric properties of the scene. We evaluate our approach in its ability to enable dense semantic 3D object tracking and demonstrate high-quality results that are fast to render, for a diverse set of scenes. Our project webpage is available on https://isaaclabe.github.io/DGD-Website/

Is it possible to understand or imitate a policy maker's rationale by looking at past decisions they made? We formalize this question as the problem of learning social welfare functions belonging to the well-studied family of power mean functions. We focus on two learning tasks; in the first, the input is vectors of utilities of an action (decision or policy) for individuals in a group and their associated social welfare as judged by a policy maker, whereas in the second, the input is pairwise comparisons between the welfares associated with a given pair of utility vectors. We show that power mean functions are learnable with polynomial sample complexity in both cases, even if the comparisons are social welfare information is noisy. Finally, we design practical algorithms for these tasks and evaluate their performance.

We introduce and study the problem of detecting whether an agent is updating their prior beliefs given new evidence in an optimal way that is Bayesian, or whether they are biased towards their own prior. In our model, biased agents form posterior beliefs that are a convex combination of their prior and the Bayesian posterior, where the more biased an agent is, the closer their posterior is to the prior. Since we often cannot observe the agent's beliefs directly, we take an approach inspired by information design. Specifically, we measure an agent's bias by designing a signaling scheme and observing the actions they take in response to different signals, assuming that they are maximizing their own expected utility; our goal is to detect bias with a minimum number of signals. Our main results include a characterization of scenarios where a single signal suffices and a computationally efficient algorithm to compute optimal signaling schemes.

In many sequential decision problems, an agent performs a repeated task. He then suffers regret and obtains information that he may use in the following rounds. However, sometimes the agent may also obtain information and avoid suffering regret by querying external sources. We study the trade-off between the information an agent accumulates and the regret it suffers. We invoke information-theoretic methods for obtaining regret lower bounds, that also allow us to easily re-derive several known lower bounds. We introduce the first Bayesian regret lower bounds that depend on the information an agent accumulates. We also prove regret upper bounds using the amount of information the agent accumulates. These bounds show that information measured in bits, can be traded off for regret, measured in reward. Finally, we demonstrate the utility of these bounds in improving the performance of a question-answering task with large language models, allowing us to obtain valuable insights.

In the context of reinforcement learning from human feedback (RLHF), the reward function is generally derived from maximum likelihood estimation of a random utility model based on pairwise comparisons made by humans. The problem of learning a reward function is one of preference aggregation that, we argue, largely falls within the scope of social choice theory. From this perspective, we can evaluate different aggregation methods via established axioms, examining whether these methods meet or fail well-known standards. We demonstrate that both the Bradley-Terry-Luce Model and its broad generalizations fail to meet basic axioms. In response, we develop novel rules for learning reward functions with strong axiomatic guarantees. A key innovation from the standpoint of social choice is that our problem has a linear structure, which greatly restricts the space of feasible rules and leads to a new paradigm that we call linear social choice.

In economies without monetary transfers, token systems serve as an alternative to sustain cooperation, alleviate free riding, and increase efficiency. This paper studies whether a token-based economy can be effective in marketplaces with thin exogenous supply. We consider a marketplace in which at each time period one agent requests a service, one agent provides the service, and one token (artificial currency) is used to pay for service provision. The number of tokens each agent has represents the difference between the amount of service provisions and service requests by the agent. We are interested in the behavior of this economy when very few agents are available to provide the requested service. Since balancing the number of tokens across agents is key to sustain cooperation, the agent with the minimum amount of tokens is selected to provide service among the available agents. When exactly one random agent is available to provide service, we show that the token distribution is unstable. However, already when just two random agents are available to provide service, the token distribution is stable, in the sense that agents' token balance is unlikely to deviate much from their initial endowment, and agents return to their initial endowment in finite expected time. Our results mirror the power of two choices paradigm in load balancing problems. Supported by numerical simulations using kidney exchange data, our findings suggest that token systems may generate efficient outcomes in kidney exchange marketplaces by sustaining cooperation between hospitals., Comment: 32 pages

A $\lambda$-cover of a string $S$ is a set of strings $\{C_i\}_1^\lambda$ such that every index in $S$ is contained in an occurrence of at least one string $C_i$. The existence of a $1$-cover defines a well-known class of quasi-periodic strings. Quasi-periodicity can be decided in linear time, and all $1$-covers of a string can be reported in linear time plus the size of the output. Since in general it is NP-complete to decide whether a string has a $\lambda$-cover, the natural next step is the development of efficient algorithms for $2$-covers. Radoszewski and Straszy\'nski [ESA 2020] analysed the particular case where the strings in a $2$-cover must be of the same length. They provided an algorithm that reports all such $2$-covers of $S$ in time near-linear in $|S|$ and in the size of the output. In this work, we consider $2$-covers in full generality. Since every length-$n$ string has $\Omega(n^2)$ trivial $2$-covers (every prefix and suffix of total length at least $n$ constitute such a $2$-cover), we state the reporting problem as follows: given a string $S$ and a number $m$, report all $2$-covers $\{C_1,C_2\}$ of $S$ with length $|C_1|+|C_2|$ upper bounded by $m$. We present an $\tilde{O}(n + Output)$ time algorithm solving this problem, with Output being the size of the output. This algorithm admits a simpler modification that finds a $2$-cover of minimum length. We also provide an $\tilde{O}(n)$ time construction of a $2$-cover oracle which, given two substrings $C_1,C_2$ of $S$, reports in poly-logarithmic time whether $\{C_1,C_2\}$ is a $2$-cover of $S$., Comment: 31 pages

We consider the problem of learning uncertainty regions for parameter estimation problems. The regions are ellipsoids that minimize the average volumes subject to a prescribed coverage probability. As expected, under the assumption of jointly Gaussian data, we prove that the optimal ellipsoid is centered around the conditional mean and shaped as the conditional covariance matrix. In more practical cases, we propose a differentiable optimization approach for approximately computing the optimal ellipsoids using a neural network with proper calibration. Compared to existing methods, our network requires less storage and less computations in inference time, leading to accurate yet smaller ellipsoids. We demonstrate these advantages on four real-world localization datasets.

Systems driven far from equilibrium often retain structural memories of their processing history. This memory has, in some cases, been shown to dramatically alter the material response. For example, work hardening in crystalline metals can alter the hardness, yield strength, and tensile strength to prevent catastrophic failure. Whether memory of processing history can be similarly exploited in flowing systems, where significantly larger changes in structure should be possible, remains poorly understood. Here, we demonstrate a promising route to embedding such useful memories. We build on work showing that exposing a sheared dense suspension to acoustic perturbations of different power allows for dramatically tuning the sheared suspension viscosity and underlying structure. We find that, for sufficiently dense suspensions, upon removing the acoustic perturbations, the suspension shear jams with shear stress contributions from the maximum compressive and maximum extensive axes that reflect the acoustic training. Because the contributions from these two orthogonal axes to the total shear stress are antagonistic, it is possible to tune the resulting suspension response in surprising ways. For example, we show that differently trained sheared suspensions exhibit: 1) different susceptibility to the same acoustic perturbation; 2) orders of magnitude changes in their instantaneous viscosities upon shear reversal; and 3) even a shear stress that increases in magnitude upon shear cessation. To further illustrate the power of this approach for controlling suspension properties, we demonstrate that flowing states well below the shear jamming threshold can be shear jammed via acoustic training. Collectively, our work paves the way for using acoustically induced memory in dense suspensions to generate rapidly and widely tunable materials., Comment: To be published in Physical Review X

A modest fraction of the stars in galactic nuclei fed towards the central supermassive black hole (SMBH) approach on low-eccentricity orbits driven by gravitational-wave radiation (extreme mass ratio inspiral, EMRI). In the likely event that a gaseous accretion disk is created in the nucleus during this slow inspiral (e.g., via an independent tidal-disruption event; TDE), star-disk collisions generate regular short-lived flares consistent with the observed quasi-periodic eruption (QPE) sources. We present a model for the coupled star-disk evolution which self-consistently accounts for mass and thermal energy injected into the disk from stellar collisions and associated mass ablation. For weak collision/ablation heating, the disk is thermally-unstable and undergoes limit-cycle oscillations which modulate its properties and lead to accretion-powered outbursts on timescales of years to decades, with a time-averaged accretion rate $\sim 0.1 \dot{M}_{\rm Edd}$. Stronger collision/ablation heating acts to stabilize the disk, enabling roughly steady accretion at the EMRI-stripping rate. In either case, the stellar destruction time through ablation, and hence the maximum QPE lifetime, is $\sim 10^{2}-10^{3}$ yr, far longer than fall-back accretion after a TDE. The quiescent accretion disks in QPE sources may at the present epoch be self-sustaining and fed primarily by EMRI ablation. Indeed, the observed range of secular variability broadly match those predicted for collision-fed disks. Changes in the QPE recurrence pattern following such outbursts, similar to that observed in GSN 069, could arise from temporary misalignment between the EMRI-fed disk and the SMBH equatorial plane as the former regrows its mass after a state transition., Comment: 24 pages, 6 figures. Submitted to ApJ. Comments welcome!

Hairpin completion, derived from the hairpin formation observed in DNA biochemistry, is an operation applied to strings, particularly useful in DNA computing. Conceptually, a right hairpin completion operation transforms a string $S$ into $S\cdot S'$ where $S'$ is the reverse complement of a prefix of $S$. Similarly, a left hairpin completion operation transforms a string $S$ into $S'\cdot S$ where $S'$ is the reverse complement of a suffix of $S$. The hairpin completion distance from $S$ to $T$ is the minimum number of hairpin completion operations needed to transform $S$ into $T$. Recently Boneh et al. showed an $O(n^2)$ time algorithm for finding the hairpin completion distance between two strings of length at most $n$. In this paper we show that for any $\varepsilon>0$ there is no $O(n^{2-\varepsilon})$-time algorithm for the hairpin completion distance problem unless the Strong Exponential Time Hypothesis (SETH) is false. Thus, under SETH, the time complexity of the hairpin completion distance problem is quadratic, up to sub-polynomial factors., Comment: To be published in CPM 2024

We present iSeg, a new interactive technique for segmenting 3D shapes. Previous works have focused mainly on leveraging pre-trained 2D foundation models for 3D segmentation based on text. However, text may be insufficient for accurately describing fine-grained spatial segmentations. Moreover, achieving a consistent 3D segmentation using a 2D model is challenging since occluded areas of the same semantic region may not be visible together from any 2D view. Thus, we design a segmentation method conditioned on fine user clicks, which operates entirely in 3D. Our system accepts user clicks directly on the shape's surface, indicating the inclusion or exclusion of regions from the desired shape partition. To accommodate various click settings, we propose a novel interactive attention module capable of processing different numbers and types of clicks, enabling the training of a single unified interactive segmentation model. We apply iSeg to a myriad of shapes from different domains, demonstrating its versatility and faithfulness to the user's specifications. Our project page is at https://threedle.github.io/iSeg/., Comment: Project page: https://threedle.github.io/iSeg/

We propose a method that achieves near-optimal rates for smooth stochastic convex optimization and requires essentially no prior knowledge of problem parameters. This improves on prior work which requires knowing at least the initial distance to optimality d0. Our method, U-DoG, combines UniXGrad (Kavis et al., 2019) and DoG (Ivgi et al., 2023) with novel iterate stabilization techniques. It requires only loose bounds on d0 and the noise magnitude, provides high probability guarantees under sub-Gaussian noise, and is also near-optimal in the non-smooth case. Our experiments show consistent, strong performance on convex problems and mixed results on neural network training.

An inertial navigation system (INS) utilizes three orthogonal accelerometers and gyroscopes to determine platform position, velocity, and orientation. There are countless applications for INS, including robotics, autonomous platforms, and the internet of things. Recent research explores the integration of data-driven methods with INS, highlighting significant innovations, improving accuracy and efficiency. Despite the growing interest in this field and the availability of INS datasets, no datasets are available for gyro-free INS (GFINS) and multiple inertial measurement unit (MIMU) architectures. To fill this gap and to stimulate further research in this field, we designed and recorded GFINS and MIMU datasets using 54 inertial sensors grouped in nine inertial measurement units. These sensors can be used to define and evaluate different types of MIMU and GFINS architectures. The inertial sensors were arranged in three different sensor configurations and mounted on a mobile robot and a passenger car. In total, the dataset contains 35 hours of inertial data and corresponding ground truth trajectories. The data and code are freely accessible through our GitHub repository., Comment: 10 pages, 16 figures, 6 tables

We present an innovative approach leveraging Physics-Guided Neural Networks (PGNNs) for enhancing agricultural quality assessments. Central to our methodology is the application of physics-guided inverse regression, a technique that significantly improves the model's ability to precisely predict quality metrics of crops. This approach directly addresses the challenges of scalability, speed, and practicality that traditional assessment methods face. By integrating physical principles, notably Fick`s second law of diffusion, into neural network architectures, our developed PGNN model achieves a notable advancement in enhancing both the interpretability and accuracy of assessments. Empirical validation conducted on cucumbers and mushrooms demonstrates the superior capability of our model in outperforming conventional computer vision techniques in postharvest quality evaluation. This underscores our contribution as a scalable and efficient solution to the pressing demands of global food supply challenges.

We present the first finite time global convergence analysis of policy gradient in the context of infinite horizon average reward Markov decision processes (MDPs). Specifically, we focus on ergodic tabular MDPs with finite state and action spaces. Our analysis shows that the policy gradient iterates converge to the optimal policy at a sublinear rate of $O\left({\frac{1}{T}}\right),$ which translates to $O\left({\log(T)}\right)$ regret, where $T$ represents the number of iterations. Prior work on performance bounds for discounted reward MDPs cannot be extended to average reward MDPs because the bounds grow proportional to the fifth power of the effective horizon. Thus, our primary contribution is in proving that the policy gradient algorithm converges for average-reward MDPs and in obtaining finite-time performance guarantees. In contrast to the existing discounted reward performance bounds, our performance bounds have an explicit dependence on constants that capture the complexity of the underlying MDP. Motivated by this observation, we reexamine and improve the existing performance bounds for discounted reward MDPs. We also present simulations to empirically evaluate the performance of average reward policy gradient algorithm., Comment: 29 pages, 5 figures