OpenRaiser/Intern-Atlas huggingface dataset:
An Improved Sub-Packetization Bound for Minimum Storage Regenerating Codes
Venue: arXiv cs.IT 2013
Year: 2013

Distributed storage systems employ codes to provide resilience to failure of multiple storage disks. Specifically, an $(n, k)$ MDS code stores $k$ symbols in $n$ disks such that the overall system is tolerant to a failure of up to $n-k$ disks. However, access to at least $k$ disks is still required to repair a single erasure. To reduce repair bandwidth, array codes are used where the stored symbols or packets are vectors of length $\ell$. MDS array codes have the potential to repair a single erasure using a fraction $1/(n-k)$ of data stored in the remaining disks. We introduce new methods of analysis which capitalize on the translation of the storage system problem into a geometric problem on a set of operators and subspaces. In particular, we ask the following question: for a given $(n, k)$, what is the minimum vector-length or sub-packetization factor $\ell$ required to achieve this optimal fraction? For \emph{exact recovery} of systematic disks in an MDS code of low redundancy, i.e. $k/n > 1/2$, the best known explicit codes \cite{WTB12} have a sub-packetization factor $\ell$ which is exponential in $k$. It has been conjectured \cite{TWB12} that for a fixed number of parity nodes, it is in fact necessary for $\ell$ to be exponential in $k$. In this paper, we provide a new log-squared converse bound on $k$ for a given $\ell$, and prove that $k \le 2\log_2\ell\left(\log_δ\ell+1\right)$, for an arbitrary number of parity nodes $r = n-k$, where $δ= r/(r-1)$.
Wavelet Based Authentication/Secret Transmission Through Image Resizing(WASTIR)
Venue: arXiv cs.CR 2013
Year: 2013

The paper is aimed for a wavelet based steganographic or watermarking technique in frequency domain termed as WASTIR for secret message or image transmission or image authentication. Number system conversion of the secret image by changing radix form decimal to quaternary is the pre-processing of the technique. Cover image scaling through inverse discrete wavelet transformation with false Horizontal and vertical coefficients are embedded with quaternary digits through hash function and a secret key. Experimental results are computed and compared with the existing steganographic techniques like WTSIC, Yuancheng Lis Method and Region-Based in terms of Mean Square Error (MSE), Peak Signal to Noise Ratio (PSNR) and Image Fidelity (IF) which show better performances in WASTIR.
A fast randomized Kaczmarz algorithm for sparse solutions of consistent linear systems
Venue: arXiv cs.NA 2013
Year: 2013

The Kaczmarz algorithm is a popular solver for overdetermined linear systems due to its simplicity and speed. In this paper, we propose a modification that speeds up the convergence of the randomized Kaczmarz algorithm for systems of linear equations with sparse solutions. The speedup is achieved by projecting every iterate onto a weighted row of the linear system while maintaining the random row selection criteria of Strohmer and Vershynin. The weights are chosen to attenuate the contribution of row elements that lie outside of the estimated support of the sparse solution. While the Kaczmarz algorithm and its variants can only find solutions to overdetermined linear systems, our algorithm surprisingly succeeds in finding sparse solutions to underdetermined linear systems as well. We present empirical studies which demonstrate the acceleration in convergence to the sparse solution using this modified approach in the overdetermined case. We also demonstrate the sparse recovery capabilities of our approach in the underdetermined case and compare the performance with that of $\ell_1$ minimization.
Analysing the Assumed Benefits of Software Requirements
Venue: arXiv cs.SE 2013
Year: 2013

Often during the requirements engineering (RE) process, the value of a requirement is assessed, e.g., in requirement prioritisation, release planning, and trade-off analysis. In order to support these activities, this research evaluates Goal Oriented Requirements Engineering (GORE) methods for the description of a requirement's value. Specifically, we investigate the goal-to-goal contribution relationship for its ability to demonstrate the value of a requirement, and propose that it is enriched with concepts such as correlation, confidence, and utility.
Analysis Of Interest Points Of Curvelet Coefficients Contributions Of Microscopic Images And Improvement Of Edges
Venue: arXiv cs.CV 2013
Year: 2013

This paper focuses on improved edge model based on Curvelet coefficients analysis. Curvelet transform is a powerful tool for multiresolution representation of object with anisotropic edge. Curvelet coefficients contributions have been analyzed using Scale Invariant Feature Transform (SIFT), commonly used to study local structure in images. The permutation of Curvelet coefficients from original image and edges image obtained from gradient operator is used to improve original edges. Experimental results show that this method brings out details on edges when the decomposition scale increases.
An exponential lower bound for Cunningham's rule
Venue: arXiv cs.CC 2013
Year: 2013

In this paper we give an exponential lower bound for Cunningham's least recently considered (round-robin) rule as applied to parity games, Markhov decision processes and linear programs. This improves a recent subexponential bound of Friedmann for this rule on these problems. The round-robin rule fixes a cyclical order of the variables and chooses the next pivot variable starting from the previously chosen variable and proceeding in the given circular order. It is perhaps the simplest example from the class of history-based pivot rules. Our results are based on a new lower bound construction for parity games. Due to the nature of the construction we are also able to obtain an exponential lower bound for the round-robin rule applied to acyclic unique sink orientations of hypercubes (AUSOs). Furthermore these AUSOs are realizable as polytopes. We believe these are the first such results for history based rules for AUSOs, realizable or not. The paper is self-contained and requires no previous knowledge of parity games.
Two-Hop Interference Channels: Impact of Linear Time-Varying Schemes
Venue: arXiv cs.IT 2013
Year: 2013

We consider the two-hop interference channel (IC) with constant real channel coefficients, which consists of two source-destination pairs, separated by two relays. We analyze the achievable degrees of freedom (DoF) of such network when relays are restricted to perform scalar amplify-forward (AF) operations, with possibly time-varying coefficients. We show that, somewhat surprisingly, by providing the flexibility of choosing time-varying AF coefficients at the relays, it is possible to achieve 4/3 sum-DoF. We also develop a novel outer bound that matches our achievability, hence characterizing the sum-DoF of two-hop interference channels with time-varying AF relaying strategies.
Reducing Revenue to Welfare Maximization: Approximation Algorithms and other Generalizations
Venue: arXiv cs.GT 2013
Year: 2013

It was recently shown in [http://arxiv.org/abs/1207.5518] that revenue optimization can be computationally efficiently reduced to welfare optimization in all multi-dimensional Bayesian auction problems with arbitrary (possibly combinatorial) feasibility constraints and independent additive bidders with arbitrary (possibly combinatorial) demand constraints. This reduction provides a poly-time solution to the optimal mechanism design problem in all auction settings where welfare optimization can be solved efficiently, but it is fragile to approximation and cannot provide solutions to settings where welfare maximization can only be tractably approximated. In this paper, we extend the reduction to accommodate approximation algorithms, providing an approximation preserving reduction from (truthful) revenue maximization to (not necessarily truthful) welfare maximization. The mechanisms output by our reduction choose allocations via black-box calls to welfare approximation on randomly selected inputs, thereby generalizing also our earlier structural results on optimal multi-dimensional mechanisms to approximately optimal mechanisms. Unlike [http://arxiv.org/abs/1207.5518], our results here are obtained through novel uses of the Ellipsoid algorithm and other optimization techniques over {\em non-convex regions}.
Understanding Incentives: Mechanism Design becomes Algorithm Design
Venue: arXiv cs.GT 2013
Year: 2013

We provide a computationally efficient black-box reduction from mechanism design to algorithm design in very general settings. Specifically, we give an approximation-preserving reduction from truthfully maximizing \emph{any} objective under \emph{arbitrary} feasibility constraints with \emph{arbitrary} bidder types to (not necessarily truthfully) maximizing the same objective plus virtual welfare (under the same feasibility constraints). Our reduction is based on a fundamentally new approach: we describe a mechanism's behavior indirectly only in terms of the expected value it awards bidders for certain behavior, and never directly access the allocation rule at all. Applying our new approach to revenue, we exhibit settings where our reduction holds \emph{both ways}. That is, we also provide an approximation-sensitive reduction from (non-truthfully) maximizing virtual welfare to (truthfully) maximizing revenue, and therefore the two problems are computationally equivalent. With this equivalence in hand, we show that both problems are NP-hard to approximate within any polynomial factor, even for a single monotone submodular bidder. We further demonstrate the applicability of our reduction by providing a truthful mechanism maximizing fractional max-min fairness. This is the first instance of a truthful mechanism that optimizes a non-linear objective.
Data Quality Principles in the Semantic Web
Venue: arXiv cs.DL 2013
Year: 2013

The increasing size and availability of web data make data quality a core challenge in many applications. Principles of data quality are recognized as essential to ensure that data fit for their intended use in operations, decision-making, and planning. However, with the rise of the Semantic Web, new data quality issues appear and require deeper consideration. In this paper, we propose to extend the data quality principles to the context of Semantic Web. Based on our extensive industrial experience in data integration, we identify five main classes suited for data quality in Semantic Web. For each class, we list the principles that are involved at all stages of the data management process. Following these principles will provide a sound basis for better decision-making within organizations and will maximize long-term data integration and interoperability.
Font Acknowledgment and Character Extraction of Digital and Scanned Images
Venue: arXiv cs.CV 2013
Year: 2013

The font recognition and character extraction is of immense importance as these are many scenarios where data are in such a form, which cannot be processed like in image form or as a hard copy. So the procedure developed in this paper is basically related to identifying the font (Times New Roman, Arial and Comic Sans MS) and afterwards recovering the text using simple correlation based method where the binary templates are correlated to the input image text characters. All of this extraction is done in the presence of a little noise as images may have noisy patterns due to photocopying. The significance of this method exists in extraction of data from various monitoring (Surveillance) camera footages or even more. The method is developed on Matlab\c{opyright} which takes input image and recovers text and font information from it in a text file.
Using Bias Optimization for Reversible Data Hiding Using Image Interpolation
Venue: arXiv cs.MM 2013
Year: 2013

In this paper, we propose a reversible data hiding method in the spatial domain for compressed grayscale images. The proposed method embeds secret bits into a compressed thumbnail of the original image by using a novel interpolation method and the Neighbour Mean Interpolation (NMI) technique as scaling up to the original image occurs. Experimental results presented in this paper show that the proposed method has significantly improved embedding capacities over the approach proposed by Jung and Yoo.
Mobile Network Anomaly Detection and Mitigation: The NEMESYS Approach
Venue: arXiv cs.CR 2013
Year: 2013

Mobile malware and mobile network attacks are becoming a significant threat that accompanies the increasing popularity of smart phones and tablets. Thus in this paper we present our research vision that aims to develop a network-based security solution combining analytical modelling, simulation and learning, together with billing and control-plane data, to detect anomalies and attacks, and eliminate or mitigate their effects, as part of the EU FP7 NEMESYS project. These ideas are supplemented with a careful review of the state-of-the-art regarding anomaly detection techniques that mobile network operators may use to protect their infrastructure and secure users against malware.
International Co-authorship Relations in the Social Science Citation Index: Is Internationalization Leading the Network?
Venue: arXiv cs.DL 2013
Year: 2013

We analyze international co-authorship relations in the Social Science Citation Index 2011 using all citable items in the DVD-version of this index. Network statistics indicate four groups of nations: (i) an Asian-Pacific one to which all Anglo-Saxon nations (including the UK and Ireland) are attributed; (ii) a continental European one including also the Latin-American countries; (iii) the Scandinavian nations; and (iv) a community of African nations. Within the EU-28 (including Croatia), eleven of the EU-15 states have dominant positions. Collapsing the EU-28 into a single node leads to a bi-polar structure between the US and EU-28; China is part of the US-pole. We develop an information-theoretical test to distinguish whether international collaborations or domestic collaborations prevail; the results are mixed, but the international dimension is more important than the national one in the aggregated sets (this was found in both SSCI and SCI). In France, however, the national distribution is more important than the international one, while the reverse is true for most European nations in the core group (UK, Germany, the Netherlands, etc.). Decomposition of the USA in terms of states shows a similarly mixed result; more US states are domestically oriented in SSCI, whereas more internationally in SCI. The international networks have grown during the last decades in addition to the national ones, but not by replacing them.
Self-Stabilizing Paxos
Venue: arXiv cs.DC 2013
Year: 2013

We present the first self-stabilizing consensus and replicated state machine for asynchronous message passing systems. The scheme does not require that all participants make a certain number of steps prior to reaching a practically infinite execution where the replicated state machine exhibits the desired behavior. In other words, the system reaches a configuration from which it operates according to the specified requirements of the replicated state-machine, for a long enough execution regarding all practical considerations.
Connected Domatic Packings in Node-capacitated Graphs
Venue: arXiv cs.DS 2013
Year: 2013

A set of vertices in a graph is a dominating set if every vertex outside the set has a neighbor in the set. A dominating set is connected if the subgraph induced by its vertices is connected. The connected domatic partition problem asks for a partition of the nodes into connected dominating sets. The connected domatic number of a graph is the size of a largest connected domatic partition and it is a well-studied graph parameter with applications in the design of wireless networks. In this note, we consider the fractional counterpart of the connected domatic partition problem in \emph{node-capacitated} graphs. Let $n$ be the number of nodes in the graph and let $k$ be the minimum capacity of a node separator in $G$. Fractionally we can pack at most $k$ connected dominating sets subject to the capacities on the nodes, and our algorithms construct packings whose sizes are proportional to $k$. Some of our main contributions are the following: \begin{itemize} \item An algorithm for constructing a fractional connected domatic packing of size $Ω(k)$ for node-capacitated planar and minor-closed families of graphs. \item An algorithm for constructing a fractional connected domatic packing of size $Ω(k / \ln{n})$ for node-capacitated general graphs. \end{itemize}
Performance Analysis of Parallel Pollard's Rho Algorithm
Venue: arXiv cs.DC 2013
Year: 2013

Integer factorization is one of the vital algorithms discussed as a part of analysis of any black-box cipher suites where the cipher algorithm is based on number theory. The origin of the problem is from Discrete Logarithmic Problem which appears under the analysis of the crypto-graphic algorithms as seen by a crypt-analyst. The integer factorization algorithm poses a potential in computational science too, obtaining the factors of a very large number is challenging with a limited computing infrastructure. This paper analyses the Pollards Rho heuristic with a varying input size to evaluate the performance under a multi-core environment and also to estimate the threshold for each computing infrastructure.
3DES ECB Optimized for Massively Parallel CUDA GPU Architecture
Venue: arXiv cs.DC 2013
Year: 2013

Modern computers have graphics cards with much higher theoretical efficiency than conventional CPU. The paper presents application possibilities GPU CUDA acceleration for encryption of data using the new architecture tailored to the 3DES algorithm, characterized by increased security compared to the normal DES. The algorithm used in ECB mode (Electronic Codebook), in which 64-bit data blocks are encrypted independently by stream processors (CUDA cores).
Reliability-based Error Detection for Feedback Communication with Low Latency
Venue: arXiv cs.IT 2013
Year: 2013

This paper presents a reliability-based decoding scheme for variable-length coding with feedback and demonstrates via simulation that it can achieve higher rates than Polyanskiy et al.'s random coding lower bound for variable-length feedback (VLF) coding on both the BSC and AWGN channel. The proposed scheme uses the reliability output Viterbi algorithm (ROVA) to compute the word error probability after each decoding attempt, which is compared against a target error threshold and used as a stopping criterion to terminate transmission. The only feedback required is a single bit for each decoding attempt, informing the transmitter whether the ROVA-computed word-error probability is sufficiently low. Furthermore, the ROVA determines whether transmission/decoding may be terminated without the need for a rate-reducing CRC.
Algorithms for Self-Healing Networks
Venue: arXiv cs.DS 2013
Year: 2013

Many modern networks are \emph{reconfigurable}, in the sense that the topology of the network can be changed by the nodes in the network. For example, peer-to-peer, wireless and ad-hoc networks are reconfigurable. More generally, many social networks, such as a company's organizational chart; infrastructure networks, such as an airline's transportation network; and biological networks, such as the human brain, are also reconfigurable. Modern reconfigurable networks have a complexity unprecedented in the history of engineering, resembling more a dynamic and evolving living animal rather than a structure of steel designed from a blueprint. Unfortunately, our mathematical and algorithmic tools have not yet developed enough to handle this complexity and fully exploit the flexibility of these networks. We believe that it is no longer possible to build networks that are scalable and never have node failures. Instead, these networks should be able to admit small, and maybe, periodic failures and still recover like skin heals from a cut. This process, where the network can recover itself by maintaining key invariants in response to attack by a powerful adversary is what we call \emph{self-healing}. Here, we present several fast and provably good distributed algorithms for self-healing in reconfigurable dynamic networks. Each of these algorithms have different properties, a different set of gaurantees and limitations. We also discuss future directions and theoretical questions we would like to answer. %in the final dissertation that this document is proposed to lead to.
Aplicacion de las Redes Neuronales al Reconocimiento de Sistemas Operativos
Venue: arXiv cs.CR 2013
Year: 2013

In this work we present a family of neural networks, the multi-layer perceptron networks, and some of the algorithms used to train those networks (we hope that with enough details and precision as to satisfy a mathematical public). Then we study how to use those networks to solve a problem that arises from the field of information security: the remote identification of Operating Systems (part of the information gathering steps of the penetration testing methodology). This is the contribution of this work: it is an application of classic Artificial Intelligence techniques to a classification problem that gave better results than the classic techniques used to solve it.
A qoi based energy efficient clustering for dense wireless sensor network
Venue: arXiv cs.NI 2013
Year: 2013

In a wireless sensor network Quality of Information (QoI), Energy Efficiency, Redundant data avoidance, congestion control are the important metrics that affect the performance of wireless sensor network. As many approaches were proposed to increase the performance of a wireless sensor network among them clustering is one of the efficient approaches in sensor network. Many clustering algorithms concentrate mainly on power Optimization like FSCH, LEACH, and EELBCRP. There is necessity of the above metrics in wireless sensor network where nodes are densely deployed in a given network area. As the nodes are deployed densely there is maximum possibility of nodes appear in the sensing region of other nodes. So there exists an option that nodes have to send the information that is already reached the base station by its own cluster members or by members of other clusters. This mechanism will affect the QoI, Energy factor and congestion control of the wireless sensor networks. Even though clustering uses TDMA (Time Division Multiple Access) for avoiding congestion control for intra clustering data transmission, but it may fail in some critical situation. This paper proposed a energy efficient clustering which avoid data redundancy in a dense sensor network until the network becomes sparse and hence uses the TDMA efficiently during high density of the nodes.
The Doxastic Interpretation of Team Semantics
Venue: arXiv cs.AI 2013
Year: 2013

We advance a doxastic interpretation for many of the logical connectives considered in Dependence Logic and in its extensions, and we argue that Team Semantics is a natural framework for reasoning about beliefs and belief updates.
Easy identification of generalized common and conserved nested intervals
Venue: arXiv cs.DS 2013
Year: 2013

In this paper we explain how to easily compute gene clusters, formalized by classical or generalized nested common or conserved intervals, between a set of K genomes represented as K permutations. A b-nested common (resp. conserved) interval I of size |I| is either an interval of size 1 or a common (resp. conserved) interval that contains another b-nested common (resp. conserved) interval of size at least |I|-b. When b=1, this corresponds to the classical notion of nested interval. We exhibit two simple algorithms to output all b-nested common or conserved intervals between K permutations in O(Kn+nocc) time, where nocc is the total number of such intervals. We also explain how to count all b-nested intervals in O(Kn) time. New properties of the family of conserved intervals are proposed to do so.