Search

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.

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-10\ \rm mHz$ frequency range by up to a factor of $\approx3.5$, relative to the instrumental noise., Comment: 14 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 interactive decision-making tasks, information can be acquired by direct interactions, through receiving indirect feedback, and from external knowledgeable sources. We examine the trade-off between the information an agent accumulates and the regret it suffers. We show that information from external sources, measured in bits, can be traded off for regret, measured in reward. We invoke information-theoretic methods for obtaining regret lower bounds, that also allow us to easily re-derive several known lower bounds. We then generalize a variety of interactive decision-making tasks with external information to a new setting. Using this setting, we introduce the first Bayesian regret lower bounds that depend on the information an agent accumulates. These lower bounds also prove the near-optimality of Thompson sampling for Bayesian problems. 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

We establish a separation principle for the output feedback stabilisation of state-affine systems that are observable at the stabilization target. Relying on control templates (recently introduced in [4]), that allow to approximate a feedback control while maintaining observability, we design a closed loop hybrid state-observer system that we show to be semi-globally asymptotically stable. Under assumption of polynomiality of the system with respect to the control, we give an explicit construction of control templates. We illustrate the results of the paper with numerical simulations.

Natural systems with emergent behaviors often organize along low-dimensional subsets of high-dimensional spaces. For example, despite the tens of thousands of genes in the human genome, the principled study of genomics is fruitful because biological processes rely on coordinated organization that results in lower dimensional phenotypes. To uncover this organization, many nonlinear dimensionality reduction techniques have successfully embedded high-dimensional data into low-dimensional spaces by preserving local similarities between data points. However, the nonlinearities in these methods allow for too much curvature to preserve general trends across multiple non-neighboring data clusters, thereby limiting their interpretability and generalizability to out-of-distribution data. Here, we address both of these limitations by regularizing the curvature of manifolds generated by variational autoencoders, a process we coin ``$\Gamma$-VAE''. We demonstrate its utility using two example data sets: bulk RNA-seq from the The Cancer Genome Atlas (TCGA) and the Genotype Tissue Expression (GTEx); and single cell RNA-seq from a lineage tracing experiment in hematopoietic stem cell differentiation. We find that the resulting regularized manifolds identify mesoscale structure associated with different cancer cell types, and accurately re-embed tissues from completely unseen, out-of distribution cancers as if they were originally trained on them. Finally, we show that preserving long-range relationships to differentiated cells separates undifferentiated cells -- which have not yet specialized -- according to their eventual fate. Broadly, we anticipate that regularizing the curvature of generative models will enable more consistent, predictive, and generalizable models in any high-dimensional system with emergent low-dimensional behavior., Comment: 8 pages, 4 figures

Materials with strongly correlated electrons exhibit physical properties that are often difficult to predict as they result from the interactions of large numbers of electrons combined with several quantum degrees of freedom. The layered oxide perovskite Sr$_2$RuO$_4$ is a strongly correlated electron material that has been intensively investigated since its discovery due to its unusual physical properties. Whilst recent experiments have reopened the debate on the exact symmetry of the superconducting state in Sr$_2$RuO$_4$, a deeper understanding of the Sr$_2$RuO$_4$ normal state appears crucial as this is the background in which electron pairing occurs. Here, by using low-energy muon spin spectroscopy we discover the existence of magnetism at the surface of Sr$_2$RuO$_4$ in its normal state. We detect static weak dipolar fields yet manifesting below a relatively high onset temperature larger than 50 K, which reveals the unconventional nature of the observed magnetism. We relate the origin of this phase breaking time reversal symmetry to electronic ordering in the form of orbital loop currents that originate at the reconstructed Sr$_2$RuO$_4$ surface. Our observations set a reference for the discovery of the same magnetic phase in other materials and unveil an electronic ordering mechanism that can influence unconventional electron pairing with broken time reversal symmetry in those materials where the observed magnetic phase coexists with superconductivity., Comment: 20 pages, 5 figures

Polaritons are quasi-particles describing the coupling between a photon and a material excitation, which can carry large momentum and confine electromagnetic fields to small dimensions, enabling strong light-matter interactions. In the visible (VIS) to near-infrared (NIR) spectral ranges, the intraband response of metals gives rise to surface-plasmon-polaritons (SPPs), which have practically governed polaritonic response and its utilization in nanophotonics. Recently, the concept of interband-based VIS/NIR in-plane exciton polaritons has been introduced in two-dimensional materials, such as transition-metal-dichalcogenides (TMDs), thus providing an excitonic alternative to plasmonic systems. Here, we compare the properties of such in-plane exciton polaritons supported by monolayer TMDs to the equivalent configuration of SPPs supported by thin metallic films, known as the short-range-SPPs (SRSPPs). Taking into account both excitonic and plasmonic nonlocal corrections, which play a major role in large momentum modes, we find that in-plane exciton polaritons provide confinement factors that are an order of magnitude larger than those of SRSPPs, and with six times lower propagation losses. In addition, we show that unlike SPPs, in-plane exciton polaritons are coupled to the TMD's valley degree of freedom, leading to directional propagation that depends on the exciton's valley. These properties make in-plane exciton polaritons promising candidates for VIS/NIR nanophotonics and strong light-matter interaction.

Taming the generation outcome of state of the art Diffusion and Flow-Matching (FM) models without having to re-train a task-specific model unlocks a powerful tool for solving inverse problems, conditional generation, and controlled generation in general. In this work we introduce D-Flow, a simple framework for controlling the generation process by differentiating through the flow, optimizing for the source (noise) point. We motivate this framework by our key observation stating that for Diffusion/FM models trained with Gaussian probability paths, differentiating through the generation process projects gradient on the data manifold, implicitly injecting the prior into the optimization process. We validate our framework on linear and non-linear controlled generation problems including: image and audio inverse problems and conditional molecule generation reaching state of the art performance across all., Comment: ICML 2024

Binaries containing a compact object orbiting a supermassive black hole are thought to be precursors of gravitational wave events, but their identification has been extremely challenging. Here, we report quasi-periodic variability in X-ray absorption which we interpret as quasi-periodic outflows (QPOuts) from a previously low-luminosity active galactic nucleus after an outburst, likely caused by a stellar tidal disruption. We rule out several models based on observed properties and instead show using general relativistic magnetohydrodynamic simulations that QPOuts, separated by roughly 8.3 days, can be explained with an intermediate-mass black hole secondary on a mildly eccentric orbit at a mean distance of about 100 gravitational radii from the primary. Our work suggests that QPOuts could be a new way to identify intermediate/extreme-mass ratio binary candidates., Comment: Accepted for publication in Science Advances. We report a new supermassive black hole phenomenon that we call quasi-periodic outflows (QPOuts)

Internet image collections containing photos captured by crowds of photographers show promise for enabling digital exploration of large-scale tourist landmarks. However, prior works focus primarily on geometric reconstruction and visualization, neglecting the key role of language in providing a semantic interface for navigation and fine-grained understanding. In constrained 3D domains, recent methods have leveraged vision-and-language models as a strong prior of 2D visual semantics. While these models display an excellent understanding of broad visual semantics, they struggle with unconstrained photo collections depicting such tourist landmarks, as they lack expert knowledge of the architectural domain. In this work, we present a localization system that connects neural representations of scenes depicting large-scale landmarks with text describing a semantic region within the scene, by harnessing the power of SOTA vision-and-language models with adaptations for understanding landmark scene semantics. To bolster such models with fine-grained knowledge, we leverage large-scale Internet data containing images of similar landmarks along with weakly-related textual information. Our approach is built upon the premise that images physically grounded in space can provide a powerful supervision signal for localizing new concepts, whose semantics may be unlocked from Internet textual metadata with large language models. We use correspondences between views of scenes to bootstrap spatial understanding of these semantics, providing guidance for 3D-compatible segmentation that ultimately lifts to a volumetric scene representation. Our results show that HaLo-NeRF can accurately localize a variety of semantic concepts related to architectural landmarks, surpassing the results of other 3D models as well as strong 2D segmentation baselines. Our project page is at https://tau-vailab.github.io/HaLo-NeRF/., Comment: Eurographics 2024. Project page: https://tau-vailab.github.io/HaLo-NeRF/

Quasi-periodic Eruptions (QPEs) represent a novel class of extragalactic X-ray transients that are known to repeat at roughly regular intervals of a few hours to days. Their underlying physical mechanism is a topic of heated debate, with most models proposing that they originate either from instabilities within the inner accretion flow or from orbiting objects. At present, our knowledge of how QPEs evolve over an extended timescale of multiple years is limited, except for the unique QPE source GSN 069. In this study, we present results from strategically designed Swift observing programs spanning the past three years, aimed at tracking eruptions from eRO-QPE1. Our main results are: 1) the recurrence time of eruptions can vary between 0.6 and 1.2 days, 2) there is no detectable secular trend in evolution of the recurrence times, 3) consistent with prior studies, their eruption profiles can have complex shapes, and 4) the peak flux of the eruptions has been declining over the past 3 years with the eruptions barely detected in the most recent Swift dataset taken in June of 2023. This trend of weakening eruptions has been reported recently in GSN 069. However, because the background luminosity of eRO-QPE1 is below our detection limit, we cannot verify if the weakening is correlated with the background luminosity (as is claimed to be the case for GSN 069). We discuss these findings within the context of various proposed QPE models., Comment: Resubmitted to ApJ Letters after implementing referee comments

We introduce SPIRIT-LM, a foundation multimodal language model that freely mixes text and speech. Our model is based on a pretrained text language model that we extend to the speech modality by continuously training it on text and speech units. Speech and text sequences are concatenated as a single set of tokens, and trained with a word-level interleaving method using a small automatically-curated speech-text parallel corpus. SPIRIT-LM comes in two versions: a BASE version that uses speech semantic units and an EXPRESSIVE version that models expressivity using pitch and style units in addition to the semantic units. For both versions, the text is encoded with subword BPE tokens. The resulting model displays both the semantic abilities of text models and the expressive abilities of speech models. Additionally, we demonstrate that SPIRIT-LM is able to learn new tasks in a few-shot fashion across modalities (i.e. ASR, TTS, Speech Classification).

We present a new decoder for the surface code, which combines the accuracy of the tensor-network decoders with the efficiency and parallelism of the belief-propagation algorithm. Our main idea is to replace the expensive tensor-network contraction step in the tensor-network decoders with the blockBP algorithm - a recent approximate contraction algorithm, based on belief propagation. Our decoder is therefore a belief-propagation decoder that works in the degenerate maximal likelihood decoding framework. Unlike conventional tensor-network decoders, our algorithm can run efficiently in parallel, and may therefore be suitable for real-time decoding. We numerically test our decoder and show that for a large range of lattice sizes and noise levels it delivers a logical error probability that outperforms the Minimal-Weight-Perfect-Matching (MWPM) decoder, sometimes by more than an order of magnitude., Comment: 13 pages, 7 figures. Comments are welcome. Version2: minor modifications + typos

We consider a model of third-degree price discrimination where the seller's product valuation is unknown to the market designer, who aims to maximize buyer surplus by revealing buyer valuation information. Our main result shows that the regret is bounded by a $\frac{1}{e}$-fraction of the optimal buyer surplus when the seller has zero valuation for the product. This bound is attained by randomly drawing a seller valuation and applying the segmentation of Bergemann et al. (2015) with respect to the drawn valuation. We show that this bound is tight in the case of binary buyer valuation.

Causal discovery aims to recover information about an unobserved causal graph from the observable data it generates. Layerings are orderings of the variables which place causes before effects. In this paper, we provide ways to recover layerings of a graph by accessing the data via a conditional entropy oracle, when distributions are discrete. Our algorithms work by repeatedly removing sources or sinks from the graph. Under appropriate assumptions and conditioning, we can separate the sources or sinks from the remainder of the nodes by comparing their conditional entropy to the unconditional entropy of their noise. Our algorithms are provably correct and run in worst-case quadratic time. The main assumptions are faithfulness and injective noise, and either known noise entropies or weakly monotonically increasing noise entropies along directed paths. In addition, we require one of either a very mild extension of faithfulness, or strictly monotonically increasing noise entropies, or expanding noise injectivity to include an additional single argument in the structural functions.

We introduce MAGNeT, a masked generative sequence modeling method that operates directly over several streams of audio tokens. Unlike prior work, MAGNeT is comprised of a single-stage, non-autoregressive transformer. During training, we predict spans of masked tokens obtained from a masking scheduler, while during inference we gradually construct the output sequence using several decoding steps. To further enhance the quality of the generated audio, we introduce a novel rescoring method in which, we leverage an external pre-trained model to rescore and rank predictions from MAGNeT, which will be then used for later decoding steps. Lastly, we explore a hybrid version of MAGNeT, in which we fuse between autoregressive and non-autoregressive models to generate the first few seconds in an autoregressive manner while the rest of the sequence is being decoded in parallel. We demonstrate the efficiency of MAGNeT for the task of text-to-music and text-to-audio generation and conduct an extensive empirical evaluation, considering both objective metrics and human studies. The proposed approach is comparable to the evaluated baselines, while being significantly faster (x7 faster than the autoregressive baseline). Through ablation studies and analysis, we shed light on the importance of each of the components comprising MAGNeT, together with pointing to the trade-offs between autoregressive and non-autoregressive modeling, considering latency, throughput, and generation quality. Samples are available on our demo page https://pages.cs.huji.ac.il/adiyoss-lab/MAGNeT.

This paper considers the dynamics of cheap talk interactions between a sender and receiver, departing from conventional models by focusing on the receiver's perspective. We study two models, one with transparent motives and another one in which the receiver can \emph{filter} the information that is accessible by the sender. We give a geometric characterization of the best receiver equilibrium under transparent motives and prove that the receiver does not benefit from filtering information in this case. However, in general, we show that the receiver can strictly benefit from filtering and provide efficient algorithms for computing optimal equilibria. This innovative analysis aligns with user-based platforms where receivers (users) control information accessible to senders (sellers). Our findings provide insights into communication dynamics, leveling the sender's inherent advantage, and offering strategic interaction predictions.