Search

The H\'enon-Heiles system, initially introduced as a simplified model of galactic dynamics, has become a paradigmatic example in the study of nonlinear systems. Despite its simplicity, it exhibits remarkably rich dynamical behavior, including the interplay between regular and chaotic orbital dynamics, resonances, and stochastic regions in phase space, which have inspired extensive research in nonlinear dynamics. In this work, we investigate the system's solutions at small energy levels, deriving asymptotic constants of motion that remain valid over remarkably long timescales -- far exceeding the range of validity of conventional perturbation techniques. Our approach leverages the system's inherent two-scale dynamics, employing a novel analytical framework to uncover these long-lived invariants. The derived formulas exhibit excellent agreement with numerical simulations, providing a deeper understanding of the system's long-term behavior., Comment: 22 pages, 6 figures

While transformers have been at the core of most recent advancements in sequence generative models, their computational cost remains quadratic in sequence length. Several subquadratic architectures have been proposed to address this computational issue. Some of them, including long convolution sequence models (LCSMs), such as Hyena, address this issue at training time but remain quadratic during inference. We propose a method for speeding up LCSMs' exact inference to quasilinear $O(L\log^2L)$ time, identify the key properties that make this possible, and propose a general framework that exploits these. Our approach, inspired by previous work on relaxed polynomial interpolation, is based on a tiling which helps decrease memory movement and share computation. It has the added benefit of allowing for almost complete parallelization across layers of the position-mixing part of the architecture. Empirically, we provide a proof of concept implementation for Hyena, which gets up to $1.6\times$ end-to-end improvement over standard inference by improving $50\times$ within the position-mixing part., Comment: 15 pages, 9 figures, 5 algorithms

This paper introduces the Hamiltonian-Adaptive Ternary Tree (HATT) framework to compile optimized Fermion-to-qubit mapping for specific Fermionic Hamiltonians. In the simulation of Fermionic quantum systems, efficient Fermion-to-qubit mapping plays a critical role in transforming the Fermionic system into a qubit system. HATT utilizes ternary tree mapping and a bottom-up construction procedure to generate Hamiltonian aware Fermion-to-qubit mapping to reduce the Pauli weight of the qubit Hamiltonian, resulting in lower quantum simulation circuit overhead. Additionally, our optimizations retain the important vacuum state preservation property in our Fermion-to-qubit mapping and reduce the complexity of our algorithm from $O(N^4)$ to $O(N^3)$. Evaluations and simulations of various Fermionic systems demonstrate $5\sim20\%$ reduction in Pauli weight, gate count, and circuit depth, alongside excellent scalability to larger systems. Experiments on the Ionq quantum computer also show the advantages of our approach in noise resistance in quantum simulations.

Resource efficient and high precision compilation of programs into quantum circuits expressed in Fault-Tolerant gate sets, such as the Clifford+T gate set, is vital for the success of quantum computing. Optimal analytical compilation methods are known for restricted classes of unitaries, otherwise the problem is intractable. Empirical search-based synthesis methods, including Reinforcement Learning and simulated annealing, can generate good implementations for a more extensive set of unitaries, but require trade-offs in approximation precision and resource use. We leverage search-based methods to reduce the general unitary synthesis problem to one of synthesizing diagonal unitaries; a problem solvable efficiently in general and optimally in the single-qubit case. We demonstrate how our approach improves the implementation precision attainable by Fault-Tolerant synthesis algorithms on an array of unitaries taken from real quantum algorithms. On these benchmarks, many of which cannot be handled by existing approaches, we observe an average of 95% fewer resource-intensive non-Clifford gates compared to the more general Quantum Shannon Decomposition. On a subset of algorithms of interest for future term applications, diagonalization can reduce T gate counts by up to 16.8% compared to other methods., Comment: 22 pages, 11 figures

In this paper we gather and extend classical results for parabolic cylinder functions, namely solutions of the Weber differential equations, using a systematic approach by Borel-Laplace methods. We revisit the definition and construction of the standard solutions $U,V$ of the Weber differential equation \begin{equation*} w''(z)-\left(\frac{z^2}{4}+a\right)w(z)=0 \end{equation*} and provide representations by Laplace integrals extended to include all values of the complex parameter $a$; we find an integral integral representation for the function $V$; none was previously available. For the Weber equation in the form \begin{equation*} u''(x)+\left(\frac{x^2}{4}-a\right)u(x)=0, \end{equation*} we define a new fundamental system $E_\pm$ which is analytic in $a\in\mathbb{C}$, based on asymptotic behavior; they appropriately extend and modify the classical solutions $E,E^*$ of the real Weber equation to the complex domain. The techniques used are general and we include details and motivations for the approach.

Research in the field of language models is rapidly evolving, with many open models being released to the public. Openly available pretraining corpora usually focus on only a handful of languages, with many others either missing completely or extremely underrepresented. In this report, we introduce FuLG, a hundred-fifty-billion-token Romanian corpus extracted from CommonCrawl. We present our methodology for filtering FuLG and compare it via ablation studies against existing Romanian corpora.

Hyperscalers dominate the landscape of large network deployments, yet they rarely share data or insights about the challenges they face. In light of this supremacy, what problems can we find to solve in this space? We take an unconventional approach to find relevant research directions, starting from public plans to build a $100 billion datacenter for machine learning applications. Leveraging the language models scaling laws, we discover what workloads such a datacenter might carry and explore the challenges one may encounter in doing so, with a focus on networking research. We conclude that building the datacenter and training such models is technically possible, but this requires novel wide-area transports for inter-DC communication, a multipath transport and novel datacenter topologies for intra-datacenter communication, high speed scale-up networks and transports, outlining a rich research agenda for the networking community.

Languages such as P4 and NPL have enabled a wide and diverse range of networking applications that take advantage of programmable dataplanes. However, software development in these languages is difficult. To address this issue, high-level languages have been designed to offer programmers powerful abstractions that reduce the time, effort and domain-knowledge required for developing networking applications. These languages are then translated by a compiler into P4/NPL code. Inspired by the recent success of Large Language Models (LLMs) in the task of code generation, we propose to raise the level of abstraction even higher, employing LLMs to translate prose into high-level networking code. We analyze the problem, focusing on the motivation and opportunities, as well as the challenges involved and sketch out a roadmap for the development of a system that can generate high-level dataplane code from natural language instructions. We present some promising preliminary results on generating Lucid code from natural language.

Existing numerical optimizers deployed in quantum compilers use expensive $\mathcal{O}(4^n)$ matrix-matrix operations. Inspired by recent advances in quantum machine learning (QML), QFactor-Sample replaces matrix-matrix operations with simpler $\mathcal{O}(2^n)$ circuit simulations on a set of sample inputs. The simpler the circuit, the lower the number of required input samples. We validate QFactor-Sample on a large set of circuits and discuss its hyperparameter tuning. When incorporated in the BQSKit quantum compiler and compared against a state-of-the-art domain-specific optimizer, We demonstrate improved scalability and a reduction in compile time, achieving an average speedup factor of 69 for circuits with more than 8 qubits. We also discuss how improved numerical optimization affects the dynamics of partitioning-based compilation schemes, which allow a trade-off between compilation speed and solution quality., Comment: 15 pages, 8 figures, and 4 appendices

The increasing demand of machine learning (ML) workloads in datacenters places significant stress on current congestion control (CC) algorithms, many of which struggle to maintain performance at scale. These workloads generate bursty, synchronized traffic that requires both rapid response and fairness across flows. Unfortunately, existing CC algorithms that rely heavily on delay as a primary congestion signal often fail to react quickly enough and do not consistently ensure fairness. In this paper, we propose FASTFLOW, a streamlined sender-based CC algorithm that integrates delay, ECN signals, and optional packet trimming to achieve precise, real-time adjustments to congestion windows. Central to FASTFLOW is the QuickAdapt mechanism, which provides accurate bandwidth estimation at the receiver, enabling faster reactions to network conditions. We also show that FASTFLOW can effectively enhance receiver-based algorithms such as EQDS by improving their ability to manage in-network congestion. Our evaluation reveals that FASTFLOW outperforms cutting-edge solutions, including EQDS, Swift, BBR, and MPRDMA, delivering up to 50% performance improvements in modern datacenter networks.

The design space of current quantum computers is expansive with no obvious winning solution. This leaves practitioners with a clear question: "What is the optimal system configuration to run an algorithm?". This paper explores hardware design trade-offs across NISQ systems to guide algorithm and hardware design choices. The evaluation is driven by algorithmic workloads and algorithm fidelity models which capture architectural features such as gate expressivity, fidelity, and crosstalk. We also argue that the criteria for gate design and selection should be extended from maximizing average fidelity to a more comprehensive approach that takes into account the gate expressivity with respect to algorithmic structures. We consider native entangling gates (CNOT, ECR, CZ, ZZ, XX, Sycamore, $\sqrt{\text{iSWAP}}$), proposed gates (B Gate, $\sqrt[4]{\text{CNOT}}$, $\sqrt[8]{\text{CNOT}}$), as well as parameterized gates (FSim, XY). Our methodology is driven by a custom synthesis driven circuit compilation workflow, which is able to produce minimal circuit representations for a given system configuration. By providing a method to evaluate the suitability of algorithms for hardware platforms, this work emphasizes the importance of hardware-software co-design for quantum computing.

Coronary artery disease (CAD) is the dominant cause of death and hospitalization across the globe. Atherosclerosis, an inflammatory condition that gradually narrows arteries and has potentially fatal effects, is the most frequent cause of CAD. Nonetheless, the circulation regularly adapts in the presence of atherosclerosis, through the formation of collateral arteries, resulting in significant long-term health benefits. Therefore, timely detection of coronary collateral circulation (CCC) is crucial for CAD personalized medicine. We propose a novel deep learning based method to detect CCC in angiographic images. Our method relies on a convolutional backbone to extract spatial features from each frame of an angiography sequence. The features are then concatenated, and subsequently processed by another convolutional layer that processes embeddings temporally. Due to scarcity of data, we also experiment with pretraining the backbone on coronary artery segmentation, which improves the results consistently. Moreover, we experiment with few-shot learning to further improve performance, given our low data regime. We present our results together with subgroup analyses based on Rentrop grading, collateral flow, and collateral grading, which provide valuable insights into model performance. Overall, the proposed method shows promising results in detecting CCC, and can be further extended to perform landmark based CCC detection and CCC quantification.

On a convex polyhedron P, the cut locus C(x) with respect to a point x is a tree of geodesic segments (shortest paths) on P that includes every vertex. We say that P has a skeletal cut locus if there is some x in P such that C(x) is a subset of Sk(P), where Sk(P) is the 1-skeleton of P . At a first glance, there seems to be very little relation between the cut locus and the 1-skeleton, as the first one is an intrinsic geometry notion, and the second one specifies the combinatorics of P. In this paper we study skeletal cut loci, obtaining four main results. First, given any combinatorial tree T without degree-2 nodes, there exists a convex polyhedron P and a point x in P with a cut locus that lies in Sk(P), and whose combinatorics match T. Second, any (non-degenerate) polyhedron P has at most a finite number of points x for which C(x) is a subset of Sk(P). Third, we show that almost all polyhedra have no skeletal cut locus. Fourth, we provide a combinatorial restriction to the existence of skeletal cut loci. Because the source unfolding of P with respect to x is always a non-overlapping net for P, and because the boundary of the source unfolding is the (unfolded) cut locus, source unfoldings of polyhedra with skeletal cut loci are edge-unfoldings, and moreover "blooming," avoiding self-intersection during an unfolding process., Comment: 20 pages, 12 figures, 9 references. v2: Many minor improvements

We call a pair of vertex-disjoint, induced subtrees of a rooted trees twins if they have the same counts of vertices by out-degrees. The likely maximum size of twins in a uniformly random, rooted Cayley tree of size $n\to\infty$ is studied. It is shown that the expected number of twins of size $(2+\delta)\sqrt{\log n\cdot\log\log n}$ approaches zero, while the expected number of twins of size $(2-\delta)\sqrt{\log n\cdot\log\log n}$ approaches infinity., Comment: 16 pages

The Riemann-Hilbert (RH) approach, whose origins can be traced back to Riemann's PhD thesis, is well known to be far-reaching. It provides a general framework for expressing solutions of integrable problems such as ODEs or PDEs. Its generalization concerning monodromy groups of Fuchsian systems is one of Hilbert's 23 problems. In this paper we extend a basic result in scalar RH theory, the Sokhotski-Plemelj formula. Classically, this formula is derived under assumptions of H\"older continuity, although it also holds true under weaker, Dini, continuity conditions. Dini continuity is still too restrictive. We prove the Sokhotski-Plemelj formula under weaker assumptions, namely continuity at a point and an $L^1$ condition. Furthermore, we provide sufficient conditions for the existence of the Cauchy $\rm{P.V.}$ integral which are in a precise sense also necessary: weakening them runs into obstructions of a mathematical foundations nature.

In the noisy intermediate-scale quantum era, mid-circuit measurement and reset operations facilitate novel circuit optimization strategies by reducing a circuit's qubit count in a method called resizing. This paper introduces two such algorithms. The first one leverages gate-dependency rules to reduce qubit count by 61.6% or 45.3% when optimizing depth as well. Based on numerical instantiation and synthesis, the second algorithm finds resizing opportunities in previously unresizable circuits via dependency rules and other state-of-the-art tools. This resizing algorithm reduces qubit count by 20.7% on average for these previously impossible-to-resize circuits.

Understanding the internal representations learned by neural networks is a cornerstone challenge in the science of machine learning. While there have been significant recent strides in some cases towards understanding how neural networks implement specific target functions, this paper explores a complementary question -- why do networks arrive at particular computational strategies? Our inquiry focuses on the algebraic learning tasks of modular addition, sparse parities, and finite group operations. Our primary theoretical findings analytically characterize the features learned by stylized neural networks for these algebraic tasks. Notably, our main technique demonstrates how the principle of margin maximization alone can be used to fully specify the features learned by the network. Specifically, we prove that the trained networks utilize Fourier features to perform modular addition and employ features corresponding to irreducible group-theoretic representations to perform compositions in general groups, aligning closely with the empirical observations of Nanda et al. and Chughtai et al. More generally, we hope our techniques can help to foster a deeper understanding of why neural networks adopt specific computational strategies., Comment: Accepted as Spotlight at ICLR 2024

Using resurgent analysis we offer a novel mathematical perspective on a curious bijection (duality) that has many potential applications ranging from the theory of vertex algebras to the physics of SCFTs in various dimensions, to q-series invariants in low-dimensional topology that arise, e.g. in Vafa-Witten theory and in non-perturbative completion of complex Chern-Simons theory. In particular, we introduce explicit numerical algorithms that efficiently implement this bijection. This bijection is founded on preservation of relations, a fundamental property of resurgent functions. Using resurgent analysis we find new structures and patterns in complex Chern-Simons theory on closed hyperbolic 3-manifolds obtained by surgeries on hyperbolic twist knots. The Borel plane exhibits several intriguing hints of a new form of integrability. An important role in this analysis is played by the twisted Alexander polynomials and the adjoint Reidemeister torsion, which help us determine the Stokes data. The method of singularity elimination enables extraction of geometric data even for very distant Borel singularities, leading to detailed non-perturbative information from perturbative data. We also introduce a new double-scaling limit to probe 0-surgeries from the limiting $r\to\infty$ behavior of 1/r surgeries, and apply it to the family of hyperbolic twist knots., Comment: 115 pages; 32 figures

Supporting mainstream applications is fundamental for a new OS to have impact. It is generally achieved by developing a layer of compatibility allowing applications developed for a mainstream OS like Linux to run unmodified on the new OS. Building such a layer, as we show, results in large engineering inefficiencies due to the lack of efficient methods to precisely measure the OS features required by a set of applications. We propose Loupe, a novel method based on dynamic analysis that determines the OS features that need to be implemented in a prototype OS to bring support for a target set of applications and workloads. Loupe guides and boosts OS developers as they build compatibility layers, prioritizing which features to implement in order to quickly support many applications as early as possible. We apply our methodology to 100+ applications and several OSes currently under development, demonstrating high engineering effort savings vs. existing approaches: for example, for the 62 applications supported by the OSv kernel, we show that using Loupe, would have required implementing only 37 system calls vs. 92 for the non-systematic process followed by OSv developers. We study our measurements and extract novel key insights. Overall, we show that the burden of building compatibility layers is significantly less than what previous works suggest: in some cases, only as few as 20% of system calls reported by static analysis, and 50% of those reported by naive dynamic analysis need an implementation for an application to successfully run standard benchmarks., Comment: Accepted to appear at ASPLOS'24 (https://www.asplos-conference.org/asplos2024/)

In this paper, we investigate the fundamental limits of MIMO-OFDM integrated sensing and communications (ISAC) systems based on a Bayesian Cram\'er-Rao bound (BCRB) analysis. We derive the BCRB for joint channel parameter estimation and data symbol detection, in which a performance trade-off between both functionalities is observed. We formulate the optimization problem for a linear precoder design and propose the stochastic Riemannian gradient descent (SRGD) approach to solve the non-convex problem. We analyze the optimality conditions and show that SRGD ensures convergence with high probability. The simulation results verify our analyses and also demonstrate a fast convergence speed. Finally, the performance trade-off is illustrated and investigated., Comment: Accepted to IEEE GLOBECOM 2023

WebAssembly (Wasm) is a low-level portable code format offering near native performance. It is intended as a compilation target for a wide variety of source languages. However, Wasm provides no direct support for non-local control flow features such as async/await, generators/iterators, lightweight threads, first-class continuations, etc. This means that compilers for source languages with such features must ceremoniously transform whole source programs in order to target Wasm. We present WasmFX, an extension to Wasm which provides a universal target for non-local control features via effect handlers, enabling compilers to translate such features directly into Wasm. Our extension is minimal and only adds three main instructions for creating, suspending, and resuming continuations. Moreover, our primitive instructions are type-safe providing typed continuations which are well-aligned with the design principles of Wasm whose stacks are typed. We present a formal specification of WasmFX and show that the extension is sound. We have implemented WasmFX as an extension to the Wasm reference interpreter and also built a prototype WasmFX extension for Wasmtime, a production-grade Wasm engine, piggybacking on Wasmtime's existing fibers API. The preliminary performance results for our prototype are encouraging, and we outline future plans to realise a native implementation

This paper describes the solutions submitted by the UPB team to the AuTexTification shared task, featured as part of IberLEF-2023. Our team participated in the first subtask, identifying text documents produced by large language models instead of humans. The organizers provided a bilingual dataset for this subtask, comprising English and Spanish texts covering multiple domains, such as legal texts, social media posts, and how-to articles. We experimented mostly with deep learning models based on Transformers, as well as training techniques such as multi-task learning and virtual adversarial training to obtain better results. We submitted three runs, two of which consisted of ensemble models. Our best-performing model achieved macro F1-scores of 66.63% on the English dataset and 67.10% on the Spanish dataset., Comment: 10 pages. Accepted for publication in the IberLEF 2023 Proceedings, at https://ceur-ws.org/