OpenRaiser/Intern-Atlas huggingface dataset:
Evaluation of Computability Criterions for Runtime Web Service Integration
Venue: arXiv cs.SE 2011
Year: 2011

Today's competitive environment drives the enterprises to extend their focus and collaborate with their business partners to carry out the necessities. Tight coordination among business partners assists to share and integrate the service logic globally. But integrating service logics across diverse enterprises leads to exponential problem which stipulates developers to comprehend the whole service and must resolve suitable method to integrate the services. It is complex and time-consuming task. So the present focus is to have a mechanized system to analyze the Business logics and convey the proper mode to integrate them. There is no standard model to undertake these issues and one such a framework proposed in this paper examines the Business logics individually and suggests proper structure to integrate them. One of the innovative concepts of proposed model is Property Evaluation System which scrutinizes the service logics and generates Business Logic Property Schema (BLPS) for the required services. BLPS holds necessary information to recognize the correct structure for integrating the service logics. At the time of integration, System consumes this BLPS schema and suggests the feasible ways to integrate the service logics. Also if the service logics are attempted to integrate in invalid structure or attempted to violate accessibility levels, system will throw exception with necessary information. This helps developers to ascertain the efficient structure to integrate the services with least effort.
Near Linear-Work Parallel SDD Solvers, Low-Diameter Decomposition, and Low-Stretch Subgraphs
Venue: arXiv cs.DS 2011
Year: 2011

We present the design and analysis of a near linear-work parallel algorithm for solving symmetric diagonally dominant (SDD) linear systems. On input of a SDD $n$-by-$n$ matrix $A$ with $m$ non-zero entries and a vector $b$, our algorithm computes a vector $\tilde{x}$ such that $\norm[A]{\tilde{x} - A^+b} \leq \vareps \cdot \norm[A]{A^+b}$ in $O(m\log^{O(1)}{n}\log{\frac1ε})$ work and $O(m^{1/3+θ}\log \frac1ε)$ depth for any fixed $θ> 0$. The algorithm relies on a parallel algorithm for generating low-stretch spanning trees or spanning subgraphs. To this end, we first develop a parallel decomposition algorithm that in polylogarithmic depth and $\otilde(|E|)$ work, partitions a graph into components with polylogarithmic diameter such that only a small fraction of the original edges are between the components. This can be used to generate low-stretch spanning trees with average stretch $O(n^α)$ in $O(n^{1+α})$ work and $O(n^α)$ depth. Alternatively, it can be used to generate spanning subgraphs with polylogarithmic average stretch in $\otilde(|E|)$ work and polylogarithmic depth. We apply this subgraph construction to derive a parallel linear system solver. By using this solver in known applications, our results imply improved parallel randomized algorithms for several problems, including single-source shortest paths, maximum flow, minimum-cost flow, and approximate maximum flow.
Widescope - A social platform for serious conversations on the Web
Venue: arXiv cs.SI 2011
Year: 2011

There are several web platforms that people use to interact and exchange ideas, such as social networks like Facebook, Twitter, and Google+; Q&A sites like Quora and Yahoo! Answers; and myriad independent fora. However, there is a scarcity of platforms that facilitate discussion of complex subjects where people with divergent views can easily rationalize their points of view using a shared knowledge base, and leverage it towards shared objectives, e.g. to arrive at a mutually acceptable compromise. In this paper, as a first step, we present Widescope, a novel collaborative web platform for catalyzing shared understanding of the US Federal and State budget debates in order to help users reach data-driven consensus about the complex issues involved. It aggregates disparate sources of financial data from different budgets (i.e. from past, present, and proposed) and presents a unified interface using interactive visualizations. It leverages distributed collaboration to encourage exploration of ideas and debate. Users can propose budgets ab-initio, support existing proposals, compare between different budgets, and collaborate with others in real time. We hypothesize that such a platform can be useful in bringing people's thoughts and opinions closer. Toward this, we present preliminary evidence from a simple pilot experiment, using triadic voting (which we also formally analyze to show that is better than hot-or-not voting), that 5 out of 6 groups of users with divergent views (conservatives vs liberals) come to a consensus while aiming to halve the deficit using Widescope. We believe that tools like Widescope could have a positive impact on other complex, data-driven social issues.
Adaptive Subcarrier and Bit Allocation for Downlink OFDMA System with Proportional Fairness
Venue: arXiv cs.NI 2011
Year: 2011

This paper investigates the adaptive subcarrier and bit allocation algorithm for OFDMA systems. To minimize overall transmitted power, we propose a novel adaptive subcarrier and bit allocation algorithm based on channel state information (CSI) and quality state information (QSI). A suboptimal approach that separately performs subcarrier allocation and bit loading is proposed. It is shown that a near optimal solution is obtained by the proposed algorithm which has low complexity compared to that of other conventional algorithm. We will study the problem of finding an optimal sub-carrier and power allocation strategy for downlink communication to multiple users in an OFDMA based wireless system. Assuming knowledge of the instantaneous channel gains for all users, we propose a multiuser OFDMA subcarrier, and bit allocation algorithm to minimize the total transmit power. This is done by assigning each user a set of subcarriers and by determining the number of bits and the transmit power level for each subcarrier. The objective is to minimize the total transmitted power over the entire network to satisfy the application layer and physical layer. We formulate this problem as a constrained optimization problem and present centralized algorithms. The simulation results will show that our approach results in an efficient assignment of subcarriers and transmitter power levels in terms of the energy required for transmitting each bit of information, to address this need, we also present a bit loading algorithm for allocating subcarriers and bits in order to satisfy the rate requirements of the links.
Minimum Process Coordinated Checkpointing Scheme for Ad Hoc Networks
Venue: arXiv cs.DC 2011
Year: 2011

The wireless mobile ad hoc network (MANET) architecture is one consisting of a set of mobile hosts capable of communicating with each other without the assistance of base stations. This has made possible creating a mobile distributed computing environment and has also brought several new challenges in distributed protocol design. In this paper, we study a very fundamental problem, the fault tolerance problem, in a MANET environment and propose a minimum process coordinated checkpointing scheme. Since potential problems of this new environment are insufficient power and limited storage capacity, the proposed scheme tries to reduce the amount of information saved for recovery. The MANET structure used in our algorithm is hierarchical based. The scheme is based for Cluster Based Routing Protocol (CBRP) which belongs to a class of Hierarchical Reactive routing protocols. The protocol proposed by us is nonblocking coordinated checkpointing algorithm suitable for ad hoc environments. It produces a consistent set of checkpoints; the algorithm makes sure that only minimum number of nodes in the cluster are required to take checkpoints; it uses very few control messages. Performance analysis shows that our algorithm outperforms the existing related works and is a novel idea in the field. Firstly, we describe an organization of the cluster. Then we propose a minimum process coordinated checkpointing scheme for cluster based ad hoc routing protocols.
On the Throughput Capacity of Wireless Multi-hop Networks with ALOHA, Node Coloring and CSMA
Venue: arXiv cs.NI 2011
Year: 2011

We quantify the throughput capacity of wireless multi-hop networks with several medium access schemes. We analyze pure ALOHA scheme where simultaneous transmitters are dispatched according to a uniform Poisson distribution and exclusion schemes where simultaneous transmitters are dispatched according to an exclusion rule such as node coloring and carrier sense based schemes. We consider both no-fading and standard Rayleigh fading channel models. Our results show that, under no-fading, slotted ALOHA can achieve at least one-third (or half under Rayleigh fading) of the throughput capacity of node coloring scheme whereas carrier sense based scheme can achieve almost the same throughput capacity as node coloring.
Complexity of Counting CSP with Complex Weights
Venue: arXiv cs.CC 2011
Year: 2011

We give a complexity dichotomy theorem for the counting Constraint Satisfaction Problem (#CSP in short) with complex weights. To this end, we give three conditions for its tractability. Let F be any finite set of complex-valued functions, then we prove that #CSP(F) is solvable in polynomial time if all three conditions are satisfied; and is #P-hard otherwise. Our complexity dichotomy generalizes a long series of important results on counting problems: (a) the problem of counting graph homomorphisms is the special case when there is a single symmetric binary function in F; (b) the problem of counting directed graph homomorphisms is the special case when there is a single not-necessarily-symmetric binary function in F; and (c) the standard form of #CSP is when all functions in F take values in {0,1}.
Probabilistic Analysis of Onion Routing in a Black-box Model
Venue: arXiv cs.CR 2011
Year: 2011

We perform a probabilistic analysis of onion routing. The analysis is presented in a black-box model of anonymous communication in the Universally Composable framework that abstracts the essential properties of onion routing in the presence of an active adversary that controls a portion of the network and knows all a priori distributions on user choices of destination. Our results quantify how much the adversary can gain in identifying users by exploiting knowledge of their probabilistic behavior. In particular, we show that, in the limit as the network gets large, a user u's anonymity is worst either when the other users always choose the destination u is least likely to visit or when the other users always choose the destination u chooses. This worst-case anonymity with an adversary that controls a fraction b of the routers is shown to be comparable to the best-case anonymity against an adversary that controls a fraction \surdb.
Testing the Connectivity of Networks
Venue: arXiv cs.DS 2011
Year: 2011

In this article we discuss general strategies and computer algorithms to test the connectivity of unstructured networks which consist of a number of segments connected through randomly distributed nodes.
A Security Architecture for Data Aggregation and Access Control in Smart Grids
Venue: arXiv cs.NI 2011
Year: 2011

We propose an integrated architecture for smart grids, that supports data aggregation and access control. Data can be aggregated by home area network, building area network and neighboring area network in such a way that the privacy of customers is protected. We use homomorphic encryption technique to achieve this. The consumer data that is collected is sent to the substations where it is monitored by remote terminal units (RTU). The proposed access control mechanism gives selective access to consumer data stored in data repositories and used by different smart grid users. Users can be maintenance units, utility centers, pricing estimator units or analyzing and prediction groups. We solve this problem of access control using cryptographic technique of attribute-based encryption. RTUs and users have attributes and cryptographic keys distributed by several key distribution centers (KDC). RTUs send data encrypted under a set of attributes. Users can decrypt information provided they have valid attributes. The access control scheme is distributed in nature and does not rely on a single KDC to distribute keys. Bobba \emph{et al.} \cite{BKAA09} proposed an access control scheme, which relies on a centralized KDC and is thus prone to single-point failure. The other requirement is that the KDC has to be online, during data transfer which is not required in our scheme. Our access control scheme is collusion resistant, meaning that users cannot collude and gain access to data, when they are not authorized to access. We theoretically analyze our schemes and show that the computation overheads are low enough to be carried out in smart grids. To the best of our knowledge, ours is the first work on smart grids, which integrates these two important security components (privacy preserving data aggregation and access control) and presents an overall security architecture in smart grids.
Power Allocation for Outage Minimization in Cognitive Radio Networks with Limited Feedback
Venue: arXiv cs.IT 2011
Year: 2011

We address an optimal transmit power allocation problem that minimizes the outage probability of a secondary user (SU) who is allowed to coexist with a primary user (PU) in a narrowband spectrum sharing cognitive radio network, under a long term average transmit power constraint at the secondary transmitter (SU-TX) and an average interference power constraint at the primary receiver (PU-RX), with quantized channel state information (CSI) (including both the channels from SU-TX to SU-RX, denoted as $g_1$ and the channel from SU-TX to PU-RX, denoted as $g_0$) at the SU-TX. The optimal quantization regions in the vector channel space is shown to have a 'stepwise' structure. With this structure, the above outage minimization problem can be explicitly formulated and solved by employing the Karush-Kuhn-Tucker (KKT) necessary optimality conditions to obtain a locally optimal quantized power codebook. A low-complexity near-optimal quantized power allocation algorithm is derived for the case of large number of feedback bits. An explicit expression for the asymptotic SU outage probability at high rate quantization (as the number of feedback bits goes to infinity) is also provided, and is shown to approximate the optimal outage behavior extremely well for large number of bits of feedback via numerical simulations. Numerical results also illustrate that with 6 bits of feedback, the derived algorithms provide SU outage performance very close to that with full CSI at the SU-TX.
A Novel Approach for Web Page Set Mining
Venue: arXiv cs.DB 2011
Year: 2011

The one of the most time consuming steps for association rule mining is the computation of the frequency of the occurrences of itemsets in the database. The hash table index approach converts a transaction database to an hash index tree by scanning the transaction database only once. Whenever user requests for any Uniform Resource Locator (URL), the request entry is stored in the Log File of the server. This paper presents the hash index table structure, a general and dense structure which provides web page set extraction from Log File of server. This hash table provides information about the original database. Web Page set mining (WPs-Mine) provides a complete representation of the original database. This approach works well for both sparse and dense data distributions. Web page set mining supported by hash table index shows the performance always comparable with and often better than algorithms accessing data on flat files. Incremental update is feasible without reaccessing the original transactional database.
Cryptanalysis of Song's advanced smart card based password authentication protocol
Venue: arXiv cs.CR 2011
Year: 2011

Song \cite{Song10} proposed very recently a password-based authentication and key establishment protocol using smart cards which attempts to solve some weaknesses found in a previous scheme suggested by Xu, Zhu, and Feng \cite{XZF09}. In this paper, we present attacks on the improved protocol, showing that it fails to achieve the claimed security goals.
Cyclotomic Constructions of Cyclic Codes with Length Being the Product of Two Primes
Venue: arXiv cs.IT 2011
Year: 2011

Cyclic codes are an interesting type of linear codes and have applications in communication and storage systems due to their efficient encoding and decoding algorithms. They have been studied for decades and a lot of progress has been made. In this paper, three types of generalized cyclotomy of order two and three classes of cyclic codes of length $n_1n_2$ and dimension $(n_1n_2+1)/2$ are presented and analysed, where $n_1$ and $n_2$ are two distinct primes. Bounds on their minimum odd-like weight are also proved. The three constructions produce the best cyclic codes in certain cases.
A coinductive semantics of the Unlimited Register Machine
Venue: arXiv cs.LO 2011
Year: 2011

We exploit (co)inductive specifications and proofs to approach the evaluation of low-level programs for the Unlimited Register Machine (URM) within the Coq system, a proof assistant based on the Calculus of (Co)Inductive Constructions type theory. Our formalization allows us to certify the implementation of partial functions, thus it can be regarded as a first step towards the development of a workbench for the formal analysis and verification of both converging and diverging computations.
A multiprecision matrix calculation library and its extension library for a matrix-product-state simulation of quantum computing
Venue: arXiv cs.MS 2011
Year: 2011

A C++ library, named ZKCM, has been developed for the purpose of multiprecision matrix calculations, which is based on the GNU MP and MPFR libraries. It is especially convenient for writing programs involving tensor-product operations, tracing-out operations, and singular-value decompositions. Its extension library, ZKCM_QC, for simulating quantum computing has been developed using the time-dependent matrix-product-state simulation method. This report gives a brief introduction to the libraries with sample programs.
Proving the power of postselection
Venue: arXiv cs.CC 2011
Year: 2011

It is a widely believed, though unproven, conjecture that the capability of postselection increases the language recognition power of both probabilistic and quantum polynomial-time computers. It is also unknown whether polynomial-time quantum machines with postselection are more powerful than their probabilistic counterparts with the same resource restrictions. We approach these problems by imposing additional constraints on the resources to be used by the computer, and are able to prove for the first time that postselection does augment the computational power of both classical and quantum computers, and that quantum does outperform probabilistic in this context, under simultaneous time and space bounds in a certain range. We also look at postselected versions of space-bounded classes, as well as those corresponding to error-free and one-sided error recognition, and provide classical characterizations. It is shown that $\mathsf{NL}$ would equal $\mathsf{RL}$ if the randomized machines had the postselection capability.
On the Derivation of Optimal Partial Successive Interference Cancellation
Venue: arXiv cs.IT 2011
Year: 2011

The necessity of accurate channel estimation for Successive and Parallel Interference Cancellation is well known. Iterative channel estimation and channel decoding (for instance by means of the Expectation-Maximization algorithm) is particularly important for these multiuser detection schemes in the presence of time varying channels, where a high density of pilots is necessary to track the channel. This paper designs a method to analytically derive a weighting factor $α$, necessary to improve the efficiency of interference cancellation in the presence of poor channel estimates. Moreover, this weighting factor effectively mitigates the presence of incorrect decisions at the output of the channel decoder. The analysis provides insight into the properties of such interference cancellation scheme and the proposed approach significantly increases the effectiveness of Successive Interference Cancellation under the presence of channel estimation errors, which leads to gains of up to 3 dB.
Effective Ways of Secure, Private and Trusted Cloud Computing
Venue: arXiv cs.DC 2011
Year: 2011

Cloud computing is an Internet-based computing, where shared resources, software and information, are provided to computers and devices on-demand. It provides people the way to share distributed resources and services that belong to different organization. Since cloud computing uses distributed resources in open environment, thus it is important to provide the security and trust to share the data for developing cloud computing applications. In this paper we assess how can cloud providers earn their customers' trust and provide the security, privacy and reliability, when a third party is processing sensitive data in a remote machine located in various countries? A concept of utility cloud has been represented to provide the various services to the users. Emerging technologies can help address the challenges of Security, Privacy and Trust in cloud computing.
Salt-and-Pepper Noise Removal Based on Sparse Signal Processing
Venue: arXiv cs.IT 2011
Year: 2011

In this paper, we propose a new method for Salt-and-Pepper noise removal from images. Whereas most of the existing methods are based on Ordered Statistics filters, our method is based on the growing theory of Sparse Signal Processing. In other words, we convert the problem of denoising into a sparse signal reconstruction problem which can be dealt with the corresponding techniques. As a result, the output image of our method is preserved from the undesirable opacity which is a disadvantage of most of the other methods. We also introduce an efficient reconstruction algorithm which will be used in our method. Simulation results indicate that our method outperforms the other best-known methods both in term of PSNR and visual criterion. Furthermore, our method can be easily used for reconstruction of missing samples in erasure channels.
Mining Biclusters of Similar Values with Triadic Concept Analysis
Venue: arXiv cs.DS 2011
Year: 2011

Biclustering numerical data became a popular data-mining task in the beginning of 2000's, especially for analysing gene expression data. A bicluster reflects a strong association between a subset of objects and a subset of attributes in a numerical object/attribute data-table. So called biclusters of similar values can be thought as maximal sub-tables with close values. Only few methods address a complete, correct and non redundant enumeration of such patterns, which is a well-known intractable problem, while no formal framework exists. In this paper, we introduce important links between biclustering and formal concept analysis. More specifically, we originally show that Triadic Concept Analysis (TCA), provides a nice mathematical framework for biclustering. Interestingly, existing algorithms of TCA, that usually apply on binary data, can be used (directly or with slight modifications) after a preprocessing step for extracting maximal biclusters of similar values.