Abstract

In a recent work, authors prove a yet another no-go theorem that forbids the existence of a universal probabilistic quantum protocol producing a superposition of two unknown quantum states. In this short note, we show that in the presence of closed time like curves, one can indeed create superposition of unknown quantum states and evade the no-go result.

Abstract

We find a single parameter family of genuinely entangled three qubit pure states, called the maximally Bell inequality violating states (MBV), which exhibit maximum Bell inequality violation by the reduced bipartite system for a fixed amount of genuine tripartite entanglement quantified by the so called tangle measure. This in turn implies that there holds a complementary relation between the Bell inequality violation by the reduced bipartite systems and the tangle present in the three qubit states, not necessarily pure. The MBV states also exhibit maximum Bell inequality violation by the reduced bipartite systems of the three qubit pure states with a fixed amount of genuine tripartite correlation quantified by the generalized geometric measure, a genuine entanglement measure of multiparty pure states, and the discord monogamy score, a multipartite quantum correlation measure from information theoretic paradigm. The aforementioned complementary relation has also been established for three qubit pure states for the generalized geometric measure and the discord monogamy score respectively. The complementarity between the Bell inequality violation by the reduced bipartite systems and the genuine tripartite correlation suggests that the Bell inequality violation in the reduced two qubit system comes at the cost of the total tripartite correlation present in the entire system.

Abstract

In this paper we design and implement an algorithm for finding the biconnected components of a given graph. Our algorithm is based on experimental evidence that finding the bridges of a graph is usually easier and faster in the parallel setting. We use this property to first decompose the graph into independent and maximal 2-edge-connected subgraphs. To identify the articulation points in these 2-edge connected subgraphs, we again convert this into a problem of finding the bridges on an auxiliary graph. It is interesting to note that during the conversion process, the size of the graph may increase. However, we show that this small increase in size and the run time is offset by the consideration that finding bridges is easier in a parallel setting. We implement our algorithm on an Intel i7 980X CPU running 12 threads. We show that our algorithm is on average 2.45 x faster than the best known current algorithms implemented on the same platform. Finally, we extend our approach to dense graphs by applying the sparsification technique suggested by Cong and Bader

Abstract

Computing metrics on nodes of a graph is an essential step in understanding the properties of the graph. Pagerank is one such metric that is popular and is being used to measure the importance of nodes in not only web graphs but also in social networks, biological networks, road networks, and the like. The core of the computation of pagerank can be seen as an iterative approach that updates the pageranks of nodes until the values converge.

Abstract

Parallel graph algorithms continue to attract a lot of research attention given their applications to several fields of sciences and engineering. Efficient design and implementation of graph algorithms on modern manycore accelerators has to however contend with a host of challenges including not being able to reach full memory system throughput and irregularity. Of late, focusing on real-world graphs, researchers are addressing these challenges by using decomposition and preprocessing techniques guided by the structural properties of such graphs. In this direction, we present a new GPU algorithm for obtaining an ear decomposition of a graph. Our implementation of the proposed algorithm on an NVidia Tesla K40c improves the state-of-the-art by a factor of 2.3x on average on a collection of real-world and synthetic graphs. The improved performance of our algorithm is due to our proposed characterization that identifies edges of the graph as redundant for the purposes of an ear decomposition. We then study an application of the ear decomposition of a graph in computing the betweenness-centrality values of nodes in the graph. We use an ear decomposition of the input graph to systematically remove nodes of degree two. The actual computation of betweenness-centrality is done on the remaining nodes and the results are extended to nodes removed in the previous step. We show that this approach improves the state-of-the-art for computing betweenness-centrality on an NVidia K40c GPU by a factor of 1.9x on average over a collection of real-world graphs.

Abstract

This paper extends recent work on vulnerability extrapolation. A surge in vulnerability exploits against old and new softwares, urges the importance of detection of vulnerabilities and possible attacks prior to the attacker. How sophisticated an exploit may be, an underlying prerequisite remains to be the presence of at least one memory corruption bug, serving as entry point for the exploit. Therefore several rigorous software testing techniques are borrowed to detect and eliminate software bugs as early as possible. Code similarity based bug detection is one of such techniques, which, in the parlance of software security, is also termed as vulnerability extrapolation. In this paper, we present a source code similarity based bug identification technique by considering code features that are relevant for security related bugs. Our technique works by enriching (augmenting) abstract syntax trees (ASTs) of functions by considering security relevant properties of the code. We show the effectiveness of the augmented AST based similarity approach over existing methods by evaluating proposed method on real-world applications.

Abstract

Consider a synchronous distributed network which is partly controlled by an adversary. In a Perfectly Secret Message Transmission(PSMT) protocol, the sender S wishes to transmit a message to the receiver R such that the adversary learns nothing about the message. We characterize the set of directed graphs that admit PSMT protocols tolerating a dual failure model where up to tp nodes are passively corrupted and further up to any tf nodes may fail.

Abstract

Software quality has always been an important criterion for assessing stability of a product. It is quite challenging for large-scale complex products, especially integrated products, to endure and withstand the competition after a new version release in its market domain. Unlike regular software, integrated software products require detailed exploration on the spread and impact of a defect to improve overall product quality. In this paper, we use heuristic approaches like generalized defect dependency approach, control flow graph based approach, and feature correlation based approach to study the widespread of defects in large software and suggest a metric called defect dependency metric to study the dependency of defects. We implemented the generalized defect dependency approach on an industry dataset and gathered noteworthy results. We provide a comparative a study of the heuristic approaches …

Abstract

Software engineering activities like code reviews, change management, knowledge management, issue tracking, etc. tend to be heavily process oriented. Gamification of such activities by composing the core activities with game design elements like badges and points can increase developers' interest in performing such activities. While there are various frameworks/applications that assist in gamification, extending the frameworks to add any/all desired game design elements has not been adequately addressed. In this paper, we propose an extensible architectural framework for gamification of software engineering activities where in the game design elements are modeled as services. We create an example instance of our framework by building a prototype for code review activity and note the challenges of designing such an extensible architectural framework. The example instance uses python's Flask micro …

Abstract

Energy efficiency is an area of growing importance in datacenters. While the energy proportionality wall poses a challenge to further improve the dynamic power range of servers, heterogeneous systems offer a new opportunity to achieve higher energy efficiency by improving the match between application workload demands on the large heterogeneous system configuration space. This paper proposes a model-driven energy proportionality analysis of heterogeneous clusters consisting of server nodes with different performance-to-power ratio (PPR). Our analysis shows that inter-node heterogeneity has a positive effect of scaling the energy proportionality wall by exposing configurations with sub-linear energy proportionality. Secondly, analysis of these sub-linear configurations on the 95th percentile response time shows that heterogeneity is beneficial in workloads where the PPR of wimpy nodes is higher than brawny nodes.