• ### Strain-controlled valley and spin separation in silicene heterojunctions(1707.02465)

June 28, 2018 cond-mat.mes-hall
We adopt the tight-binding mode-matching method to study the strain effect on silicene heterojunctions. It is found that valley- and spin-dependent separation of electrons cannot be achieved by the electric field only. When a strain and an electric field are simultaneously applied to the central scattering region, not only are the electrons of valleys K and K' separated into two distinct transmission lobes in opposite transverse directions, but the up-spin and down-spin electrons will also move in the two opposite transverse directions. Therefore, one can realize an effective modulation of valley- and spin-dependent transport by changing the amplitude and the stretch direction of the strain. The phenomenon of the strain-induced valley and spin deflection can be exploited for silicene-based valleytronics devices.
• ### AGN Feedback and Multi-phase Gas in Giant Elliptical Galaxies(1805.03217)

May 8, 2018 astro-ph.GA
Recent observations have found extended multi-phase gas in a significant fraction of massive elliptical galaxies. We perform high-resolution three-dimensional hydrodynamical simulations of two idealized elliptical galaxies -- one representing a typical galaxy characterized by initial conditions conducive to the development of thermal instability and the other one less likely to develop thermal instability -- in order to study the development of thermal instability and the formation of multi-phase structures. We analyze the interplay between radiative cooling, momentum-driven AGN feedback, star formation, and stellar feedback from both young and old stars. We find that in one class of elliptical galaxies, the entropy of the hot halo gas rises sharply as a function of radius, and the hot halo is thermally stable and run-away cooling can only happen in the very center of the galaxy. In other class of ellipticals, the hot halo gas has a cooling to free-fall time ratio close to 10, and the non-linear perturbation driven by AGN feedback can cause the hot gas to frequently precipitate into extended multi-phase filaments. Both multi- and single-phase elliptical galaxies experience cooling-driven AGN feedback cycles. Interestingly, AGN feedback maintains the multi- or single-phase nature of the halo but does not turn multi-phase galaxies into single-phase ones or vice versa. Some of the extended cold gas in the multi-phase galaxy also forms young stars. The level of star formation and its spatial distribution are in excellent agreement with {\it Hubble} observations of nearby elliptical galaxies.
• ### New bounds for range closest-pair problems(1712.09749)

March 31, 2018 cs.CG
Given a dataset $S$ of points in $\mathbb{R}^2$, the range closest-pair (RCP) problem aims to preprocess $S$ into a data structure such that when a query range $X$ is specified, the closest-pair in $S \cap X$ can be reported efficiently. The RCP problem can be viewed as a range-search version of the classical closest-pair problem, and finds applications in many areas. Due to its non-decomposability, the RCP problem is much more challenging than many traditional range-search problems. This paper revisits the RCP problem, and proposes new data structures for various query types including quadrants, strips, rectangles, and halfplanes. Both worst-case and average-case analyses (in the sense that the data points are drawn uniformly and independently from the unit square) are applied to these new data structures, which result in new bounds for the RCP problem. Some of the new bounds significantly improve the previous results, while the others are entirely new.
• ### Phase amplification in optical interferometry with weak measurement(1803.07735)

March 21, 2018 quant-ph, physics.optics
Improving the phase resolution of interferometry is crucial for high-precision measurements of various physical quantities. Systematic phase errors dominate the phase uncertainties in most realistic optical interferometers. Here we propose and experimentally demonstrate a weak measurement scheme to considerably suppress the phase uncertainties by the direct amplification of phase shift in optical interferometry. Given an initial ultra-small phase shift between orthogonal polarization states, we observe the phase amplification effect with a factor of 388. Our weak measurement scheme provides a practical approach to significantly improve the interferometric phase resolution, which is favorable for precision measurement applications.
• ### Graph-based regularization for regression problems with highly-correlated designs(1803.07658)

March 20, 2018 cs.LG, stat.ML
Sparse models for high-dimensional linear regression and machine learning have received substantial attention over the past two decades. Model selection, or determining which features or covariates are the best explanatory variables, is critical to the interpretability of a learned model. Much of the current literature assumes that covariates are only mildly correlated. However, in modern applications ranging from functional MRI to genome-wide association studies, covariates are highly correlated and do not exhibit key properties (such as the restricted eigenvalue condition, RIP, or other related assumptions). This paper considers a high-dimensional regression setting in which a graph governs both correlations among the covariates and the similarity among regression coefficients. Using side information about the strength of correlations among features, we form a graph with edge weights corresponding to pairwise covariances. This graph is used to define a graph total variation regularizer that promotes similar weights for highly correlated features. The graph structure encapsulated by this regularizer helps precondition correlated features to yield provably accurate estimates. Using graph-based regularizers to develop theoretical guarantees for highly-correlated covariates has not been previously examined. This paper shows how our proposed graph-based regularization yields mean-squared error guarantees for a broad range of covariance graph structures and correlation strengths which in many cases are optimal by imposing additional structure on $\beta^{\star}$ which encourages \emph{alignment} with the covariance graph. Our proposed approach outperforms other state-of-the-art methods for highly-correlated design in a variety of experiments on simulated and real fMRI data.
• ### Large deviations analysis for the $M/H_2/n + M$ queue in the Halfin-Whitt regime(1803.01082)

March 3, 2018 math.PR
We consider the FCFS $M/H_2/n + M$ queue in the Halfin-Whitt heavy traffic regime. It is known that the normalized sequence of steady-state queue length distributions is tight and converges weakly to a limiting random variable W. However, those works only describe W implicitly as the invariant measure of a complicated diffusion. Although it was proven by Gamarnik and Stolyar that the tail of W is sub-Gaussian, the actual value of $\lim_{x \rightarrow \infty}x^{-2}\log(P(W >x))$ was left open. In subsequent work, Dai and He conjectured an explicit form for this exponent, which was insensitive to the higher moments of the service distribution. We explicitly compute the true large deviations exponent for W when the abandonment rate is less than the minimum service rate, the first such result for non-Markovian queues with abandonments. Interestingly, our results resolve the conjecture of Dai and He in the negative. Our main approach is to extend the stochastic comparison framework of Gamarnik and Goldberg to the setting of abandonments, requiring several novel and non-trivial contributions. Our approach sheds light on several novel ways to think about multi-server queues with abandonments in the Halfin-Whitt regime, which should hold in considerable generality and provide new tools for analyzing these systems.
• ### Colored stochastic dominance problems(1612.06954)

Feb. 25, 2018 cs.CG
In this paper, we study the dominance relation under a stochastic setting. Let $\mathcal{S}$ be a set of $n$ colored stochastic points in $\mathbb{R}^d$, each of which is associated with an existence probability. We investigate the problem of computing the probability that a realization of $\mathcal{S}$ contains inter-color dominances, which we call the \textit{colored stochastic dominance} (CSD) problem. We propose the first algorithm to solve the CSD problem for $d=2$ in $O(n^2 \log^2 n)$ time. On the other hand, we prove that, for $d \geq 3$, even the CSD problem with a restricted color pattern is \#P-hard. In addition, even if the existence probabilities are restricted to be $\frac{1}{2}$, the problem remains \#P-hard for $d \geq 7$. A simple FPRAS is then provided to approximate the desired probability in any dimension. We also study a variant of the CSD problem in which the dominance relation is considered with respect to not only the standard basis but any orthogonal basis of $\mathbb{R}^d$. Specifically, this variant, which we call the {\em free-basis colored stochastic dominance} (FBCSD) problem, considers the probability that a realization of $\mathcal{S}$ contains inter-color dominances with respect to any orthogonal basis of $\mathbb{R}^d$. We show that the CSD problem is polynomial-time reducible to the FBCSD problem in the same dimension, which proves the \#P-hardness of the latter for $d \geq 3$. Conversely, we reduce the FBCSD problem in $\mathbb{R}^2$ to the CSD problem in $\mathbb{R}^2$, by which an $O(n^4 \log^2 n)$ time algorithm for the former is obtained.
• ### Protonation induced high-Tc phases in iron-based superconductors evidenced by NMR and magnetization measurements(1712.01191)

Chemical substitution during growth is a well-established method to manipulate electronic states of quantum materials, and leads to rich spectra of phase diagrams in cuprate and iron-based superconductors. Here we report a novel and generic strategy to achieve nonvolatile electron doping in series of (i.e. 11 and 122 structures) Fe-based superconductors by ionic liquid gating induced protonation at room temperature. Accumulation of protons in bulk compounds induces superconductivity in the parent compounds, and enhances the Tc largely in some superconducting ones. Furthermore, the existence of proton in the lattice enables the first proton nuclear magnetic resonance (NMR) study to probe directly superconductivity. Using FeS as a model system, our NMR study reveals an emergent high-Tc phase with no coherence peak which is hard to measure by NMR with other isotopes. This novel electric-field-induced proton evolution opens up an avenue for manipulation of competing electronic states (e.g. Mott insulators), and may provide an innovative way for a broad perspective of NMR measurements with greatly enhanced detecting resolution.
• ### NMR Evidence of Charge Fluctuations in Multiferroic CuBr2(1802.00928)

Feb. 3, 2018 cond-mat.str-el
We report combined magnetic susceptibility, dielectric constant, nuclear quadruple resonance (NQR) and zero-field nuclear magnetic resonance (NMR) measurements on single crystals of multiferroics CuBr$_2$. High quality of the sample is demonstrated by the sharp magnetic and magnetic-driven ferroelectric transition at $T_N=T_C\approx$ 74~K. The zero-field $^{79}$Br and $^{81}$Br NMR are resolved below $T_N$. The spin-lattice relaxation rates reveal charge fluctuations when cooled below 60~K. Evidences of an increase of NMR linewidth, a reduction of dielectric constant, and an increase of magnetic susceptibility are also seen at low temperatures. These data suggest an emergent instability which competes with the spiral magnetic ordering and the ferroelectricity. Candidate mechanisms are discussed based on the quasi-one-dimensional (1D) nature of the magnetic system.
• ### Generating electromagnetic modes with fine tunable orbital angular momentum by planar topological circuits(1801.04395)

Metamaterials made of periodic arrangements of electric permittivity and magnetic permeability and arrays of resonators can provide optic properties unexperienced in conventional materials, such as negative refractive index which can be used to achieve superlensing and cloaking. Developing new simpler structures with richer electromagnetic (EM) properties and wider working frequency bands is highly demanded for fast light-based information transfer and information processing. In the present work, we propose theoretically that a honeycomb-structured LC circuit with short-range textures in inductance can generate a topological photonic state accompanied by inversion between p- and d-orbital like EM modes carrying optic orbital angular momenta (OAM). We realize experimentally the topological photonic state in planar microstrips, a sandwich structure of bottom metallic substrate, middle dielectric film and top metallic strips with hexagonal patterns in strip width, in microwave frequency. Measuring accurately the amplitude and phase of EM fields, we demonstrate explicitly that topological interfacial EM waves launched from a linearly polarized dipole source propagate in opposite directions according to the sign of OAM, with the relative weight of p- and d-orbital like EM modes tunable precisely by sweeping the frequency in the topological band gap, which can hardly be achieved in other photonic systems and condensed-matter systems. Achieving the topological photonic state in a simple and easy fabricable structure, the present work uncovers a new direction for generating and manipulating EM modes with rich internal degrees of freedom, which can be exploited for various applications.
• ### Dirac and nodal line magnons in three-dimensional antiferromagnets(1703.08545)

We study the topological properties of magnon excitations in three-dimensional antiferromagnets, where the ground state configuration is invariant under time-reversal followed by space-inversion ($PT$-symmetry). We prove that Dirac points and nodal lines, the former being the limiting case of the latter, are the generic forms of symmetry-protected band crossings between magnon branches. As a concrete example, we study a Heisenberg spin model for a "spin-web" compound, Cu$_3$TeO$_6$, and show the presence of the magnon Dirac points assuming a collinear magnetic structure. Upon turning on symmetry-allowed Dzyaloshinsky-Moriya interactions, which introduce a small non-collinearity in the ground state configuration, we find that the Dirac points expand into nodal lines with nontrivial $Z_2$-topological charge, a new type of nodal lines unpredicted in any materials so far.
• ### Learning Unified Embedding for Apparel Recognition(1707.05929)

Aug. 15, 2017 cs.CV
In apparel recognition, specialized models (e.g. models trained for a particular vertical like dresses) can significantly outperform general models (i.e. models that cover a wide range of verticals). Therefore, deep neural network models are often trained separately for different verticals. However, using specialized models for different verticals is not scalable and expensive to deploy. This paper addresses the problem of learning one unified embedding model for multiple object verticals (e.g. all apparel classes) without sacrificing accuracy. The problem is tackled from two aspects: training data and training difficulty. On the training data aspect, we figure out that for a single model trained with triplet loss, there is an accuracy sweet spot in terms of how many verticals are trained together. To ease the training difficulty, a novel learning scheme is proposed by using the output from specialized models as learning targets so that L2 loss can be used instead of triplet loss. This new loss makes the training easier and make it possible for more efficient use of the feature space. The end result is a unified model which can achieve the same retrieval accuracy as a number of separate specialized models, while having the model complexity as one. The effectiveness of our approach is shown in experiments.
• ### Learning how to Active Learn: A Deep Reinforcement Learning Approach(1708.02383)

Aug. 8, 2017 cs.AI, cs.CL, cs.LG
Active learning aims to select a small subset of data for annotation such that a classifier learned on the data is highly accurate. This is usually done using heuristic selection methods, however the effectiveness of such methods is limited and moreover, the performance of heuristics varies between datasets. To address these shortcomings, we introduce a novel formulation by reframing the active learning as a reinforcement learning problem and explicitly learning a data selection policy, where the policy takes the role of the active learning heuristic. Importantly, our method allows the selection policy learned using simulation on one language to be transferred to other languages. We demonstrate our method using cross-lingual named entity recognition, observing uniform improvements over traditional active learning.
• ### Automatic Spatially-aware Fashion Concept Discovery(1708.01311)

Aug. 3, 2017 cs.CV
This paper proposes an automatic spatially-aware concept discovery approach using weakly labeled image-text data from shopping websites. We first fine-tune GoogleNet by jointly modeling clothing images and their corresponding descriptions in a visual-semantic embedding space. Then, for each attribute (word), we generate its spatially-aware representation by combining its semantic word vector representation with its spatial representation derived from the convolutional maps of the fine-tuned network. The resulting spatially-aware representations are further used to cluster attributes into multiple groups to form spatially-aware concepts (e.g., the neckline concept might consist of attributes like v-neck, round-neck, etc). Finally, we decompose the visual-semantic embedding space into multiple concept-specific subspaces, which facilitates structured browsing and attribute-feedback product retrieval by exploiting multimodal linguistic regularities. We conducted extensive experiments on our newly collected Fashion200K dataset, and results on clustering quality evaluation and attribute-feedback product retrieval task demonstrate the effectiveness of our automatically discovered spatially-aware concepts.
• ### Multiphoton interference in quantum Fourier transform circuits and applications to quantum metrology(1708.00296)

Aug. 1, 2017 quant-ph
Quantum Fourier transforms (QFT) have gained increased attention with the rise of quantum walks, boson sampling, and quantum metrology. Here we present and demonstrate a general technique that simplifies the construction of QFT interferometers using both path and polarization modes. On that basis, we first observed the generalized Hong-Ou-Mandel effect with up to four photons. Furthermore, we directly exploited number-path entanglement generated in these QFT interferometers and demonstrated optical phase supersensitivities deterministically.
• ### Heavy-tailed queues in the Halfin-Whitt regime(1707.07775)

July 25, 2017 math.PR
We consider the FCFS G/G/n queue in the Halfin-Whitt regime, in the presence of heavy-tailed distributions (i.e. infinite variance). We prove that under minimal assumptions, i.e. only that processing times have finite 1 + epsilon moment and inter-arrival times have finite second moment, the sequence of stationary queue length distributions, normalized by $n^{\frac{1}{2}}$, is tight. All previous tightness results for the stationary queue length required that processing times have finite 2 + epsilon moment. Furthermore, we develop simple and explicit bounds on the stationary queue length in that setting. When processing times have an asymptotically Pareto tail with index alpha in (1,2), we bound the large deviations behavior of the limiting process, and derive a matching lower bound when inter-arrival times are Markovian. Interestingly, we find that the large deviations behavior of the limit has a sub-exponential decay, differing fundamentally from the exponentially decaying tails known to hold in the light-tailed setting, and answering an open question of Gamarnik and Goldberg. For the setting where instead the inter-arrival times have an asymptotically Pareto tail with index alpha in (1,2), we extend recent results of Hurvich and Reed (who analyzed the case of deterministic processing times) by proving that for general processing time distributions, the sequence of stationary queue length distributions, normalized by $n^{\frac{1}{\alpha}}$, is tight (here we use the scaling of Hurvich and Reed, i.e. Halfin-Whitt-Reed regime). We are again able to bound the large-deviations behavior of the limit, and find that our derived bounds do not depend on the particular processing time distribution, and are in fact tight even for the case of deterministic processing times.
• ### Observation of Unusual Magnetoelastic Effects in a Quasi-1D Spiral Magnet(1512.07120)

July 13, 2017 cond-mat.str-el
We present a systematic study of spin and lattice dynamics in the quasi-one-dimensional spiral magnet CuBr2, using Raman scattering in conjunction with infrared and neutron spectroscopy. Along with the development of spin correlations upon cooling, we observe a rich set of broad Raman bands at energies that correspond to phonon-dispersion energies near the one-dimensional magnetic wave vector. The low-energy bands further exhibit a distinct intensity maximum at the spiral magnetic ordering temperature. We attribute these unusual observations to two possible underlying mechanisms: (1) formation of hybrid spin-lattice excitations, and/or (2) "quadrumerization" of the lattice caused by spin-singlet entanglement in competition with the spiral magnetism.
• ### Simple and explicit bounds for multi-server queues with universal 1 / (1 - rho) scaling(1706.04628)

June 14, 2017 math.PR
We consider the FCFS GI/GI/n queue, and prove the first simple and explicit bounds that scale gracefully and universally as 1 / (1 - rho) (and better), with rho the corresponding traffic intensity. In particular, we prove the first multi-server analogue of Kingman's bound, which has been an open problem for over fifty years. Our main results are bounds for the tail of the steady-state queue length and the steady-state probability of delay, where the strength of our bounds (e.g. in the form of tail decay rate) is a function of how many moments of the inter-arrival and service distributions are assumed finite. Supposing that the inter-arrival and service times, distributed as random variables A and S, have finite rth moment for some r > 2, our bounds are simple and explicit functions of only the normalized rth moments of A and S, r, and 1 / (1 - rho). Our simple and explicit bounds scale gracefully even when the number of servers grows large and the traffic intensity converges to unity simultaneously, as in the Halfin-Whitt scaling regime. Our proofs proceed by explicitly analyzing the bounding process which arises in the stochastic comparison bounds of Gamarnik and Goldberg for multi-server queues. Along the way we derive several novel results for suprema of random walks with stationary increments and negative drift, pooled renewal processes, and various other quantities which may be of independent interest.
• ### On the expected diameter, width, and complexity of a stochastic convex-hull(1704.07028)

May 1, 2017 cs.CG
We investigate several computational problems related to the stochastic convex hull (SCH). Given a stochastic dataset consisting of $n$ points in $\mathbb{R}^d$ each of which has an existence probability, a SCH refers to the convex hull of a realization of the dataset, i.e., a random sample including each point with its existence probability. We are interested in computing certain expected statistics of a SCH, including diameter, width, and combinatorial complexity. For diameter, we establish the first deterministic 1.633-approximation algorithm with a time complexity polynomial in both $n$ and $d$. For width, two approximation algorithms are provided: a deterministic $O(1)$-approximation running in $O(n^{d+1} \log n)$ time, and a fully polynomial-time randomized approximation scheme (FPRAS). For combinatorial complexity, we propose an exact $O(n^d)$-time algorithm. Our solutions exploit many geometric insights in Euclidean space, some of which might be of independent interest.
• ### SCAN: Structure Correcting Adversarial Network for Organ Segmentation in Chest X-rays(1703.08770)

April 10, 2017 cs.CV
Chest X-ray (CXR) is one of the most commonly prescribed medical imaging procedures, often with over 2-10x more scans than other imaging modalities such as MRI, CT scan, and PET scans. These voluminous CXR scans place significant workloads on radiologists and medical practitioners. Organ segmentation is a crucial step to obtain effective computer-aided detection on CXR. In this work, we propose Structure Correcting Adversarial Network (SCAN) to segment lung fields and the heart in CXR images. SCAN incorporates a critic network to impose on the convolutional segmentation network the structural regularities emerging from human physiology. During training, the critic network learns to discriminate between the ground truth organ annotations from the masks synthesized by the segmentation network. Through this adversarial process the critic network learns the higher order structures and guides the segmentation model to achieve realistic segmentation outcomes. Extensive experiments show that our method produces highly accurate and natural segmentation. Using only very limited training data available, our model reaches human-level performance without relying on any existing trained model or dataset. Our method also generalizes well to CXR images from a different patient population and disease profiles, surpassing the current state-of-the-art.
• ### Raman scattering study of tetragonal magnetic phase in Sr$_{1-x}$Na$_x$Fe$_2$As$_2$: structural symmetry and electronic gap(1704.00669)

We use inelastic light scattering to study Sr$_{1-x}$Na$_x$Fe$_2$As$_2$ ($x\approx0.34$), which exhibits a robust tetragonal magnetic phase that restores the four-fold rotation symmetry inside the orthorhombic magnetic phase. With cooling, we observe splitting and recombination of an $E_g$ phonon peak upon entering the orthorhombic and tetragonal magnetic phases, respectively, consistent with the reentrant phase behavior. Our electronic Raman data reveal a pronounced feature that is clearly associated with the tetragonal magnetic phase, suggesting the opening of an electronic gap. No phonon back-folding behavior can be detected above the noise level, which implies that any lattice translation symmetry breaking in the tetragonal magnetic phase must be very weak.
• ### The Effects of Ram Pressure on the Cold Clouds in the Centers of Galaxy Clusters(1703.06954)

March 20, 2017 astro-ph.GA
We discuss the effect of ram pressure on the cold clouds in the centers of cool-core galaxy clusters, and in particular, how it reduces cloud velocity and sometimes causes an offset between the cold gas and young stars. The velocities of the molecular gas in both observations and our simulations fall in the range of $100-400$ km/s, much lower than expected if they fall from a few tens of kpc ballistically. If the intra-cluster medium (ICM) is at rest, the ram pressure of the ICM only slightly reduces the velocity of the clouds. When we assume that the clouds are actually "fluffier" because they are co-moving with a warm-hot layer, the velocity becomes smaller. If we also consider the AGN wind in the cluster center by adding a wind profile measured from the simulation, the clouds are further slowed down at small radii, and the resulting velocities are in general agreement with the observations and simulations. Because ram pressure only affects gas but not stars, it can cause a separation between a filament and young stars that formed in the filament as they move through the ICM together. This separation has been observed in Perseus and also exists in our simulations. We show that the star-filament offset combined with line-of-sight velocity measurements can help determine the true motion of the cold gas, and thus distinguish between inflows and outflows.
• ### a-b anisotropy of the intra-unit-cell magnetic order in $\rm YBa_2Cu_3O_{6.6}$(1701.02866)

Jan. 11, 2017 cond-mat.supr-con
Within the complex phase diagram of the hole-doped cuprates, seizing the nature of the mysterious pseudo-gap phase is essential to unravel the microscopic origin of high-temperature superconductivity. Below the pseudo-gap temperature $\rm T^{\star}$, evidences for intra-unit-cell orders breaking the 4-fold rotation symmetry have been provided by neutron diffraction and scanning tunneling spectroscopy. Using polarized neutron diffraction on a detwinned $\rm YBa_2Cu_3O_{6.6}$ sample, we here report a distinct a-b anisotropy of the intra-unit-cell magnetic structure factor below $\rm T^{\star}$, highlighting that intra-unit-cell order in this material breaks the mirror symmetry of the CuO$_2$ bilayers. This is likely to originate from a crisscrossed arrangement of loop currents within the $\rm CuO_2$ bilayer, resulting in a bilayer mean toroidal axis along the $\rm {\bf b}$ direction.
• ### Raman signatures of inversion symmetry breaking and structural phase transition in type-II Weyl semimetal MoTe2(1606.05071)

Dec. 18, 2016 cond-mat.mtrl-sci
Transition metal dichalcogenide MoTe$_2$ is an important candidate for realizing the newly predicted type-IIWeyl fermions, for which the breaking of the inversion symmetry is a prerequisite. Here we present direct spectroscopic evidence for the inversion symmetry breaking in the low temperature phase of MoTe$_2$ by systematic Raman experiments and first principles calculations. We identify five lattice vibrational modes which are Raman active only in noncentrosymmetric structure at low temperature. A hysteresis is also observed in the peak intensity of inversion symmetry activated Raman modes, confirming a temperature induced structural phase transition with a concomitant change in the inversion symmetry. Our results provide definitive evidence for the low temperature noncentrosymmetric T$_d$ phase from vibrational spectroscopy, and suggest MoTe$_2$ as an ideal candidate for investigating the temperature induced topological phase transition.
• ### Stochastic closest-pair problem and most-likely nearest-neighbor search in tree spaces(1612.04890)

Dec. 15, 2016 cs.CG
Let $T$ be a tree space (or tree network) represented by a weighted tree with $t$ vertices, and $S$ be a set of $n$ stochastic points in $T$, each of which has a fixed location with an independent existence probability. We investigate two fundamental problems under such a stochastic setting, the closest-pair problem and the nearest-neighbor search. For the former, we study the computation of the $\ell$-threshold probability and the expectation of the closest-pair distance of a realization of $S$. We propose the first algorithm to compute the $\ell$-threshold probability in $O(t+n\log n+ \min\{tn,n^2\})$ time for any given threshold $\ell$, which immediately results in an $O(t+\min\{tn^3,n^4\})$-time algorithm for computing the expected closest-pair distance. Based on this, we further show that one can compute a $(1+\varepsilon)$-approximation for the expected closest-pair distance in $O(t+\varepsilon^{-1}\min\{tn^2,n^3\})$ time, by arguing that the expected closest-pair distance can be approximated via $O(\varepsilon^{-1}n)$ threshold probability queries. For the latter, we study the $k$ most-likely nearest-neighbor search ($k$-LNN) via a notion called $k$ most-likely Voronoi Diagram ($k$-LVD). We show that the size of the $k$-LVD $\varPsi_T^S$ of $S$ on $T$ is bounded by $O(kn)$ if the existence probabilities of the points in $S$ are constant-far from 0. Furthermore, we establish an $O(kn)$ average-case upper bound for the size of $\varPsi_T^S$, by regarding the existence probabilities as i.i.d. random variables drawn from some fixed distribution. Our results imply the existence of an LVD data structure which answers $k$-LNN queries in $O(\log n+k)$ time using average-case $O(t+k^2n)$ space, and worst-case $O(t+kn^2)$ space if the existence probabilities are constant-far from 0. Finally, we also give an $O(t+ n^2\log n+n^2k)$-time algorithm to construct the LVD data structure.