OpenRaiser/Intern-Atlas huggingface dataset:
Evolving Clustered Random Networks
Venue: arXiv cs.DM 2008
Year: 2008

We propose a Markov chain simulation method to generate simple connected random graphs with a specified degree sequence and level of clustering. The networks generated by our algorithm are random in all other respects and can thus serve as generic models for studying the impacts of degree distributions and clustering on dynamical processes as well as null models for detecting other structural properties in empirical networks.
Foundations of Information Theory
Venue: arXiv cs.IT 2008
Year: 2008

Information is the basic concept of information theory. However, there is no definition of this concept that can encompass all uses of the term information in information theories and beyond. Many question a possibility of such a definition. However, foundations of information theory developed in the context of the general theory of information made it possible to build such a relevant and at the same time, encompassing definition. Foundations of information theory are built in a form of ontological principles, which reflect basic features of information and information processes.
A Distributed and Deterministic TDMA Algorithm for Write-All-With-Collision Model
Venue: arXiv cs.OS 2008
Year: 2008

Several self-stabilizing time division multiple access (TDMA) algorithms are proposed for sensor networks. In addition to providing a collision-free communication service, such algorithms enable the transformation of programs written in abstract models considered in distributed computing literature into a model consistent with sensor networks, i.e., write all with collision (WAC) model. Existing TDMA slot assignment algorithms have one or more of the following properties: (i) compute slots using a randomized algorithm, (ii) assume that the topology is known upfront, and/or (iii) assign slots sequentially. If these algorithms are used to transform abstract programs into programs in WAC model then the transformed programs are probabilistically correct, do not allow the addition of new nodes, and/or converge in a sequential fashion. In this paper, we propose a self-stabilizing deterministic TDMA algorithm where a sensor is aware of only its neighbors. We show that the slots are assigned to the sensors in a concurrent fashion and starting from arbitrary initial states, the algorithm converges to states where collision-free communication among the sensors is restored. Moreover, this algorithm facilitates the transformation of abstract programs into programs in WAC model that are deterministically correct.
Capacity of a Class of Diamond Channels
Venue: arXiv cs.IT 2008
Year: 2008

We study a special class of diamond channels which was introduced by Schein in 2001. In this special class, each diamond channel consists of a transmitter, a noisy relay, a noiseless relay and a receiver. We prove the capacity of this class of diamond channels by providing an achievable scheme and a converse. The capacity we show is strictly smaller than the cut-set bound. Our result also shows the optimality of a combination of decode-and-forward (DAF) and compress-and-forward (CAF) at the noisy relay node. This is the first example where a combination of DAF and CAF is shown to be capacity achieving. Finally, we note that there exists a duality between this diamond channel coding problem and the Kaspi-Berger source coding problem.
Verification of Peterson's Algorithm for Leader Election in a Unidirectional Asynchronous Ring Using NuSMV
Venue: arXiv cs.LO 2008
Year: 2008

The finite intrinsic nature of the most distributed algorithms gives us this ability to use model checking tools for verification of this type of algorithms. In this paper, I attempt to use NuSMV as a model checking tool for verifying necessary properties of Peterson's algorithm for leader election problem in a unidirectional asynchronous ring topology. Peterson's algorithm for an asynchronous ring supposes that each node in the ring has a unique ID and also a queue for dealing with storage problem. By considering that the queue can have any combination of values, a constructed model for a ring with only four nodes will have more than a billion states. Although it seems that model checking is not a feasible approach for this problem, I attempt to use several effective limiting assumptions for hiring formal model checking approach without losing the correct functionality of the Peterson's algorithm. These enforced limiting assumptions target the degree of freedom in the model checking process and significantly decrease the CPU time, memory usage and the total number of page faults. By deploying these limitations, the number of nodes can be increased from four to eight in the model checking process with NuSMV.
Text Modeling using Unsupervised Topic Models and Concept Hierarchies
Venue: arXiv cs.AI 2008
Year: 2008

Statistical topic models provide a general data-driven framework for automated discovery of high-level knowledge from large collections of text documents. While topic models can potentially discover a broad range of themes in a data set, the interpretability of the learned topics is not always ideal. Human-defined concepts, on the other hand, tend to be semantically richer due to careful selection of words to define concepts but they tend not to cover the themes in a data set exhaustively. In this paper, we propose a probabilistic framework to combine a hierarchy of human-defined semantic concepts with statistical topic models to seek the best of both worlds. Experimental results using two different sources of concept hierarchies and two collections of text documents indicate that this combination leads to systematic improvements in the quality of the associated language models as well as enabling new techniques for inferring and visualizing the semantics of a document.
Cache oblivious storage and access heuristics for blocked matrix-matrix multiplication
Venue: arXiv cs.DS 2008
Year: 2008

We investigate effects of ordering in blocked matrix--matrix multiplication. We find that submatrices do not have to be stored contiguously in memory to achieve near optimal performance. Instead it is the choice of execution order of the submatrix multiplications that leads to a speedup of up to four times for small block sizes. This is in contrast to results for single matrix elements showing that contiguous memory allocation quickly becomes irrelevant as the blocksize increases.
A Formal Foundation for XrML
Venue: arXiv cs.CR 2008
Year: 2008

XrML is becoming a popular language in industry for writing software licenses. The semantics for XrML is implicitly given by an algorithm that determines if a permission follows from a set of licenses. We focus on a fragment of the language and use it to highlight some problematic aspects of the algorithm. We then correct the problems, introduce formal semantics, and show that our semantics captures the (corrected) algorithm. Next, we consider the complexity of determining if a permission is implied by a set of XrML licenses. We prove that the general problem is undecidable, but it is polynomial-time computable for an expressive fragment of the language. We extend XrML to capture a wider range of licenses by adding negation to the language. Finally, we discuss the key differences between XrML and MPEG-21, an international standard based on XrML.
The finite harmonic oscillator and its associated sequences
Venue: arXiv cs.IT 2008
Year: 2008

A system of functions (signals) on the finite line, called the oscillator system, is described and studied. Applications of this system for discrete radar and digital communication theory are explained. Keywords: Weil representation, commutative subgroups, eigenfunctions, random behavior, deterministic construction
An Almost-Surely Terminating Polynomial Protocol for Asynchronous Byzantine Agreement with Optimal Resilience
Venue: arXiv cs.DC 2008
Year: 2008

Consider an asynchronous system with private channels and $n$ processes, up to $t$ of which may be faulty. We settle a longstanding open question by providing a Byzantine agreement protocol that simultaneously achieves three properties: 1. (optimal) resilience: it works as long as $n>3t$ 2. (almost-sure) termination: with probability one, all nonfaulty processes terminate 3. (polynomial) efficiency: the expected computation time, memory consumption, message size, and number of messages sent are all polynomial in $n$. Earlier protocols have achieved only two of these three properties. In particular, the protocol of Bracha is not polynomially efficient, the protocol of Feldman and Micali is not optimally resilient, and the protocol of Canetti and Rabin does not have almost-sure termination. Our protocol utilizes a new primitive called shunning (asynchronous) verifiable secret sharing (SVSS), which ensures, roughly speaking, that either a secret is successfully shared or a new faulty process is ignored from this point onwards by some nonfaulty process.
Characterization Of any Non-linear Boolean function Using A Set of Linear Operators
Venue: arXiv cs.CC 2008
Year: 2008

Global dynamics of a non-linear Cellular Automata is, in general irregular, asymmetric and unpredictable as opposed to that of a linear CA, which is highly systematic and tractable. In the past efforts have been made to systematize non-linear CA evolutions in the light of Boolean derivatives and Jacobian Matrices. In this paper two different efforts have been made: first we try to systematize non-linear CA evolution in the light of deviant states and non-deviant states. For all the non-deviant states the nearest linear rule matrix is applicable where as for the deviant states we have a set of other matrices. Second using algebraic manipulation, an efficient algorithm is proposed by which every Non-linear Boolean function can be characterized by a sequence of binary matrices.
Initial Results on the F-logic to OWL Bi-directional Translation on a Tabled Prolog Engine
Venue: arXiv cs.AI 2008
Year: 2008

In this paper, we show our results on the bi-directional data exchange between the F-logic language supported by the Flora2 system and the OWL language. Most of the TBox and ABox axioms are translated preserving the semantics between the two representations, such as: proper inclusion, individual definition, functional properties, while some axioms and restrictions require a change in the semantics, such as: numbered and qualified cardinality restrictions. For the second case, we translate the OWL definite style inference rules into F-logic style constraints. We also describe a set of reasoning examples using the above translation, including the reasoning in Flora2 of a variety of ABox queries.
Index wiki database: design and experiments
Venue: arXiv cs.IR 2008
Year: 2008

With the fantastic growth of Internet usage, information search in documents of a special type called a "wiki page" that is written using a simple markup language, has become an important problem. This paper describes the software architectural model for indexing wiki texts in three languages (Russian, English, and German) and the interaction between the software components (GATE, Lemmatizer, and Synarcher). The inverted file index database was designed using visual tool DBDesigner. The rules for parsing Wikipedia texts are illustrated by examples. Two index databases of Russian Wikipedia (RW) and Simple English Wikipedia (SEW) are built and compared. The size of RW is by order of magnitude higher than SEW (number of words, lexemes), though the growth rate of number of pages in SEW was found to be 14% higher than in Russian, and the rate of acquisition of new words in SEW lexicon was 7% higher during a period of five months (from September 2007 to February 2008). The Zipf's law was tested with both Russian and Simple Wikipedias. The entire source code of the indexing software and the generated index databases are freely available under GPL (GNU General Public License).
The Optimal Quantile Estimator for Compressed Counting
Venue: arXiv cs.DS 2008
Year: 2008

Compressed Counting (CC) was recently proposed for very efficiently computing the (approximate) $α$th frequency moments of data streams, where $0<α<= 2$. Several estimators were reported including the geometric mean estimator, the harmonic mean estimator, the optimal power estimator, etc. The geometric mean estimator is particularly interesting for theoretical purposes. For example, when $α-> 1$, the complexity of CC (using the geometric mean estimator) is $O(1/ε)$, breaking the well-known large-deviation bound $O(1/ε^2)$. The case $α\approx 1$ has important applications, for example, computing entropy of data streams. For practical purposes, this study proposes the optimal quantile estimator. Compared with previous estimators, this estimator is computationally more efficient and is also more accurate when $α> 1$.
On zero-rate error exponent for BSC with noisy feedback
Venue: arXiv cs.IT 2008
Year: 2008

For the information transmission a binary symmetric channel is used. There is also another noisy binary symmetric channel (feedback channel), and the transmitter observes without delay all the outputs of the forward channel via that feedback channel. The transmission of a nonexponential number of messages (i.e. the transmission rate equals zero) is considered. The achievable decoding error exponent for such a combination of channels is investigated. It is shown that if the crossover probability of the feedback channel is less than a certain positive value, then the achievable error exponent is better than the similar error exponent of the no-feedback channel. The transmission method described and the corresponding lower bound for the error exponent can be strengthened, and also extended to the positive transmission rates.
Spectrum Sharing Between Cellular and Mobile Ad Hoc Networks: Transmission-Capacity Trade-Off
Venue: arXiv cs.IT 2008
Year: 2008

Spectrum sharing between wireless networks improves the efficiency of spectrum usage, and thereby alleviates spectrum scarcity due to growing demands for wireless broadband access. To improve the usual underutilization of the cellular uplink spectrum, this paper studies spectrum sharing between a cellular uplink and a mobile ad hoc networks. These networks access either all frequency sub-channels or their disjoint sub-sets, called spectrum underlay and spectrum overlay, respectively. Given these spectrum sharing methods, the capacity trade-off between the coexisting networks is analyzed based on the transmission capacity of a network with Poisson distributed transmitters. This metric is defined as the maximum density of transmitters subject to an outage constraint for a given signal-to-interference ratio (SIR). Using tools from stochastic geometry, the transmission-capacity trade-off between the coexisting networks is analyzed, where both spectrum overlay and underlay as well as successive interference cancelation (SIC) are considered. In particular, for small target outage probability, the transmission capacities of the coexisting networks are proved to satisfy a linear equation, whose coefficients depend on the spectrum sharing method and whether SIC is applied. This linear equation shows that spectrum overlay is more efficient than spectrum underlay. Furthermore, this result also provides insight into the effects of different network parameters on transmission capacities, including link diversity gains, transmission distances, and the base station density. In particular, SIC is shown to increase transmission capacities of both coexisting networks by a linear factor, which depends on the interference-power threshold for qualifying canceled interferers.
A Simple E-Voting Protocol
Venue: arXiv cs.CY 2008
Year: 2008

We propose an e-voting protocol that seems to allow citizens to verify that their vote has been accurately taken into account while preserving its secrecy, without requiring the use of a complex process. The main idea is to give each voter a receipt on which her choice is mixed with the choices of other voters.
Provably efficient instanton search algorithm for LP decoding of LDPC codes over the BSC
Venue: arXiv cs.IT 2008
Year: 2008

We consider Linear Programming (LP) decoding of a fixed Low-Density Parity-Check (LDPC) code over the Binary Symmetric Channel (BSC). The LP decoder fails when it outputs a pseudo-codeword which is not a codeword. We design an efficient algorithm termed the Instanton Search Algorithm (ISA) which, given a random input, generates a set of flips called the BSC-instanton. We prove that: (a) the LP decoder fails for any set of flips with support vector including an instanton; (b) for any input, the algorithm outputs an instanton in the number of steps upper-bounded by twice the number of flips in the input. Repeated sufficient number of times, the ISA outcomes the number of unique instantons of different sizes.
Towards Provable Secure Neighbor Discovery in Wireless Networks
Venue: arXiv cs.CR 2008
Year: 2008

In wireless systems, neighbor discovery (ND) is a fundamental building block: determining which devices are within direct radio communication is an enabler for networking protocols and a wide range of applications. To thwart abuse of ND and the resultant compromise of the dependent functionality of wireless systems, numerous works proposed solutions to secure ND. Nonetheless, until very recently, there has been no formal analysis of secure ND protocols. We close this gap in \cite{asiaccs08}, but we concentrate primarily on the derivation of an impossibility result for a class of protocols. In this paper, we focus on reasoning about specific protocols. First, we contribute a number of extensions and refinements on the framework of [24]. As we are particularly concerned with the practicality of provably secure ND protocols, we investigate availability and redefine accordingly the ND specification, and also consider composability of ND with other protocols. Then, we propose and analyze two secure ND protocols: We revisit one of the protocols analyzed in [24], and introduce and prove correct a more elaborate challenge-response protocol.
Low-Signal-Energy Asymptotics of Capacity and Mutual Information for the Discrete-Time Poisson Channel
Venue: arXiv cs.IT 2008
Year: 2008

The first terms of the low-signal-energy asymptotics for the mutual information in the discrete-time Poisson channel are derived and compared to an asymptotic expression of the capacity. In the presence of non-zero additive noise (either Poisson or geometric), the mutual information is concave at zero signal-energy and the minimum energy per bit is not attained at zero capacity. Fixed signal constellations which scale with the signal energy do not attain the minimum energy per bit. The minimum energy per bit is zero when additive Poisson noise is present and $\ew\log 2$ when additive geometric noise of mean $\ew$ is present.
Spatial planning with constraints on translational distances between geometric objects
Venue: arXiv cs.CG 2008
Year: 2008

The main constraint on relative position of geometric objects, used in spatial planning for computing the C-space maps (for example, in robotics, CAD, and packaging), is the relative non-overlapping of objects. This is the simplest constraint in which the minimum translational distance between objects is greater than zero, or more generally, than some positive value. We present a technique, based on the Minkowski operations, for generating the translational C-space maps for spatial planning with more general and more complex constraints on the relative position of geometric objects, such as constraints on various types (not only on the minimum) of the translational distances between objects. The developed technique can also be used, respectively, for spatial planning with constraints on translational distances in a given direction, and rotational distances between geometric objects, as well as for spatial planning with given dynamic geometric situation of moving objects.
On the diagonalization of the discrete Fourier transform
Venue: arXiv cs.IT 2008
Year: 2008

The discrete Fourier transform (DFT) is an important operator which acts on the Hilbert space of complex valued functions on the ring Z/NZ. In the case where N=p is an odd prime number, we exhibit a canonical basis of eigenvectors for the DFT. The transition matrix from the standard basis to the canonical basis defines a novel transform which we call the discrete oscillator transform (DOT for short). Finally, we describe a fast algorithm for computing the discrete oscillator transform in certain cases.
Network Motifs in Object-Oriented Software Systems
Venue: arXiv cs.SE 2008
Year: 2008

Nowadays, software has become a complex piece of work that may be beyond our control. Understanding how software evolves over time plays an important role in controlling software development processes. Recently, a few researchers found the quantitative evidence of structural duplication in software systems or web applications, which is similar to the evolutionary trend found in biological systems. To investigate the principles or rules of software evolution, we introduce the relevant theories and methods of complex networks into structural evolution and change of software systems. According to the results of our experiment on network motifs, we find that the stability of a motif shows positive correlation with its abundance and a motif with high Z score tends to have stable structure. These findings imply that the evolution of software systems is based on functional cloning as well as structural duplication and tends to be structurally stable. So, the work presented in this paper will be useful for the analysis of structural changes of software systems in reverse engineering.
Efficient algorithms for the basis of finite Abelian groups
Venue: arXiv cs.DS 2008
Year: 2008

Let $G$ be a finite abelian group $G$ with $N$ elements. In this paper we give a O(N) time algorithm for computing a basis of $G$. Furthermore, we obtain an algorithm for computing a basis from a generating system of $G$ with $M$ elements having time complexity $O(M\sum_{p|N} e(p)\lceil p^{1/2}\rceil^{μ(p)})$, where $p$ runs over all the prime divisors of $N$, and $p^{e(p)}$, $μ(p)$ are the exponent and the number of cyclic groups which are direct factors of the $p$-primary component of $G$, respectively. In case where $G$ is a cyclic group having a generating system with $M$ elements, a $O(MN^ε)$ time algorithm for the computation of a basis of $G$ is obtained.
Scientific Workflow Systems for 21st Century e-Science, New Bottle or New Wine?
Venue: arXiv cs.SE 2008
Year: 2008

With the advances in e-Sciences and the growing complexity of scientific analyses, more and more scientists and researchers are relying on workflow systems for process coordination, derivation automation, provenance tracking, and bookkeeping. While workflow systems have been in use for decades, it is unclear whether scientific workflows can or even should build on existing workflow technologies, or they require fundamentally new approaches. In this paper, we analyze the status and challenges of scientific workflows, investigate both existing technologies and emerging languages, platforms and systems, and identify the key challenges that must be addressed by workflow systems for e-science in the 21st century.
What It Feels Like To Hear Voices: Fond Memories of Julian Jaynes
Venue: arXiv cs.CL 2008
Year: 2008

Julian Jaynes's profound humanitarian convictions not only prevented him from going to war, but would have prevented him from ever kicking a dog. Yet according to his theory, not only are language-less dogs unconscious, but so too were the speaking/hearing Greeks in the Bicameral Era, when they heard gods' voices telling them what to do rather than thinking for themselves. I argue that to be conscious is to be able to feel, and that all mammals (and probably lower vertebrates and invertebrates too) feel, hence are conscious. Julian Jaynes's brilliant analysis of our concepts of consciousness nevertheless keeps inspiring ever more inquiry and insights into the age-old mind/body problem and its relation to cognition and language.