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 study the generalization properties of binary logistic classification in a simplified setting, for which a "memorizing" and "generalizing" solution can always be strictly defined, and elucidate empirically and analytically the mechanism underlying Grokking in its dynamics. We analyze the asymptotic long-time dynamics of logistic classification on a random feature model with a constant label and show that it exhibits Grokking, in the sense of delayed generalization and non-monotonic test loss. We find that Grokking is amplified when classification is applied to training sets which are on the verge of linear separability. Even though a perfect generalizing solution always exists, we prove the implicit bias of the logisitc loss will cause the model to overfit if the training data is linearly separable from the origin. For training sets that are not separable from the origin, the model will always generalize perfectly asymptotically, but overfitting may occur at early stages of training. Importantly, in the vicinity of the transition, that is, for training sets that are almost separable from the origin, the model may overfit for arbitrarily long times before generalizing. We gain more insights by examining a tractable one-dimensional toy model that quantitatively captures the key features of the full model. Finally, we highlight intriguing common properties of our findings with recent literature, suggesting that grokking generally occurs in proximity to the interpolation threshold, reminiscent of critical phenomena often observed in physical systems., Comment: 24 pages, 13 figures

Video detailed captioning is a key task which aims to generate comprehensive and coherent textual descriptions of video content, benefiting both video understanding and generation. In this paper, we propose AuroraCap, a video captioner based on a large multimodal model. We follow the simplest architecture design without additional parameters for temporal modeling. To address the overhead caused by lengthy video sequences, we implement the token merging strategy, reducing the number of input visual tokens. Surprisingly, we found that this strategy results in little performance loss. AuroraCap shows superior performance on various video and image captioning benchmarks, for example, obtaining a CIDEr of 88.9 on Flickr30k, beating GPT-4V (55.3) and Gemini-1.5 Pro (82.2). However, existing video caption benchmarks only include simple descriptions, consisting of a few dozen words, which limits research in this field. Therefore, we develop VDC, a video detailed captioning benchmark with over one thousand carefully annotated structured captions. In addition, we propose a new LLM-assisted metric VDCscore for bettering evaluation, which adopts a divide-and-conquer strategy to transform long caption evaluation into multiple short question-answer pairs. With the help of human Elo ranking, our experiments show that this benchmark better correlates with human judgments of video detailed captioning quality., Comment: Code, docs, weight, benchmark and training data are all avaliable at \href{https://rese1f.github.io/aurora-web/}{website}

Gene regulation is a dynamic process that underlies all aspects of human development, disease response, and other key biological processes. The reconstruction of temporal gene regulatory networks has conventionally relied on regression analysis, graphical models, or other types of relevance networks. With the large increase in time series single-cell data, new approaches are needed to address the unique scale and nature of this data for reconstructing such networks. Here, we develop a deep neural network, Marlene, to infer dynamic graphs from time series single-cell gene expression data. Marlene constructs directed gene networks using a self-attention mechanism where the weights evolve over time using recurrent units. By employing meta learning, the model is able to recover accurate temporal networks even for rare cell types. In addition, Marlene can identify gene interactions relevant to specific biological responses, including COVID-19 immune response, fibrosis, and aging., Comment: 10 pages, 5 figures

In his 1996 paper, Talagrand highlighted that the Law of Large Numbers (LLN) for independent random variables can be viewed as a geometric property of multidimensional product spaces. This phenomenon is known as the concentration of measure. To illustrate this profound connection between geometry and probability theory, we consider a seemingly intractable geometric problem in multidimensional Euclidean space and solve it using standard probabilistic tools such as the LLN and the Central Limit Theorem (CLT)., Comment: 14 pages, 3 figures

Recent years have seen significant growth of quantum technologies, and specifically quantum sensing, both in terms of the capabilities of advanced platforms and their applications. One of the leading platforms in this context is nitrogen-vacancy (NV) color centers in diamond, providing versatile, high-sensitivity, and high-resolution magnetic sensing. Nevertheless, current schemes for spin resonance magnetic sensing (as applied by NV quantum sensing) suffer from tradeoffs associated with sensitivity, dynamic range, and bandwidth. Here we address this issue, and implement machine learning tools to enhance NV magnetic sensing in terms of the sensitivity/bandwidth tradeoff in large dynamic range scenarios. We experimentally demonstrate this new approach, reaching an improvement in the relevant figure of merit by a factor of up to 5. Our results promote quantum machine learning protocols for sensing applications towards more feasible and efficient quantum technologies., Comment: 12 pages including supplementary, 6 figures

The study of coherence dynamics in open quantum systems, specifically addressing various physical realizations of quantum systems and environments, is a long-standing and central pillar of quantum science and technology. As such, a large body of work establishes a firm theoretical understanding of these processes. Nevertheless, a fundamental aspect of decoherence dynamics, namely the central limit theorem of qubit dephasing in the central spin model, which leads to a Gaussian approximation, lacks formal proof in realistically relevant scenarios. Here we prove this approximation for a bath depicted by an Ising spin system, in the presence of disorder and several (most relevant) functional forms of qubit-bath coupling. Importantly, we show that in certain cases, namely for short-range (exponentially decaying) coupling, this approximation breaks. These results provide a theoretical framework for studying decoherence dynamics in various systems and lead to insights into dephasing behavior with implications for applications in quantum information, quantum computing, and other quantum technologies.

Embodied vision-based real-world systems, such as mobile robots, require a careful balance between energy consumption, compute latency, and safety constraints to optimize operation across dynamic tasks and contexts. As local computation tends to be restricted, offloading the computation, ie, to a remote server, can save local resources while providing access to high-quality predictions from powerful and large models. However, the resulting communication and latency overhead has led to limited usability of cloud models in dynamic, safety-critical, real-time settings. To effectively address this trade-off, we introduce UniLCD, a novel hybrid inference framework for enabling flexible local-cloud collaboration. By efficiently optimizing a flexible routing module via reinforcement learning and a suitable multi-task objective, UniLCD is specifically designed to support the multiple constraints of safety-critical end-to-end mobile systems. We validate the proposed approach using a challenging, crowded navigation task requiring frequent and timely switching between local and cloud operations. UniLCD demonstrates improved overall performance and efficiency, by over 35% compared to state-of-the-art baselines based on various split computing and early exit strategies., Comment: ECCV 24

We consider the problem of estimating the direction-of-arrival (DoA) of a desired source located in a known region of interest in the presence of interfering sources and multipath. We propose an approach that precedes the DoA estimation and relies on generating a set of reference steering vectors. The steering vectors' generative model is a free space model, which is beneficial for many DoA estimation algorithms. The set of reference steering vectors is then used to compute a function that maps the received signals from the adverse environment to a reference domain free from interfering sources and multipath. We show theoretically and empirically that the proposed map, which is analogous to domain adaption, improves DoA estimation by mitigating interference and multipath effects. Specifically, we demonstrate a substantial improvement in accuracy when the proposed approach is applied before three commonly used beamformers: the delay-and-sum (DS), the minimum variance distortionless response (MVDR), and the Multiple Signal Classification (MUSIC).

We prove that a free profinite (pro-$p$) product over a set converging to 1 of countably many Demushkin groups of rank $\aleph_0$, $G_i$, that can be realized as absolute Galois groups, is isomorphic to an absolute Galois group if and only if $\log_pq(G_i)\to \infty$.

We present a novel approach for test-time adaptation via online self-training, consisting of two components. First, we introduce a statistical framework that detects distribution shifts in the classifier's entropy values obtained on a stream of unlabeled samples. Second, we devise an online adaptation mechanism that utilizes the evidence of distribution shifts captured by the detection tool to dynamically update the classifier's parameters. The resulting adaptation process drives the distribution of test entropy values obtained from the self-trained classifier to match those of the source domain, building invariance to distribution shifts. This approach departs from the conventional self-training method, which focuses on minimizing the classifier's entropy. Our approach combines concepts in betting martingales and online learning to form a detection tool capable of quickly reacting to distribution shifts. We then reveal a tight relation between our adaptation scheme and optimal transport, which forms the basis of our novel self-supervised loss. Experimental results demonstrate that our approach improves test-time accuracy under distribution shifts while maintaining accuracy and calibration in their absence, outperforming leading entropy minimization methods across various scenarios.

Topological deep learning (TDL) facilitates learning from data represented by topological structures. The primary model utilized in this setting is higher-order message-passing (HOMP), which extends traditional graph message-passing neural networks (MPNN) to diverse topological domains. Given the significant expressivity limitations of MPNNs, our paper aims to explore both the strengths and weaknesses of HOMP's expressive power and subsequently design novel architectures to address these limitations. We approach this from several perspectives: First, we demonstrate HOMP's inability to distinguish between topological objects based on fundamental topological and metric properties such as diameter, orientability, planarity, and homology. Second, we show HOMP's limitations in fully leveraging the topological structure of objects constructed using common lifting and pooling operators on graphs. Finally, we compare HOMP's expressive power to hypergraph networks, which are the most extensively studied TDL methods. We then develop two new classes of TDL models: multi-cellular networks (MCN) and scalable multi-cellular networks (SMCN). These models draw inspiration from expressive graph architectures. While MCN can reach full expressivity but is highly unscalable, SMCN offers a more scalable alternative that still mitigates many of HOMP's expressivity limitations. Finally, we construct a synthetic dataset, where TDL models are tasked with separating pairs of topological objects based on basic topological properties. We demonstrate that while HOMP is unable to distinguish between any of the pairs in the dataset, SMCN successfully distinguishes all pairs, empirically validating our theoretical findings. Our work opens a new design space and new opportunities for TDL, paving the way for more expressive and versatile models.

These lecture notes are derived from a graduate-level course in dynamic optimization, offering an introduction to techniques and models extensively used in management science, economics, operations research, engineering, and computer science. The course emphasizes the theoretical underpinnings of discrete-time dynamic programming models and advanced algorithmic strategies for solving these models. Unlike typical treatments, it provides a proof for the principle of optimality for upper semi-continuous dynamic programming, a middle ground between the simpler countable state space case \cite{bertsekas2012dynamic}, and the involved universally measurable case \cite{bertsekas1996stochastic}. This approach is sufficiently rigorous to include important examples such as dynamic pricing, consumption-savings, and inventory management models. The course also delves into the properties of value and policy functions, leveraging classical results \cite{topkis1998supermodularity} and recent developments. Additionally, it offers an introduction to reinforcement learning, including a formal proof of the convergence of Q-learning algorithms. Furthermore, the notes delve into policy gradient methods for the average reward case, presenting a convergence result for the tabular case in this context. This result is simple and similar to the discounted case but appears to be new.

Earthquake occurrence is notoriously difficult to predict. While some aspects of their spatiotemporal statistics can be relatively well captured by point-process models, very little is known regarding the magnitude of future events, and it is deeply debated whether it is possible to predict the magnitude of an earthquake before it starts. This is due both to the lack of information about fault conditions and to the inherent complexity of rupture dynamics. Consequently, even state of the art forecasting models typically assume no knowledge about the magnitude of future events besides the time-independent Gutenberg Richter (GR) distribution, which describes the marginal distribution over large regions and long times. This approach implicitly assumes that earthquake magnitudes are independent of previous seismicity and are identically distributed. In this work we challenge this view by showing that information about the magnitude of an upcoming earthquake can be directly extracted from the seismic history. We present MAGNET - MAGnitude Neural EsTimation model, an open-source, geophysically-inspired neural-network model for probabilistic forecasting of future magnitudes from cataloged properties: hypocenter locations, occurrence times and magnitudes of past earthquakes. Our history-dependent model outperforms stationary and quasi-stationary state of the art GR-based benchmarks, in real catalogs in Southern California, Japan and New-Zealand. This demonstrates that earthquake catalogs contain information about the magnitude of future earthquakes, prior to their occurrence. We conclude by proposing methods to apply the model in characterization of the preparatory phase of earthquakes, and in operational hazard alert and earthquake forecasting systems., Comment: 4 main figure, 1 main table

Blockchains implement monetary systems operated by committees of nodes. The robustness of established blockchains presents an opportunity to leverage their infrastructure for creating expansion chains. Expansion chains can provide additional functionality to the primary chain they leverage or implement separate functionalities, while benefiting from the primary chain's security and the stability of its tokens. Indeed, tools like Ethereum's EigenLayer enable nodes to stake (deposit collateral) on a primary chain to form a committee responsible for operating an expansion chain. But here is the rub. Classical protocols assume correct, well-behaved nodes stay correct indefinitely. Yet in our case, the stake incentivizes correctness--it will be slashed (revoked) if its owner deviates. Once a node withdraws its stake, there is no basis to assume its correctness. To address the new challenge, we present Aegis, an expansion chain based on primary-chain stake, assuming a bounded primary-chain write time. Aegis uses references from Aegis blocks to primary blocks to define committees, checkpoints on the primary chain to perpetuate decisions, and resets on the primary chain to establish a new committee if the previous one becomes obsolete. It ensures safety at all times and rapid progress when latency among Aegis nodes is low.

Large Language Models (LLMs) have demonstrated great performance in few-shot In-Context Learning (ICL) for a variety of generative and discriminative chemical design tasks. The newly expanded context windows of LLMs can further improve ICL capabilities for molecular inverse design and lead optimization. To take full advantage of these capabilities we developed a new semi-supervised learning method that overcomes the lack of experimental data available for many-shot ICL. Our approach involves iterative inclusion of LLM generated molecules with high predicted performance, along with experimental data. We further integrated our method in a multi-modal LLM which allows for the interactive modification of generated molecular structures using text instructions. As we show, the new method greatly improves upon existing ICL methods for molecular design while being accessible and easy to use for scientists.

We present a general analysis for the discovery potential of CP-violation (CPV) searches in scattering processes at TeV-scale colliders in an effective field theory framework, using the SMEFT basis for higher dimensional operators. In particular, we systematically examine the CP-violating sector of the SMEFT framework in some well motivated limiting cases, based on flavour symmetries of the underlying heavy theory. We show that, under naturality arguments of the underlying new physics (NP) and in the absence of (or suppressed) flavour-changing interactions, there is only a single operator, $Q_{t\phi} = \phi^\dagger \phi \left(\bar q_3 t \right) \tilde{\phi} $ which alters the top-Yukawa coupling, that can generate a non-vanishing CP-violating effect from tree-level SM$\times$NP interference terms. We find, however, that CPV from $Q_{t\phi} = \phi^\dagger \phi \left(\bar q_3 t \right) \tilde{\phi} $ is expected to be at best of $O(1\%)$ and, therefore, very challenging if at all measurable at the LHC or other future high-energy colliders. We then conclude that a potentially measurable CP-violating effect of $O(10\%)$ can arise in high-energy scattering processes ONLY if flavour-changing interactions are present in the underlying NP; in this case a sizable CPV can be generated at the tree-level by pure NP$\times$NP effects and not from SM$\times$NP interference. We provide several examples of CPV at the LHC and at a future $e^+e^-$ collider to support these statements., Comment: 15 pages, 5 figures, 6 tables

The channel output entropy of a transmitted sequence is the entropy of the possible channel outputs and similarly the channel input entropy of a received sequence is the entropy of all possible transmitted sequences. The goal of this work is to study these entropy values for the k-deletion, k-insertion channels, where exactly k symbols are deleted, inserted in the transmitted sequence, respectively. If all possible sequences are transmitted with the same probability then studying the input and output entropies is equivalent. For both the 1-deletion and 1-insertion channels, it is proved that among all sequences with a fixed number of runs, the input entropy is minimized for sequences with a skewed distribution of their run lengths and it is maximized for sequences with a balanced distribution of their run lengths. Among our results, we establish a conjecture by Atashpendar et al. which claims that for the 1-deletion channel, the input entropy is maximized by the alternating sequences over all binary sequences. This conjecture is also verified for the 2-deletion channel, where it is proved that constant sequences with a single run minimize the input entropy., Comment: arXiv admin note: substantial text overlap with arXiv:2202.03024

Enterprise chatbots, powered by generative AI, are emerging as key applications to enhance employee productivity. Retrieval Augmented Generation (RAG), Large Language Models (LLMs), and orchestration frameworks like Langchain and Llamaindex are crucial for building these chatbots. However, creating effective enterprise chatbots is challenging and requires meticulous RAG pipeline engineering. This includes fine-tuning embeddings and LLMs, extracting documents from vector databases, rephrasing queries, reranking results, designing prompts, honoring document access controls, providing concise responses, including references, safeguarding personal information, and building orchestration agents. We present a framework for building RAG-based chatbots based on our experience with three NVIDIA chatbots: for IT/HR benefits, financial earnings, and general content. Our contributions are three-fold: introducing the FACTS framework (Freshness, Architectures, Cost, Testing, Security), presenting fifteen RAG pipeline control points, and providing empirical results on accuracy-latency tradeoffs between large and small LLMs. To the best of our knowledge, this is the first paper of its kind that provides a holistic view of the factors as well as solutions for building secure enterprise-grade chatbots.", Comment: 8 pages, 6 figures, 2 tables, Preprint submission to ACM CIKM 2024

Recent improvements in generative AI made synthesizing fake images easy; as they can be used to cause harm, it is crucial to develop accurate techniques to identify them. This paper introduces "Locally Aware Deepfake Detection Algorithm" (LaDeDa), that accepts a single 9x9 image patch and outputs its deepfake score. The image deepfake score is the pooled score of its patches. With merely patch-level information, LaDeDa significantly improves over the state-of-the-art, achieving around 99% mAP on current benchmarks. Owing to the patch-level structure of LaDeDa, we hypothesize that the generation artifacts can be detected by a simple model. We therefore distill LaDeDa into Tiny-LaDeDa, a highly efficient model consisting of only 4 convolutional layers. Remarkably, Tiny-LaDeDa has 375x fewer FLOPs and is 10,000x more parameter-efficient than LaDeDa, allowing it to run efficiently on edge devices with a minor decrease in accuracy. These almost-perfect scores raise the question: is the task of deepfake detection close to being solved? Perhaps surprisingly, our investigation reveals that current training protocols prevent methods from generalizing to real-world deepfakes extracted from social media. To address this issue, we introduce WildRF, a new deepfake detection dataset curated from several popular social networks. Our method achieves the top performance of 93.7% mAP on WildRF, however the large gap from perfect accuracy shows that reliable real-world deepfake detection is still unsolved.

Subgraph Graph Neural Networks (Subgraph GNNs) enhance the expressivity of message-passing GNNs by representing graphs as sets of subgraphs. They have shown impressive performance on several tasks, but their complexity limits applications to larger graphs. Previous approaches suggested processing only subsets of subgraphs, selected either randomly or via learnable sampling. However, they make suboptimal subgraph selections or can only cope with very small subset sizes, inevitably incurring performance degradation. This paper introduces a new Subgraph GNNs framework to address these issues. We employ a graph coarsening function to cluster nodes into super-nodes with induced connectivity. The product between the coarsened and the original graph reveals an implicit structure whereby subgraphs are associated with specific sets of nodes. By running generalized message-passing on such graph product, our method effectively implements an efficient, yet powerful Subgraph GNN. Controlling the coarsening function enables meaningful selection of any number of subgraphs while, contrary to previous methods, being fully compatible with standard training techniques. Notably, we discover that the resulting node feature tensor exhibits new, unexplored permutation symmetries. We leverage this structure, characterize the associated linear equivariant layers and incorporate them into the layers of our Subgraph GNN architecture. Extensive experiments on multiple graph learning benchmarks demonstrate that our method is significantly more flexible than previous approaches, as it can seamlessly handle any number of subgraphs, while consistently outperforming baseline approaches., Comment: Preprint, under review

Simultaneous speech-to-speech translation (S2ST) holds the promise of breaking down communication barriers and enabling fluid conversations across languages. However, achieving accurate, real-time translation through mobile devices remains a major challenge. We introduce SimulTron, a novel S2ST architecture designed to tackle this task. SimulTron is a lightweight direct S2ST model that uses the strengths of the Translatotron framework while incorporating key modifications for streaming operation, and an adjustable fixed delay. Our experiments show that SimulTron surpasses Translatotron 2 in offline evaluations. Furthermore, real-time evaluations reveal that SimulTron improves upon the performance achieved by Translatotron 1. Additionally, SimulTron achieves superior BLEU scores and latency compared to previous real-time S2ST method on the MuST-C dataset. Significantly, we have successfully deployed SimulTron on a Pixel 7 Pro device, show its potential for simultaneous S2ST on-device.

Having large amounts of annotated data significantly impacts the effectiveness of deep neural networks. However, the annotation task can be very expensive in some domains, such as medical data. Thus, it is important to select the data to be annotated wisely, which is known as the subset selection problem. We investigate the relationship between subset selection and neural network pruning, which is more widely studied, and establish a correspondence between them. Leveraging insights from network pruning, we propose utilizing the norm criterion of neural network features to improve subset selection methods. We empirically validate our proposed strategy on various networks and datasets, demonstrating enhanced accuracy. This shows the potential of employing pruning tools for subset selection.

Most works on gender bias focus on intrinsic bias -- removing traces of information about a protected group from the model's internal representation. However, these works are often disconnected from the impact of such debiasing on downstream applications, which is the main motivation for debiasing in the first place. In this work, we systematically test how methods for intrinsic debiasing affect neural machine translation models, by measuring the extrinsic bias of such systems under different design choices. We highlight three challenges and mismatches between the debiasing techniques and their end-goal usage, including the choice of embeddings to debias, the mismatch between words and sub-word tokens debiasing, and the effect on different target languages. We find that these considerations have a significant impact on downstream performance and the success of debiasing.

We introduce a novel online learning framework that unifies and generalizes pre-established models, such as delayed and corrupted feedback, to encompass adversarial environments where action feedback evolves over time. In this setting, the observed loss is arbitrary and may not correlate with the true loss incurred, with each round updating previous observations adversarially. We propose regret minimization algorithms for both the full-information and bandit settings, with regret bounds quantified by the average feedback accuracy relative to the true loss. Our algorithms match the known regret bounds across many special cases, while also introducing previously unknown bounds.

A major challenge facing the world is the provision of equitable and universal access to quality education. Recent advances in generative AI (gen AI) have created excitement about the potential of new technologies to offer a personal tutor for every learner and a teaching assistant for every teacher. The full extent of this dream, however, has not yet materialised. We argue that this is primarily due to the difficulties with verbalising pedagogical intuitions into gen AI prompts and the lack of good evaluation practices, reinforced by the challenges in defining excellent pedagogy. Here we present our work collaborating with learners and educators to translate high level principles from learning science into a pragmatic set of seven diverse educational benchmarks, spanning quantitative, qualitative, automatic and human evaluations; and to develop a new set of fine-tuning datasets to improve the pedagogical capabilities of Gemini, introducing LearnLM-Tutor. Our evaluations show that LearnLM-Tutor is consistently preferred over a prompt tuned Gemini by educators and learners on a number of pedagogical dimensions. We hope that this work can serve as a first step towards developing a comprehensive educational evaluation framework, and that this can enable rapid progress within the AI and EdTech communities towards maximising the positive impact of gen AI in education.

We demonstrate the generation of non-classical light by destructive interference of identical Kerr squeezed states. Perfect pair-wise cancellation of amplitudes that contribute to odd Fock states results in light with only even Fock states, independent of the strength of the nonlinearity. The observability of this effect is only limited by the quality of the interferometer. In the low nonlinearity limit, the even-only state resembles a squeezed vacuum state, yet the even-odd oscillations persist when the nonlinearity is strong. The effect is also robust against deviations from the optimum relative phase of the input Kerr-squeezed states.

This paper presents a novel approach to address the constrained coding challenge of generating almost-balanced sequences. While strictly balanced sequences have been well studied in the past, the problem of designing efficient algorithms with small redundancy, preferably constant or even a single bit, for almost balanced sequences has remained unsolved. A sequence is $\varepsilon(n)$-almost balanced if its Hamming weight is between $0.5n\pm \varepsilon(n)$. It is known that for any algorithm with a constant number of bits, $\varepsilon(n)$ has to be in the order of $\Theta(\sqrt{n})$, with $O(n)$ average time complexity. However, prior solutions with a single redundancy bit required $\varepsilon(n)$ to be a linear shift from $n/2$. Employing an iterative method and arithmetic coding, our emphasis lies in constructing almost balanced codes with a single redundancy bit. Notably, our method surpasses previous approaches by achieving the optimal balanced order of $\Theta(\sqrt{n})$. Additionally, we extend our method to the non-binary case considering $q$-ary almost polarity-balanced sequences for even $q$, and almost symbol-balanced for $q=4$. Our work marks the first asymptotically optimal solutions for almost-balanced sequences, for both, binary and non-binary alphabet., Comment: Accepted to The IEEE International Symposium on Information Theory (ISIT) 2024

Enzymatic DNA labeling is a powerful tool with applications in biochemistry, molecular biology, biotechnology, medical science, and genomic research. This paper contributes to the evolving field of DNA-based data storage by presenting a formal framework for modeling DNA labeling in strings, specifically tailored for data storage purposes. Our approach involves a known DNA molecule as a template for labeling, employing patterns induced by a set of designed labels to represent information. One hypothetical implementation can use CRISPR-Cas9 and gRNA reagents for labeling. Various aspects of the general labeling channel, including fixed-length labels, are explored, and upper bounds on the maximal size of the corresponding codes are given. The study includes the development of an efficient encoder-decoder pair that is proven optimal in terms of maximum code size under specific conditions., Comment: Accepted to The IEEE International Symposium on Information Theory (ISIT) 2024

Millisecond pulsars with white dwarf companions have typical eccentricities $e\sim 10^{-6}-10^{-3}$. The eccentricities of helium white dwarfs are explained well by applying the fluctuation-dissipation theorem to convective eddies in their red giant progenitors. We extend this theory to more massive carbon-oxygen (CO) white dwarfs with asymptotic giant branch (AGB) progenitors. Due to the radiation pressure in AGB stars, the dominant factor in determining the remnant white dwarf's eccentricity is the critical residual hydrogen envelope mass $m_{\rm env}$ required to inflate the star to giant proportions. Using a suite of MESA stellar evolution simulations with $\Delta m_{\rm c}=10^{-3}\,{\rm M}_\odot$ core-mass intervals, we resolved the AGB thermal pulses and found that the critical $m_{\rm env}\propto m_{\rm c}^{-6}$. The resulting eccentricity $e\sim 3\times 10^{-3}$ is almost independent of the remnant CO white dwarf's mass $m_{\rm c}$. Nearly all of the measured eccentricities lie below this robust theoretical limit, indicating that the eccentricity is damped during the common-envelope inspiral that follows the unstable Roche-lobe overflow of the AGB star. Specifically, we focused on white dwarfs with median masses $m_{\rm c}>0.6\,{\rm M}_\odot$. These massive white dwarfs begin their inspiral with practically identical orbital periods and eccentricities, eliminating any dependence on the initial conditions. For this sub-sample, we find an empirical relation $e\propto P^{3/2}$ between the final period and eccentricity that is much tighter than previous studies - motivating theoretical work on the eccentricity evolution during the common envelope phase. The eccentricities of lower mass CO white dwarfs may be explained by alternative formation channels., Comment: to appear in MNRAS, new Section 5 and Appendix

We study the interaction of a dark exciton Bose-Einstein condensate with the nuclei in GaAs/AlGaAs coupled quantum wells and find clear evidence for nuclear polarization buildup that accompanies the appearance of the condensate. We show that the nuclei are polarized throughout the mesa area, extending to regions which are far away from the photoexcitation area, and persisting for seconds after the excitation is switched off. Photoluminescence measurements in the presence of RF radiation reveal that the hyperfine interaction between the nuclear and electron spins is enhanced by two orders of magnitude. We suggest that this large enhancement manifests the collective nature of the N-excitons condensate, which amplifies the interaction by a factor of sqrt{N}.

We study the question of whether a sequence d = (d_1,d_2, \ldots, d_n) of positive integers is the degree sequence of some outerplanar (a.k.a. 1-page book embeddable) graph G. If so, G is an outerplanar realization of d and d is an outerplanaric sequence. The case where \sum d \leq 2n - 2 is easy, as d has a realization by a forest (which is trivially an outerplanar graph). In this paper, we consider the family \cD of all sequences d of even sum 2n\leq \sum d \le 4n-6-2\multipl_1, where \multipl_x is the number of x's in d. (The second inequality is a necessary condition for a sequence d with \sum d\geq 2n to be outerplanaric.) We partition \cD into two disjoint subfamilies, \cD=\cD_{NOP}\cup\cD_{2PBE}, such that every sequence in \cD_{NOP} is provably non-outerplanaric, and every sequence in \cD_{2PBE} is given a realizing graph $G$ enjoying a 2-page book embedding (and moreover, one of the pages is also bipartite)., Comment: This paper has published in 35th IWOCA

Automating data generation with Large Language Models (LLMs) has become increasingly popular. In this work, we investigate the feasibility and effectiveness of LLM-based data generation in the challenging setting of source-grounded information-seeking dialogs, with response attribution, over long documents. Our source texts consist of long and noisy meeting transcripts, adding to the task complexity. Since automating attribution remains difficult, we propose a semi-automatic approach: dialog queries and responses are generated with LLMs, followed by human verification and identification of attribution spans. Using this approach, we created MISeD -- Meeting Information Seeking Dialogs dataset -- a dataset of information-seeking dialogs focused on meeting transcripts. Models finetuned with MISeD demonstrate superior performance compared to off-the-shelf models, even those of larger size. Finetuning on MISeD gives comparable response generation quality to finetuning on fully manual data, while improving attribution quality and reducing time and effort.

We provide a general condition under which e-variables in the form of a simple-vs.-simple likelihood ratio exist when the null hypothesis is a composite, multivariate exponential family. Such `simple' e-variables are easy to compute and expected-log-optimal with respect to any stopping time. Simple e-variables were previously only known to exist in quite specific settings, but we offer a unifying theorem on their existence for testing exponential families. We start with a simple alternative $Q$ and a regular exponential family null. Together these induce a second exponential family ${\cal Q}$ containing $Q$, with the same sufficient statistic as the null. Our theorem shows that simple e-variables exist whenever the covariance matrices of ${\cal Q}$ and the null are in a certain relation. Examples in which this relation holds include some $k$-sample tests, Gaussian location- and scale tests, and tests for more general classes of natural exponential families.

Animals perceive the world to plan their actions and interact with other agents to accomplish complex tasks, demonstrating capabilities that are still unmatched by AI systems. To advance our understanding and reduce the gap between the capabilities of animals and AI systems, we introduce a dataset of pet egomotion imagery with diverse examples of simultaneous egomotion and multi-agent interaction. Current video datasets separately contain egomotion and interaction examples, but rarely both at the same time. In addition, EgoPet offers a radically distinct perspective from existing egocentric datasets of humans or vehicles. We define two in-domain benchmark tasks that capture animal behavior, and a third benchmark to assess the utility of EgoPet as a pretraining resource to robotic quadruped locomotion, showing that models trained from EgoPet outperform those trained from prior datasets., Comment: https://www.amirbar.net/egopet

LLM-based code assistants are becoming increasingly popular among developers. These tools help developers improve their coding efficiency and reduce errors by providing real-time suggestions based on the developer's codebase. While beneficial, these tools might inadvertently expose the developer's proprietary code to the code assistant service provider during the development process. In this work, we propose two complementary methods to mitigate the risk of code leakage when using LLM-based code assistants. The first is a technique for reconstructing a developer's original codebase from code segments sent to the code assistant service (i.e., prompts) during the development process, enabling assessment and evaluation of the extent of code leakage to third parties (or adversaries). The second is CodeCloak, a novel deep reinforcement learning agent that manipulates the prompts before sending them to the code assistant service. CodeCloak aims to achieve the following two contradictory goals: (i) minimizing code leakage, while (ii) preserving relevant and useful suggestions for the developer. Our evaluation, employing GitHub Copilot, StarCoder, and CodeLlama LLM-based code assistants models, demonstrates the effectiveness of our CodeCloak approach on a diverse set of code repositories of varying sizes, as well as its transferability across different models. In addition, we generate a realistic simulated coding environment to thoroughly analyze code leakage risks and evaluate the effectiveness of our proposed mitigation techniques under practical development scenarios.

Visual Prompting is a technique for teaching models to perform a visual task via in-context examples, without any additional training. In this work, we analyze the activations of MAE-VQGAN, a recent Visual Prompting model, and find task vectors, activations that encode task-specific information. Equipped with this insight, we demonstrate that it is possible to identify the task vectors and use them to guide the network towards performing different tasks without providing any input-output examples. To find task vectors, we compute the average intermediate activations per task and use the REINFORCE algorithm to search for the subset of task vectors. The resulting task vectors guide the model towards performing a task better than the original model without the need for input-output examples., Comment: https://github.com/alhojel/visual_task_vectors

Covariance fitting (CF) is a comprehensive approach for direction of arrival (DoA) estimation, consolidating many common solutions. Standard practice is to use Euclidean criteria for CF, disregarding the intrinsic Hermitian positive-definite (HPD) geometry of the spatial covariance matrices. We assert that this oversight leads to inherent limitations. In this paper, as a remedy, we present a comprehensive study of the use of various Riemannian metrics of HPD matrices in CF. We focus on the advantages of the Affine-Invariant (AI) and the Log-Euclidean (LE) Riemannian metrics. Consequently, we propose a new practical beamformer based on the LE metric and derive analytically its spatial characteristics, such as the beamwidth and sidelobe attenuation, under noisy conditions. Comparing these features to classical beamformers shows significant advantage. In addition, we demonstrate, both theoretically and experimentally, the LE beamformer's robustness in scenarios with small sample sizes and in the presence of noise, interference, and multipath channels.

Dimension reduction techniques are among the most essential analytical tools in the analysis of high-dimensional data. Generalized principal component analysis (PCA) is an extension to standard PCA that has been widely used to identify low-dimensional features in high-dimensional discrete data, such as binary, multi-category and count data. For microbiome count data in particular, the multinomial PCA is a natural counterpart of the standard PCA. However, this technique fails to account for the excessive number of zero values, which is frequently observed in microbiome count data. To allow for sparsity, zero-inflated multivariate distributions can be used. We propose a zero-inflated probabilistic PCA model for latent factor analysis. The proposed model is a fully Bayesian factor analysis technique that is appropriate for microbiome count data analysis. In addition, we use the mean-field-type variational family to approximate the marginal likelihood and develop a classification variational approximation algorithm to fit the model. We demonstrate the efficiency of our procedure for predictions based on the latent factors and the model parameters through simulation experiments, showcasing its superiority over competing methods. This efficiency is further illustrated with two real microbiome count datasets. The method is implemented in R., Comment: 2 figures, 3 tables

We define a structure of an algebra on the Lagrangian Floer cohomology of a Lagrangian submanifold over the quantum cohomology of the ambient symplectic manifold. The structure is analogous to the one defined by Biran-Cornea, but is constructed in the differential forms model. In the spirit of Ganatra and Hugtenburg, we define another such algebra structure using a closed-open map. We show that the two structures coincide. As an application, we show that the module structure for the 2-dimensional Clifford torus is given by multiplication by a Novikov coefficient, similarly to the Biran-Cornea module structure for this case., Comment: 65 pages, 3 figures

Vital signs are crucial in intensive care units (ICUs). They are used to track the patient's state and to identify clinically significant changes. Predicting vital sign trajectories is valuable for early detection of adverse events. However, conventional machine learning metrics like RMSE often fail to capture the true clinical relevance of such predictions. We introduce novel vital sign prediction performance metrics that align with clinical contexts, focusing on deviations from clinical norms, overall trends, and trend deviations. These metrics are derived from empirical utility curves obtained in a previous study through interviews with ICU clinicians. We validate the metrics' usefulness using simulated and real clinical datasets (MIMIC and eICU). Furthermore, we employ these metrics as loss functions for neural networks, resulting in models that excel in predicting clinically significant events. This research paves the way for clinically relevant machine learning model evaluation and optimization, promising to improve ICU patient care. 10 pages, 9 figures., Comment: 10 pages, 9 figures, AMIA Informatics 2024

Underwater image restoration is a challenging task because of water effects that increase dramatically with distance. This is worsened by lack of ground truth data of clean scenes without water. Diffusion priors have emerged as strong image restoration priors. However, they are often trained with a dataset of the desired restored output, which is not available in our case. We also observe that using only color data is insufficient, and therefore augment the prior with a depth channel. We train an unconditional diffusion model prior on the joint space of color and depth, using standard RGBD datasets of natural outdoor scenes in air. Using this prior together with a novel guidance method based on the underwater image formation model, we generate posterior samples of clean images, removing the water effects. Even though our prior did not see any underwater images during training, our method outperforms state-of-the-art baselines for image restoration on very challenging scenes. Our code, models and data are available on the project website., Comment: ECCV 2024. Project page with results and code: https://osmosis-diffusion.github.io/

Integration is the final key step when turning an infinitesimal argument into a result applicable to quantities of finite size. Conceptually, it is about combining infinitesimal contributions to a finite whole. We make a first step towards a geometric theory of integration in the context of Synthetic Differential Geometry (SDG) by analysing the differential aspect of the integration process. Starting from two heuristic principles that combine the idea of differential forms as infinitesimal measures while formalising the process of taking infinitesimal differences at the same time we derive a general notion of differential form as an equivariant map from infinitesimal $n$-cuboids to the base ring coordinatising a line. Besides the familiar differential forms introduced by Cartan we discover two new types. We also discover a new differential operator besides the exterior derivative. Analogous to the relationship between the exterior derivative and the Stokes-Cartan integral theorem, this new operator is linked to the generalised Fundamental Theorem of Calculus in higher dimensions, as discussed in prior research. This shows that the Fundamental Theorem is an integral theorem like Stokes-Cartan, but for one of the new types of differential forms., Comment: 13 pages, 5 figures. Submitted to "Theory and Applications of Categories"

Understanding the dynamics of dissipative quantum systems, particularly beyond the weak coupling approximation, is central to various quantum applications. While numerically exact methods provide accurate solutions, they often lack the analytical insight provided by theoretical approaches. In this study, we employ the recently-developed method dubbed the effective Hamiltonian theory to understand the dynamics of system-bath configurations without resorting to a perturbative description of the system-bath coupling energy. Through a combination of mapping steps and truncation, the effective Hamiltonian theory offers both analytical insights into signatures of strong couplings in open quantum systems and a straightforward path for numerical simulations. To validate the accuracy of the method, we apply it to two canonical models: a single spin immersed in a bosonic bath and two noninteracting spins in a common bath. In both cases, we study the transient regime and the steady state limit at nonzero temperature, and spanning system-bath interactions from the weak to the strong regime. By comparing the results of the effective Hamiltonian theory with numerically exact simulations, we show that although the former overlooks non-Markovian features in the transient equilibration dynamics, it correctly captures non-perturbative bath-generated couplings between otherwise non-interacting spins as observed in their synchronization dynamics and correlations. Altogether, the effective Hamiltonian theory offers a powerful approach to understanding strong coupling dynamics and thermodynamics, capturing the signatures of such interactions in both relaxation dynamics and in the steady state limit., Comment: Journal version