OpenRaiser/Intern-Atlas huggingface dataset:
Analysis of LT Codes with Unequal Recovery Time
Venue: arXiv cs.IT 2012
Year: 2012

In this paper we analyze a specific class of rateless codes, called LT codes with unequal recovery time. These codes provide the option of prioritizing different segments of the transmitted data over other. The result is that segments are decoded in stages during the rateless transmission, where higher prioritized segments are decoded at lower overhead. Our analysis focuses on quantifying the expected amount of received symbols, which are redundant already upon arrival, i.e. all input symbols contained in the received symbols have already been decoded. This analysis gives novel insights into the probabilistic mechanisms of LT codes with unequal recovery time, which has not yet been available in the literature. We show that while these rateless codes successfully provide the unequal recovery time, they do so at a significant price in terms of redundancy in the lower prioritized segments. We propose and analyze a modification where a single intermediate feedback is transmitted, when the first segment is decoded in a code with two segments. Our analysis shows that this modification provides a dramatic improvement on the decoding performance of the lower prioritized segment.
An Efficient Method For Multichannel Wireless Mesh Networks With Pulse Coupled Neural Network
Venue: arXiv cs.NI 2012
Year: 2012

Multi cast communication is a key technology for wireless mesh networks. Multicast provides efficient data distribution among a group of nodes, Generally sensor networks and MANETs uses multicast algorithms which are designed to be energy efficient and to achieve optimal route discovery among mobile nodes whereas wireless mesh networks needs to maximize throughput. Here we propose two multicast algorithms: The Level Channel Assignment (LCA) algorithm and the Multi-Channel Multicast (MCM) algorithm to improve the throughput for multichannel sand multi interface mesh networks. The algorithm builds efficient multicast trees by minimizing the number of relay nodes and total hop count distance of the trees. Shortest path computation is a classical combinatorial optimization problem. Neural networks have been used for processing path optimization problem. Pulse Coupled Neural Networks (PCNNS) suffer from high computational cast for very long paths we propose a new PCNN modal called dual source PCNN (DSPCNN) which can improve the computational efficiency two auto waves are produced by DSPCNN one comes from source neuron and other from goal neuron when the auto waves from these two sources meet the DSPCNN stops and then the shortest path is found by backtracking the two auto waves.
Verification Condition Generation and Variable Conditions in Smallfoot
Venue: arXiv cs.LO 2012
Year: 2012

These notes are a companion to [1] which describe - the variable conditions that Smallfoot checks, - the analysis used to check them, - the algorithm used to compute a set of verification conditions corresponding to an annotated program, and - the treatment of concurrent resource initialization code.
Big-Five Personality Prediction Based on User Behaviors at Social Network Sites
Venue: arXiv cs.CY 2012
Year: 2012

Many customer services are already available at Social Network Sites (SNSs), including user recommendation and media interaction, to name a few. There are strong desires to provide online users more dedicated and personalized services that fit into individual's need, usually strongly depending on the inner personalities of the user. However, little has been done to conduct proper psychological analysis, crucial for explaining the user's outer behaviors from their inner personality. In this paper, we propose an approach that intends to facilitate this line of research by directly predicting the so called Big-Five Personality from user's SNS behaviors. Comparing to the conventional inventory-based psychological analysis, we demonstrate via experimental studies that users' personalities can be predicted with reasonable precision based on their online behaviors. Except for proving some former behavior-personality correlation results, our experiments show that extraversion is positively related to one's status republishing proportion and neuroticism is positively related to the proportion of one's angry blogs (blogs making people angry).
On the Signed (Total) $k$-Domination Number of a Graph
Venue: arXiv cs.DM 2012
Year: 2012

Let $k$ be a positive integer and $G=(V,E)$ be a graph of minimum degree at least $k-1$. A function $f:V\rightarrow \{-1,1\}$ is called a \emph{signed $k$-dominating function} of $G$ if $\sum_{u\in N_G[v]}f(u)\geq k$ for all $v\in V$. The \emph{signed $k$-domination number} of $G$ is the minimum value of $\sum_{v\in V}f(v)$ taken over all signed $k$-dominating functions of $G$. The \emph{signed total $k$-dominating function} and \emph{signed total $k$-domination number} of $G$ can be similarly defined by changing the closed neighborhood $N_G[v]$ to the open neighborhood $N_G(v)$ in the definition. The \emph{upper signed $k$-domination number} is the maximum value of $\sum_{v\in V}f(v)$ taken over all \emph{minimal} signed $k$-dominating functions of $G$. In this paper, we study these graph parameters from both algorithmic complexity and graph-theoretic perspectives. We prove that for every fixed $k\geq 1$, the problems of computing these three parameters are all \NP-hard. We also present sharp lower bounds on the signed $k$-domination number and signed total $k$-domination number for general graphs in terms of their minimum and maximum degrees, generalizing several known results about signed domination.
Improved Balas and Mazzola Linearization for Quadratic 0-1 Programs with Application in a New Cutting Plane Algorithm
Venue: arXiv cs.DS 2012
Year: 2012

Balas and Mazzola linearization (BML) is widely used in devising cutting plane algorithms for quadratic 0-1 programs. In this article, we improve BML by first strengthening the primal formulation of BML and then considering the dual formulation. Additionally, a new cutting plane algorithm is proposed.
On the existence, uniqueness and nature of Caratheodory and Filippov solutions for bimodal piecewise affine dynamical systems
Venue: arXiv cs.SY 2012
Year: 2012

In this paper, we deal with the well-posedness (in the sense of existence and uniqueness of solutions) and nature of solutions for discontinuous bimodal piecewise affine systems in a differential inclusion setting. First, we show that the conditions guaranteeing uniqueness of Filippov solutions in the context of general differential inclusions are quite restrictive when applied to bimodal piecewise affine systems. Later, we present a set of necessary and sufficient conditions for uniqueness of Filippov solutions for bimodal piecewise affine systems. We also study the so-called Zeno behavior (possibility of infinitely many switchings within a finite time interval) for Filippov solutions.
A Polynomial kernel for Proper Interval Vertex Deletion
Venue: arXiv cs.DS 2012
Year: 2012

It is known that the problem of deleting at most k vertices to obtain a proper interval graph (Proper Interval Vertex Deletion) is fixed parameter tractable. However, whether the problem admits a polynomial kernel or not was open. Here, we answers this question in affirmative by obtaining a polynomial kernel for Proper Interval Vertex Deletion. This resolves an open question of van Bevern, Komusiewicz, Moser, and Niedermeier.
Evaluation of the Design Metric to Reduce the Number of Defects in Software Development
Venue: arXiv cs.SE 2012
Year: 2012

Software design is one of the most important and key activities in the system development life cycle (SDLC) phase that ensures the quality of software. Different key areas of design are very vital to be taken into consideration while designing software. Software design describes how the software system is decomposed and managed in smaller components. Object-oriented (OO) paradigm has facilitated software industry with more reliable and manageable software and its design. The quality of the software design can be measured through different metrics such as Chidamber and Kemerer (CK) design metrics, Mood Metrics & Lorenz and Kidd metrics. CK metrics is one of the oldest and most reliable metrics among all metrics available to software industry to evaluate OO design. This paper presents an evaluation of CK metrics to propose an improved CK design metrics values to reduce the defects during software design phase in software. This paper will also describe that whether a significant effect of any CK design metrics exists on total number of defects per module or not. This is achieved by conducting survey in two software development companies.
Hardness of conjugacy and factorization of multidimensional subshifts of finite type
Venue: arXiv cs.DM 2012
Year: 2012

We investigate here the hardness of conjugacy and factorization of subshifts of finite type (SFTs) in dimension $d>1$. In particular, we prove that the factorization problem is $Σ^0_3$-complete and the conjugacy problem $Σ^0_1$-complete in the arithmetical hierarchy.
Objective Function Designing Led by User Preferences Acquisition
Venue: arXiv cs.LG 2012
Year: 2012

Many real world problems can be defined as optimisation problems in which the aim is to maximise an objective function. The quality of obtained solution is directly linked to the pertinence of the used objective function. However, designing such function, which has to translate the user needs, is usually fastidious. In this paper, a method to help user objective functions designing is proposed. Our approach, which is highly interactive, is based on man machine dialogue and more particularly on the comparison of problem instance solutions by the user. We propose an experiment in the domain of cartographic generalisation that shows promising results.
Two simulations about DPLL(T)
Venue: arXiv cs.LO 2012
Year: 2012

In this paper we relate different formulations of the DPLL(T) procedure. The first formulation is based on a system of rewrite rules, which we denote DPLL(T). The second formulation is an inference system of, which we denote LKDPLL(T). The third formulation is the application of a standard proof-search mechanism in a sequent calculus LKp(T) introduced here. We formalise an encoding from DPLL(T) to LKDPLL(T) that was, to our knowledge, never explicitly given and, in the case where DPLL(T) is extended with backjumping and Lemma learning, never even implicitly given. We also formalise an encoding from LKDPLL(T) to LKp(T), building on Ivan Gazeau's previous work: we extend his work in that we handle the "-modulo-Theory" aspect of SAT-modulo-theory, by extending the sequent calculus to allow calls to a theory solver (seen as a blackbox). We also extend his work in that we handle advanced features of DPLL such as backjumping and Lemma learning, etc. Finally, we re fine the approach by starting to formalise quantitative aspects of the simulations: the complexity is preserved (number of steps to build complete proofs). Other aspects remain to be formalised (non-determinism of the search / width of search space).
ILexicOn: toward an ECD-compliant interlingual lexical ontology described with semantic web formalisms
Venue: arXiv cs.CL 2012
Year: 2012

We are interested in bridging the world of natural language and the world of the semantic web in particular to support natural multilingual access to the web of data. In this paper we introduce a new type of lexical ontology called interlingual lexical ontology (ILexicOn), which uses semantic web formalisms to make each interlingual lexical unit class (ILUc) support the projection of its semantic decomposition on itself. After a short overview of existing lexical ontologies, we briefly introduce the semantic web formalisms we use. We then present the three layered architecture of our approach: i) the interlingual lexical meta-ontology (ILexiMOn); ii) the ILexicOn where ILUcs are formally defined; iii) the data layer. We illustrate our approach with a standalone ILexicOn, and introduce and explain a concise human-readable notation to represent ILexicOns. Finally, we show how semantic web formalisms enable the projection of a semantic decomposition on the decomposed ILUc.
Verifying Search Results Over Web Collections
Venue: arXiv cs.CR 2012
Year: 2012

Searching accounts for one of the most frequently performed computations over the Internet as well as one of the most important applications of outsourced computing, producing results that critically affect users' decision-making behaviors. As such, verifying the integrity of Internet-based searches over vast amounts of web contents is essential. We provide the first solution to this general security problem. We introduce the concept of an authenticated web crawler and present the design and prototype implementation of this new concept. An authenticated web crawler is a trusted program that computes a special "signature" $s$ of a collection of web contents it visits. Subject to this signature, web searches can be verified to be correct with respect to the integrity of their produced results. This signature also allows the verification of complicated queries on web pages, such as conjunctive keyword searches. In our solution, along with the web pages that satisfy any given search query, the search engine also returns a cryptographic proof. This proof, together with the signature $s$, enables any user to efficiently verify that no legitimate web pages are omitted from the result computed by the search engine, and that no pages that are non-conforming with the query are included in the result. An important property of our solution is that the proof size and the verification time both depend solely on the sizes of the query description and the query result, but not on the number or sizes of the web pages over which the search is performed. Our authentication protocols are based on standard Merkle trees and the more involved bilinear-map accumulators. As we experimentally demonstrate, the prototype implementation of our system gives a low communication overhead between the search engine and the user, and allows for fast verification of the returned results on the user side.
A new upper bound on the query complexity for testing generalized Reed-Muller codes
Venue: arXiv cs.IT 2012
Year: 2012

Over a finite field $\F_q$ the $(n,d,q)$-Reed-Muller code is the code given by evaluations of $n$-variate polynomials of total degree at most $d$ on all points (of $\F_q^n$). The task of testing if a function $f:\F_q^n \to \F_q$ is close to a codeword of an $(n,d,q)$-Reed-Muller code has been of central interest in complexity theory and property testing. The query complexity of this task is the minimal number of queries that a tester can make (minimum over all testers of the maximum number of queries over all random choices) while accepting all Reed-Muller codewords and rejecting words that are $δ$-far from the code with probability $Ω(δ)$. (In this work we allow the constant in the $Ω$ to depend on $d$.) In this work we give a new upper bound of $(c q)^{(d+1)/q}$ on the query complexity, where $c$ is a universal constant. In the process we also give new upper bounds on the "spanning weight" of the dual of the Reed-Muller code (which is also a Reed-Muller code). The spanning weight of a code is the smallest integer $w$ such that codewords of Hamming weight at most $w$ span the code.
Strategy Independent Reduction Lengths in Rewriting and Binary Arithmetic
Venue: arXiv cs.LO 2012
Year: 2012

In this paper we give a criterion by which one can conclude that every reduction of a basic term to normal form has the same length. As a consequence, the number of steps to reach the normal form is independent of the chosen strategy. In particular this holds for TRSs computing addition and multiplication of natural numbers, both in unary and binary notation.
Rerouting shortest paths in planar graphs
Venue: arXiv cs.DS 2012
Year: 2012

A rerouting sequence is a sequence of shortest st-paths such that consecutive paths differ in one vertex. We study the the Shortest Path Rerouting Problem, which asks, given two shortest st-paths P and Q in a graph G, whether a rerouting sequence exists from P to Q. This problem is PSPACE-hard in general, but we show that it can be solved in polynomial time if G is planar. To this end, we introduce a dynamic programming method for reconfiguration problems.
Analysis of Path-vector Routing Stability
Venue: arXiv cs.NI 2012
Year: 2012

Most studies on path-vector routing stability have been conducted empirically by means of ad-hoc analysis of BGP data traces. None of them consider prior specification of an analytic method including the use of stability measurement metrics for the systematic analysis of BGP traces and associated meta-processing for determining the local state of the routing system. In this paper, we define a set of metrics that characterize the local stability properties of path-vector routing such as BGP (Border Gateway Protocol). By means of these stability metrics, we propose a method to analyze the effects of BGP policy- and protocol-induced instability on local routers.
A new point of NP-hardness for 2-to-1 Label Cover
Venue: arXiv cs.CC 2012
Year: 2012

We show that given a satisfiable instance of the 2-to-1 Label Cover problem, it is NP-hard to find a $(23/24 + \eps)$-satisfying assignment.
Analysis of MMSE Estimation for Compressive Sensing of Block Sparse Signals
Venue: arXiv cs.IT 2012
Year: 2012

Minimum mean square error (MMSE) estimation of block sparse signals from noisy linear measurements is considered. Unlike in the standard compressive sensing setup where the non-zero entries of the signal are independently and uniformly distributed across the vector of interest, the information bearing components appear here in large mutually dependent clusters. Using the replica method from statistical physics, we derive a simple closed-form solution for the MMSE obtained by the optimum estimator. We show that the MMSE is a version of the Tse-Hanly formula with system load and MSE scaled by parameters that depend on the sparsity pattern of the source. It turns out that this is equal to the MSE obtained by a genie-aided MMSE estimator which is informed in advance about the exact locations of the non-zero blocks. The asymptotic results obtained by the non-rigorous replica method are found to have an excellent agreement with finite sized numerical simulations.
Analysis of Various Symbol Detection Techniques in Multiple-Input Multiple-Output System (MIMO)
Venue: arXiv cs.NI 2012
Year: 2012

Wireless communication is the fastest growing area of the communication industry. To keep swiftness with the indefinite increase in customers' demands and expectations, and the market competition among companies for the services offered,there is need for higher data rate along with reliable communication at low cost so that the applications can reach all. Until now, many technical challenges remain in designing robust and fast wireless systems that deliver the performance necessary to support emerging applications, due to the fact that wireless channels are frequency selective, power-limited, susceptible to noise and interference. Demand for high data rate and increasing applications offered by a wireless device calls for an effective method. Due to limit on the available bandwidth, there is a need for exploiting the available bandwidth in a way so that we get maximum advantage. Multiple-Input Multiple-Output system does exactly this thing by multiplying the data rate without any expansion in the bandwidth. This system utilizes the spatial diversity property of the multi channel system. The reliable transmission requires symbols to be effectively recovered at the receiving end. V-BLAST detection technique is employed for this purpose. This paper depicted the advantages of using multiple antennas by exploiting signal diversity offered by multipath effect and the system offers high spectral efficiency.
Cologne: A Declarative Distributed Constraint Optimization Platform
Venue: arXiv cs.DB 2012
Year: 2012

This paper presents Cologne, a declarative optimization platform that enables constraint optimization problems (COPs) to be declaratively specified and incrementally executed in distributed systems. Cologne integrates a declarative networking engine with an off-the-shelf constraint solver. We have developed the Colog language that combines distributed Datalog used in declarative networking with language constructs for specifying goals and constraints used in COPs. Cologne uses novel query processing strategies for processing Colog programs, by combining the use of bottom-up distributed Datalog evaluation with top-down goal-oriented constraint solving. Using case studies based on cloud and wireless network optimizations, we demonstrate that Cologne (1) can flexibly support a wide range of policy-based optimizations in distributed systems, (2) results in orders of magnitude less code compared to imperative implementations, and (3) is highly efficient with low overhead and fast convergence times.
Probabilistically Bounded Staleness for Practical Partial Quorums
Venue: arXiv cs.DB 2012
Year: 2012

Data store replication results in a fundamental trade-off between operation latency and data consistency. In this paper, we examine this trade-off in the context of quorum-replicated data stores. Under partial, or non-strict quorum replication, a data store waits for responses from a subset of replicas before answering a query, without guaranteeing that read and write replica sets intersect. As deployed in practice, these configurations provide only basic eventual consistency guarantees, with no limit to the recency of data returned. However, anecdotally, partial quorums are often "good enough" for practitioners given their latency benefits. In this work, we explain why partial quorums are regularly acceptable in practice, analyzing both the staleness of data they return and the latency benefits they offer. We introduce Probabilistically Bounded Staleness (PBS) consistency, which provides expected bounds on staleness with respect to both versions and wall clock time. We derive a closed-form solution for versioned staleness as well as model real-time staleness for representative Dynamo-style systems under internet-scale production workloads. Using PBS, we measure the latency-consistency trade-off for partial quorum systems. We quantitatively demonstrate how eventually consistent systems frequently return consistent data within tens of milliseconds while offering significant latency benefits.
On Locality in Distributed Storage Systems
Venue: arXiv cs.IT 2012
Year: 2012

This paper studies the design of codes for distributed storage systems (DSS) that enable local repair in the event of node failure. This paper presents locally repairable codes based on low degree multivariate polynomials. Its code construction mechanism extends work on Noisy Interpolating Set by Dvir et al. \cite{dvir2011}. The paper presents two classes of codes that allow node repair to be performed by contacting 2 and 3 surviving nodes respectively. It further shows that both classes are good in terms of their rate and minimum distance, and allow their rate to be bartered for greater flexibility in the repair process.