Search

We study Kirby problems 1.92(E)-(G), which, roughly speaking, ask for which compact oriented $3$-manifold $M$ the Kauffman bracket skein module $\mathcal{S}(M)$ has torsion as a $\mathbb{Z}[A^{\pm 1}]$-module. We give new criteria for the presence of torsion in terms of how large the $SL_2(\mathbb{C})$-character variety of $M$ is. This gives many counterexamples to question 1.92(G)-(i) in Kirby's list. For manifolds with incompressible tori, we give new effective criteria for the presence of torsion, revisiting the work of Przytycki and Veve. We also show that $\mathcal{S}(\mathbb{R P}^3# L(p,1))$ has torsion when $p$ is even. Finally, we show that for $M$ an oriented Seifert manifold, closed or with boundary, $\mathcal{S}(M)$ has torsion if and only if $M$ admits a $2$-sided non-boundary parallel essential surface., Comment: 37 pages, 16 figures. Comments welcome!

We establish the geometry behind the quantum $6j$-symbols under only the admissibility conditions as in the definition of the Turaev-Viro invariants of $3$-manifolds. As a classification, we show that the $6$-tuples in the quantum $6j$-symbols give in a precise way to the dihedral angles of (1) a spherical tetrahedron, (2) a generalized Euclidean tetrahedron, (3) a generalized hyperbolic tetrahedron or (4) in the degenerate case the angles between four oriented straight lines in the Euclidean plane. We also show that for a large proportion of the cases, the $6$-tuples always give the dihedral angles of a generalized hyperbolic tetrahedron and the exponential growth rate of the corresponding quantum $6j$-symbols equals the suitably defined volume of this generalized hyperbolic tetrahedron. It is worth mentioning that the volume of a generalized hyperbolic tetrahedron can be negative, hence the corresponding sequence of the quantum $6j$-symbols could decay exponentially. This is a phenomenon that has never been aware of before., Comment: 55 pages, 16 figures

We show that the Volume Conjecture for polyhedra implies a weak version of the Stoker Conjecture; in turn we prove that this weak version of the Stoker conjecture implies the Stoker conjecture. The main tool used is an extension of a result of Montcouquiol and Weiss, saying that dihedral angles are local coordinates for compact polyhedra with angles $\leq \pi$., Comment: 11 pages, comments welcome

Data is the driving force of machine learning, with the amount and quality of training data often being more important for the performance of a system than architecture and training details. But collecting, processing and annotating real data at scale is difficult, expensive, and frequently raises additional privacy, fairness and legal concerns. Synthetic data is a powerful tool with the potential to address these shortcomings: 1) it is cheap 2) supports rich ground-truth annotations 3) offers full control over data and 4) can circumvent or mitigate problems regarding bias, privacy and licensing. Unfortunately, software tools for effective data generation are less mature than those for architecture design and training, which leads to fragmented generation efforts. To address these problems we introduce Kubric, an open-source Python framework that interfaces with PyBullet and Blender to generate photo-realistic scenes, with rich annotations, and seamlessly scales to large jobs distributed over thousands of machines, and generating TBs of data. We demonstrate the effectiveness of Kubric by presenting a series of 13 different generated datasets for tasks ranging from studying 3D NeRF models to optical flow estimation. We release Kubric, the used assets, all of the generation code, as well as the rendered datasets for reuse and modification., Comment: 21 pages, CVPR2022

The asymptotic behavior of quantum $6j$-symbols is closely related to the volume of truncated hyperideal tetrahedra\,\cite{C}, and plays a central role in understanding the asymptotics of the Turaev-Viro invariants of $3$-manifolds. In this paper, we propose a conjecture relating the asymptotics of the discrete Fourier transforms of quantum $6j$-symbols on one hand, and the volume of deeply truncated tetrahedra of various types on the other. As supporting evidence, we prove the conjecture in the case that the dihedral angles are sufficiently small, and provide numerical calculations in the case that the dihedral angles are relatively big. A key observation is a relationship between quantum $6j$-symbols and the co-volume function of deeply truncated tetrahedra, which is of interest in its own right. More ambitiously, we extend the conjecture to the discrete Fourier transforms of the Yokota invariants of planar graphs and volume of deeply truncated polyhedra, and provide supporting evidence., Comment: 33 pages, 12 figures. arXiv admin note: text overlap with arXiv:2008.05045

In a recent paper, we have demonstrated how the affinity between TPUs and multi-dimensional financial simulation resulted in fast Monte Carlo simulations that could be setup in a few lines of python Tensorflow code. We also presented a major benefit from writing high performance simulations in an automated differentiation language such as Tensorflow: a single line of code enabled us to estimate sensitivities, i.e. the rate of change in price of financial instrument with respect to another input such as the interest rate, the current price of the underlying, or volatility. Such sensitivities (otherwise known as the famous financial "Greeks") are fundamental for risk assessment and risk mitigation. In the present follow-up short paper, we extend the developments exposed in our previous work about the use of Tensor Processing Units and Tensorflow for TPUs.

We conjecture an upper bound on the growth of the Yokota invariant of polyhedral graphs, extending a previous result on the growth of the $6j$-symbol. Using Barrett's Fourier transform we are able to prove this conjecture in a large family of examples. As a consequence of this result, we prove the Turaev-Viro Volume Conjecture for a new infinite family of hyperbolic manifolds., Comment: 39 pages, 26 figures. Updated with new title and a stronger focus on the upper bound conjecture; accepted for publication at Algebraic and Geometric Topology

We study the supremum of the volume of hyperbolic polyhedra with some fixed combinatorics and with vertices of any kind (real, ideal or hyperideal). We find that the supremum is always equal to the volume of the rectification of the 1-skeleton. The theorem is proved by applying a sort of volume-increasing flow to any hyperbolic polyhedron. Singularities may arise in the flow because some strata of the polyhedron may degenerate to lower-dimensional objects; when this occurs, we need to study carefully the combinatorics of the resulting polyhedron and continue with the flow, until eventually we get a rectified polyhedron., Comment: 37 pages, 14 figures. Updated reference; comments welcome!

Monte Carlo methods are critical to many routines in quantitative finance such as derivatives pricing, hedging and risk metrics. Unfortunately, Monte Carlo methods are very computationally expensive when it comes to running simulations in high-dimensional state spaces where they are still a method of choice in the financial industry. Recently, Tensor Processing Units (TPUs) have provided considerable speedups and decreased the cost of running Stochastic Gradient Descent (SGD) in Deep Learning. After highlighting computational similarities between training neural networks with SGD and simulating stochastic processes, we ask in the present paper whether TPUs are accurate, fast and simple enough to use for financial Monte Carlo. Through a theoretical reminder of the key properties of such methods and thorough empirical experiments we examine the fitness of TPUs for option pricing, hedging and risk metrics computation. In particular we demonstrate that, in spite of the use of mixed precision, TPUs still provide accurate estimators which are fast to compute when compared to GPUs. We also show that the Tensorflow programming model for TPUs is elegant, expressive and simplifies automated differentiation.

Characterizing temporal dependence patterns is a critical step in understanding the statistical properties of sequential data. Long Range Dependence (LRD) --- referring to long-range correlations decaying as a power law rather than exponentially w.r.t. distance --- demands a different set of tools for modeling the underlying dynamics of the sequential data. While it has been widely conjectured that LRD is present in language modeling and sequential recommendation, the amount of LRD in the corresponding sequential datasets has not yet been quantified in a scalable and model-independent manner. We propose a principled estimation procedure of LRD in sequential datasets based on established LRD theory for real-valued time series and apply it to sequences of symbols with million-item-scale dictionaries. In our measurements, the procedure estimates reliably the LRD in the behavior of users as they write Wikipedia articles and as they interact with YouTube. We further show that measuring LRD better informs modeling decisions in particular for RNNs whose ability to capture LRD is still an active area of research. The quantitative measure informs new Evolutive Recurrent Neural Networks (EvolutiveRNNs) designs, leading to state-of-the-art results on language understanding and sequential recommendation tasks at a fraction of the computational cost.

Recommender system research suffers from a disconnect between the size of academic data sets and the scale of industrial production systems. In order to bridge that gap, we propose to generate large-scale user/item interaction data sets by expanding pre-existing public data sets. Our key contribution is a technique that expands user/item incidence matrices matrices to large numbers of rows (users), columns (items), and non-zero values (interactions). The proposed method adapts Kronecker Graph Theory to preserve key higher order statistical properties such as the fat-tailed distribution of user engagements, item popularity, and singular value spectra of user/item interaction matrices. Preserving such properties is key to building large realistic synthetic data sets which in turn can be employed reliably to benchmark recommender systems and the systems employed to train them. We further apply our stochastic expansion algorithm to the binarized MovieLens 20M data set, which comprises 20M interactions between 27K movies and 138K users. The resulting expanded data set has 1.2B ratings, 2.2M users, and 855K items, which can be scaled up or down., Comment: arXiv admin note: substantial text overlap with arXiv:1901.08910

Due to the great growth of motorcycles in the urban fleet and the growth of the study on its behavior and of how this vehicle affects the flow of traffic becomes necessary the development of tools and techniques different from the conventional ones to identify its presence in the traffic flow and be able to extract your information. The article in question attempts to contribute to the study on this type of vehicle by generating a motorcycle image bank and developing and calibrating a motorcycle classifier by combining the LBP techniques to create the characteristic vectors and the classification technique LinearSVC to perform the predictions. In this way the classifier of vehicles of the type motorcycle developed in this research can classify the images of vehicles extracted of videos of monitoring between two classes motorcycles and non-motorcycles with a precision and an accuracy superior to 0,9., Comment: 12 pages, 6 figures, 4 table

Understanding temporal dynamics has proved to be highly valuable for accurate recommendation. Sequential recommenders have been successful in modeling the dynamics of users and items over time. However, while different model architectures excel at capturing various temporal ranges or dynamics, distinct application contexts require adapting to diverse behaviors. In this paper we examine how to build a model that can make use of different temporal ranges and dynamics depending on the request context. We begin with the analysis of an anonymized Youtube dataset comprising millions of user sequences. We quantify the degree of long-range dependence in these sequences and demonstrate that both short-term and long-term dependent behavioral patterns co-exist. We then propose a neural Multi-temporal-range Mixture Model (M3) as a tailored solution to deal with both short-term and long-term dependencies. Our approach employs a mixture of models, each with a different temporal range. These models are combined by a learned gating mechanism capable of exerting different model combinations given different contextual information. In empirical evaluations on a public dataset and our own anonymized YouTube dataset, M3 consistently outperforms state-of-the-art sequential recommendation methods., Comment: Accepted at WWW 2019

Recommender System research suffers currently from a disconnect between the size of academic data sets and the scale of industrial production systems. In order to bridge that gap we propose to generate more massive user/item interaction data sets by expanding pre-existing public data sets. User/item incidence matrices record interactions between users and items on a given platform as a large sparse matrix whose rows correspond to users and whose columns correspond to items. Our technique expands such matrices to larger numbers of rows (users), columns (items) and non zero values (interactions) while preserving key higher order statistical properties. We adapt the Kronecker Graph Theory to user/item incidence matrices and show that the corresponding fractal expansions preserve the fat-tailed distributions of user engagements, item popularity and singular value spectra of user/item interaction matrices. Preserving such properties is key to building large realistic synthetic data sets which in turn can be employed reliably to benchmark Recommender Systems and the systems employed to train them. We provide algorithms to produce such expansions and apply them to the MovieLens 20 million data set comprising 20 million ratings of 27K movies by 138K users. The resulting expanded data set has 10 billion ratings, 864K items and 2 million users in its smaller version and can be scaled up or down. A larger version features 655 billion ratings, 7 million items and 17 million users.

Industrial recommender systems deal with extremely large action spaces -- many millions of items to recommend. Moreover, they need to serve billions of users, who are unique at any point in time, making a complex user state space. Luckily, huge quantities of logged implicit feedback (e.g., user clicks, dwell time) are available for learning. Learning from the logged feedback is however subject to biases caused by only observing feedback on recommendations selected by the previous versions of the recommender. In this work, we present a general recipe of addressing such biases in a production top-K recommender system at Youtube, built with a policy-gradient-based algorithm, i.e. REINFORCE. The contributions of the paper are: (1) scaling REINFORCE to a production recommender system with an action space on the orders of millions; (2) applying off-policy correction to address data biases in learning from logged feedback collected from multiple behavior policies; (3) proposing a novel top-K off-policy correction to account for our policy recommending multiple items at a time; (4) showcasing the value of exploration. We demonstrate the efficacy of our approaches through a series of simulations and multiple live experiments on Youtube.

We prove the Turaev-Viro invariants volume conjecture for a "universal" class of cusped hyperbolic 3-manifolds that produces all 3-manifolds with empty or toroidal boundary by Dehn filling. This leads to two-sided bounds on the volume of any hyperbolic 3-manifold with empty or toroidal boundary in terms of the growth rate of the Turaev-Viro invariants of the complement of an appropriate link contained in the manifold. We also provide evidence for a conjecture of Andersen, Masbaum and Ueno (AMU conjecture) about certain quantum representations of surface mapping class groups. A key step in our proofs is finding a sharp upper bound on the growth rate of the quantum $6j-$symbol evaluated at $q=e^{\frac{2\pi i}{r}}.$, Comment: 29 pages, 3 figures, to appear in Journal of Differential Geometry

This article shows how the recent breakthroughs in Reinforcement Learning (RL) that have enabled robots to learn to play arcade video games, walk or assemble colored bricks, can be used to perform other tasks that are currently at the core of engineering cyberphysical systems. We present the first use of RL for the control of systems modeled by discretized non-linear Partial Differential Equations (PDEs) and devise a novel algorithm to use non-parametric control techniques for large multi-agent systems. We show how neural network based RL enables the control of discretized PDEs whose parameters are unknown, random, and time-varying. We introduce an algorithm of Mutual Weight Regularization (MWR) which alleviates the curse of dimensionality of multi-agent control schemes by sharing experience between agents while giving each agent the opportunity to specialize its action policy so as to tailor it to the local parameters of the part of the system it is located in.

Linear causal analysis is central to a wide range of important application spanning finance, the physical sciences, and engineering. Much of the existing literature in linear causal analysis operates in the time domain. Unfortunately, the direct application of time domain linear causal analysis to many real-world time series presents three critical challenges: irregular temporal sampling, long range dependencies, and scale. Moreover, real-world data is often collected at irregular time intervals across vast arrays of decentralized sensors and with long range dependencies which make naive time domain correlation estimators spurious. In this paper we present a frequency domain based estimation framework which naturally handles irregularly sampled data and long range dependencies while enabled memory and communication efficient distributed processing of time series data. By operating in the frequency domain we eliminate the need to interpolate and help mitigate the effects of long range dependencies. We implement and evaluate our new work-flow in the distributed setting using Apache Spark and demonstrate on both Monte Carlo simulations and high-frequency financial trading that we can accurately recover causal structure at scale.

Second order stationary models in time series analysis are based on the analysis of essential statistics whose computations follow a common pattern. In particular, with a map-reduce nomenclature, most of these operations can be modeled as mapping a kernel that only depends on short windows of consecutive data and reducing the results produced by each computation. This computational pattern stems from the ergodicity of the model under consideration and is often referred to as weak or short memory when it comes to data indexed with respect to time. In the following we will show how studying weak memory systems can be done in a scalable manner thanks to a framework relying on specifically designed overlapping distributed data structures that enable fragmentation and replication of the data across many machines as well as parallelism in computations. This scheme has been implemented for Apache Spark but is certainly not system specific. Indeed we prove it is also adapted to leveraging high bandwidth fragmented memory blocks on GPUs.

We report first-principle atomistic simulations on the effect of local strain gradients on the nanoscale domain morphology of free-standing PbTiO$_3$ ultrathin films. First, the ferroelectric properties of free films at the atomic level are reviewed. For the explored thicknesses (10 to 23 unit cells), we find flux-closure domain structures whose morphology is thickness dependent. A critical value of 20 unit cells is observed: thinner films show structures with 90$^\circ$ domain loops, whereas thicker ones develop, in addition, 180$^\circ$ domain walls, giving rise to structures of the Landau-Lifshitz type. When a local and compressive strain gradient at the top surface is imposed, the gradient is able to switch the polarization of the downward domains, but not to the opposite ones. The evolution of the domain pattern as a function of the strain gradient strength consequently depends on the film thickness. Our simulations indicate that in thinner films, first the 90$^\circ$ domain loops migrate towards the strain-gradient region, and then the polarization in that zone is gradually switched. In thicker films, instead, the switching in the strain-gradient region is progressive, not involving domain-wall motion, which is attributed to less mobile 180$^\circ$ domain walls. The ferroelectric switching is understood based on the knowledge of the local atomic properties, and the results confirm that mechanical flexoelectricity provides a means to control the nanodomain pattern in ferroelectric systems., Comment: 9 pages, 6 figures

Using the dedicated computer Janus, we follow the nonequilibrium dynamics of the Ising spin glass in three dimensions for eleven orders of magnitude. The use of integral estimators for the coherence and correlation lengths allows us to study dynamic heterogeneities and the presence of a replicon mode and to obtain safe bounds on the Edwards-Anderson order parameter below the critical temperature. We obtain good agreement with experimental determinations of the temperature-dependent decay exponents for the thermoremanent magnetization. This magnitude is observed to scale with the much harder to measure coherence length, a potentially useful result for experimentalists. The exponents for energy relaxation display a linear dependence on temperature and reasonable extrapolations to the critical point. We conclude examining the time growth of the coherence length, with a comparison of critical and activated dynamics., Comment: 38 pages, 26 figures

We study numerically the nonequilibrium dynamics of the Ising Spin Glass, for a time that spans eleven orders of magnitude, thus approaching the experimentally relevant scale (i.e. {\em seconds}). We introduce novel analysis techniques that allow to compute the coherence length in a model-independent way. Besides, we present strong evidence for a replicon correlator and for overlap equivalence. The emerging picture is compatible with non-coarsening behavior., Comment: 4 pages, 4 eps color figures. Version accepted for publication in Phys. Rev. Lett

This paper describes JANUS, a modular massively parallel and reconfigurable FPGA-based computing system. Each JANUS module has a computational core and a host. The computational core is a 4x4 array of FPGA-based processing elements with nearest-neighbor data links. Processors are also directly connected to an I/O node attached to the JANUS host, a conventional PC. JANUS is tailored for, but not limited to, the requirements of a class of hard scientific applications characterized by regular code structure, unconventional data manipulation instructions and not too large data-base size. We discuss the architecture of this configurable machine, and focus on its use on Monte Carlo simulations of statistical mechanics. On this class of application JANUS achieves impressive performances: in some cases one JANUS processing element outperfoms high-end PCs by a factor ~ 1000. We also discuss the role of JANUS on other classes of scientific applications., Comment: 11 pages, 6 figures. Improved version, largely rewritten, submitted to Computing in Science & Engineering

We evaluate IBM's Enhanced Cell Broadband Engine (BE) as a possible building block of a new generation of lattice QCD machines. The Enhanced Cell BE will provide full support of double-precision floating-point arithmetics, including IEEE-compliant rounding. We have developed a performance model and applied it to relevant lattice QCD kernels. The performance estimates are supported by micro- and application-benchmarks that have been obtained on currently available Cell BE-based computers, such as IBM QS20 blades and PlayStation 3. The results are encouraging and show that this processor is an interesting option for lattice QCD applications. For a massively parallel machine on the basis of the Cell BE, an application-optimized network needs to be developed., Comment: 7 pages, 3 figures, contribution to Lattice 2007 (Regensburg, Germany)

We describe the hardwired implementation of algorithms for Monte Carlo simulations of a large class of spin models. We have implemented these algorithms as VHDL codes and we have mapped them onto a dedicated processor based on a large FPGA device. The measured performance on one such processor is comparable to O(100) carefully programmed high-end PCs: it turns out to be even better for some selected spin models. We describe here codes that we are currently executing on the IANUS massively parallel FPGA-based system., Comment: 19 pages, 8 figures; submitted to Computer Physics Communications

Dedicated machines designed for specific computational algorithms can outperform conventional computers by several orders of magnitude. In this note we describe {\it Ianus}, a new generation FPGA based machine and its basic features: hardware integration and wide reprogrammability. Our goal is to build a machine that can fully exploit the performance potential of new generation FPGA devices. We also plan a software platform which simplifies its programming, in order to extend its intended range of application to a wide class of interesting and computationally demanding problems. The decision to develop a dedicated processor is a complex one, involving careful assessment of its performance lead, during its expected lifetime, over traditional computers, taking into account their performance increase, as predicted by Moore's law. We discuss this point in detail.