OpenRaiser/Intern-Atlas huggingface dataset:
Analysis of multi-stage open shop processing systems
Venue: arXiv cs.DS 2011
Year: 2011

We study algorithmic problems in multi-stage open shop processing systems that are centered around reachability and deadlock detection questions. We characterize safe and unsafe system states. We show that it is easy to recognize system states that can be reached from the initial state (where the system is empty), but that in general it is hard to decide whether one given system state is reachable from another given system state. We show that the problem of identifying reachable deadlock states is hard in general open shop systems, but is easy in the special case where no job needs processing on more than two machines (by linear programming and matching theory), and in the special case where all machines have capacity one (by graph-theoretic arguments).
Publish or Patent: Bibliometric evidence for empirical trade-offs in national funding strategies
Venue: arXiv cs.DL 2011
Year: 2011

Multivariate linear regression models suggest a trade-off in allocations of national R&D investments. Government funding, and spending in the higher education sector, seem to encourage publications, whereas other components such as industrial funding, and spending in the business sector, encourage patenting. Our results help explain why the US trails the EU in publications, because of its focus on industrial funding - some 70% of its total R&D investment. Conversely, it also helps explain why the EU trails the US in patenting. Government funding is indicated as a negative incentive to high-quality patenting. The models here can also be used to predict an output indicator for a country, once the appropriate input indicator is known. This usually is done within a dataset for a single year, but the process can be extended to predict outputs a few years into the future, if reasonable forecasts can be made of the input indicators. We provide new forecasts about the further relationships of the US, the EU-27, and the PRC in the case of publishing. Models for individual countries may be more successful, however, than regression models whose parameters are averaged over a set of countries.
Covering Point Patterns
Venue: arXiv cs.IT 2011
Year: 2011

An encoder observes a point pattern---a finite number of points in the interval $[0,T]$---which is to be described to a reconstructor using bits. Based on these bits, the reconstructor wishes to select a subset of $[0,T]$ that contains all the points in the pattern. It is shown that, if the point pattern is produced by a homogeneous Poisson process of intensity $λ$, and if the reconstructor is restricted to select a subset of average Lebesgue measure not exceeding $DT$, then, as $T$ tends to infinity, the minimum number of bits per second needed by the encoder is $-λ\log D$. It is also shown that, as $T$ tends to infinity, any point pattern on $[0,T]$ containing no more than $λT$ points can be successfully described using $-λ\log D$ bits per second in this sense. Finally, a Wyner-Ziv version of this problem is considered where some of the points in the pattern are known to the reconstructor.
Automated Complexity Analysis Based on the Dependency Pair Method
Venue: arXiv cs.LO 2011
Year: 2011

This article is concerned with automated complexity analysis of term rewrite systems. Since these systems underlie much of declarative programming, time complexity of functions defined by rewrite systems is of particular interest. Among other results, we present a variant of the dependency pair method for analysing runtime complexities of term rewrite systems automatically. The established results significantly extent previously known techniques: we give examples of rewrite systems subject to our methods that could previously not been analysed automatically. Furthermore, the techniques have been implemented in the Tyrolean Complexity Tool. We provide ample numerical data for assessing the viability of the method.
Connection between Annealed Free Energy and Belief Propagation on Random Factor Graph Ensembles
Venue: arXiv cs.IT 2011
Year: 2011

Recently, Vontobel showed the relationship between Bethe free energy and annealed free energy for protograph factor graph ensembles. In this paper, annealed free energy of any random regular, irregular and Poisson factor graph ensembles are connected to Bethe free energy. The annealed free energy is expressed as the solution of maximization problem whose stationary condition equations coincide with equations of belief propagation since the contribution to partition function of particular type of variable and factor nodes has similar form of minus Bethe free energy. It gives simple derivation of replica symmetric solution. As consequence, it is shown that on replica symmetric ansatz, replica symmetric solution and annealed free energy are equal for regular ensemble.
A Complete Characterization of Irreducible Cyclic Orbit Codes
Venue: arXiv cs.IT 2011
Year: 2011

We give a complete list of orbit codes that are generated by an irreducible cyclic group, i.e. an irreducible group having one generator. We derive some of the basic properties of these codes such as the cardinality and the minimum distance.
Coding for Cryptographic Security Enhancement using Stopping Sets
Venue: arXiv cs.CR 2011
Year: 2011

In this paper we discuss the ability of channel codes to enhance cryptographic secrecy. Toward that end, we present the secrecy metric of degrees of freedom in an attacker's knowledge of the cryptogram, which is similar to equivocation. Using this notion of secrecy, we show how a specific practical channel coding system can be used to hide information about the ciphertext, thus increasing the difficulty of cryptographic attacks. The system setup is the wiretap channel model where transmitted data traverse through independent packet erasure channels with public feedback for authenticated ARQ (Automatic Repeat reQuest). The code design relies on puncturing nonsystematic low-density parity-check codes with the intent of inflicting an eavesdropper with stopping sets in the decoder. Furthermore, the design amplifies errors when stopping sets occur such that a receiver must guess all the channel-erased bits correctly to avoid an expected error rate of one half in the ciphertext. We extend previous results on the coding scheme by giving design criteria that reduces the effectiveness of a maximum-likelihood attack to that of a message-passing attack. We further extend security analysis to models with multiple receivers and collaborative attackers. Cryptographic security is enhanced in all these cases by exploiting properties of the physical-layer. The enhancement is accurately presented as a function of the degrees of freedom in the eavesdropper's knowledge of the ciphertext, and is even shown to be present when eavesdroppers have better channel quality than legitimate receivers.
One Packet Suffices - Highly Efficient Packetized Network Coding With Finite Memory
Venue: arXiv cs.IT 2011
Year: 2011

Random Linear Network Coding (RLNC) has emerged as a powerful tool for robust high-throughput multicast. Projection analysis - a recently introduced technique - shows that the distributed packetized RLNC protocol achieves (order) optimal and perfectly pipelined information dissemination in many settings. In the original approach to RNLC intermediate nodes code together all available information. This requires intermediate nodes to keep considerable data available for coding. Moreover, it results in a coding complexity that grows linearly with the size of this data. While this has been identified as a problem, approaches that combine queuing theory and network coding have heretofore not provided a succinct representation of the memory needs of network coding at intermediates nodes. This paper shows the surprising result that, in all settings with a continuous stream of data, network coding continues to perform optimally even if only one packet per node is kept in active memory and used for computations. This leads to an extremely simple RLNC protocol variant with drastically reduced requirements on computational and memory resources. By extending the projection analysis, we show that in all settings in which the RLNC protocol was proven to be optimal its finite memory variant performs equally well. In the same way as the original projection analysis, our technique applies in a wide variety of network models, including highly dynamic topologies that can change completely at any time in an adversarial fashion.
The Two-User Gaussian Fading Broadcast Channel
Venue: arXiv cs.IT 2011
Year: 2011

This paper presents outerbounds for the two-user Gaussian fading broadcast channel. These outerbounds are based on Costa's entropy power inequality (Costa-EPI) and are formulated mathematically as a feasibility problem. For classes of the two-user Gaussian fading broadcast channel where the outerbound is found to have a feasible solution, we find conditions under which a suitable inner and outer bound meet. For all such cases, this paper provides a partial characterization of the capacity region of the Gaussian two-user fading broadcast channel.
Weak randomness and Kamae's theorem on normal numbers
Venue: arXiv cs.IT 2011
Year: 2011

A function from sequences to their subsequences is called selection function. A selection function is called admissible (with respect to normal numbers) if for all normal numbers, their subsequences obtained by the selection function are normal numbers. In Kamae (1973) selection functions that are not depend on sequences (depend only on coordinates) are studied, and their necessary and sufficient condition for admissibility is given. In this paper we introduce a notion of weak randomness and study an algorithmic analogy to the Kamae's theorem.
Belief propagation for joint sparse recovery
Venue: arXiv cs.IT 2011
Year: 2011

Compressed sensing (CS) demonstrates that sparse signals can be recovered from underdetermined linear measurements. We focus on the joint sparse recovery problem where multiple signals share the same common sparse support sets, and they are measured through the same sensing matrix. Leveraging a recent information theoretic characterization of single signal CS, we formulate the optimal minimum mean square error (MMSE) estimation problem, and derive a belief propagation algorithm, its relaxed version, for the joint sparse recovery problem and an approximate message passing algorithm. In addition, using density evolution, we provide a sufficient condition for exact recovery.
Reasoning about Social Choice Functions
Venue: arXiv cs.MA 2011
Year: 2011

We introduce a logic specifically designed to support reasoning about social choice functions. The logic includes operators to capture strategic ability, and operators to capture agent preferences. We establish a correspondence between formulae in the logic and properties of social choice functions, and show that the logic is expressively complete with respect to social choice functions, i.e., that every social choice function can be characterised as a formula of the logic. We prove that the logic is decidable, and give a complete axiomatization. To demonstrate the value of the logic, we show in particular how it can be applied to the problem of determining whether a social choice function is strategy-proof.
On conjugacy classes of subgroups of the general linear group and cyclic orbit codes
Venue: arXiv cs.IT 2011
Year: 2011

Orbit codes are a family of codes employable for communications on a random linear network coding channel. The paper focuses on the classification of these codes. We start by classifying the conjugacy classes of cyclic subgroups of the general linear group. As a result, we are able to focus the study of cyclic orbit codes to a restricted family of them.
Detecting Separation in Robotic and Sensor Networks
Venue: arXiv cs.RO 2011
Year: 2011

In this paper we consider the problem of monitoring detecting separation of agents from a base station in robotic and sensor networks. Such separation can be caused by mobility and/or failure of the agents. While separation/cut detection may be performed by passing messages between a node and the base in static networks, such a solution is impractical for networks with high mobility, since routes are constantly changing. We propose a distributed algorithm to detect separation from the base station. The algorithm consists of an averaging scheme in which every node updates a scalar state by communicating with its current neighbors. We prove that if a node is permanently disconnected from the base station, its state converges to $0$. If a node is connected to the base station in an average sense, even if not connected in any instant, then we show that the expected value of its state converges to a positive number. Therefore, a node can detect if it has been separated from the base station by monitoring its state. The effectiveness of the proposed algorithm is demonstrated through simulations, a real system implementation and experiments involving both static as well as mobile networks.
Layered Index-less Indexed Flash Codes for Improving Average Performance
Venue: arXiv cs.IT 2011
Year: 2011

In the present paper, a modification of the Index-less Indexed Flash Codes (ILIFC) for flash memory storage system is presented. Although the ILIFC proposed by Mahdavifar et al. has excellent worst case performance, the ILIFC can be further improved in terms of the average case performance. The proposed scheme, referred to as the {\em layered ILIFC}, is based on the ILIFC. However, the primary focus of the present study is the average case performance. The main feature of the proposed scheme is the use of the layer-based index coding to represent indices of information bits. The layer index coding promotes the uniform use of cell levels, which leads to better average case performance. Based on experiments, the proposed scheme achieves a larger average number of rewritings than the original ILIFC without loss of worst case performance.
Traced communication complexity of cellular automata
Venue: arXiv cs.FL 2011
Year: 2011

We study cellular automata with respect to a new communication complexity problem: each of two players know half of some finite word, and must be able to tell whether the state of the central cell will follow a given evolution, by communicating as little as possible between each other. We present some links with classical dynamical concepts, especially equicontinuity, expansiveness, entropy and give the asymptotic communication complexity of most elementary cellular automata.
Generation of Innovative and Sparse Encoding Vectors for Broadcast Systems with Feedback
Venue: arXiv cs.IT 2011
Year: 2011

In the application of linear network coding to wireless broadcasting with feedback, we prove that the problem of determining the existence of an innovative encoding vector is NP-complete when the finite field size is two. When the finite field size is larger than or equal to the number of users, it is shown that we can always find an encoding vector which is both innovative and sparse. The sparsity can be utilized in speeding up the decoding process. An efficient algorithm to generate innovative and sparse encoding vectors is developed. Simulations show that the delay performance of our scheme with binary finite field outperforms a number of existing schemes in terms of average and worst-case delay.
A Flow-aware MAC Protocol for a Passive Optical Metropolitan Area Network
Venue: arXiv cs.NI 2011
Year: 2011

The paper introduces an original MAC protocol for a passive optical metropolitan area network using time-domain wavelength interleaved networking (TWIN)% as proposed recently by Bell Labs . Optical channels are shared under the distributed control of destinations using a packet-based polling algorithm. This MAC is inspired more by EPON dynamic bandwidth allocation than the slotted, GPON-like access control generally envisaged for TWIN. Management of source-destination traffic streams is flow-aware with the size of allocated time slices being proportional to the number of active flows. This emulates a network-wide, distributed fair queuing scheduler, bringing the well-known implicit service differentiation and robustness advantages of this mechanism to the metro area network. The paper presents a comprehensive performance evaluation based on analytical modelling supported by simulations. The proposed MAC is shown to have excellent performance in terms of both traffic capacity and packet latency.
Optimal Spectrum Management in Multiuser Interference Channels
Venue: arXiv cs.IT 2011
Year: 2011

In this paper, we study the non-convex problem of continuous frequency optimal spectrum management in multiuser frequency selective interference channels. Firstly, a simple pairwise channel condition for FDMA schemes to achieve all Pareto optimal points of the rate region is derived. It enables fully distributed global optimal decision making on whether any two users should use orthogonal channels. Next, we present in detail an analytical solution to finding the global optimum of sum-rate maximization in two-user symmetric flat channels. Generalizing this solution to frequency selective channels, a convex optimization is established that solves the global optimum. Finally, we show that our method generalizes to K-user (K>=2) weighted sum-rate maximization in asymmetric frequency selective channels, and transform this classic non-convex optimization in the primal domain to an equivalent convex optimization. The complexity is shown to be separable in its dependence on the channel parameters and the power constraints.
On the Capacity Region of the Cognitive Interference Channel with Unidirectional Destination Cooperation
Venue: arXiv cs.IT 2011
Year: 2011

The cognitive interference channel with unidirectional destination cooperation (CIFC-UDC) is a variant of the cognitive interference channel (CIFC) where the cognitive (secondary) destination not only decodes the information sent from its sending dual but also helps enhance the communication of the primary user. This channel is an extension of the original CIFC to achieve a win-win solution under the coexistence condition. The CIFC-UDC comprises a broadcast channel (BC), a relay channel (RC), as well as a partially cooperative relay broadcast channel (PCRBC), and can be degraded to any one of them. In this paper, we propose a new achievable rate region for the dis-crete memoryless CIFC-UDC which improves the previous re-sults and includes the largest known rate regions of the BC, the RC, the PCRBC and the CIFC. A new outer bound is presented and proved to be tight for two classes of the CIFC-UDCs, result-ing in the characterization of the capacity region.
Efficient Algorithms for Dualizing Large-Scale Hypergraphs
Venue: arXiv cs.DS 2011
Year: 2011

A hypergraph ${\cal F}$ is a set family defined on vertex set $V$. The dual of ${\cal F}$ is the set of minimal subsets $H$ of $V$ such that $F\cap H \ne \emptyset$ for any $F\in {\cal F}$. The computation of the dual is equivalent to many problems, such as minimal hitting set enumeration of a subset family, minimal set cover enumeration, and the enumeration of hypergraph transversals. Although many algorithms have been proposed for solving the problem, to the best of our knowledge, none of them can work on large-scale input with a large number of output minimal hitting sets. This paper focuses on developing time- and space-efficient algorithms for solving the problem. We propose two new algorithms with new search methods, new pruning methods, and fast techniques for the minimality check. The computational experiments show that our algorithms are quite fast even for large-scale input for which existing algorithms do not terminate in a practical time.
On the Gain of Joint Processing of Pilot and Data Symbols in Stationary Rayleigh Fading Channels
Venue: arXiv cs.IT 2011
Year: 2011

In many typical mobile communication receivers the channel is estimated based on pilot symbols to allow for a coherent detection and decoding in a separate processing step. Currently much work is spent on receivers which break up this separation, e.g., by enhancing channel estimation based on reliability information on the data symbols. In the present work, we evaluate the possible gain of a joint processing of data and pilot symbols in comparison to the case of a separate processing in the context of stationary Rayleigh flat-fading channels. Therefore, we discuss the nature of the possible gain of a joint processing of pilot and data symbols. We show that the additional information that can be gained by a joint processing is captured in the temporal correlation of the channel estimation error of the solely pilot based channel estimation, which is not retrieved by the channel decoder in case of separate processing. In addition, we derive a new lower bound on the achievable rate for joint processing of pilot and data symbols.
Probability Based Clustering for Document and User Properties
Venue: arXiv cs.HC 2011
Year: 2011

Information Retrieval systems can be improved by exploiting context information such as user and document features. This article presents a model based on overlapping probabilistic or fuzzy clusters for such features. The model is applied within a fusion method which linearly combines several retrieval systems. The fusion is based on weights for the different retrieval systems which are learned by exploiting relevance feedback information. This calculation can be improved by maintaining a model for each document and user cluster. That way, the optimal retrieval system for each document or user type can be identified and applied. The extension presented in this article allows overlapping, probabilistic clusters of features to further refine the process.
On the Imitation Strategy for Games on Graphs
Venue: arXiv cs.GT 2011
Year: 2011

In evolutionary game theory, repeated two-player games are used to study strategy evolution in a population under natural selection. As the evolution greatly depends on the interaction structure, there has been growing interests in studying the games on graphs. In this setting, players occupy the vertices of a graph and play the game only with their immediate neighbours. Various evolutionary dynamics have been studied in this setting for different games. Due to the complexity of the analysis, however, most of the work in this area is experimental. This paper aims to contribute to a more complete understanding, by providing rigorous analysis. We study the imitation dynamics on two classes of graph: cycles and complete graphs. We focus on three well known social dilemmas, namely the Prisoner's Dilemma, the Stag Hunt and the Snowdrift Game. We also consider, for completeness, the so-called Harmony Game. Our analysis shows that, on the cycle, all four games converge fast, either to total cooperation or total defection. On the complete graph, all but the Snowdrift game converge fast, either to cooperation or defection. The Snowdrift game reaches a metastable state fast, where cooperators and defectors coexist. It will converge to cooperation or defection only after spending time in this state which is exponential in the size, n, of the graph. In exceptional cases, it will remain in this state indefinitely. Our theoretical results are supported by experimental investigations.