OpenRaiser/Intern-Atlas huggingface dataset:
The Serializability of Network Codes
Venue: arXiv cs.IT 2010
Year: 2010

Network coding theory studies the transmission of information in networks whose vertices may perform nontrivial encoding and decoding operations on data as it passes through the network. The main approach to deciding the feasibility of network coding problems aims to reduce the problem to optimization over a polytope of entropic vectors subject to constraints imposed by the network structure. In the case of directed acyclic graphs, these constraints are completely understood, but for general graphs the problem of enumerating them remains open: it is not known how to classify the constraints implied by a property that we call serializability, which refers to the absence of paradoxical circular dependencies in a network code. In this work we initiate the first systematic study of the constraints imposed on a network code by serializability. We find that serializability cannot be detected solely by evaluating the Shannon entropy of edge sets in the graph, but nevertheless, we give a polynomial-time algorithm that decides the serializability of a network code. We define a certificate of non-serializability, called an information vortex, that plays a role in the theory of serializability comparable to the role of fractional cuts in multicommodity flow theory, including a type of min-max relation. Finally, we study the serializability deficit of a network code, defined as the minimum number of extra bits that must be sent in order to make it serializable. For linear codes, we show that it is NP-hard to approximate this parameter within a constant factor, and we demonstrate some surprising facts about the behavior of this parameter under parallel composition of codes.
Optimal Cooperative Relaying Schemes for Improving Wireless Physical Layer Security
Venue: arXiv cs.IT 2010
Year: 2010

We consider a cooperative wireless network in the presence of one of more eavesdroppers, and exploit node cooperation for achieving physical (PHY) layer based security. Two different cooperation schemes are considered. In the first scheme, cooperating nodes retransmit a weighted version of the source signal in a decode-and-forward (DF) fashion. In the second scheme, while the source is transmitting, cooperating nodes transmit weighted noise to confound the eavesdropper (cooperative jamming (CJ)). We investigate two objectives, i.e., maximization of achievable secrecy rate subject to a total power constraint, and minimization of total power transmit power under a secrecy rate constraint. For the first design objective with a single eavesdropper we obtain expressions for optimal weights under the DF protocol in closed form, and give an algorithm that converges to the optimal solution for the CJ scheme; while for multiple eavesdroppers we give an algorithm for the solution using the DF protocol that is guaranteed to converge to the optimal solution for two eavesdroppers. For the second design objective, existing works introduced additional constraints in order to reduce the degree of difficulty, thus resulting in suboptimal solutions. In this work, either a closed form solution is obtained, or algorithms to search for the solution are proposed. Numerical results are presented to illustrate the proposed schemes and demonstrate the advantages of cooperation as compared to direct transmission.
On the Capacity of Non-Coherent Network Coding
Venue: arXiv cs.IT 2010
Year: 2010

We consider the problem of multicasting information from a source to a set of receivers over a network where intermediate network nodes perform randomized network coding operations on the source packets. We propose a channel model for the non-coherent network coding introduced by Koetter and Kschischang in [6], that captures the essence of such a network operation, and calculate the capacity as a function of network parameters. We prove that use of subspace coding is optimal, and show that, in some cases, the capacity-achieving distribution uses subspaces of several dimensions, where the employed dimensions depend on the packet length. This model and the results also allow us to give guidelines on when subspace coding is beneficial for the proposed model and by how much, in comparison to a coding vector approach, from a capacity viewpoint. We extend our results to the case of multiple source multicast that creates a virtual multiple access channel.
Combinatorial Auctions with Budgets
Venue: arXiv cs.GT 2010
Year: 2010

We consider budget constrained combinatorial auctions where bidder $i$ has a private value $v_i$, a budget $b_i$, and is interested in all the items in $S_i$. The value to agent $i$ of a set of items $R$ is $|R \cap S_i| \cdot v_i$. Such auctions capture adword auctions, where advertisers offer a bid for ads in response to an advertiser-dependent set of adwords, and advertisers have budgets. It is known that even of all items are identical and all budgets are public it is not possible to be truthful and efficient. Our main result is a novel auction that runs in polynomial time, is incentive compatible, and ensures Pareto-optimality for such auctions when the valuations are private and the budgets are public knowledge. This extends the result of Dobzinski et al. (FOCS 2008) for auctions of multiple {\sl identical} items and public budgets to single-valued {\sl combinatorial} auctions with public budgets.
Threshold Saturation via Spatial Coupling: Why Convolutional LDPC Ensembles Perform so well over the BEC
Venue: arXiv cs.IT 2010
Year: 2010

Convolutional LDPC ensembles, introduced by Felstrom and Zigangirov, have excellent thresholds and these thresholds are rapidly increasing as a function of the average degree. Several variations on the basic theme have been proposed to date, all of which share the good performance characteristics of convolutional LDPC ensembles. We describe the fundamental mechanism which explains why "convolutional-like" or "spatially coupled" codes perform so well. In essence, the spatial coupling of the individual code structure has the effect of increasing the belief-propagation (BP) threshold of the new ensemble to its maximum possible value, namely the maximum-a-posteriori (MAP) threshold of the underlying ensemble. For this reason we call this phenomenon "threshold saturation." This gives an entirely new way of approaching capacity. One significant advantage of such a construction is that one can create capacity-approaching ensembles with an error correcting radius which is increasing in the blocklength. Our proof makes use of the area theorem of the BP-EXIT curve and the connection between the MAP and BP threshold recently pointed out by Measson, Montanari, Richardson, and Urbanke. Although we prove the connection between the MAP and the BP threshold only for a very specific ensemble and only for the binary erasure channel, empirically a threshold saturation phenomenon occurs for a wide class of ensembles and channels. More generally, we conjecture that for a large range of graphical systems a similar saturation of the "dynamical" threshold occurs once individual components are coupled sufficiently strongly. This might give rise to improved algorithms as well as to new techniques for analysis.
Generalized Degrees of Freedom of the Interference Channel with a Signal Cognitive Relay
Venue: arXiv cs.IT 2010
Year: 2010

We study the interference channel with a signal cognitive relay. A signal cognitive relay knows the transmit signals (but not the messages) of the sources non-causally, and tries to help them communicating with their respective destinations. We derive upper bounds and provide achievable schemes for this channel. These upper and lower bounds are shown to be tight from generalized degrees of freedom point of view. As a result, a characterization of the generalized degrees of freedom of the interference channel with a signal cognitive relay is given.
New Criteria for Iterative Decoding
Venue: arXiv cs.IT 2010
Year: 2010

Iterative decoding was not originally introduced as the solution to an optimization problem rendering the analysis of its convergence very difficult. In this paper, we investigate the link between iterative decoding and classical optimization techniques. We first show that iterative decoding can be rephrased as two embedded minimization processes involving the Fermi-Dirac distance. Based on this new formulation, an hybrid proximal point algorithm is first derived with the additional advantage of decreasing a desired criterion. In a second part, an hybrid minimum entropy algorithm is proposed with improved performance compared to the classical iterative decoding. Even if this paper focus on iterative decoding for BICM, the results can be applied to the large class of turbo-like decoders.
Formal Theories for Logspace Counting
Venue: arXiv cs.LO 2010
Year: 2010

We introduce two-sorted theories in the style of Cook and Nguyen for the complexity classes ParityL and DET, whose complete problems include determinants over GF(2) and Z, respectively. The definable functions in these theories are the functions in the corresponding complexity classes; thus each theory formalizes reasoning using concepts from its corresponding complexity class.
A Framework for Validation of Object Oriented Design Metrics
Venue: arXiv cs.SE 2010
Year: 2010

A large number of metrics have been proposed for the quality of object oriented software. Many of these metrics have not been properly validated due to poor methods of validation and non acceptance of metrics on scientific grounds. In the literature, two types of validations namely internal (theoretical) and external (empirical) are recommended. In this study, the authors have used both theoretical as well as empirical validation for validating already proposed set of metrics for the five quality factors. These metrics were proposed by Kumar and Soni.
NLHB : A Non-Linear Hopper Blum Protocol
Venue: arXiv cs.CR 2010
Year: 2010

In this paper, we propose a light-weight provably-secure authentication protocol called the NLHB protocol, which is a variant of the HB protocol. The HB protocol uses the complexity of decoding linear codes for security against passive attacks. In contrast, security for the NLHB protocol is proved by reducing passive attacks to the problem of decoding a class of non-linear codes that are provably hard. We demonstrate that the existing passive attacks on the HB protocol family, which have contributed to considerable reduction in its effective key-size, are ineffective against the NLHB protocol. From the evidence, we conclude that smaller-key sizes are sufficient for the NLHB protocol to achieve the same level of passive attack security as the HB Protocol. Further, for this choice of parameters, we provide an implementation instance for the NLHB protocol for which the Prover/Verifier complexity is lower than the HB protocol, enabling authentication on very low-cost devices like RFID tags. Finally, in the spirit of the HB$^{+}$ protocol, we extend the NLHB protocol to the NLHB$^{+}$ protocol and prove security against the class of active attacks defined in the DET Model.
Deriving the Probabilistic Capacity of General Run-Length Sets Using Generating Functions
Venue: arXiv cs.IT 2010
Year: 2010

In "Reliable Communication in the Absence of a Common Clock" (Yeung et al., 2009), the authors introduce general run-length sets, which form a class of constrained systems that permit run-lengths from a countably infinite set. For a particular definition of probabilistic capacity, they show that probabilistic capacity is equal to combinatorial capacity. In the present work, it is shown that the same result also holds for Shannon's original definition of probabilistic capacity. The derivation presented here is based on generating functions of constrained systems as developed in "On the Capacity of Constrained Systems" (Boecherer et al., 2010) and provides a unified information-theoretic treatment of general run-length sets.
Syllable Analysis to Build a Dictation System in Telugu language
Venue: arXiv cs.CL 2010
Year: 2010

In recent decades, Speech interactive systems gained increasing importance. To develop Dictation System like Dragon for Indian languages it is most important to adapt the system to a speaker with minimum training. In this paper we focus on the importance of creating speech database at syllable units and identifying minimum text to be considered while training any speech recognition system. There are systems developed for continuous speech recognition in English and in few Indian languages like Hindi and Tamil. This paper gives the statistical details of syllables in Telugu and its use in minimizing the search space during recognition of speech. The minimum words that cover maximum syllables are identified. This words list can be used for preparing a small text which can be used for collecting speech sample while training the dictation system. The results are plotted for frequency of syllables and the number of syllables in each word. This approach is applied on the CIIL Mysore text corpus which is of 3 million words.
Call Admission Control performance model for Beyond 3G Wireless Networks
Venue: arXiv cs.NI 2010
Year: 2010

The Next Generation Wireless Networks (NGWN) will be heterogeneous in nature where the different Radio Access Technologies (RATs) operate together .The mobile terminals operating in this heterogeneous environment will have different QoS requirements to be handled by the system. These QoS requirements are determined by a set of QoS parameters. The radio resource management is one of the key challenges in NGWN. Call admission control is one of the radio resource management technique plays instrumental role in ensure the desired QoS to the users working on different applications which have diversified QoS requirements from the wireless networks . The call blocking probability is one such QoS parameter for the wireless network. For better QoS it is desirable to reduce the call blocking probability. In this customary scenario it is highly desirable to obtain analytic Performance model. In this paper we propose a higher order Markov chain based performance model for call admission control in a heterogeneous wireless network environment. In the proposed algorithm we have considered three classes of traffic having different QoS requirements and we have considered the heterogeneous network environment which includes the RATs that can effectively handle applications like voice calls, Web browsing and file transfer applications which are with varied QoS parameters. The paper presents the call blocking probabilities for all the three types of traffic both for fixed and varied traffic scenario.
Efficient Candidacy Reduction For Frequent Pattern Mining
Venue: arXiv cs.DB 2010
Year: 2010

Certainly, nowadays knowledge discovery or extracting knowledge from large amount of data is a desirable task in competitive businesses. Data mining is a main step in knowledge discovery process. Meanwhile frequent patterns play central role in data mining tasks such as clustering, classification, and association analysis. Identifying all frequent patterns is the most time consuming process due to a massive number of candidate patterns. For the past decade there have been an increasing number of efficient algorithms to mine the frequent patterns. However reducing the number of candidate patterns and comparisons for support counting are still two problems in this field which have made the frequent pattern mining one of the active research themes in data mining. A reasonable solution is identifying a small candidate pattern set from which can generate all frequent patterns. In this paper, a method is proposed based on a new candidate set called candidate head set or H which forms a small set of candidate patterns. The experimental results verify the accuracy of the proposed method and reduction of the number of candidate patterns and comparisons.
Mutual Information of IID Complex Gaussian Signals on Block Rayleigh-faded Channels
Venue: arXiv cs.IT 2010
Year: 2010

We present a method to compute, quickly and efficiently, the mutual information achieved by an IID (independent identically distributed) complex Gaussian input on a block Rayleigh-faded channel without side information at the receiver. The method accommodates both scalar and MIMO (multiple-input multiple-output) settings. Operationally, the mutual information thus computed represents the highest spectral efficiency that can be attained using standard Gaussian codebooks. Examples are provided that illustrate the loss in spectral efficiency caused by fast fading and how that loss is amplified by the use of multiple transmit antennas. These examples are further enriched by comparisons with the channel capacity under perfect channel-state information at the receiver, and with the spectral efficiency attained by pilot-based transmission.
Dense Error Correction for Low-Rank Matrices via Principal Component Pursuit
Venue: arXiv cs.IT 2010
Year: 2010

We consider the problem of recovering a low-rank matrix when some of its entries, whose locations are not known a priori, are corrupted by errors of arbitrarily large magnitude. It has recently been shown that this problem can be solved efficiently and effectively by a convex program named Principal Component Pursuit (PCP), provided that the fraction of corrupted entries and the rank of the matrix are both sufficiently small. In this paper, we extend that result to show that the same convex program, with a slightly improved weighting parameter, exactly recovers the low-rank matrix even if "almost all" of its entries are arbitrarily corrupted, provided the signs of the errors are random. We corroborate our result with simulations on randomly generated matrices and errors.
Stable Principal Component Pursuit
Venue: arXiv cs.IT 2010
Year: 2010

In this paper, we study the problem of recovering a low-rank matrix (the principal components) from a high-dimensional data matrix despite both small entry-wise noise and gross sparse errors. Recently, it has been shown that a convex program, named Principal Component Pursuit (PCP), can recover the low-rank matrix when the data matrix is corrupted by gross sparse errors. We further prove that the solution to a related convex program (a relaxed PCP) gives an estimate of the low-rank matrix that is simultaneously stable to small entrywise noise and robust to gross sparse errors. More precisely, our result shows that the proposed convex program recovers the low-rank matrix even though a positive fraction of its entries are arbitrarily corrupted, with an error bound proportional to the noise level. We present simulation results to support our result and demonstrate that the new convex program accurately recovers the principal components (the low-rank matrix) under quite broad conditions. To our knowledge, this is the first result that shows the classical Principal Component Analysis (PCA), optimal for small i.i.d. noise, can be made robust to gross sparse errors; or the first that shows the newly proposed PCP can be made stable to small entry-wise perturbations.
On the Sets of Real Numbers Recognized by Finite Automata in Multiple Bases
Venue: arXiv cs.LO 2010
Year: 2010

This article studies the expressive power of finite automata recognizing sets of real numbers encoded in positional notation. We consider Muller automata as well as the restricted class of weak deterministic automata, used as symbolic set representations in actual applications. In previous work, it has been established that the sets of numbers that are recognizable by weak deterministic automata in two bases that do not share the same set of prime factors are exactly those that are definable in the first order additive theory of real and integer numbers. This result extends Cobham's theorem, which characterizes the sets of integer numbers that are recognizable by finite automata in multiple bases. In this article, we first generalize this result to multiplicatively independent bases, which brings it closer to the original statement of Cobham's theorem. Then, we study the sets of reals recognizable by Muller automata in two bases. We show with a counterexample that, in this setting, Cobham's theorem does not generalize to multiplicatively independent bases. Finally, we prove that the sets of reals that are recognizable by Muller automata in two bases that do not share the same set of prime factors are exactly those definable in the first order additive theory of real and integer numbers. These sets are thus also recognizable by weak deterministic automata. This result leads to a precise characterization of the sets of real numbers that are recognizable in multiple bases, and provides a theoretical justification to the use of weak automata as symbolic representations of sets.
A new proof of Delsarte, Goethals and Mac Williams theorem on minimal weight codewords of generalized Reed-Muller code
Venue: arXiv cs.IT 2010
Year: 2010

We give a new proof of Delsarte, Goethals and Mac williams theorem on minimal weight codewords of generalized Reed-Muller codes published in 1970. To prove this theorem, we consider intersection of support of minimal weight codewords with affine hyperplanes and we proceed by recursion.
Delay-rate tradeoff for ergodic interference alignment in the Gaussian case
Venue: arXiv cs.IT 2010
Year: 2010

In interference alignment, users sharing a wireless channel are each able to achieve data rates of up to half of the non-interfering channel capacity, no matter the number of users. In an ergodic setting, this is achieved by pairing complementary channel realizations in order to amplify signals and cancel interference. However, this scheme has the possibility for large delays in decoding message symbols. We show that delay can be mitigated by using outputs from potentially more than two channel realizations, although data rate may be reduced. We further demonstrate the tradeoff between rate and delay via a time-sharing strategy. Our analysis considers Gaussian channels; an extension to finite field channels is also possible.
A Steganography Based on CT-CDMA Communication Scheme Using Complete Complementary Codes
Venue: arXiv cs.IT 2010
Year: 2010

It has been shown that complete complementary codes can be applied into some communication systems like approximately synchronized CDMA systems because of its good correlation properties. CT-CDMA is one of the communication systems based on complete complementary codes. In this system, the information data of the multiple users can be transmitted by using the same set of complementary codes through a single frequency band. In this paper, we propose to apply CT-CDMA systems into a kind of steganography. It is shown that a large amount of secret data can be embedded in the stego image by the proposed method through some numerical experiments using color images.