Entropy of quantum states: Ambiguities

The von Neumann entropy of a generic quantum state is not unique unless the state can be uniquely decomposed as a sum of extremal or pure states. As pointed out to us by Sorkin, this happens if the GNS representation (of the algebra of observables in some quantum state) is reducible, and some representations in the decomposition occur with non-trivial degeneracy. This non-unique entropy can occur at zero temperature. We will argue elsewhere in detail that the degeneracies in the GNS representation can be interpreted as an emergent broken gauge symmetry, and play an important role in the analysis of emergent entropy due to non-Abelian anomalies. Finally, we establish the analogue of an H-theorem for this entropy by showing that its evolution is Markovian, determined by a stochastic matrix.

Rainbow colouring of split and threshold Graphs

A rainbow colouring of a connected graph is a colouring of the edges of the graph, such that every pair of vertices is connected by at least one path in which no two edges are coloured the same. Such a colouring using minimum possible number of colours is called an optimal rainbow colouring, and the minimum number of colours required is called the rainbow connection number of the graph. A Chordal Graph is a graph in which every cycle of length more than 3 has a chord. A Split Graph is a chordal graph whose vertices can be partitioned into a clique and an independent set. A threshold graph is a split graph in which the neighbourhoods of the independent set vertices form a linear order under set inclusion. In this article, we show the following: 1. The problem of deciding whether a graph can be rainbow coloured using 3 colours remains NP-complete even when restricted to the class of split graphs. However, any split graph can be rainbow coloured in linear time using at most one more colour than the optimum. 2. For every integer k ≥ 3, the problem of deciding whether a graph can be rainbow coloured using k colours remains NP-complete even when restricted to the class of chordal graphs. 3. For every positive integer k, threshold graphs with rainbow connection number k can be characterised based on their degree sequence alone. Further, we can optimally rainbow colour a threshold graph in linear time.

Polynomial time and parameterized approximation algorithms for boxicity

The boxicity (cubicity) of a graph G, denoted by box(G) (respectively cub(G)), is the minimum integer k such that G can be represented as the intersection graph of axis parallel boxes (cubes) in ℝ k . The problem of computing boxicity (cubicity) is known to be inapproximable in polynomial time even for graph classes like bipartite, co-bipartite and split graphs, within an O(n 0.5 − ε ) factor for any ε > 0, unless NP = ZPP. We prove that if a graph G on n vertices has a clique on n − k vertices, then box(G) can be computed in time n22O(k2logk) . Using this fact, various FPT approximation algorithms for boxicity are derived. The parameter used is the vertex (or edge) edit distance of the input graph from certain graph families of bounded boxicity - like interval graphs and planar graphs. Using the same fact, we also derive an O(nloglogn√logn√) factor approximation algorithm for computing boxicity, which, to our knowledge, is the first o(n) factor approximation algorithm for the problem. We also present an FPT approximation algorithm for computing the cubicity of graphs, with vertex cover number as the parameter.

Compositional hierarchical monitoring automaton construction for LTL

In this paper we give a compositional (or inductive) construction of monitoring automata for LTL formulas. Our construction is similar in spirit to the compositional construction of Kesten and Pnueli [5]. We introduce the notion of hierarchical Büchi automata and phrase our constructions in the framework of these automata. We give detailed constructions for all the principal LTL operators including past operators, along with proofs of correctness of the constructions.

Model-checking bisimulation-based information flow properties for infinite state sstems

Bisimulation-based information flow properties were introduced by Focardi and Gorrieri [1] as a way of specifying security properties for transition system models. These properties were shown to be decidable for finite-state systems. In this paper, we study the problem of verifying these properties for some well-known classes of infinite state systems. We show that all the properties are undecidable for each of these classes of systems.

Scalable flow-sensitive pointer analysis for fava with strong updates

The ability to perform strong updates is the main contributor to the precision of flow-sensitive pointer analysis algorithms. Traditional flow-sensitive pointer analyses cannot strongly update pointers residing in the heap. This is a severe restriction for Java programs. In this paper, we propose a new flow-sensitive pointer analysis algorithm for Java that can perform strong updates on heap-based pointers effectively. Instead of points-to graphs, we represent our points-to information as maps from access paths to sets of abstract objects. We have implemented our analysis and run it on several large Java benchmarks. The results show considerable improvement in precision over the points-to graph based flow-insensitive and flow-sensitive analyses, with reasonable running time.

Mechanism design for time critical and cost critical task execution via crowdsourcing

An exciting application of crowdsourcing is to use social networks in complex task execution. In this paper, we address the problem of a planner who needs to incentivize agents within a network in order to seek their help in executing an atomic task as well as in recruiting other agents to execute the task. We study this mechanism design problem under two natural resource optimization settings: (1) cost critical tasks, where the planner's goal is to minimize the total cost, and (2) time critical tasks, where the goal is to minimize the total time elapsed before the task is executed. We identify a set of desirable properties that should ideally be satisfied by a crowdsourcing mechanism. In particular, sybil-proofness and collapse-proofness are two complementary properties in our desiderata. We prove that no mechanism can satisfy all the desirable properties simultaneously. This leads us naturally to explore approximate versions of the critical properties. We focus our attention on approximate sybil-proofness and our exploration leads to a parametrized family of payment mechanisms which satisfy collapse-proofness. We characterize the approximate versions of the desirable properties in cost critical and time critical domain.

Sufficient conditions for formation of a network topology by self-interested agents

Networks such as organizational network of a global company play an important role in a variety of knowledge management and information diffusion tasks. The nodes in these networks correspond to individuals who are self-interested. The topology of these networks often plays a crucial role in deciding the ease and speed with which certain tasks can be accomplished using these networks. Consequently, growing a stable network having a certain topology is of interest. Motivated by this, we study the following important problem: given a certain desired network topology, under what conditions would best response (link addition/deletion) strategies played by self-interested agents lead to formation of a pairwise stable network with only that topology. We study this interesting reverse engineering problem by proposing a natural model of recursive network formation. In this model, nodes enter the network sequentially and the utility of a node captures principal determinants of network formation, namely (1) benefits from immediate neighbors, (2) costs of maintaining links with immediate neighbors, (3) benefits from indirect neighbors, (4) bridging benefits, and (5) network entry fee. Based on this model, we analyze relevant network topologies such as star graph, complete graph, bipartite Turan graph, and multiple stars with interconnected centers, and derive a set of sufficient conditions under which these topologies emerge as pairwise stable networks. We also study the social welfare properties of the above topologies.

Regional variations in the nonlinearity and anisotropy of bovine aortic elastin

Arterial walls have a regular and lamellar organization of elastin present as concentric fenestrated networks in the media. In contrast, elastin networks are longitudinally oriented in layers adjacent to the media. In a previous model exploring the biomechanics of arterial elastin, we had proposed a microstructurally motivated strain energy function modeled using orthotropic material symmetry. Using mechanical experiments, we showed that the neo-Hookean term had a dominant contribution to the overall form of the strain energy function. In contrast, invariants corresponding to the two fiber families had smaller contributions. To extend these investigations, we use biaxial force-controlled experiments to quantify regional variations in the anisotropy and nonlinearity of elastin isolated from bovine aortic tissues proximal and distal to the heart. Results from this study show that tissue nonlinearity significantly increases distal to the heart as compared to proximally located regions (). Distally located samples also have a trend for increased anisotropy (), with the circumferential direction stiffer than the longitudinal, as compared to an isotropic and relatively linear response for proximally located elastin samples. These results are consistent with the underlying tissue histology from proximally located samples that had higher optical density (), fiber thickness (), and trend for lower tortuosity () in elastin fibers as compared to the thinner and highly undulating elastin fibers isolated from distally located samples. Our studies suggest that it is important to consider elastin fiber orientations in investigations that use microstructure-based models to describe the contributions of elastin and collagen to arterial mechanics.

Spontaneous Lorentz violation in gauge theories

Frohlich, Morchio and Strocchi long ago proved that the Lorentz invariance is spontaneously broken in QED because of infrared effects. We develop a simple model where the consequences of this breakdown can be explicitly and easily calculated. For this purpose, the superselected U(1) charge group of QED is extended to a superselected ``Sky'' group containing direction-dependent gauge transformations at infinity. It is the analog of the Spi group of gravity. As Lorentz transformations do not commute with Sky, they are spontaneously broken. These Abelian considerations and model are extended to non-Abelian gauge symmetries. Basic issues regarding the observability of twisted non-Abelian gauge symmetries and of the asymptotic ADM symmetries of quantum gravity are raised.

Polyvinylidene fluoride film based nasal sensor to monitor human respiration pattern: An initial clinical study

Design and development of a piezoelectric polyvinylidene fluoride (PVDF) thin film based nasal sensor to monitor human respiration pattern (RP) from each nostril simultaneously is presented in this paper. Thin film based PVDF nasal sensor is designed in a cantilever beam configuration. Two cantilevers are mounted on a spectacle frame in such a way that the air flow from each nostril impinges on this sensor causing bending of the cantilever beams. Voltage signal produced due to air flow induced dynamic piezoelectric effect produce a respective RP. A group of 23 healthy awake human subjects are studied. The RP in terms of respiratory rate (RR) and Respiratory air-flow changes/alterations obtained from the developed PVDF nasal sensor are compared with RP obtained from respiratory inductance plethysmograph (RIP) device. The mean RR of the developed nasal sensor (19.65 +/- A 4.1) and the RIP (19.57 +/- A 4.1) are found to be almost same (difference not significant, p > 0.05) with the correlation coefficient 0.96, p < 0.0001. It was observed that any change/alterations in the pattern of RIP is followed by same amount of change/alterations in the pattern of PVDF nasal sensor with k = 0.815 indicating strong agreement between the PVDF nasal sensor and RIP respiratory air-flow pattern. The developed sensor is simple in design, non-invasive, patient friendly and hence shows promising routine clinical usage. The preliminary result shows that this new method can have various applications in respiratory monitoring and diagnosis.

Modulation of redox regulatory molecules and electron transport chain activity in muscle of air breathing fish Heteropneustes fossilis under air exposure stress

Responses of redox regulatory system to long-term survival (> 18 h) of the catfish Heteropneustes fossilis in air are not yet understood. Lipid and protein oxidation level, oxidant (H2O2) generation, antioxidative status (levels of superoxide dismutase, catalase, glutathione peroxidase and reductase, ascorbic acid and non-protein sulfhydryl) and activities of respiratory complexes (I, II, III and IV) in mitochondria were investigated in muscle of H. fossilis under air exposure condition (0, 3, 6, 12 and 18 h at 25 A degrees C). The increased levels of both H2O2 and tissue oxidation were observed due to the decreased activities of antioxidant enzymes in muscle under water deprivation condition. However, ascorbic acid and non-protein thiol groups were the highest at 18 h air exposure time. A linear increase in complex II activity with air exposure time and an increase up to 12 h followed by a decrease in activity of complex I at 18 h were observed. Negative correlation was observed for complex III and V activity with exposure time. Critical time to modulate the above parameters was found to be 3 h air exposure. Dehydration induced oxidative stress due to modulation of electron transport chain and redox metabolizing enzymes in muscle of H. fossilis was clearly observed. Possible contribution of redox regulatory system in muscle tissue of the fish for long-term survival in air is elucidated. Results of the present study may be useful to understand the redox metabolism in muscle of fishes those are exposed to air in general and air breathing fishes in particular.