Edge states of a three-dimensional topological insulator

We use the bulk Hamiltonian for a three-dimensional topological insulator such as Bi-2 Se-3 to study the states which appear on its various surfaces and along the edge between two surfaces. We use both analytical methods based on the surface Hamiltonians (which are derived from the bulk Hamiltonian) and numerical methods based on a lattice discretization of the bulk Hamiltonian. We find that the application of a potential barrier along an edge can give rise to states localized at that edge. These states have an unusual energy-momentum dispersion which can be controlled by applying a potential along the edge; in particular, the velocity of these states can be tuned to zero. The scattering and conductance across the edge is studied as a function of the edge potential. We show that a magnetic field in a particular direction can also give rise to zero energy states on certain edges. We point out possible experimental ways of looking for the various edge states.

On the Parameterized Complexity of the Maximum Edge 2-Coloring Problem

We investigate the parameterized complexity of the following edge coloring problem motivated by the problem of channel assignment in wireless networks. For an integer q >= 2 and a graph G, the goal is to find a coloring of the edges of G with the maximum number of colors such that every vertex of the graph sees at most q colors. This problem is NP-hard for q >= 2, and has been well-studied from the point of view of approximation. Our main focus is the case when q = 2, which is already theoretically intricate and practically relevant. We show fixed-parameter tractable algorithms for both the standard and the dual parameter, and for the latter problem, the result is based on a linear vertex kernel.

Multiscale Symmetry Detection in Scalar Fields by Clustering Contours

The complexity in visualizing volumetric data often limits the scope of direct exploration of scalar fields. Isocontour extraction is a popular method for exploring scalar fields because of its simplicity in presenting features in the data. In this paper, we present a novel representation of contours with the aim of studying the similarity relationship between the contours. The representation maps contours to points in a high-dimensional transformation-invariant descriptor space. We leverage the power of this representation to design a clustering based algorithm for detecting symmetric regions in a scalar field. Symmetry detection is a challenging problem because it demands both segmentation of the data and identification of transformation invariant segments. While the former task can be addressed using topological analysis of scalar fields, the latter requires geometry based solutions. Our approach combines the two by utilizing the contour tree for segmenting the data and the descriptor space for determining transformation invariance. We discuss two applications, query driven exploration and asymmetry visualization, that demonstrate the effectiveness of the approach.

On the Communication Complexity of Secret Key Generation in the Multiterminal Source Model

Communication complexity refers to the minimum rate of public communication required for generating a maximal-rate secret key (SK) in the multiterminal source model of Csiszar and Narayan. Tyagi recently characterized this communication complexity for a two-terminal system. We extend the ideas in Tyagi's work to derive a lower bound on communication complexity in the general multiterminal setting. In the important special case of the complete graph pairwise independent network (PIN) model, our bound allows us to determine the exact linear communication complexity, i.e., the communication complexity when the communication and SK are restricted to be linear functions of the randomness available at the terminals.

Efficient QR Decomposition Using Low Complexity Column-wise Givens Rotation (CGR)

QR decomposition (QRD) is a widely used Numerical Linear Algebra (NLA) kernel with applications ranging from SONAR beamforming to wireless MIMO receivers. In this paper, we propose a novel Givens Rotation (GR) based QRD (GR QRD) where we reduce the computational complexity of GR and exploit higher degree of parallelism. This low complexity Column-wise GR (CGR) can annihilate multiple elements of a column of a matrix simultaneously. The algorithm is first realized on a Two-Dimensional (2 D) systolic array and then implemented on REDEFINE which is a Coarse Grained run-time Reconfigurable Architecture (CGRA). We benchmark the proposed implementation against state-of-the-art implementations to report better throughput, convergence and scalability.

Low Complexity Power and Scheduling Policies for Wireless Networks to Provide Quality of Service

We consider optimal power allocation policies for a single server, multiuser system. The power is consumed in transmission of data only. The transmission channel may experience multipath fading. We obtain very efficient, low computational complexity algorithms which minimize power and ensure stability of the data queues. We also obtain policies when the users may have mean delay constraints. If the power required is a linear function of rate then we exploit linearity and obtain linear programs with low complexity.

On the Parameterized Complexity of Finding Separators with Non-Hereditary Properties

We study the problem of finding small s-t separators that induce graphs having certain properties. It is known that finding a minimum clique s-t separator is polynomial-time solvable (Tarjan in Discrete Math. 55:221-232, 1985), while for example the problems of finding a minimum s-t separator that induces a connected graph or forms an independent set are fixed-parameter tractable when parameterized by the size of the separator (Marx et al. in ACM Trans. Algorithms 9(4): 30, 2013). Motivated by these results, we study properties that generalize cliques, independent sets, and connected graphs, and determine the complexity of finding separators satisfying these properties. We investigate these problems also on bounded-degree graphs. Our results are as follows: Finding a minimum c-connected s-t separator is FPT for c=2 and W1]-hard for any ca parts per thousand yen3. Finding a minimum s-t separator with diameter at most d is W1]-hard for any da parts per thousand yen2. Finding a minimum r-regular s-t separator is W1]-hard for any ra parts per thousand yen1. For any decidable graph property, finding a minimum s-t separator with this property is FPT parameterized jointly by the size of the separator and the maximum degree. Finding a connected s-t separator of minimum size does not have a polynomial kernel, even when restricted to graphs of maximum degree at most 3, unless .

Robust local and nonlocal transport in the topological Kondo insulator SmB6 in the presence of a high magnetic field

SmB6 has been predicted to be a Kondo topological insulator with topologically protected conducting surface states. We have studied quantitatively the electrical transport through surface states in high-quality single crystals of SmB6. We observe a large nonlocal surface signal at temperatures lower than the bulk Kondo gap scale. Measurements and finite-element simulations allow us to distinguish unambiguously between the contributions from different transport channels. In contrast to general expectations, the electrical transport properties of the surface channels were found to be insensitive to high magnetic fields. We propose possible scenarios that might explain this unexpected finding. Local and nonlocal magnetoresistance measurements allowed us to identify possible signatures of helical spin states and strong interband scattering at the surface.

Efficient Low Complexity Power Allocation Policies for Wireless Communication Systems Guaranteeing QoS

We consider near-optimal policies for a single user transmitting on a wireless channel which minimize average queue length under average power constraint. The power is consumed in transmission of data only. We consider the case when the power used in transmission is a linear function of the data transmitted. The transmission channel may experience multipath fading. Later, we also extend these results to the multiuser case. We show that our policies can be used in a system with energy harvesting sources at the transmitter. Next we consider data users which require minimum rate guarantees. Finally we consider the system which has both data and real time users. Our policies have low computational complexity, closed form expression for mean delays and require only the mean arrival rate with no queue length information.

Bulk-Induced 1/f Noise at the Surface of Three-Dimensional Topological Insulators

Slow intrinsic fluctuations of resistance, also known as the flicker noise or 1/f-noise, in the surface transport of strong topological insulators (TIs) is a poorly understood phenomenon. Here, we have systematically explored the 1/f-noise in field-effect transistors (FET) of mechanically exfoliated Bi1.6Sb0.4Te2Se TI films when transport occurs predominantly via the surface states. We find that the slow kinetics of the charge disorder within the bulk of the TI induces mobility fluctuations at the surface, providing a new source of intrinsic 1/f-noise that is unique to bulk TI systems. At small channel thickness, the noise magnitude can be extremely small, corresponding to the phenomenological Hooge parameter gamma(H) as low as approximate to 10(-4), but it increases rapidly when channel thickness exceeds similar to 1 mu m. From the temperature (T)-dependence of noise, which displayed sharp peaks at characteristic values of T, we identified generation-recombination processes from interband transitions within the TI bulk as the dominant source of the mobility fluctuations in surface transport. Our experiment not only establishes an intrinsic microscopic origin of noise in TI surface channels, but also reveals a unique spectroscopic information on the impurity bands that can be useful in bulk TI systems in general.

Tailoring of Electronic Structure and Thermoelectric Properties of a Topological Crystalline Insulator by Chemical Doping

Topological crystalline insulators (TCIs) are a new quantum state of matter in which linearly dispersed metallic surface states are protected by crystal mirror symmetry. Owing to its vanishingly small bulk band gap, a TCI like Pb0.6Sn0.4Te has poor thermoelectric properties. Breaking of crystal symmetry can widen the band gap of TCI. While breaking of mirror symmetry in a TCI has been mostly explored by various physical perturbation techniques, chemical doping, which may also alter the electronic structure of TCI by perturbing the local mirror symmetry, has not yet been explored. Herein, we demonstrate that Na doping in Pb0.6Sn0.4Te locally breaks the crystal symmetry and opens up a bulk electronic band gap, which is confirmed by direct electronic absorption spectroscopy and electronic structure calculations. Na doping in Pb0.6Sn0.4Te increases p-type carrier concentration and suppresses the bipolar conduction (by widening the band gap), which collectively gives rise to a promising zT of 1 at 856 K for Pb0.58Sn0.40Na0.02Te. Breaking of crystal symmetry by chemical doping widens the bulk band gap in TCI, which uncovers a route to improve TCI for thermoelectric applications.

Kernelization complexity of possible winner and coalitional manipulation problems in voting

In the POSSIBLE WINNER problem in computational social choice theory, we are given a set of partial preferences and the question is whether a distinguished candidate could be made winner by extending the partial preferences to linear preferences. Previous work has provided, for many common voting rules, fixed parameter tractable algorithms for the POSSIBLE WINNER problem, with number of candidates as the parameter. However, the corresponding kernelization question is still open and in fact, has been mentioned as a key research challenge 10]. In this paper, we settle this open question for many common voting rules. We show that the POSSIBLE WINNER problem for maximin, Copeland, Bucklin, ranked pairs, and a class of scoring rules that includes the Borda voting rule does not admit a polynomial kernel with the number of candidates as the parameter. We show however that the COALITIONAL MANIPULATION problem which is an important special case of the POSSIBLE WINNER problem does admit a polynomial kernel for maximin, Copeland, ranked pairs, and a class of scoring rules that includes the Borda voting rule, when the number of manipulators is polynomial in the number of candidates. A significant conclusion of our work is that the POSSIBLE WINNER problem is harder than the COALITIONAL MANIPULATION problem since the COALITIONAL MANIPULATION problem admits a polynomial kernel whereas the POSSIBLE WINNER problem does not admit a polynomial kernel. (C) 2015 Elsevier B.V. All rights reserved.

Pressure-induced phase transition in Bi2Se3 at 3 GPa: electronic topological transition or not?

In recent years, a low pressure transition around P similar to 3 GPa exhibited by the A(2)B(3)-type 3D topological insulators is attributed to an electronic topological transition (ETT) for which there is no direct evidence either from theory or experiments. We address this phase transition and other transitions at higher pressure in bismuth selenide (Bi2Se3) using Raman spectroscopy at pressure up to 26.2 GPa. We see clear Raman signatures of an isostructural phase transition at P similar to 2.4 GPa followed by structural transitions at similar to 10 GPa and 16 GPa. First-principles calculations reveal anomalously sharp changes in the structural parameters like the internal angle of the rhombohedral unit cell with a minimum in the c/a ratio near P similar to 3 GPa. While our calculations reveal the associated anomalies in vibrational frequencies and electronic bandgap, the calculated Z(2) invariant and Dirac conical surface electronic structure remain unchanged, showing that there is no change in the electronic topology at the lowest pressure transition.