title: Hot electron cooling in Dirac semimetal Cd$_3$As$_2$ due to polar optical phonons

abstract: A theory of hot electron cooling power due to polar optical phonons $P_{\rm op}$ is developed in three-dimensional Dirac semimetal($3$DDS) Cd$_3$As$_2$ taking account of hot phonon effect. Hot phonon distribution $N_q$ and $P_{\rm op}$ are investigated as a function of electron temperature $T_e$, electron density $n_e$, and phonon relaxation time $\tau_p$. It is found that $P_{\rm op}$ increases rapidly (slowly) with $T_e$ at lower (higher) temperature regime. Whereas, $P_{\rm op}$ is weakly deceasing with increasing $n_e$. The results are compared with those for three-dimensional electron gas ($3$DEG) in Cd$_3$As$_2$ semiconductor. Hot phonon effect is found to reduce $P_{\rm op}$ considerably and it is stronger in 3DDS Cd$_3$As$_2$ than in Cd$_3$As$_2$ semiconductor. $P_{\rm op}$ is also compared with the hot electron cooling power due to acoustic phonons $P_{\rm ac}$. We find that a crossover takes place from $P_{\rm ac}$ dominated cooling at low $T_e$ to $P_{\rm op}$ dominated cooling at higher $T_e$. The temperature at which this crossover occurs shifts towards higher values with the increase of $n_e$. Also, hot electron energy relaxation time $\tau_e$ is discussed and estimated.


title: Maximizing the number of edges in three-dimensional colored triangulations whose building blocks are balls

abstract: Colored triangulations offer a generalization of combinatorial maps to higher dimensions. Just like maps are gluings of polygons, colored triangulations are built as gluings of special, higher-dimensional building blocks, such as octahedra, which we call colored building blocks and known in the dual as bubbles. A colored building block is determined by its boundary triangulation, which in the case of polygons is simply characterized by its length. In three dimensions, colored building blocks are labeled by some 2D triangulations and those homeomorphic to the 3-ball are labeled by the subset of planar ones. Similarly to Euler's formula in 2D which provides an upper bound to the number of vertices at fixed number of polygons with given lengths, we look in three dimensions for an upper bound on the number of edges at fixed number of given colored building blocks. In this article we solve this problem when all colored building blocks, except possibly one, are homeomorphic to the 3-ball. To do this, we find a characterization of the way a colored building block homeomorphic to the ball has to be glued to other blocks of arbitrary topology in a colored triangulation which maximizes the number of edges. This local characterization can be extended to the whole triangulation as long as there is at most one colored building block which is not a 3-ball. The triangulations obtained this way are in bijection with trees. The number of edges is given as an independent sum over the building blocks of such a triangulation. In the case of all colored building blocks being homeomorphic to the 3-ball, we show that these triangulations are homeomorphic to the 3-sphere. Those results were only known for the octahedron and for melonic building blocks before. This article is self-contained and can be used as an introduction to colored triangulations and their bubbles from a purely combinatorial point of view.


title: Spectral stability of nonlinear gravity waves in the atmosphere

abstract: We apply spectral stability theory to investigate nonlinear gravity waves in the atmosphere. These waves are determined by modulation equations that result from Wentzel-Kramers-Brillouin theory. First, we establish that plane waves, which represent exact solutions to the inviscid Boussinesq equations, are spectrally stable with respect to their nonlinear modulation equations under the same conditions as what is known as modulational stability from weakly nonlinear theory. In contrast to Boussinesq, the pseudo-incompressible regime does account for the altitudinal varying background density. Second, we show for the first time that upward-traveling wave fronts solving the inviscid modulation equations, that compare to pseudo-incompressible theory, are unconditionally unstable. Both inviscid regimes turn out to be ill-posed as the spectra allow for arbitrarily large instability growth rates. Third, a regularization is found by including dissipative effects. The corresponding traveling wave solutions have localized amplitude and blow up unconditionally by embedded eigenvalue instabilities but the instability growth rate is bounded from above. Additionally, all three types of nonlinear modulation equations are solved numerically to further investigate and illustrate the nature of the analytic stability results.


title: Measuring Accessibility using Gravity and Radiation Models

abstract: Since the presentation of the Radiation Model, much work has been done to compare its findings with those obtained from Gravitational Models. These comparisons always aim at measuring the accuracy with which the models reproduce the mobility described by origin-destination matrices. This has been done at different spatial scales using different datasets, and several versions of the models have been proposed to adjust to various spatial systems. However the models, to our knowledge, have never been compared with respect to policy testing scenarios. For this reason, here we use the models to analyze the impact of the introduction of a new transportation network, a Bus Rapid Transport system, in the city of Teresina in Brazil. We do this by measuring the estimated variation in the trip distribution, and formulate an accessibility to employment indicator for the different zones of the city. By comparing the results obtained with the two approaches, we are able, not only to better assess the goodness of fit and the impact of this intervention, but also to understand reasons for the systematic similarities and differences in their predictions.


title: Stochastic stability of invariant measures: The 2D Euler equation

abstract: In finite-dimensional dynamical systems, stochastic stability provides the selection of physical relevant measures from the myriad invariant measures of conservative systems. That this might also apply to infinite-dimensional systems is the inspiration for this work. As an example the 2D Euler equation is studied. Among other results this study suggests that the coherent structures observed in 2D hydrodynamics are associated to configurations that maximize stochastically stable measures uniquely determined by the boundary conditions in mode space.


title: Experimental investigation of dynamical structures formation due to flowing complex plasma past an obstacle

abstract: We report the experimental observation of dynamical behavior of flowing complex plasma past a spherical obstacle. The experiment has been carried out in a $\Pi$-shaped DC glow discharge experimental device using kaolin particles as the dust component in a background of Argon plasma. A stationary dust cloud is formed by maintaining the pumping speed and gas flow rate. A spherical obstacle vertically mounted on the cathode tray acts as an obstacle to the flow of dust particles. The controlled dust flow is generated by reducing the mass flow of the neutrals through a mass flow controller. The flowing dust particles are repelled by the electrostatic field of the negatively charged sphere and a microparticle free region (dust void) is formed surrounding the obstacle. The far particles are attracted towards the floating obstacle and reflected back when they have arrived at a minimum distance, causing a ring shaped structure around the obstacle. We characterize the shape of this structure over a range of dust flow speeds and obstacle biases. For a supersonic flow of dust fluid around a negatively biased obstacle, a bow shock is formed on the upstream side of the sphere, while the generation of wave structures is observed on the downstream side for a particular range of flow velocities. Reynolds numbers in this case is estimated as $R_e \gtrsim 50$. This wave structure reminds of the beginning of the formation of a Von-K\'arm\'an vortex street. A physical picture for the observed structure based on ion-drag, neutral streaming and electric forces is discussed.


title: End-to-end Audiovisual Speech Recognition

abstract: Several end-to-end deep learning approaches have been recently presented which extract either audio or visual features from the input images or audio signals and perform speech recognition. However, research on end-to-end audiovisual models is very limited. In this work, we present an end-to-end audiovisual model based on residual networks and Bidirectional Gated Recurrent Units (BGRUs). To the best of our knowledge, this is the first audiovisual fusion model which simultaneously learns to extract features directly from the image pixels and audio waveforms and performs within-context word recognition on a large publicly available dataset (LRW). The model consists of two streams, one for each modality, which extract features directly from mouth regions and raw waveforms. The temporal dynamics in each stream/modality are modeled by a 2-layer BGRU and the fusion of multiple streams/modalities takes place via another 2-layer BGRU. A slight improvement in the classification rate over an end-to-end audio-only and MFCC-based model is reported in clean audio conditions and low levels of noise. In presence of high levels of noise, the end-to-end audiovisual model significantly outperforms both audio-only models.


title: Parabolic orbits of $2$-nilpotent elements for classical groups

abstract: We consider the conjugation-action of the Borel subgroup of the symplectic or the orthogonal group on the variety of nilpotent complex elements of nilpotency degree $2$ in its Lie algebra. We translate the setup to a representation-theoretic context in the language of a symmetric quiver algebra. This makes it possible to provide a parametrization of the orbits via a combinatorial tool that we call symplectic/orthogonal oriented link patterns. We deduce information about numerology. We then generalize these classifications to standard parabolic subgroups for all classical groups. Finally, our results are restricted to the nilradical.


title: Estimating scale-invariant future in continuous time

abstract: Natural learners must compute an estimate of future outcomes that follow from a stimulus in continuous time. Widely used reinforcement learning algorithms discretize continuous time and estimate either transition functions from one step to the next (model-based algorithms) or a scalar value of exponentially-discounted future reward using the Bellman equation (model-free algorithms). An important drawback of model-based algorithms is that computational cost grows linearly with the amount of time to be simulated. On the other hand, an important drawback of model-free algorithms is the need to select a time-scale required for exponential discounting. We present a computational mechanism, developed based on work in psychology and neuroscience, for computing a scale-invariant timeline of future outcomes. This mechanism efficiently computes an estimate of inputs as a function of future time on a logarithmically-compressed scale, and can be used to generate a scale-invariant power-law-discounted estimate of expected future reward. The representation of future time retains information about what will happen when. The entire timeline can be constructed in a single parallel operation which generates concrete behavioral and neural predictions. This computational mechanism could be incorporated into future reinforcement learning algorithms.


abstract: In this article, we discuss Iwasawa Main Conjecture for $p$-adic families of elliptic modular cuspforms. After the overview on the situation of the ordinary case of Hida family, we will introduce a Coleman map for Coleman family for the non-ordinary case (Coleman family) which was obtained as a joint work with Filippo Nuccio [NO16] and we give some results on Iwasawa Theory for Coleman families as applications of . First, we give a construction of a two-variable $p$-adic $L$-function for a Coleman family thanks to the ingredients given in [NO16] (Theorem 5.1). Combining this result and Coleman map obtained in [NO16], we also construct Beilinson-Kato Euler systems over a Coleman family (Thorem 5.3). Finally we formulate Iwasawa Main conjecture for a Coleman family and prove the half of Iwasawa Main Conjecture (Theorem 5.6).


title: Improving Mild Cognitive Impairment Prediction via Reinforcement Learning and Dialogue Simulation

abstract: Mild cognitive impairment (MCI) is a prodromal phase in the progression from normal aging to dementia, especially Alzheimers disease. Even though there is mild cognitive decline in MCI patients, they have normal overall cognition and thus is challenging to distinguish from normal aging. Using transcribed data obtained from recorded conversational interactions between participants and trained interviewers, and applying supervised learning models to these data, a recent clinical trial has shown a promising result in differentiating MCI from normal aging. However, the substantial amount of interactions with medical staff can still incur significant medical care expenses in practice. In this paper, we propose a novel reinforcement learning (RL) framework to train an efficient dialogue agent on existing transcripts from clinical trials. Specifically, the agent is trained to sketch disease-specific lexical probability distribution, and thus to converse in a way that maximizes the diagnosis accuracy and minimizes the number of conversation turns. We evaluate the performance of the proposed reinforcement learning framework on the MCI diagnosis from a real clinical trial. The results show that while using only a few turns of conversation, our framework can significantly outperform state-of-the-art supervised learning approaches.


title: Cech cohomology and the Capitulation kernel

abstract: We discuss the capitulation kernel associated to a degree n covering using Cech cohomology and the Kummer sequence. The main result is a five-term exact sequence that relates the capitulation kernel to the Cech cohomology of the n-th roots of unity and a certain subquotient of the group of units modulo n-th powers.


title: DARTS: Deceiving Autonomous Cars with Toxic Signs

abstract: Sign recognition is an integral part of autonomous cars. Any misclassification of traffic signs can potentially lead to a multitude of disastrous consequences, ranging from a life-threatening accident to even a large-scale interruption of transportation services relying on autonomous cars. In this paper, we propose and examine security attacks against sign recognition systems for Deceiving Autonomous caRs with Toxic Signs (we call the proposed attacks DARTS). In particular, we introduce two novel methods to create these toxic signs. First, we propose Out-of-Distribution attacks, which expand the scope of adversarial examples by enabling the adversary to generate these starting from an arbitrary point in the image space compared to prior attacks which are restricted to existing training/test data (In-Distribution). Second, we present the Lenticular Printing attack, which relies on an optical phenomenon to deceive the traffic sign recognition system. We extensively evaluate the effectiveness of the proposed attacks in both virtual and real-world settings and consider both white-box and black-box threat models. Our results demonstrate that the proposed attacks are successful under both settings and threat models. We further show that Out-of-Distribution attacks can outperform In-Distribution attacks on classifiers defended using the adversarial training defense, exposing a new attack vector for these defenses.


title: String Model with Mesons and Baryons in Modified Measure Theory

abstract: We consider string meson and string baryon models in the framework of the modified measure theory, the theory that does not use the determinant of the metric to construct the invariant volume element. As the outcome of this theory, the string tension is not placed ad hoc but is derived. When the charges are presented, the tension undergoes alterations. In the string meson model there are one string and two opposite charges at the endpoints. In the string baryon model there are two strings, two pairs of opposite charges at the endpoints and one additional charge at the intersection point, the point where these two strings are connected. The application of the modified measure theory is justified because the Neumann boundary conditions are obtained dynamically at every point where the charge is located and Dirichlet boundary conditions arise naturally at the intersection point. In particular, the Neumann boundary conditions that are obtained at the intersection point differ from that considered before by 't Hooft in [hep-th/0408148] and are stronger, which appears to solve the nonlocality problem that was encountered in the standard measure approach. The solutions of the equations of motion are presented. Assuming that each endpoint is the dynamical massless particle, the Regge trajectory with the slope parameter that depends on three different tensions is obtained.


title: Music Genre Classification using Masked Conditional Neural Networks

abstract: The ConditionaL Neural Networks (CLNN) and the Masked ConditionaL Neural Networks (MCLNN) exploit the nature of multi-dimensional temporal signals. The CLNN captures the conditional temporal influence between the frames in a window and the mask in the MCLNN enforces a systematic sparseness that follows a filterbank-like pattern over the network links. The mask induces the network to learn about time-frequency representations in bands, allowing the network to sustain frequency shifts. Additionally, the mask in the MCLNN automates the exploration of a range of feature combinations, usually done through an exhaustive manual search. We have evaluated the MCLNN performance using the Ballroom and Homburg datasets of music genres. MCLNN has achieved accuracies that are competitive to state-of-the-art handcrafted attempts in addition to models based on Convolutional Neural Networks.


title: Interpolating by functions from model subspaces in $H^1$

abstract: Given an interpolating Blaschke product $B$ with zeros $\{a_j\}$, we seek to characterize the sequences of values $\{w_j\}$ for which the interpolation problem $$f(a_j)=w_j\qquad (j=1,2,\dots)$$ can be solved with a function $f$ from the model subspace $H^1\cap B\overline{H^1_0}$ of the Hardy space $H^1$.


title: Random time-changes and asymptotic results for a class of continuous-time Markov chains on integers with alternating rates

abstract: We consider continuous-time Markov chains on integers which allow transitions to adjacent states only, with alternating rates. We give explicit formulas for probability generating functions, and also for means, variances and state probabilities of the random variables of the process. Moreover we study independent random time-changes with the inverse of the stable subordinator, the stable subordinator and the tempered stable subodinator. We also present some asymptotic results in the fashion of large deviations. These results give some generalizations of those presented in Di Crescenzo A., Macci C., Martinucci B. (2014).


title: Topological Methods in the Quest for Periodic Orbits

abstract: These are lecture notes on Floer and Rabinowitz-Floer homology written for a graduate course at UNICAMP August-December 2016 and a mini-course held at IMPA in August 2017.

categories: math.SG math-ph math.DG math.DS math.GT math.MP


title: Multicritical edge statistics for the momenta of fermions in non-harmonic traps

abstract: We compute the joint statistics of the momenta $p_i$ of $N$ non-interacting fermions in a trap, near the Fermi edge, with a particular focus on the largest one $p_{\max}$. For a $1d$ harmonic trap, momenta and positions play a symmetric role and hence, the joint statistics of momenta is identical to that of the positions. In particular, $p_{\max}$, as $x_{\max}$, is distributed according to the Tracy-Widom distribution. Here we show that novel "momentum edge statistics" emerge when the curvature of the potential vanishes, i.e. for "flat traps" near their minimum, with $V(x) \sim x^{2n}$ and $n>1$. These are based on generalisations of the Airy kernel that we obtain explicitly. The fluctuations of $p_{\max}$ are governed by new universal distributions determined from the $n$-th member of the second Painlev\'e hierarchy of non-linear differential equations, with connections to multicritical random matrix models. Finite temperature extensions and possible experimental signatures in cold atoms are discussed.

categories: cond-mat.stat-mech cond-mat.quant-gas math-ph math.MP math.PR


title: What We Read, What We Search: Media Attention and Public Attention Among 193 Countries

abstract: We investigate the alignment of international attention of news media organizations within 193 countries with the expressed international interests of the public within those same countries from March 7, 2016 to April 14, 2017. We collect fourteen months of longitudinal data of online news from Unfiltered News and web search volume data from Google Trends and build a multiplex network of media attention and public attention in order to study its structural and dynamic properties. Structurally, the media attention and the public attention are both similar and different depending on the resolution of the analysis. For example, we find that 63.2% of the country-specific media and the public pay attention to different countries, but local attention flow patterns, which are measured by network motifs, are very similar. We also show that there are strong regional similarities with both media and public attention that is only disrupted by significantly major worldwide incidents (e.g., Brexit). Using Granger causality, we show that there are a substantial number of countries where media attention and public attention are dissimilar by topical interest. Our findings show that the media and public attention toward specific countries are often at odds, indicating that the public within these countries may be ignoring their country-specific news outlets and seeking other online sources to address their media needs and desires.


title: Theory of nonlinear microwave absorption by interacting two-level systems

abstract: The microwave absorption and noise caused by quantum two-level systems (TLS) dramatically suppress the coherence in Josephson junction qubits that are promising candidates for a quantum information applications. Microwave absorption by TLSs is not clearly understood yet because of the complexity of their interactions leading to the spectral diffusion. Here, the theory of the non-linear absorption in the presence of spectral diffusion is developed using the generalized master equation formalism. The theory predicts that the linear absorption regime holds while a TLS Rabi frequency is smaller than their phase decoherence rate. At higher external fields, a novel non-linear absorption regime is found with the loss tangent inversely proportional to the intensity of the field. The theory can be generalized to acoustic absorption and lower dimensions realized in superconducting qubits.


title: Local Optimality and Generalization Guarantees for the Langevin Algorithm via Empirical Metastability

abstract: We study the detailed path-wise behavior of the discrete-time Langevin algorithm for non-convex Empirical Risk Minimization (ERM) through the lens of metastability, adopting some techniques from Berglund and Gentz (2003. For a particular local optimum of the empirical risk, with an arbitrary initialization, we show that, with high probability, at least one of the following two events will occur: (1) the Langevin trajectory ends up somewhere outside the $\varepsilon$-neighborhood of this particular optimum within a short recurrence time; (2) it enters this $\varepsilon$-neighborhood by the recurrence time and stays there until a potentially exponentially long escape time. We call this phenomenon empirical metastability. This two-timescale characterization aligns nicely with the existing literature in the following two senses. First, the effective recurrence time (i.e., number of iterations multiplied by stepsize) is dimension-independent, and resembles the convergence time of continuous-time deterministic Gradient Descent (GD). However unlike GD, the Langevin algorithm does not require strong conditions on local initialization, and has the possibility of eventually visiting all optima. Second, the scaling of the escape time is consistent with the Eyring-Kramers law, which states that the Langevin scheme will eventually visit all local minima, but it will take an exponentially long time to transit among them. We apply this path-wise concentration result in the context of statistical learning to examine local notions of generalization and optimality.


title: Capacitated Dynamic Programming: Faster Knapsack and Graph Algorithms

abstract: One of the most fundamental problems in Computer Science is the Knapsack problem. Given a set of n items with different weights and values, it asks to pick the most valuable subset whose total weight is below a capacity threshold T. Despite its wide applicability in various areas in Computer Science, Operations Research, and Finance, the best known running time for the problem is O(Tn). The main result of our work is an improved algorithm running in time O(TD), where D is the number of distinct weights. Previously, faster runtimes for Knapsack were only possible when both weights and values are bounded by M and V respectively, running in time O(nMV) [Pisinger'99]. In comparison, our algorithm implies a bound of O(nM^2) without any dependence on V, or O(nV^2) without any dependence on M. Additionally, for the unbounded Knapsack problem, we provide an algorithm running in time O(M^2) or O(V^2). Both our algorithms match recent conditional lower bounds shown for the Knapsack problem [Cygan et al'17, K\"unnemann et al'17]. We also initiate a systematic study of general capacitated dynamic programming, of which Knapsack is a core problem. This problem asks to compute the maximum weight path of length k in an edge- or node-weighted directed acyclic graph. In a graph with m edges, these problems are solvable by dynamic programming in time O(km), and we explore under which conditions the dependence on k can be eliminated. We identify large classes of graphs where this is possible and apply our results to obtain linear time algorithms for the problem of k-sparse Delta-separated sequences. The main technical innovation behind our results is identifying and exploiting concavity that appears in relaxations and subproblems of the tasks we consider.


title: Deep neural decoders for near term fault-tolerant experiments

abstract: Finding efficient decoders for quantum error correcting codes adapted to realistic experimental noise in fault-tolerant devices represents a significant challenge. In this paper we introduce several decoding algorithms complemented by deep neural decoders and apply them to analyze several fault-tolerant error correction protocols such as the surface code as well as Steane and Knill error correction. Our methods require no knowledge of the underlying noise model afflicting the quantum device making them appealing for real-world experiments. Our analysis is based on a full circuit-level noise model. It considers both distance-three and five codes, and is performed near the codes pseudo-threshold regime. Training deep neural decoders in low noise rate regimes appears to be a challenging machine learning endeavour. We provide a detailed description of our neural network architectures and training methodology. We then discuss both the advantages and limitations of deep neural decoders. Lastly, we provide a rigorous analysis of the decoding runtime of trained deep neural decoders and compare our methods with anticipated gate times in future quantum devices. Given the broad applications of our decoding schemes, we believe that the methods presented in this paper could have practical applications for near term fault-tolerant experiments.


title: Tame and Wild Symmetric Special Multiserial Algebras

abstract: We provide a complete classification of all tame and wild symmetric special multiserial algebras in terms of the underlying Brauer configuration. Our classification contains the symmetric special multiserial algebras of finite representation type.


title: Lifting Private Information Retrieval from Two to any Number of Messages

abstract: We study private information retrieval (PIR) on coded data with possibly colluding servers. Devising PIR schemes with optimal download rate in the case of collusion and coded data is still open in general. We provide a lifting operation that can transform what we call one-shot PIR schemes for two messages into schemes for any number of messages. We apply this lifting operation on existing PIR schemes and describe two immediate implications. First, we obtain novel PIR schemes with improved download rate in the case of MDS coded data and server collusion. Second, we provide a simplified description of existing optimal PIR schemes on replicated data as lifted secret sharing based PIR.


title: Efficient Collaborative Multi-Agent Deep Reinforcement Learning for Large-Scale Fleet Management

abstract: Large-scale online ride-sharing platforms have substantially transformed our lives by reallocating transportation resources to alleviate traffic congestion and promote transportation efficiency. An efficient fleet management strategy not only can significantly improve the utilization of transportation resources but also increase the revenue and customer satisfaction. It is a challenging task to design an effective fleet management strategy that can adapt to an environment involving complex dynamics between demand and supply. Existing studies usually work on a simplified problem setting that can hardly capture the complicated stochastic demand-supply variations in high-dimensional space. In this paper we propose to tackle the large-scale fleet management problem using reinforcement learning, and propose a contextual multi-agent reinforcement learning framework including three concrete algorithms to achieve coordination among a large number of agents adaptive to different contexts. We show significant improvements of the proposed framework over state-of-the-art approaches through extensive empirical studies.


title: Dancing twins: stellar hierarchies that formed sequentially?

abstract: This paper attracts attention to the class of resolved triple stars with moderate ratios of inner and outer periods (possibly in a mean motion resonance) and nearly circular, mutually aligned orbits. Moreover, stars in the inner pair are twins with almost identical masses, while the mass sum of the inner pair is comparable to the mass of the outer component. Such systems could be formed either sequentially (inside-out) by disk fragmentation with subsequent accretion and migration or by a cascade hierarchical fragmentation of a rotating cloud. Orbits of the outer and inner subsystems are computed or updated in four such hierarchies: LHS 1070 (GJ 2005, periods 77.6 and 17.25 years), HIP 9497 (80 and 14.4 years), HIP 25240 (1200 and 47.0 years), and HIP 78842 (131 and 10.5 years).


title: Fast 5DOF Needle Tracking in iOCT

abstract: Purpose. Intraoperative Optical Coherence Tomography (iOCT) is an increasingly available imaging technique for ophthalmic microsurgery that provides high-resolution cross-sectional information of the surgical scene. We propose to build on its desirable qualities and present a method for tracking the orientation and location of a surgical needle. Thereby, we enable direct analysis of instrument-tissue interaction directly in OCT space without complex multimodal calibration that would be required with traditional instrument tracking methods. Method. The intersection of the needle with the iOCT scan is detected by a peculiar multi-step ellipse fitting that takes advantage of the directionality of the modality. The geometric modelling allows us to use the ellipse parameters and provide them into a latency aware estimator to infer the 5DOF pose during needle movement. Results. Experiments on phantom data and ex-vivo porcine eyes indicate that the algorithm retains angular precision especially during lateral needle movement and provides a more robust and consistent estimation than baseline methods. Conclusion. Using solely crosssectional iOCT information, we are able to successfully and robustly estimate a 5DOF pose of the instrument in less than 5.5 ms on a CPU.


title: Eigenvalue bounds for Stark operators with complex potentials

abstract: We consider the 3-dimensional Stark operator perturbed by a complex-valued potential. We obtain an estimate for the number of eigenvalues of this operator as well as for the sum of imaginary parts of eigenvalues situated in the upper half-plane.


title: Particle resuspension from complex surfaces: current knowledge and limitations

abstract: This review explores particle resuspension from surfaces due to fluid flows. The objective of this review is to provide a general framework and terminology for particle resuspension while highlighting the future developments needed to deepen our understanding of these phenomena. For that purpose, the manuscript is organized with respect to three mechanisms identified in particle resuspension, namely: the incipient motion of particles (i.e. how particles are set in motion), their migration on the surface (i.e. rolling or sliding motion) and their re-entrainment in the flow (i.e. their motion in the near-wall region after detachment). Recent measurements and simulations of particle resuspension are used to underline our current understanding of each mechanism for particle resuspension. These selected examples also highlight the limitations in the present knowledge of particle resuspension, while providing insights into future developments that need to be addressed. In particular, the paper addresses the issue of adhesion forces between complex surfaces - where more detailed characterizations of adhesion force distributions are needed - and the issue of particle sliding/rolling motion on the surface - which can lead to particles halting/being trapped in regions with high adhesion forces.


title: Toric topology of the complex Grassmann manifolds

abstract: The family of the complex Grassmann manifolds $G_{n,k}$ with a canonical action of the torus $T^n=\mathbb{T}^{n}$ and the analogue of the moment map $\mu : G_{n,k}\to \Delta _{n,k}$ for the hypersimplex $\Delta _{n,k}$, is well known. In this paper we study the structure of the orbit space $G_{n,k}/T^n$ by developing the methods of toric geometry and toric topology. We use a subdivision of $G_{n,k}$ into the strata $W_{\sigma}$ and determine all regular and singular points of the moment map $\mu$, introduce the notion of the admissible polytopes $P_\sigma$ such that $\mu (W_{\sigma}) = \stackrel{\circ}{P_{\sigma}}$ and the notion of the spaces of parameters $F_{\sigma}$, which together describe $W_{\sigma}/T^{n}$ as the product $\stackrel{\circ}{P_{\sigma}} \times F_{\sigma}$. To find the appropriate topology for the set $\cup _{\sigma} \stackrel{\circ}{P_{\sigma}} \times F_{\sigma}$ we introduce the notions of the universal space of parameters $\tilde{\mathcal{F}}$ and the virtual spaces of parameters $\tilde{F}_{\sigma}\subset \tilde{\mathcal{F}}$ such that there exist the projections $\tilde{F}_{\sigma}\to F_{\sigma}$. Hence, we propose a method for the description of the orbit space $G_{n,k}/T^n$. Earlier we proved that the orbit space $G_{4,2}/T^4$, defined by the canonical $T^4$-action of complexity $1$, is homeomorphic to $\partial \Delta _{4,2}\ast \mathbb{C} P^1$. We prove here that the orbit space $G_{5,2}/T^5$, defined by the canonical $T^5$-action of complexity $2$, is homotopy equivalent to the space obtained by attaching the disc $D^8$ to the space $\Sigma ^{4}\mathbb{R} P^2$ by the generator of the group $\pi _{7}(\Sigma ^{4}\mathbb{R} P^2)=\mathbb{Z} _{4}$. In particular, $(G_{5,2}/G_{4,2})/T^5$ is homotopy equivalent to $\partial \Delta _{5,2}\ast \mathbb{C} P^2$. The methods and the results of this paper are fundaments for our theory of $(2l,q)$-manifolds.


title: Reducing Initial Cell-search Latency in mmWave Networks

abstract: Millimeter-wave (mmWave) networks rely on directional transmissions, in both control plane and data plane, to overcome severe path-loss. Nevertheless, the use of narrow beams complicates the initial cell-search procedure where we lack sufficient information for beamforming. In this paper, we investigate the feasibility of random beamforming for cell-search. We develop a stochastic geometry framework to analyze the performance in terms of failure probability and expected latency of cell-search. Meanwhile, we compare our results with the naive, but heavily used, exhaustive search scheme. Numerical results show that, for a given discovery failure probability, random beamforming can substantially reduce the latency of exhaustive search, especially in dense networks. Our work demonstrates that developing complex cell-discovery algorithms may be unnecessary in dense mmWave networks and thus shed new lights on mmWave system design.


title: D-Sempre: Learning Deep Semantic-Preserving Embeddings for User interests-Social Contents Modeling

abstract: Exponential growth of social media consumption demands effective user interests-social contents modeling for more personalized recommendation and social media summarization. However, due to the heterogeneous nature of social contents, traditional approaches lack the ability of capturing the hidden semantic correlations across these multi-modal data, which leads to semantic gaps between social content understanding and user interests. To effectively bridge the semantic gaps, we propose a novel deep learning framework for user interests-social contents modeling. We first mine and parse data, i.e. textual content, visual content, social context and social relation, from heterogeneous social media feeds. Then, we design a two-branch network to map the social contents and users into a same latent space. Particularly, the network is trained by a large margin objective that combines a cross-instance distance constraint with a within-instance semantic-preserving constraint in an end-to- end manner. At last, a Deep Semantic-Preserving Embedding (D-Sempre) is learned, and the ranking results can be given by calculating distances between social contents and users. To demonstrate the effectiveness of D-Sempre in user interests-social contents modeling, we construct a Twitter dataset and conduct extensive experiments on it. As a result, D-Sempre effectively integrates the multi-modal data from heterogeneous social media feeds and captures the hidden semantic correlations between users' interests and social contents.


title: Direct linearisation of the discrete-time two-dimensional Toda lattices

abstract: The discrete-time two-dimensional Toda lattice of $A_\infty$-type is studied within the direct linearisation framework, which allows us to deal with several nonlinear equations in this class simultaneously and to construct more general solutions of these equations. The periodic reductions of this model are also considered, giving rise to the discrete-time two-dimensional Toda lattices of $A_{r-1}^{(1)}$-type for $r\geq 2$ (which amount to the negative flows of members in the discrete Gel'fand--Dikii hierarchy) and their integrability properties.


title: Rescaling nonsmooth optimization using BFGS and Shor updates

abstract: The BFGS quasi-Newton methodology, popular for smooth minimization, has also proved surprisingly effective in nonsmooth optimization. Through a variety of simple examples and computational experiments, we explore how the BFGS matrix update improves the local metric associated with a convex function even in the absence of smoothness and without using a line search. We compare the behavior of the BFGS and Shor r-algorithm updates.


title: DA-GAN: Instance-level Image Translation by Deep Attention Generative Adversarial Networks (with Supplementary Materials)

abstract: Unsupervised image translation, which aims in translating two independent sets of images, is challenging in discovering the correct correspondences without paired data. Existing works build upon Generative Adversarial Network (GAN) such that the distribution of the translated images are indistinguishable from the distribution of the target set. However, such set-level constraints cannot learn the instance-level correspondences (e.g. aligned semantic parts in object configuration task). This limitation often results in false positives (e.g. geometric or semantic artifacts), and further leads to mode collapse problem. To address the above issues, we propose a novel framework for instance-level image translation by Deep Attention GAN (DA-GAN). Such a design enables DA-GAN to decompose the task of translating samples from two sets into translating instances in a highly-structured latent space. Specifically, we jointly learn a deep attention encoder, and the instancelevel correspondences could be consequently discovered through attending on the learned instance pairs. Therefore, the constraints could be exploited on both set-level and instance-level. Comparisons against several state-ofthe- arts demonstrate the superiority of our approach, and the broad application capability, e.g, pose morphing, data augmentation, etc., pushes the margin of domain translation problem.


title: Bayesian Uncertainty Estimation for Batch Normalized Deep Networks

abstract: We show that training a deep network using batch normalization is equivalent to approximate inference in Bayesian models. We further demonstrate that this finding allows us to make meaningful estimates of the model uncertainty using conventional architectures, without modifications to the network or the training procedure. Our approach is thoroughly validated by measuring the quality of uncertainty in a series of empirical experiments on different tasks. It outperforms baselines with strong statistical significance, and displays competitive performance with recent Bayesian approaches.


title: Optimal allocation of attentional resource to multiple items with unequal relevance

abstract: In natural perception, different items (objects) in a scene are rarely equally relevant to the observer. The brain improves performance by directing attention to the most relevant items, for example the ones most likely to be probed. For a general set of probing probabilities, it is not known how attentional resources should be allocated to maximize performance. Here, we investigate the optimal strategy for allocating a fixed resource budget E among N items when on each trial, only one item gets probed. We develop an efficient algorithm that, for any concave utility function, reduces the N-dimensional problem to a set of N one-dimensional problems that the brain could plausibly solve. We find that the intuitive strategy of allocating resource in proportion to the probing probabilities is in general not optimal. In particular, in some tasks, if resource is low, the optimal strategy involves allocating zero resource to items with a nonzero probability of being probed. Our work opens the door to normatively guided studies of attentional allocation.


title: Circles and crossing planar compact convex sets

abstract: Let $K_0$ be a compact convex subset of the plane $\mathbb R^2$, and assume that whenever $K_1\subseteq \mathbb R^2$ is congruent to $K_0$, then $K_0$ and $K_1$ are not crossing in a natural sense due to L. Fejes-T\'oth. A theorem of L. Fejes-T\'oth from 1967 states that the assumption above holds for $K_0$ if and only if $K_0$ is a disk. In a paper appeared in 2017, the present author introduced a new concept of crossing, and proved that L. Fejes-T\'oth's theorem remains true if the old concept is replaced by the new one. Our purpose is to describe the hierarchy among several variants of the new concepts and the old concept of crossing. In particular, we prove that each variant of the new concept of crossing is more restrictive then the old one. Therefore, L. Fejes-T\'oth's theorem from 1967 becomes an immediate consequence of the 2017 characterization of circles but not conversely. Finally, a mini-survey shows that this purely geometric paper has precursor in combinatorics and, mainly, in lattice theory.


title: A Generative Modeling Approach to Limited Channel ECG Classification

abstract: Processing temporal sequences is central to a variety of applications in health care, and in particular multi-channel Electrocardiogram (ECG) is a highly prevalent diagnostic modality that relies on robust sequence modeling. While Recurrent Neural Networks (RNNs) have led to significant advances in automated diagnosis with time-series data, they perform poorly when models are trained using a limited set of channels. A crucial limitation of existing solutions is that they rely solely on discriminative models, which tend to generalize poorly in such scenarios. In order to combat this limitation, we develop a generative modeling approach to limited channel ECG classification. This approach first uses a Seq2Seq model to implicitly generate the missing channel information, and then uses the latent representation to perform the actual supervisory task. This decoupling enables the use of unsupervised data and also provides highly robust metric spaces for subsequent discriminative learning. Our experiments with the Physionet dataset clearly evidence the effectiveness of our approach over standard RNNs in disease prediction.


title: Structured Label Inference for Visual Understanding

abstract: Visual data such as images and videos contain a rich source of structured semantic labels as well as a wide range of interacting components. Visual content could be assigned with fine-grained labels describing major components, coarse-grained labels depicting high level abstractions, or a set of labels revealing attributes. Such categorization over different, interacting layers of labels evinces the potential for a graph-based encoding of label information. In this paper, we exploit this rich structure for performing graph-based inference in label space for a number of tasks: multi-label image and video classification and action detection in untrimmed videos. We consider the use of the Bidirectional Inference Neural Network (BINN) and Structured Inference Neural Network (SINN) for performing graph-based inference in label space and propose a Long Short-Term Memory (LSTM) based extension for exploiting activity progression on untrimmed videos. The methods were evaluated on (i) the Animal with Attributes (AwA), Scene Understanding (SUN) and NUS-WIDE datasets for multi-label image classification, (ii) the first two releases of the YouTube-8M large scale dataset for multi-label video classification, and (iii) the THUMOS'14 and MultiTHUMOS video datasets for action detection. Our results demonstrate the effectiveness of structured label inference in these challenging tasks, achieving significant improvements against baselines.


title: Embedding distance graphs in finite field vector spaces

abstract: We show that large subsets of vector spaces over finite fields determine certain point configurations with prescribed distance structure. More specifically, we consider the complete graph with vertices as the points of $A \subseteq \mathbf{F}_q^d$ and edges assigned the algebraic distance between pairs of vertices. We prove nontrivial results on locating specified subgraphs of maximum vertex degree at most $t$ in dimensions $d \geq 2t$.


title: Octupole deformation in neutron-rich actinides and superheavy nuclei and the role of nodal structure of single-particle wavefunctions in extremely deformed structures of light nuclei

abstract: Octupole deformed shapes in neutron-rich actinides and superheavy nuclei as well as extremely deformed shapes of the N~Z light nuclei have been investigated within the framework of covariant density functional theory. We confirmed the presence of new region of octupole deformation in neutron-rich actinides with the center around Z~96, N~196 but our calculations do not predict octupole deformation in the ground states of superheavy Z~108 nuclei. As exemplified by the study of 36Ar, the nodal structure of the wavefunction of occupied single-particle orbitals in extremely deformed structures allows to understand the formation of the alpha-clusters in very light nuclei, the suppression of the alpha-clusterization with the increase of mass number, the formation of ellipsoidal mean-field type structures and nuclear molecules.


title: Heuristic Based Induction of Answer Set Programs: From Default theories to combinatorial problems

abstract: Significant research has been conducted in recent years to extend Inductive Logic Programming (ILP) methods to induce Answer Set Programs (ASP). These methods perform an exhaustive search for the correct hypothesis by encoding an ILP problem instance as an ASP program. Exhaustive search, however, results in loss of scalability. In addition, the language bias employed in these methods is overly restrictive too. In this paper we extend our previous work on learning stratified answer set programs that have a single stable model to learning arbitrary (i.e., non-stratified) ones with multiple stable models. Our extended algorithm is a greedy FOIL-like algorithm, capable of inducing non-monotonic logic programs, examples of which includes programs for combinatorial problems such as graph-coloring and N-queens. To the best of our knowledge, this is the first heuristic-based ILP algorithm to induce answer set programs with multiple stable models.


title: Guaranteed Recovery of One-Hidden-Layer Neural Networks via Cross Entropy

abstract: We study model recovery for data classification, where the training labels are generated from a one-hidden-layer neural network with sigmoid activations, also known as a single-layer feedforward network, and the goal is to recover the weights of the neural network. We consider two network models, the fully-connected network (FCN) and the non-overlapping convolutional neural network (CNN). We prove that with Gaussian inputs, the empirical risk based on cross entropy exhibits strong convexity and smoothness {\em uniformly} in a local neighborhood of the ground truth, as soon as the sample complexity is sufficiently large. This implies that if initialized in this neighborhood, gradient descent converges linearly to a critical point that is provably close to the ground truth. Furthermore, we show such an initialization can be obtained via the tensor method. This establishes the global convergence guarantee for empirical risk minimization using cross entropy via gradient descent for learning one-hidden-layer neural networks, at the near-optimal sample and computational complexity with respect to the network input dimension without unrealistic assumptions such as requiring a fresh set of samples at each iteration.


title: Robust Fitting in Computer Vision: Easy or Hard?

abstract: Robust model fitting plays a vital role in computer vision, and research into algorithms for robust fitting continues to be active. Arguably the most popular paradigm for robust fitting in computer vision is consensus maximisation, which strives to find the model parameters that maximise the number of inliers. Despite the significant developments in algorithms for consensus maximisation, there has been a lack of fundamental analysis of the problem in the computer vision literature. In particular, whether consensus maximisation is "tractable" remains a question that has not been rigorously dealt with, thus making it difficult to assess and compare the performance of proposed algorithms, relative to what is theoretically achievable. To shed light on these issues, we present several computational hardness results for consensus maximisation. Our results underline the fundamental intractability of the problem, and resolve several ambiguities existing in the literature.


title: The class of a fibre in Noncommutative Geometry

abstract: This paper studies the K-homology of a crossed product of a discrete group acting smoothly on a manifold, with a better understanding of the noncommutative geometry of the crossed-product as the primary goal, and the Baum-Connes apparatus as the main tool. Examples suggest that the correct notion of the `Dirac class' of such a noncommutative space is the image under the equivalence determined by Baum-Connes of the fibre of the fibration of the Borel space associated to the action and a smooth model for the classifying space of the group. We give a systematic study of such fibre, or `Dirac classes,' with applications to the construction of interesting spectral triples and computation of their K-theory functionals, and we prove in particular that both the well-known deformation of the Dolbeault operator on the noncommutative torus, and the class of the boundary extension of a hyperbolic group, are both Dirac classes in this sense and therefore can be treated topologically in the same way.


title: Recurrent Binary Embedding for GPU-Enabled Exhaustive Retrieval from Billion-Scale Semantic Vectors

abstract: Rapid advances in GPU hardware and multiple areas of Deep Learning open up a new opportunity for billion-scale information retrieval with exhaustive search. Building on top of the powerful concept of semantic learning, this paper proposes a Recurrent Binary Embedding (RBE) model that learns compact representations for real-time retrieval. The model has the unique ability to refine a base binary vector by progressively adding binary residual vectors to meet the desired accuracy. The refined vector enables efficient implementation of exhaustive similarity computation with bit-wise operations, followed by a near- lossless k-NN selection algorithm, also proposed in this paper. The proposed algorithms are integrated into an end-to-end multi-GPU system that retrieves thousands of top items from over a billion candidates in real-time. The RBE model and the retrieval system were evaluated with data from a major paid search engine. When measured against the state-of-the-art model for binary representation and the full precision model for semantic embedding, RBE significantly outperformed the former, and filled in over 80% of the AUC gap in-between. Experiments comparing with our production retrieval system also demonstrated superior performance. While the primary focus of this paper is to build RBE based on a particular class of semantic models, generalizing to other types is straightforward, as exemplified by two different models at the end of the paper.


title: Memorize or generalize? Searching for a compositional RNN in a haystack

abstract: Neural networks are very powerful learning systems, but they do not readily generalize from one task to the other. This is partly due to the fact that they do not learn in a compositional way, that is, by discovering skills that are shared by different tasks, and recombining them to solve new problems. In this paper, we explore the compositional generalization capabilities of recurrent neural networks (RNNs). We first propose the lookup table composition domain as a simple setup to test compositional behaviour and show that it is theoretically possible for a standard RNN to learn to behave compositionally in this domain when trained with standard gradient descent and provided with additional supervision. We then remove this additional supervision and perform a search over a large number of model initializations to investigate the proportion of RNNs that can still converge to a compositional solution. We discover that a small but non-negligible proportion of RNNs do reach partial compositional solutions even without special architectural constraints. This suggests that a combination of gradient descent and evolutionary strategies directly favouring the minority models that developed more compositional approaches might suffice to lead standard RNNs towards compositional solutions.


title: Dose evaluation of fast synthetic-CT generation using a generative adversarial network for general pelvis MR-only radiotherapy

abstract: To enable magnetic resonance (MR)-only radiotherapy and facilitate modelling of radiation attenuation in humans, synthetic-CT (sCT) images need to be generated. Considering the application of MR-guided radiotherapy and online adaptive replanning, sCT generation should occur within minutes. This work aims at assessing whether an existing deep learning network can rapidly generate sCT images to be used for accurate MR-based dose calculations in the entire pelvis. A study was conducted on data of 91 patients with prostate, rectal and cervical cancer who underwent external beam radiotherapy acquiring both CT and MRI for patients' simulation. Dixon reconstructed water, fat and in-phase images obtained from a conventional dual gradient-recalled echo sequence were used to generate sCT images. A conditional generative adversarial network (cGAN) was trained in a paired fashion on 2D transverse slices of 32 prostate cancer patients. The trained network was tested on the remaining patients to generate sCT images. For 30 patients in the test set, dose recalculations of the clinical plan were performed on sCT images. Dose distributions were evaluated comparing voxel-based dose differences, gamma and dose-volume histogram (DVH) analysis. The sCT generation required 5.6 s and 21 s for a single patient volume on a GPU and CPU, respectively. On average, sCT images resulted in a higher dose to the target of maximum 0.3%. Results suggest that accurate MR-based dose calculation using sCT images generated with a cGAN trained on prostate cancer patients is feasible for the entire pelvis. The sCT generation was sufficiently fast to be integrated into an MR-guided radiotherapy workflow.


title: Active fluids at circular boundaries: Swim pressure and anomalous droplet ripening

abstract: We investigate the swim pressure exerted by non-chiral and chiral active particles on convex or concave circular boundaries. Active particles are modeled as non-interacting and non-aligning self-propelled Brownian particles. The convex and concave circular boundaries are used as models representing a fixed inclusion immersed in an active bath and a cavity (or container) enclosing the active particles, respectively. We first present a detailed analysis of the role of convex versus concave boundary curvature and of the chirality of active particles on their spatial distribution, chirality-induced currents, and the swim pressure they exert on the bounding surfaces. The results will then be used to predict the mechanical equilibria of suspended fluid enclosures (generically referred to as 'droplets') in a bulk with active particles being present either inside the bulk fluid or within the suspended droplets. We show that, while droplets containing active particles and suspended in a normal bulk behave in accordance with standard capillary paradigms, those containing a normal fluid exhibit anomalous behaviors when suspended in an active bulk. In the latter case, the excess swim pressure results in non-monotonic dependence of the inside droplet pressure on the droplet radius. As a result, we find a regime of anomalous capillarity for a single droplet, where the inside droplet pressure increases upon increasing the droplet size. In the case of two interconnected droplets, we show that mechanical equilibrium can occur also when they have different sizes. We further identify a regime of anomalous ripening, where two unequal-sized droplets can reach a final state of equal sizes upon interconnection, in stark contrast with the standard Ostwald ripening phenomenon, implying shrinkage of the smaller droplet in favor of the larger one.

categories: cond-mat.soft cond-mat.stat-mech physics.bio-ph physics.chem-ph


title: A model for a network of conveyor belts with discontinuous speed and capacity

abstract: We introduce a macroscopic model for a network of conveyor belts with various speeds and capacities. In a different way from traffic flow models, the product densities are forced to move with a constant velocity unless they reach a maximal capacity and start to queue. This kind of dynamics is governed by scalar conservation laws consisting of a discontinuous flux function. We define appropriate coupling conditions to get well-posed solutions at intersections and provide a detailed description of the solution. Some numerical simulations are presented to illustrate and confirm the theoretical results for different network configurations.


title: Solitons and rogue waves in spinor Bose-Einstein condensates

abstract: We present a general classification of one-soliton solutions as well as novel families of rogue-wave solutions for $F=1$ spinor Bose-Einstein condensates (BECs). These solutions are obtained from the inverse scattering transform for a focusing matrix nonlinear Schr\"odinger equation which models condensates in the case of attractive mean field interactions and ferromagnetic spin-exchange interactions. In particular, we show that, when no background is present, all one-soliton solutions are reducible via unitary transformations to a combination of oppositely-polarized solitonic solutions of single-component BECs. On the other hand, we show that, when a non-zero background is present, not all matrix one-soliton solutions are reducible to a simple combination of scalar solutions. We show that some solitons are topological ones and others are dark-bright solitons. Finally, by taking suitable limits of all the solutions on a non-zero background we also obtain three families of rogue-wave (i.e., rational) solutions, two of which are novel to the best of our knowledge.


title: Online convex optimization for cumulative constraints

abstract: We propose the algorithms for online convex optimization which lead to cumulative squared constraint violations of the form $\sum\limits_{t=1}^T\big([g(x_t)]_+\big)^2=O(T^{1-\beta})$, where $\beta\in(0,1)$. Previous literature has focused on long-term constraints of the form $\sum\limits_{t=1}^Tg(x_t)$. There, strictly feasible solutions can cancel out the effects of violated constraints. In contrast, the new form heavily penalizes large constraint violations and cancellation effects cannot occur. Furthermore, useful bounds on the single step constraint violation $[g(x_t)]_+$ are derived. For convex objectives, our regret bounds generalize existing bounds, and for strongly convex objectives we give improved regret bounds. In numerical experiments, we show that our algorithm closely follows the constraint boundary leading to low cumulative violation.


title: Examples of tropical-to-Lagrangian correspondence

abstract: The paper associates Lagrangian submanifolds in symplectic toric varieties to certain tropical curves inside the convex polyhedral domains of $\R^n$ that appear as the images of the moment map of the toric varieties. We pay a particular attention to the case $n=2$, where we reprove Givental's theorem on Lagrangian embeddability of non-oriented surfaces to $\C^2$, as well as to the case $n=3$, where we see appearance of the graph 3-manifolds studied by Waldhausen as Lagrangian submanifolds. In particular, rational tropical curves in $\R^3$ produce 3-dimensional rational homology spheres. The order of their first homology groups is determined by the multiplicity of tropical curves in the corresponding enumerative problems.


title: A Closed-form Solution to Photorealistic Image Stylization

abstract: Photorealistic image stylization concerns transferring style of a reference photo to a content photo with the constraint that the stylized photo should remain photorealistic. While several photorealistic image stylization methods exist, they tend to generate spatially inconsistent stylizations with noticeable artifacts. In this paper, we propose a method to address these issues. The proposed method consists of a stylization step and a smoothing step. While the stylization step transfers the style of the reference photo to the content photo, the smoothing step ensures spatially consistent stylizations. Each of the steps has a closed-form solution and can be computed efficiently. We conduct extensive experimental validations. The results show that the proposed method generates photorealistic stylization outputs that are more preferred by human subjects as compared to those by the competing methods while running much faster. Source code and additional results are available at https://github.com/NVIDIA/FastPhotoStyle .


title: A multivariate Berry--Esseen theorem with explicit constants

abstract: We provide a Lyapunov type bound in the multivariate central limit theorem for sums of independent, but not necessarily identically distributed random vectors. The error in the normal approximation is estimated for certain classes of sets, which include the class of measurable convex sets. The error bound is stated with explicit constants. The result is proved by means of Stein's method. In addition, we improve the constant in the bound of the Gaussian perimeter of convex sets.


title: Simultaneous Modeling of Multiple Complications for Risk Profiling in Diabetes Care

abstract: Type 2 diabetes mellitus (T2DM) is a chronic disease that often results in multiple complications. Risk prediction and profiling of T2DM complications is critical for healthcare professionals to design personalized treatment plans for patients in diabetes care for improved outcomes. In this paper, we study the risk of developing complications after the initial T2DM diagnosis from longitudinal patient records. We propose a novel multi-task learning approach to simultaneously model multiple complications where each task corresponds to the risk modeling of one complication. Specifically, the proposed method strategically captures the relationships (1) between the risks of multiple T2DM complications, (2) between the different risk factors, and (3) between the risk factor selection patterns. The method uses coefficient shrinkage to identify an informative subset of risk factors from high-dimensional data, and uses a hierarchical Bayesian framework to allow domain knowledge to be incorporated as priors. The proposed method is favorable for healthcare applications because in additional to improved prediction performance, relationships among the different risks and risk factors are also identified. Extensive experimental results on a large electronic medical claims database show that the proposed method outperforms state-of-the-art models by a significant margin. Furthermore, we show that the risk associations learned and the risk factors identified lead to meaningful clinical insights.


title: On the sheaf of smooth forms on Lie algebroids over triangulated spaces

abstract: Cohomology of a compatible family of Lie algebroids defined on a family of transverse manifolds is defined. A sheaf of differential forms on a compatible family of Lie algebroids defined over regular open subsets of a simplicial complex is constructed. It is proved that sheaf is fine.


title: An Efficient Local Search for the Minimum Independent Dominating Set Problem

abstract: In the present paper, we propose an efficient local search for the minimum independent dominating set problem. We consider a local search that uses $k$-swap as the neighborhood operation. Given a feasible solution $S$, it is the operation of obtaining another feasible solution by dropping exactly $k$ vertices from $S$ and then by adding any number of vertices to it. We show that, when $k=2$, (resp., $k=3$ and a given solution is minimal with respect to 2-swap), we can find an improved solution in the neighborhood or conclude that no such solution exists in $O(n\Delta)$ (resp., $O(n\Delta^3)$) time, where $n$ denotes the number of vertices and $\Delta$ denotes the maximum degree. We develop a metaheuristic algorithm that repeats the proposed local search and the plateau search iteratively, where the plateau search examines solutions of the same size as the current solution that are obtainable by exchanging a solution vertex and a non-solution vertex. The algorithm is so effective that, among 80 DIMACS graphs, it updates the best-known solution size for five graphs and performs as well as existing methods for the remaining graphs.


title: Optimal leader selection and demotion in leader-follower multi-agent systems

abstract: We consider leader-follower multi-agent systems that have many leaders, defined on any connected weighted undirected graphs, and address the leader selection and demotion problems. The leader selection problem is formulated as a minimization problem for the $H^2$ norm of the difference between the transfer functions of the original and new agent systems, under the assumption that the leader agents to be demoted are fixed. The leader demotion problem is that of finding optimal leader agents to be demoted, and is formulated using the global optimal solution to the leader selection problem. We prove that a global optimal solution to the leader selection problem is the set of the original leader agents except for those that are demoted to followers. To this end, we relax the original problem into a differentiable problem. Then, by calculating the gradient and Hessian of the objective function of the relaxed problem, we prove that the function is convex. It is shown that zero points of the gradient are global optimal solutions to the leader selection problem, which is a finite combinatorial optimization problem. Furthermore, we prove that any set of leader agents to be demoted subject to a fixed number of elements is a solution to the leader demotion problem. By combining the solutions to the leader selection and demotion problems, we prove that if we choose new leader agents from the original ones except for those specified by the set of leader agents to be demoted, then the relative $H^2$ error between the transfer functions of the original and new agent systems is completely determined by the numbers of original leader agents and leader agents that are demoted to follower agents. That is, we reveal that the relative $H^2$ error does not depend on the number of agents on the graph. Finally, we verify the solutions using a simple example.


title: Accelerated Primal-Dual Policy Optimization for Safe Reinforcement Learning

abstract: Constrained Markov Decision Process (CMDP) is a natural framework for reinforcement learning tasks with safety constraints, where agents learn a policy that maximizes the long-term reward while satisfying the constraints on the long-term cost. A canonical approach for solving CMDPs is the primal-dual method which updates parameters in primal and dual spaces in turn. Existing methods for CMDPs only use on-policy data for dual updates, which results in sample inefficiency and slow convergence. In this paper, we propose a policy search method for CMDPs called Accelerated Primal-Dual Optimization (APDO), which incorporates an off-policy trained dual variable in the dual update procedure while updating the policy in primal space with on-policy likelihood ratio gradient. Experimental results on a simulated robot locomotion task show that APDO achieves better sample efficiency and faster convergence than state-of-the-art approaches for CMDPs.


title: Finite-Length Construction of High Performance Spatially-Coupled Codes via Optimized Partitioning and Lifting

abstract: Spatially-coupled (SC) codes are a family of graph-based codes that have attracted significant attention thanks to their capacity approaching performance and low decoding latency. An SC code is constructed by partitioning an underlying block code into a number of components and coupling their copies together. In this paper, we first introduce a general approach for the enumeration of detrimental combinatorial objects in the graph of finite-length SC codes. Our approach is general in the sense that it effectively works for SC codes with various column weights and memories. Next, we present a two-stage framework for the construction of high-performance binary SC codes optimized for additive white Gaussian noise channel; we aim at minimizing the number of detrimental combinatorial objects in the error floor regime. In the first stage, we deploy a novel partitioning scheme, called the optimal overlap partitioning, to produce optimal partitioning corresponding to the smallest number of detrimental objects. In the second stage, we apply a new circulant power optimizer to further reduce the number of detrimental objects in the lifted graph. An SC code constructed by our new framework has nearly 5 orders of magnitudes error floor performance improvement compared to the uncoupled setting.


title: Optimal Graph Laplacian

abstract: This paper provides a construction method of the nearest graph Laplacian to a matrix identified from measurement data of graph Laplacian dynamics that include biochemical systems, synchronization systems, and multi-agent systems. We consider the case where the network structure, i.e., the connection relationship of edges of a given graph, is known. A problem of finding the nearest graph Laplacian is formulated as a convex optimization problem. Thus, our problem can be solved using interior point methods. However, the complexity of each iteration by interior point methods is $O(n^6)$, where $n$ is the number of nodes of the network. That is, if $n$ is large, interior point methods cannot solve our problem within a practical time. To resolve this issue, we propose a simple and efficient algorithm with the calculation complexity $O(n^2)$. Simulation experiments demonstrate that our method is useful to perform data-driven modeling of graph Laplacian dynamics.


title: Committee Scoring Rules: Axiomatic Characterization and Hierarchy

abstract: Committee scoring voting rules are multiwinner analogues of positional scoring rules which constitute an important subclass of single-winner voting rules. We identify several natural subclasses of committee scoring rules, namely, weakly separable, representation-focused, top-$k$-counting, OWA-based, and decomposable rules. We characterize SNTV, Bloc, and $k$-Approval Chamberlin--Courant as the only nontrivial rules in pairwise intersections of these classes. We provide some axiomatic characterizations for these classes, where monotonicity properties appear to be especially useful. The class of decomposable rules is new to the literature. We show that it strictly contains the class of OWA-based rules and describe some of the applications of decomposable rules.


title: A positive fraction mutually avoiding sets theorem

abstract: Two sets $A$ and $B$ of points in the plane are \emph{mutually avoiding} if no line generated by any two points in $A$ intersects the convex hull of $B$, and vice versa. In 1994, Aronov, Erd\H os, Goddard, Kleitman, Klugerman, Pach, and Schulman showed that every set of $n$ points in the plane in general position contains a pair of mutually avoiding sets each of size at least $\sqrt{n/12}$. As a corollary, their result implies that for every set of $n$ points in the plane in general position one can find at least $\sqrt{n/12}$ segments, each joining two of the points, such that these segments are pairwise crossing. In this note, we prove a fractional version of their theorem: for every $k > 0$ there is a constant $\varepsilon_k > 0$ such that any sufficiently large point set $P$ in the plane contains $2k$ subsets $A_1,\ldots, A_{k},B_1,\ldots, B_k$, each of size at least $\varepsilon_k|P|$, such that every pair of sets $A = \{a_1,\ldots, a_k\}$ and $B = \{b_1,\ldots, b_k\}$, with $a_i \in A_i$ and $b_i \in B_i$, are mutually avoiding. Moreover, we show that $\varepsilon_k = \Omega(1/k^4)$. Similar results are obtained in higher dimensions


title: Robust Estimation via Robust Gradient Estimation

abstract: We provide a new computationally-efficient class of estimators for risk minimization. We show that these estimators are robust for general statistical models: in the classical Huber epsilon-contamination model and in heavy-tailed settings. Our workhorse is a novel robust variant of gradient descent, and we provide conditions under which our gradient descent variant provides accurate estimators in a general convex risk minimization problem. We provide specific consequences of our theory for linear regression, logistic regression and for estimation of the canonical parameters in an exponential family. These results provide some of the first computationally tractable and provably robust estimators for these canonical statistical models. Finally, we study the empirical performance of our proposed methods on synthetic and real datasets, and find that our methods convincingly outperform a variety of baselines.


title: Attractor Cosmology from non-minimally Coupled Gravity

abstract: By using a bottom-up reconstruction technique for non-minimally coupled scalar-tensor theories, we realize the Einstein frame attractor cosmologies in the $\Omega (\phi)$-Jordan frame. For our approach, what is needed for the reconstruction method to work is the functional form of the non-minimal coupling $\Omega(\phi)$ and of the scalar-to-tensor ratio, and also the assumption of the slow-roll inflation in the $\Omega (\phi)$-Jordan frame. By appropriately choosing the scalar-to-tensor ratio, we demonstrate that the observational indices of the attractor cosmologies can be realized directly in the $\Omega (\phi)$-Jordan frame. We investigate the special conditions that are required to hold true in for this realization to occur, and we provide the analytic form of the potential in the $\Omega (\phi)$-Jordan frame. Also, by performing a conformal transformation, we find the corresponding Einstein frame canonical scalar-tensor theory, and we calculate in detail the corresponding observational indices. The result indicates that although the spectral index of the primordial curvature perturbations is the same in the Jordan and Einstein frames, at leading order in the $e$-foldings number, the scalar-to-tensor ratio differs. We discuss the possible reasons behind this discrepancy, and we argue that the difference is due to some approximation we performed to the functional form of the potential in the Einstein frame, in order to obtain analytical results, and also due to the difference in the definition of the $e$-foldings number in the two frames, which is also pointed out in the related literature. Finally, we find the $F(R)$ gravity corresponding to the Einstein frame canonical scalar-tensor theory.


title: Poisson geometry and representations of PI 4-dimensional Sklyanin algebras

abstract: Take S to be a 4-dimensional Sklyanin (elliptic) algebra that is module-finite over its center Z; thus, S is PI. Our first result is the construction of a Poisson Z-order structure on S such that the induced Poisson bracket on Z is non-vanishing. We also provide the explicit Jacobian structure of this bracket, leading to a description of the symplectic core decomposition of the maximal spectrum Y of Z. We then classify the irreducible representations of S by combining (1) the geometry of the Poisson order structures, with (2) algebro-geometric methods for the elliptic curve attached to S, along with (3) representation-theoretic methods using line and fat point modules of S. Along the way, we improve results of Smith and Tate obtaining a description the singular locus of Y for such S. The classification results for irreducible representations are in turn used to determine the zero sets of the discriminants ideals of these algebras S.


title: Tiny SSD: A Tiny Single-shot Detection Deep Convolutional Neural Network for Real-time Embedded Object Detection

abstract: Object detection is a major challenge in computer vision, involving both object classification and object localization within a scene. While deep neural networks have been shown in recent years to yield very powerful techniques for tackling the challenge of object detection, one of the biggest challenges with enabling such object detection networks for widespread deployment on embedded devices is high computational and memory requirements. Recently, there has been an increasing focus in exploring small deep neural network architectures for object detection that are more suitable for embedded devices, such as Tiny YOLO and SqueezeDet. Inspired by the efficiency of the Fire microarchitecture introduced in SqueezeNet and the object detection performance of the single-shot detection macroarchitecture introduced in SSD, this paper introduces Tiny SSD, a single-shot detection deep convolutional neural network for real-time embedded object detection that is composed of a highly optimized, non-uniform Fire sub-network stack and a non-uniform sub-network stack of highly optimized SSD-based auxiliary convolutional feature layers designed specifically to minimize model size while maintaining object detection performance. The resulting Tiny SSD possess a model size of 2.3MB (~26X smaller than Tiny YOLO) while still achieving an mAP of 61.3% on VOC 2007 (~4.2% higher than Tiny YOLO). These experimental results show that very small deep neural network architectures can be designed for real-time object detection that are well-suited for embedded scenarios.


title: Local field theory construction of Very Special Conformal Symmetry

abstract: Cohen and Glashow argued that very special conformal field theories of a particular kind (i.e. with HOM(2) or SIM(2) invariance) cannot be constructed within the framework of local field theories. We, however, show examples of local construction by using non-linear realization. We further construct linear realization from the topological twist at the cost of unitarity. To demonstrate the ubiquity of our idea, we also present corresponding holographic models.


title: On the exact solvability of the anisotropic central spin model: An operator approach

abstract: Using an operator approach based on a commutator scheme that has been previously applied to Richardson's reduced BCS model and the inhomogeneous Dicke model, we obtain general exact solvability requirements for an anisotropic central spin model with $XXZ$-type hyperfine coupling between the central spin and the spin bath, without any prior knowledge of integrability of the model. We outline the basic steps of the usage of the operator approach, and pedagogically summarize them into two \emph{Lemmas} and two \emph{Constraints}. Through a step-by-step construction of the eigen-problem, we show that the condition $g'^2_j-g_j^2=c$ naturally arises for the model to be exactly solvable, where $c$ is a constant independent of the bath-spin index $j$, and $\{g_j\}$ and $\{g'_j\}$ are the longitudinal and transverse hyperfine interactions, respectively. The obtained conditions and the resulting Bethe ansatz equations are consistent with that in previous literature.


title: Trace Ideals and the Gorenstein Property

abstract: Let R be a local Noetherian commutative ring. We prove that R is an Artinian Gorenstein ring if and only if every ideal in R is a trace ideal. We discuss when the trace ideal of a module coincides with its double annihilator.


title: Attributed Hierarchical Port Graphs and Applications

abstract: We present attributed hierarchical port graphs (AHP) as an extension of port graphs that aims at facilitating the design of modular port graph models for complex systems. AHP consist of a number of interconnected layers, where each layer defines a port graph whose nodes may link to layers further down the hierarchy; attributes are used to store user-defined data as well as visualisation and run-time system parameters. We also generalise the notion of strategic port graph rewriting (a particular kind of graph transformation system, where port graph rewriting rules are controlled by user-defined strategies) to deal with AHP following the Single Push-out approach. We outline examples of application in two areas: functional programming and financial modelling.


title: A Method to Translate Order-Sorted Algebras to Many-Sorted Algebras

abstract: Order-sorted algebras and many sorted algebras exist in a long history with many different implementations and applications. A lot of language specifications have been defined in order-sorted algebra frameworks such as the language specifications in K (an order-sorted algebra framework). The biggest problem in a lot of the order-sorted algebra frameworks is that even if they might allow developers to write programs and language specifications easily, but they do not have a large set of tools to provide reasoning infrastructures to reason about the specifications built on the frameworks, which are very common in some many-sorted algebra framework such as Isabelle/HOL, Coq and FDR. This fact brings us the necessity to marry the worlds of order-sorted algebras and many sorted algebras. In this paper, we propose an algorithm to translate a strictly sensible order-sorted algebra to a many-sorted one in a restricted domain by requiring the order-sorted algebra to be strictly sensible. The key idea of the translation is to add an equivalence relation called core equality to the translated many-sorted algebras. By defining this relation, we reduce the complexity of translating a strictly sensible order-sorted algebra to a many-sorted one, make the translated many-sorted algebra equations only increasing by a very small amount of new equations, and keep the number of rewrite rules in the algebra in the same amount. We then prove the order-sorted algebra and its translated many-sorted algebra are bisimilar. To the best of our knowledge, our translation and bisimilar proof is the first attempt in translating and relating an order-sorted algebra with a many-sorted one in a way that keeps the size of the translated many-sorted algebra relatively small.


title: Transforming Proof Tableaux of Hoare Logic into Inference Sequences of Rewriting Induction

abstract: A proof tableau of Hoare logic is an annotated program with pre- and post-conditions, which corresponds to an inference tree of Hoare logic. In this paper, we show that a proof tableau for partial correctness can be transformed into an inference sequence of rewriting induction for constrained rewriting. We also show that the resulting sequence is a valid proof for an inductive theorem corresponding to the Hoare triple if the constrained rewriting system obtained from the program is terminating. Such a valid proof with termination of the constrained rewriting system implies total correctness of the program w.r.t. the Hoare triple. The transformation enables us to apply techniques for proving termination of constrained rewriting to proving total correctness of programs together with proof tableaux for partial correctness.


title: Efficient Implementation of Evaluation Strategies via Token-Guided Graph Rewriting

abstract: In implementing evaluation strategies of the lambda-calculus, both correctness and efficiency of implementation are valid concerns. While the notion of correctness is determined by the evaluation strategy, regarding efficiency there is a larger design space that can be explored, in particular the trade-off between space versus time efficiency. We contributed to the study of this trade-off by the introduction of an abstract machine for call-by-need, inspired by Girard's Geometry of Interaction, a machine combining token passing and graph rewriting. This work presents an extension of the machine, to additionally accommodate left-to-right and right-to-left call-by-value strategies. We show soundness and completeness of the extended machine with respect to each of the call-by-need and two call-by-value strategies. Analysing time cost of its execution classifies the machine as "efficient" in Accattoli's taxonomy of abstract machines.


title: Reduced Dependency Spaces for Existential Parameterised Boolean Equation Systems

abstract: A parameterised Boolean equation system (PBES) is a set of equations that defines sets satisfying the equations as the least and/or greatest fixed-points. Thus this system is regarded as a declarative program defining predicates, where a program execution returns whether a given ground atomic formula holds or not. The program execution corresponds to the membership problem of PBESs, which is however undecidable in general. This paper proposes a subclass of PBESs which expresses universal-quantifiers free formulas, and studies a technique to solve the problem on it. We use the fact that the membership problem is reduced to the problem whether a proof graph exists. To check the latter problem, we introduce a so-called dependency space which is a graph containing all of the minimal proof graphs. Dependency spaces are, however, infinite in general. Thus, we propose some conditions for equivalence relations to preserve the result of the membership problem, then we identify two vertices as the same under the relation. In this sense, dependency spaces possibly result in a finite graph. We show some examples having infinite dependency spaces which are reducible to finite graphs by equivalence relations. We provide a procedure to construct finite dependency spaces and show the soundness of the procedure. We also implement the procedure using an SMT solver and experiment on some examples including a downsized McCarthy 91 function.


title: Transforming Dependency Chains of Constrained TRSs into Bounded Monotone Sequences of Integers

abstract: In the dependency pair framework for proving termination of rewriting systems, polynomial interpretations are used to transform dependency chains into bounded decreasing sequences of integers, and they play an important role for the success of proving termination, especially for constrained rewriting systems. In this paper, we show sufficient conditions of linear polynomial interpretations for transforming dependency chains into bounded monotone (i.e., decreasing or increasing) sequences of integers. Such polynomial interpretations transform rewrite sequences of the original system into decreasing or increasing sequences independently of the transformation of dependency chains. When we transform rewrite sequences into increasing sequences, polynomial interpretations have non-positive coefficients for reducible positions of marked function symbols. We propose four DP processors parameterized by transforming dependency chains and rewrite sequences into either decreasing or increasing sequences of integers, respectively. We show that such polynomial interpretations make us succeed in proving termination of the McCarthy 91 function over the integers.


title: Space Improvements and Equivalences in a Functional Core Language

abstract: We explore space improvements in LRP, a polymorphically typed call-by-need functional core language. A relaxed space measure is chosen for the maximal size usage during an evaluation. It abstracts from the details of the implementation via abstract machines, but it takes garbage collection into account and thus can be seen as a realistic approximation of space usage. The results are: a context lemma for space improving translations and for space equivalences, all but one reduction rule of the calculus are shown to be space improvements, and for the exceptional one we show bounds on the space increase. Several further program transformations are shown to be space improvements or space equivalences in particular the translation into machine expressions is a space equivalence. We also classify certain space-worsening transformations as space-leaks or as space-safe. These results are a step forward in making predictions about the change in runtime space behavior of optimizing transformations in call-by-need functional languages.


title: Higher order Hamiltonians for the trigonometric Gaudin model

abstract: We consider the trigonometric classical $r$-matrix for $\mathfrak{gl}_N$ and the associated quantum Gaudin model. We produce higher Hamiltonians in an explicit form by applying the limit $q\to 1$ to elements of the Bethe subalgebra for the $XXZ$ model.


title: The Initial Approximations for Achromatic Doublets of the XVIII Century

abstract: Analysis of the both type (flint-forward and crown-forward) achromatic doublets was carried out. The investigation revealed possible initial approximations which could be used by opticians at producing of the achromatic doublets in last half of XVIII century. The comparative analysis of approximate versions of achromatic doublets has provided additional explanation to some historical events. One more confirmation that the earliest achromatic doublets were really flint-forward type was found.


title: Recommendations with Negative Feedback via Pairwise Deep Reinforcement Learning

abstract: Recommender systems play a crucial role in mitigating the problem of information overload by suggesting users' personalized items or services. The vast majority of traditional recommender systems consider the recommendation procedure as a static process and make recommendations following a fixed strategy. In this paper, we propose a novel recommender system with the capability of continuously improving its strategies during the interactions with users. We model the sequential interactions between users and a recommender system as a Markov Decision Process (MDP) and leverage Reinforcement Learning (RL) to automatically learn the optimal strategies via recommending trial-and-error items and receiving reinforcements of these items from users' feedback. Users' feedback can be positive and negative and both types of feedback have great potentials to boost recommendations. However, the number of negative feedback is much larger than that of positive one; thus incorporating them simultaneously is challenging since positive feedback could be buried by negative one. In this paper, we develop a novel approach to incorporate them into the proposed deep recommender system (DEERS) framework. The experimental results based on real-world e-commerce data demonstrate the effectiveness of the proposed framework. Further experiments have been conducted to understand the importance of both positive and negative feedback in recommendations.


title: EA-CG: An Approximate Second-Order Method for Training Fully-Connected Neural Networks

abstract: For training fully-connected neural networks (FCNNs), we propose a practical approximate second-order method including: 1) an approximation of the Hessian matrix and 2) a conjugate gradient (CG) based method. Our proposed approximate Hessian matrix is memory-efficient and can be applied to any FCNNs where the activation and criterion functions are twice differentiable. We devise a CG-based method incorporating one-rank approximation to derive Newton directions for training FCNNs, which significantly reduces both space and time complexity. This CG-based method can be employed to solve any linear equation where the coefficient matrix is Kronecker-factored, symmetric and positive definite. Empirical studies show the efficacy and efficiency of our proposed method.


title: Multicolor Gallai-Ramsey numbers of $C_9$ and $C_{11}$

abstract: A Gallai coloring is a coloring of the edges of a complete graph without rainbow triangles, and a Gallai $k$-coloring is a Gallai coloring that uses $k$ colors. We study Ramsey-type problems in Gallai colorings. Given an integer $k\ge1$ and a graph $H$, the Gallai-Ramsey number $GR_k(H)$ is the least positive integer $n$ such that every Gallai $k$-coloring of the complete graph on $n$ vertices contains a monochromatic copy of $H$. It turns out that $GR_k(H)$ is more well-behaved than the classical Ramsey number $R_k(H)$. However, finding exact values of $GR_k (H)$ is far from trivial. In this paper, we study Gallai-Ramsey numbers of odd cycles. We prove that for $n\in\{4,5\}$ and all $k\ge1$, $GR_k(C_{2n+1})= n\cdot 2^k+1$. This new result provides partial evidence for the first two open cases of the Triple Odd Cycle Conjecture of Bondy and Erd\H{o}s from 1973. Our technique relies heavily on the structural result of Gallai on Gallai colorings of complete graphs. We believe the method we developed can be used to determine the exact values of $GR_k(C_{2n+1})$ for all $n\ge6$.


title: Compiling Diderot: From Tensor Calculus to C

abstract: Diderot is a parallel domain-specific language for analysis and visualization of multidimensional scientific images, such as those produced by CT and MRI scanners. In particular, it supports algorithms where tensor fields (i.e., functions from 3D points to tensor values) are used to represent the underlying physical objects that were scanned by the imaging device. Diderot supports higher-order programming where tensor fields are first-class values and where differential operators and lifted linear-algebra operators can be used to express mathematical reasoning directly in the language. While such lifted field operations are central to the definition and computation of many scientific visualization algorithms, to date they have required extensive manual derivations and laborious implementation. The challenge for the Diderot compiler is to effectively translate the high-level mathematical concepts that are expressible in the surface language to a low-level and efficient implementation in C. This paper describes our approach to this challenge, which is based around the careful design of an intermediate representation (IR), called EIN, and a number of compiler transformations that lower the program from tensor calculus to C while avoiding combinatorial explosion in the size of the IR. We describe the challenges in compiling a language like Diderot, the design of EIN, and the transformation used by the compiler. We also present an evaluation of EIN with respect to both compiler efficiency and quality of generated code.