OpenRaiser/Intern-Atlas huggingface dataset:
Relations between $β$ and $δ$ for QP and LP in Compressed Sensing Computations
Venue: arXiv cs.IT 2010
Year: 2010

In many compressed sensing applications, linear programming (LP) has been used to reconstruct a sparse signal. When observation is noisy, the LP formulation is extended to allow an inequality constraint and the solution is dependent on a parameter $δ$, related to the observation noise level. Recently, some researchers also considered quadratic programming (QP) for compressed sensing signal reconstruction and the solution in this case is dependent on a Lagrange multiplier $β$. In this work, we investigated the relation between $δ$ and $β$ and derived an upper and a lower bound on $β$ in terms of $δ$. For a given $δ$, these bounds can be used to approximate $β$. Since $δ$ is a physically related quantity and easy to determine for an application while there is no easy way in general to determine $β$, our results can be used to set $β$ when the QP is used for compressed sensing. Our results and experimental verification also provide some insight into the solutions generated by compressed sensing.
Quasirandom Rumor Spreading: An Experimental Analysis
Venue: arXiv cs.DS 2010
Year: 2010

We empirically analyze two versions of the well-known "randomized rumor spreading" protocol to disseminate a piece of information in networks. In the classical model, in each round each informed node informs a random neighbor. In the recently proposed quasirandom variant, each node has a (cyclic) list of its neighbors. Once informed, it starts at a random position of the list, but from then on informs its neighbors in the order of the list. While for sparse random graphs a better performance of the quasirandom model could be proven, all other results show that, independent of the structure of the lists, the same asymptotic performance guarantees hold as for the classical model. In this work, we compare the two models experimentally. This not only shows that the quasirandom model generally is faster, but also that the runtime is more concentrated around the mean. This is surprising given that much fewer random bits are used in the quasirandom process. These advantages are also observed in a lossy communication model, where each transmission does not reach its target with a certain probability, and in an asynchronous model, where nodes send at random times drawn from an exponential distribution. We also show that typically the particular structure of the lists has little influence on the efficiency.
Analysis of Computer Science Communities Based on DBLP
Venue: arXiv cs.DL 2010
Year: 2010

It is popular nowadays to bring techniques from bibliometrics and scientometrics into the world of digital libraries to analyze the collaboration patterns and explore mechanisms which underlie community development. In this paper we use the DBLP data to investigate the author's scientific career and provide an in-depth exploration of some of the computer science communities. We compare them in terms of productivity, population stability and collaboration trends.Besides we use these features to compare the sets of topranked conferences with their lower ranked counterparts.
Symmetry Breaking with Polynomial Delay
Venue: arXiv cs.AI 2010
Year: 2010

A conservative class of constraint satisfaction problems CSPs is a class for which membership is preserved under arbitrary domain reductions. Many well-known tractable classes of CSPs are conservative. It is well known that lexleader constraints may significantly reduce the number of solutions by excluding symmetric solutions of CSPs. We show that adding certain lexleader constraints to any instance of any conservative class of CSPs still allows us to find all solutions with a time which is polynomial between successive solutions. The time is polynomial in the total size of the instance and the additional lexleader constraints. It is well known that for complete symmetry breaking one may need an exponential number of lexleader constraints. However, in practice, the number of additional lexleader constraints is typically polynomial number in the size of the instance. For polynomially many lexleader constraints, we may in general not have complete symmetry breaking but polynomially many lexleader constraints may provide practically useful symmetry breaking -- and they sometimes exclude super-exponentially many solutions. We prove that for any instance from a conservative class, the time between finding successive solutions of the instance with polynomially many additional lexleader constraints is polynomial even in the size of the instance without lexleaderconstraints.
Looking for plausibility
Venue: arXiv cs.AI 2010
Year: 2010

In the interpretation of experimental data, one is actually looking for plausible explanations. We look for a measure of plausibility, with which we can compare different possible explanations, and which can be combined when there are different sets of data. This is contrasted to the conventional measure for probabilities as well as to the proposed measure of possibilities. We define what characteristics this measure of plausibility should have. In getting to the conception of this measure, we explore the relation of plausibility to abductive reasoning, and to Bayesian probabilities. We also compare with the Dempster-Schaefer theory of evidence, which also has its own definition for plausibility. Abduction can be associated with biconditionality in inference rules, and this provides a platform to relate to the Collins-Michalski theory of plausibility. Finally, using a formalism for wiring logic onto Hopfield neural networks, we ask if this is relevant in obtaining this measure.
Business Mereology: Imaginative Definitions of Insourcing and Outsourcing Transformations
Venue: arXiv cs.SE 2010
Year: 2010

Outsourcing, the passing on of tasks by organizations to other organizations, often including the personnel and means to perform these tasks, has become an important IT-business strategy over the past decades. We investigate imaginative definitions for outsourcing relations and outsourcing transformations. Abstract models of an extreme and unrealistic simplicity are considered in order to investigate possible definitions of outsourcing. Rather than covering all relevant practical cases an imaginative definition of a concept provides obvious cases of its instantiation from which more refined or liberal definitions may be derived. A definition of outsourcing induces to a complementary definition of insourcing. Outsourcing and insourcing have more complex variations in which multiple parties are involved. All of these terms both refer to state transformations and to state descriptions pertaining to the state obtained after such transformations. We make an attempt to disambiguate the terminology in that respect and we make an attempt to characterize the general concept of sourcing which captures some representative cases. Because mereology is the most general theory of parthood relations we coin business mereology as the general theory in business studies which concerns the full variety of sourcing relations and transformations.
All liaisons are dangerous when all your friends are known to us
Venue: arXiv cs.SI 2010
Year: 2010

Online Social Networks (OSNs) are used by millions of users worldwide. Academically speaking, there is little doubt about the usefulness of demographic studies conducted on OSNs and, hence, methods to label unknown users from small labeled samples are very useful. However, from the general public point of view, this can be a serious privacy concern. Thus, both topics are tackled in this paper: First, a new algorithm to perform user profiling in social networks is described, and its performance is reported and discussed. Secondly, the experiments --conducted on information usually considered sensitive-- reveal that by just publicizing one's contacts privacy is at risk and, thus, measures to minimize privacy leaks due to social graph data mining are outlined.
Popular b-matchings
Venue: arXiv cs.DS 2010
Year: 2010

Suppose that each member of a set of agents has a preference list of a subset of houses, possibly involving ties and each agent and house has their capacity denoting the maximum number of correspondingly agents/houses that can be matched to him/her/it. We want to find a matching $M$, for which there is no other matching $M'$ such that more agents prefer $M'$ to $M$ than $M$ to $M'$. (What it means that an agent prefers one matching to the other is explained in the paper.) Popular matchings have been studied quite extensively, especially in the one-to-one setting. We provide a characterization of popular b-matchings for two defintions of popularity, show some $NP$-hardness results and for certain versions describe polynomial algorithms.
Optimizing ccNUMA locality for task-parallel execution under OpenMP and TBB on multicore-based systems
Venue: arXiv cs.DC 2010
Year: 2010

Task parallelism as employed by the OpenMP task construct or some Intel Threading Building Blocks (TBB) components, although ideal for tackling irregular problems or typical producer/consumer schemes, bears some potential for performance bottlenecks if locality of data access is important, which is typically the case for memory-bound code on ccNUMA systems. We present a thin software layer ameliorates adverse effects of dynamic task distribution by sorting tasks into locality queues, each of which is preferably processed by threads that belong to the same locality domain. Dynamic scheduling is fully preserved inside each domain, and is preferred over possible load imbalance even if nonlocal access is required, making this strategy well-suited for typical multicore-mutisocket systems. The effectiveness of the approach is demonstrated by using a blocked six-point stencil solver as a toy model.
Link Spam Detection based on DBSpamClust with Fuzzy C-means Clustering
Venue: arXiv cs.IR 2010
Year: 2010

Search engine became omnipresent means for ingoing to the web. Spamming Search engine is the technique to deceiving the ranking in search engine and it inflates the ranking. Web spammers have taken advantage of the vulnerability of link based ranking algorithms by creating many artificial references or links in order to acquire higher-than-deserved ranking n search engines' results. Link based algorithms such as PageRank, HITS utilizes the structural details of the hyperlinks for ranking the content in the web. In this paper an algorithm DBSpamClust is proposed for link spam detection. As showing through experiments such a method can filter out web spam effectively
Dynamic Feature Description in Human Action Recognition
Venue: arXiv cs.HC 2010
Year: 2010

This work aims to present novel description methods for human action recognition. Generally, a video sequence can be represented as a collection of spatial temporal words by detecting space-time interest points and describing the unique features around the detected points (Bag of Words representation). Interest points as well as the cuboids around them are considered informative for feature description in terms of both the structural distribution of interest points and the information content inside the cuboids. Our proposed description approaches are based on this idea and making the feature descriptors more discriminative.
A Robust and Efficient Node Authentication Protocol for Mobile Ad Hoc Networks
Venue: arXiv cs.CR 2010
Year: 2010

A mobile ad hoc network (MANET) is a collection of mobile nodes that communicate with each other by forming a multi-hop radio network. Security remains a major challenge for these networks due to their features of open medium, dynamically changing topologies, reliance on cooperative algorithms, absence of centralized monitoring points, and lack of clear lines of defense. Design of an efficient and reliable node authentication protocol for such networks is a particularly challenging task since the nodes are battery-driven and resource constrained. This paper presents a robust and efficient key exchange protocol for nodes authentication in a MANET based on multi-path communication. Simulation results demonstrate that the protocol is effective even in presence of large fraction of malicious nodes in the network. Moreover, it has a minimal computation and communication overhead that makes it ideally suitable for MANETs.
Modelling to study its non-linear effects on Communication System's performance with BER as performance measure
Venue: arXiv cs.IT 2010
Year: 2010

This paper is a study of non-linear effects of RF Amplifiers on Communication Systems Performance. High speed data communication is made possible by Multilevel Modulation schemes. This paper presents a study of these non linear effects on multilevel Modulation schemes like MPSK and MQAM. We make use of Bit Error Ratio (BER) as performance measure. BER vs SNR (Signal-to-Noise Ratio) curves provide comparison between the non linear effects caused by Gain Compression in particular.
Decompositions of graphs of functions and efficient iterations of lookup tables
Venue: arXiv cs.CC 2010
Year: 2010

We show that every function f implemented as a lookup table can be implemented such that the computational complexity of evaluating f^m(x) is small, independently of m and x. The implementation only increases the storage space by a small_constant_ factor.
An approach to RAID-6 based on cyclic groups of a prime order
Venue: arXiv cs.IT 2010
Year: 2010

As the size of data storing arrays of disks grows, it becomes vital to protect data against double disk failures. A popular method of protection is via the Reed-Solomon (RS) code with two parity words. In the present paper we construct alternative examples of linear block codes protecting against two erasures. Our construction is based on an abstract notion of cone. Concrete cones are constructed via matrix representations of cyclic groups of prime order. In particular, this construction produces EVENODD code. Interesting conditions on the prime number arise in our analysis of these codes. At the end, we analyse an assembly implementation of the corresponding system on a general purpose processor and compare its write and recovery speed with the standard DP-RAID system.
Constructive Dimension and Turing Degrees
Venue: arXiv cs.CC 2010
Year: 2010

This paper examines the constructive Hausdorff and packing dimensions of Turing degrees. The main result is that every infinite sequence S with constructive Hausdorff dimension dim_H(S) and constructive packing dimension dim_P(S) is Turing equivalent to a sequence R with dim_H(R) <= (dim_H(S) / dim_P(S)) - epsilon, for arbitrary epsilon > 0. Furthermore, if dim_P(S) > 0, then dim_P(R) >= 1 - epsilon. The reduction thus serves as a *randomness extractor* that increases the algorithmic randomness of S, as measured by constructive dimension. A number of applications of this result shed new light on the constructive dimensions of Turing degrees. A lower bound of dim_H(S) / dim_P(S) is shown to hold for the Turing degree of any sequence S. A new proof is given of a previously-known zero-one law for the constructive packing dimension of Turing degrees. It is also shown that, for any regular sequence S (that is, dim_H(S) = dim_P(S)) such that dim_H(S) > 0, the Turing degree of S has constructive Hausdorff and packing dimension equal to 1. Finally, it is shown that no single Turing reduction can be a universal constructive Hausdorff dimension extractor, and that bounded Turing reductions cannot extract constructive Hausdorff dimension. We also exhibit sequences on which weak truth-table and bounded Turing reductions differ in their ability to extract dimension.
Integral Biomathics: A Post-Newtonian View into the Logos of Bios (On the New Meaning, Relations and Principles of Life in Science)
Venue: arXiv cs.NE 2010
Year: 2010

This work is an attempt for a state-of-the-art survey of natural and life sciences with the goal to define the scope and address the central questions of an original research program. It is focused on the phenomena of emergence, adaptive dynamics and evolution of self-assembling, self-organizing, self-maintaining and self-replicating biosynthetic systems viewed from a newly-arranged perspective and understanding of computation and communication in the living nature.
Eigenvalue Estimates and Mutual Information for the Linear Time-Varying Channel
Venue: arXiv cs.IT 2011
Year: 2011

We consider linear time-varying channels with additive white Gaussian noise. For a large class of such channels we derive rigorous estimates of the eigenvalues of the correlation matrix of the effective channel in terms of the sampled time-varying transfer function and, thus, provide a theoretical justification for a relationship that has been frequently observed in the literature. We then use this eigenvalue estimate to derive an estimate of the mutual information of the channel. Our approach is constructive and is based on a careful balance of the trade-off between approximate operator diagonalization, signal dimension loss, and accuracy of eigenvalue estimates.
Protocol Channels
Venue: arXiv cs.CR 2011
Year: 2011

Covert channel techniques are used by attackers to transfer data in a way prohibited by the security policy. There are two main categories of covert channels: timing channels and storage channels. This paper introduces a new storage channel technique called a protocol channel. A protocol channel switches one of at least two protocols to send a bit combination to a destination. The main goal of a protocol channel is that packets containing covert information look equal to all other packets within a network, what makes a protocol channel hard to detect.
Learning Hidden Markov Models using Non-Negative Matrix Factorization
Venue: arXiv cs.LG 2011
Year: 2011

The Baum-Welsh algorithm together with its derivatives and variations has been the main technique for learning Hidden Markov Models (HMM) from observational data. We present an HMM learning algorithm based on the non-negative matrix factorization (NMF) of higher order Markovian statistics that is structurally different from the Baum-Welsh and its associated approaches. The described algorithm supports estimation of the number of recurrent states of an HMM and iterates the non-negative matrix factorization (NMF) algorithm to improve the learned HMM parameters. Numerical examples are provided as well.
Perspective Drawing of Surfaces with Line Hidden Line Elimination, Dibujando Superficies En Perspectiva Con Eliminacion De Lineas Ocultas
Venue: arXiv cs.GR 2011
Year: 2011

An efficient computer algorithm is described for the perspective drawing of a wide class of surfaces. The class includes surfaces corresponding lo single-valued, continuous functions which are defined over rectangular domains. The algorithm automatically computes and eliminates hidden lines. The number of computations in the algorithm grows linearly with the number of sample points on the surface to be drawn. An analysis of the algorithm is presented, and extensions lo certain multi-valued functions are indicated. The algorithm is implemented and tested on .Net 2.0 platform that left interactive use. Running times are found lo be exceedingly efficient for visualization, where interaction on-line and view-point control, enables effective and rapid examination of a surfaces from many perspectives.
On the Vocabulary of Grammar-Based Codes and the Logical Consistency of Texts
Venue: arXiv cs.IT 2011
Year: 2011

The article presents a new interpretation for Zipf-Mandelbrot's law in natural language which rests on two areas of information theory. Firstly, we construct a new class of grammar-based codes and, secondly, we investigate properties of strongly nonergodic stationary processes. The motivation for the joint discussion is to prove a proposition with a simple informal statement: If a text of length $n$ describes $n^β$ independent facts in a repetitive way then the text contains at least $n^β/\log n$ different words, under suitable conditions on $n$. In the formal statement, two modeling postulates are adopted. Firstly, the words are understood as nonterminal symbols of the shortest grammar-based encoding of the text. Secondly, the text is assumed to be emitted by a finite-energy strongly nonergodic source whereas the facts are binary IID variables predictable in a shift-invariant way.
Binar Sort: A Linear Generalized Sorting Algorithm
Venue: arXiv cs.DS 2011
Year: 2011

Sorting is a common and ubiquitous activity for computers. It is not surprising that there exist a plethora of sorting algorithms. For all the sorting algorithms, it is an accepted performance limit that sorting algorithms are linearithmic or O(N lg N). The linearithmic lower bound in performance stems from the fact that the sorting algorithms use the ordering property of the data. The sorting algorithm uses comparison by the ordering property to arrange the data elements from an initial permutation into a sorted permutation. Linear O(N) sorting algorithms exist, but use a priori knowledge of the data to use a specific property of the data and thus have greater performance. In contrast, the linearithmic sorting algorithms are generalized by using a universal property of data-comparison, but have a linearithmic performance lower bound. The trade-off in sorting algorithms is generality for performance by the chosen property used to sort the data elements. A general-purpose, linear sorting algorithm in the context of the trade-off of performance for generality at first consideration seems implausible. But, there is an implicit assumption that only the ordering property is universal. But, as will be discussed and examined, it is not the only universal property for data elements. The binar sort is a general-purpose sorting algorithm that uses this other universal property to sort linearly.
Immunity and Pseudorandomness of Context-Free Languages
Venue: arXiv cs.CC 2011
Year: 2011

We discuss the computational complexity of context-free languages, concentrating on two well-known structural properties---immunity and pseudorandomness. An infinite language is REG-immune (resp., CFL-immune) if it contains no infinite subset that is a regular (resp., context-free) language. We prove that (i) there is a context-free REG-immune language outside REG/n and (ii) there is a REG-bi-immune language that can be computed deterministically using logarithmic space. We also show that (iii) there is a CFL-simple set, where a CFL-simple language is an infinite context-free language whose complement is CFL-immune. Similar to the REG-immunity, a REG-primeimmune language has no polynomially dense subsets that are also regular. We further prove that (iv) there is a context-free language that is REG/n-bi-primeimmune. Concerning pseudorandomness of context-free languages, we show that (v) CFL contains REG/n-pseudorandom languages. Finally, we prove that (vi) against REG/n, there exists an almost 1-1 pseudorandom generator computable in nondeterministic pushdown automata equipped with a write-only output tape and (vii) against REG, there is no almost 1-1 weakly pseudorandom generator computable deterministically in linear time by a single-tape Turing machine.