OpenRaiser/Intern-Atlas huggingface dataset:
Discrete Memoryless Interference and Broadcast Channels with Confidential Messages: Secrecy Rate Regions
Venue: arXiv cs.IT 2007
Year: 2007

We study information-theoretic security for discrete memoryless interference and broadcast channels with independent confidential messages sent to two receivers. Confidential messages are transmitted to their respective receivers with information-theoretic secrecy. That is, each receiver is kept in total ignorance with respect to the message intended for the other receiver. The secrecy level is measured by the equivocation rate at the eavesdropping receiver. In this paper, we present inner and outer bounds on secrecy capacity regions for these two communication systems. The derived outer bounds have an identical mutual information expression that applies to both channel models. The difference is in the input distributions over which the expression is optimized. The inner bound rate regions are achieved by random binning techniques. For the broadcast channel, a double-binning coding scheme allows for both joint encoding and preserving of confidentiality. Furthermore, we show that, for a special case of the interference channel, referred to as the switch channel, the two bound bounds meet. Finally, we describe several transmission schemes for Gaussian interference channels and derive their achievable rate regions while ensuring mutual information-theoretic secrecy. An encoding scheme in which transmitters dedicate some of their power to create artificial noise is proposed and shown to outperform both time-sharing and simple multiplexed transmission of the confidential messages.
An identity of Chernoff bounds with an interpretation in statistical physics and applications in information theory
Venue: arXiv cs.IT 2007
Year: 2007

An identity between two versions of the Chernoff bound on the probability a certain large deviations event, is established. This identity has an interpretation in statistical physics, namely, an isothermal equilibrium of a composite system that consists of multiple subsystems of particles. Several information--theoretic application examples, where the analysis of this large deviations probability naturally arises, are then described from the viewpoint of this statistical mechanical interpretation. This results in several relationships between information theory and statistical physics, which we hope, the reader will find insightful.
Wild, Wild Wikis: A way forward
Venue: arXiv cs.IR 2007
Year: 2007

Wikis can be considered as public domain knowledge sharing system. They provide opportunity for those who may not have the privilege to publish their thoughts through the traditional methods. They are one of the fastest growing systems of online encyclopaedia. In this study, we consider the importance of wikis as a way of creating, sharing and improving public knowledge. We identify some of the problems associated with wikis to include, (a) identification of the identities of information and its creator (b) accuracy of information (c) justification of the credibility of authors (d) vandalism of quality of information (e) weak control over the contents. A solution to some of these problems is sought through the use of an annotation model. The model assumes that contributions in wikis can be seen as annotation to the initial document. It proposed a systematic control of contributors and contributions to the initiative and the keeping of records of what existed and what was done to initial documents. We believe that with this model, analysis can be done on the progress of wiki initiatives. We assumed that using this model, wikis can be better used for creation and sharing of knowledge for public use.
AMIEDoT: An annotation model for document tracking and recommendation service
Venue: arXiv cs.IR 2007
Year: 2007

The primary objective of document annotation in whatever form, manual or electronic is to allow those who may not have control to original document to provide personal view on information source. Beyond providing personal assessment to original information sources, we are looking at a situation where annotation made can be used as additional source of information for document tracking and recommendation service. Most of the annotation tools existing today were conceived for their independent use with no reference to the creator of the annotation. We propose AMIEDoT (Annotation Model for Information Exchange and Document Tracking) an annotation model that can assist in document tracking and recommendation service. The model is based on three parameters in the acts of annotation. We believe that introducing document parameters, time and the parameters of the creator of annotation into an annotation process can be a dependable source to know, who used a document, when a document was used and for what a document was used for. Beyond document tracking, our model can be used in not only for selective dissemination of information but for recommendation services. AMIEDoT can also be used for information sharing and information reuse.
Guessing based on length functions
Venue: arXiv cs.IT 2007
Year: 2007

A guessing wiretapper's performance on a Shannon cipher system is analyzed for a source with memory. Close relationships between guessing functions and length functions are first established. Subsequently, asymptotically optimal encryption and attack strategies are identified and their performances analyzed for sources with memory. The performance metrics are exponents of guessing moments and probability of large deviations. The metrics are then characterized for unifilar sources. Universal asymptotically optimal encryption and attack strategies are also identified for unifilar sources. Guessing in the increasing order of Lempel-Ziv coding lengths is proposed for finite-state sources, and shown to be asymptotically optimal. Finally, competitive optimality properties of guessing in the increasing order of description lengths and Lempel-Ziv coding lengths are demonstrated.
Efficient Searching and Retrieval of Documents in PROSA
Venue: arXiv cs.DC 2007
Year: 2007

Retrieving resources in a distributed environment is more difficult than finding data in centralised databases. In the last decade P2P system arise as new and effective distributed architectures for resource sharing, but searching in such environments could be difficult and time-consuming. In this paper we discuss efficiency of resource discovery in PROSA, a self-organising P2P system heavily inspired by social networks. All routing choices in PROSA are made locally, looking only at the relevance of the next peer to each query. We show that PROSA is able to effectively answer queries for rare documents, forwarding them through the most convenient path to nodes that much probably share matching resources. This result is heavily related to the small-world structure that naturally emerges in PROSA.
Tree Automata and Essential Input Variables
Venue: arXiv cs.CC 2007
Year: 2007

We introduce and study the essential inputs (variables) for terms (trees) and tree automata.
Assessing the Value of Coooperation in Wikipedia
Venue: arXiv cs.DL 2007
Year: 2007

Since its inception six years ago, the online encyclopedia Wikipedia has accumulated 6.40 million articles and 250 million edits, contributed in a predominantly undirected and haphazard fashion by 5.77 million unvetted volunteers. Despite the apparent lack of order, the 50 million edits by 4.8 million contributors to the 1.5 million articles in the English-language Wikipedia follow strong certain overall regularities. We show that the accretion of edits to an article is described by a simple stochastic mechanism, resulting in a heavy tail of highly visible articles with a large number of edits. We also demonstrate a crucial correlation between article quality and number of edits, which validates Wikipedia as a successful collaborative effort.
Games on the Sperner Triangle
Venue: arXiv cs.GT 2007
Year: 2007

We create a new two-player game on the Sperner Triangle based on Sperner's lemma. Our game has simple rules and several desirable properties. First, the game is always certain to have a winner. Second, like many other interesting games such as Hex and Geography, we prove that deciding whether one can win our game is a PSPACE-complete problem. Third, there is an elegant balance in the game such that neither the first nor the second player always has a decisive advantage. We provide a web-based version of the game, playable at: http://cs-people.bu.edu/paithan/spernerGame/ . In addition we propose other games, also based on fixed-point theorems.
In Search of Simplicity: A Self-Organizing Multi-Source Multicast Overlay
Venue: arXiv cs.DC 2007
Year: 2007

Multicast communication primitives have broad utility as building blocks for distributed applications. The challenge is to create and maintain the distributed structures that support these primitives while accounting for volatile end nodes and variable network characteristics. Most solutions proposed to date rely on complex algorithms or global information, thus limiting the scale of deployments and acceptance outside the academic realm. This article introduces a low-complexity, self organizing solution for maintaining multicast trees, that we refer to as UMM (Unstructured Multi-source Multicast). UMM uses traditional distributed systems techniques: layering, soft-state, and passive data collection to adapt to the dynamics of the physical network and maintain data dissemination trees. The result is a simple, adaptive system with lower overheads than more complex alternatives. We have implemented UMM and evaluated it on a 100-node PlanetLab testbed and on up to 1024-node emulated ModelNet networks Extensive experimental evaluations demonstrate UMM's low overhead, efficient network usage compared to alternative solutions, and ability to quickly adapt to network changes and to recover from failures.
Intensional properties of polygraphs
Venue: arXiv cs.LO 2007
Year: 2007

We present polygraphic programs, a subclass of Albert Burroni's polygraphs, as a computational model, showing how these objects can be seen as first-order functional programs. We prove that the model is Turing complete. We use polygraphic interpretations, a termination proof method introduced by the second author, to characterize polygraphic programs that compute in polynomial time. We conclude with a characterization of polynomial time functions and non-deterministic polynomial time functions.
NLC-2 graph recognition and isomorphism
Venue: arXiv cs.DS 2007
Year: 2007

NLC-width is a variant of clique-width with many application in graph algorithmic. This paper is devoted to graphs of NLC-width two. After giving new structural properties of the class, we propose a $O(n^2 m)$-time algorithm, improving Johansson's algorithm \cite{Johansson00}. Moreover, our alogrithm is simple to understand. The above properties and algorithm allow us to propose a robust $O(n^2 m)$-time isomorphism algorithm for NLC-2 graphs. As far as we know, it is the first polynomial-time algorithm.
Outage Probability of Multiple-Input Single-Output (MISO) Systems with Delayed Feedback
Venue: arXiv cs.IT 2007
Year: 2007

We investigate the effect of feedback delay on the outage probability of multiple-input single-output (MISO) fading channels. Channel state information at the transmitter (CSIT) is a delayed version of the channel state information available at the receiver (CSIR). We consider two cases of CSIR: (a) perfect CSIR and (b) CSI estimated at the receiver using training symbols. With perfect CSIR, under a short-term power constraint, we determine: (a) the outage probability for beamforming with imperfect CSIT (BF-IC) analytically, and (b) the optimal spatial power allocation (OSPA) scheme that minimizes outage numerically. Results show that, for delayed CSIT, BF-IC is close to optimal for low SNR and uniform spatial power allocation (USPA) is close to optimal at high SNR. Similarly, under a long-term power constraint, we show that BF-IC is close to optimal for low SNR and USPA is close to optimal at high SNR. With imperfect CSIR, we obtain an upper bound on the outage probability with USPA and BF-IC. Results show that the loss in performance due to imperfection in CSIR is not significant, if the training power is chosen appropriately.
An $L (1/3 + ε)$ Algorithm for the Discrete Logarithm Problem for Low Degree Curves
Venue: arXiv cs.CR 2007
Year: 2007

The discrete logarithm problem in Jacobians of curves of high genus $g$ over finite fields $\FF_q$ is known to be computable with subexponential complexity $L_{q^g}(1/2, O(1))$. We present an algorithm for a family of plane curves whose degrees in $X$ and $Y$ are low with respect to the curve genus, and suitably unbalanced. The finite base fields are arbitrary, but their sizes should not grow too fast compared to the genus. For this family, the group structure can be computed in subexponential time of $L_{q^g}(1/3, O(1))$, and a discrete logarithm computation takes subexponential time of $L_{q^g}(1/3+ε, o(1))$ for any positive $ε$. These runtime bounds rely on heuristics similar to the ones used in the number field sieve or the function field sieve algorithms.
Delay and Throughput Optimal Scheduling for OFDM Broadcast Channels
Venue: arXiv cs.IT 2007
Year: 2007

In this paper a scheduling policy is presented which minimizes the average delay of the users. The scheduling scheme is investigated both by analysis and simulations carried out in the context of Orthogonal Frequency Division Multiplexing (OFDM) broadcast channels (BC). First the delay optimality is obtained for a static scenario providing solutions for specific subproblems, then the analysis is carried over to the dynamic scheme. Furthermore auxiliary tools are given for proving throughput optimality. Finally simulations show the superior performance of the presented scheme.
Doppler Resilient Waveforms with Perfect Autocorrelation
Venue: arXiv cs.IT 2007
Year: 2007

We describe a method of constructing a sequence of phase coded waveforms with perfect autocorrelation in the presence of Doppler shift. The constituent waveforms are Golay complementary pairs which have perfect autocorrelation at zero Doppler but are sensitive to nonzero Doppler shifts. We extend this construction to multiple dimensions, in particular to radar polarimetry, where the two dimensions are realized by orthogonal polarizations. Here we determine a sequence of two-by-two Alamouti matrices where the entries involve Golay pairs and for which the sum of the matrix-valued ambiguity functions vanish at small Doppler shifts. The Prouhet-Thue-Morse sequence plays a key role in the construction of Doppler resilient sequences of Golay pairs.
Geometry and the complexity of matrix multiplication
Venue: arXiv cs.CC 2007
Year: 2007

We survey results in algebraic complexity theory, focusing on matrix multiplication. Our goals are (i.) to show how open questions in algebraic complexity theory are naturally posed as questions in geometry and representation theory, (ii.) to motivate researchers to work on these questions, and (iii.) to point out relations with more general problems in geometry. The key geometric objects for our study are the secant varieties of Segre varieties. We explain how these varieties are also useful for algebraic statistics, the study of phylogenetic invariants, and quantum computing.
Broadcast Capacity Region of Two-Phase Bidirectional Relaying
Venue: arXiv cs.IT 2007
Year: 2007

In a three-node network a half-duplex relay node enables bidirectional communication between two nodes with a spectral efficient two phase protocol. In the first phase, two nodes transmit their message to the relay node, which decodes the messages and broadcast a re-encoded composition in the second phase. In this work we determine the capacity region of the broadcast phase. In this scenario each receiving node has perfect information about the message that is intended for the other node. The resulting set of achievable rates of the two-phase bidirectional relaying includes the region which can be achieved by applying XOR on the decoded messages at the relay node. We also prove the strong converse for the maximum error probability and show that this implies that the $[\eps_1,\eps_2]$-capacity region defined with respect to the average error probability is constant for small values of error parameters $\eps_1$, $\eps_2$.
Dimension and Relative Frequencies
Venue: arXiv cs.CC 2007
Year: 2007

We show how to calculate the finite-state dimension (equivalently, the finite-state compressibility) of a saturated sets $X$ consisting of {\em all} infinite sequences $S$ over a finite alphabet $Σ_m$ satisfying some given condition $P$ on the asymptotic frequencies with which various symbols from $Σ_m$ appear in $S$. When the condition $P$ completely specifies an empirical probability distribution $π$ over $Σ_m$, i.e., a limiting frequency of occurrence for {\em every} symbol in $Σ_m$, it has been known since 1949 that the Hausdorff dimension of $X$ is precisely $\CH(π)$, the Shannon entropy of $π$, and the finite-state dimension was proven to have this same value in 2001. The saturated sets were studied by Volkmann and Cajar decades ago. It got attention again only with the recent developments in multifractal analysis by Barreira, Saussol, Schmeling, and separately Olsen. However, the powerful methods they used -- ergodic theory and multifractal analysis -- do not yield a value for the finite-state (or even computable) dimension in an obvious manner. We give a pointwise characterization of finite-state dimensions of saturated sets. Simultaneously, we also show that their finite-state dimension and strong dimension coincide with their Hausdorff and packing dimension respectively, though the techniques we use are completely elementary. Our results automatically extend to less restrictive effective settings (e.g., constructive, computable, and polynomial-time dimensions).
Some problems in asymptotic convex geometry and random matrices motivated by numerical algorithms
Venue: arXiv cs.CG 2007
Year: 2007

The simplex method in Linear Programming motivates several problems of asymptotic convex geometry. We discuss some conjectures and known results in two related directions -- computing the size of projections of high dimensional polytopes and estimating the norms of random matrices and their inverses.
Constrained Cost-Coupled Stochastic Games with Independent State Processes
Venue: arXiv cs.IT 2007
Year: 2007

We consider a non-cooperative constrained stochastic games with N players with the following special structure. With each player there is an associated controlled Markov chain. The transition probabilities of the i-th Markov chain depend only on the state and actions of controller i. The information structure that we consider is such that each player knows the state of its own MDP and its own actions. It does not know the states of, and the actions taken by other players. Finally, each player wishes to minimize a time-average cost function, and has constraints over other time-avrage cost functions. Both the cost that is minimized as well as those defining the constraints depend on the state and actions of all players. We study in this paper the existence of a Nash equilirium. Examples in power control in wireless communications are given.
Practical Identity-Based Encryption (IBE) in Multiple PKG Environments and Its Applications
Venue: arXiv cs.CR 2007
Year: 2007

In this paper, we present a new identity-based encryption (IBE) scheme using bilinear pairings. Our IBE scheme enjoys the same \textsf{Key Extraction} and \textsf{Decryption} algorithms with the famous IBE scheme of Boneh and Franklin (BF-IBE for short), while differs from the latter in that it has modified \textsf{Setup} and \textsf{Encryption} algorithms. Compared with BF-IBE, we show that ours are more practical in a multiple private key generator (PKG) environment, mainly due to that the session secret $g_{ID}$ could be pre-computed \emph{before} any interaction, and the sender could encrypt a message using $g_{ID}$ prior to negotiating with the intended recipient(s). As an application of our IBE scheme, we also derive an escrowed ElGamal scheme which possesses certain good properties in practice.
Clustering and Sharing Incentives in BitTorrent Systems
Venue: arXiv cs.NI 2007
Year: 2007

Peer-to-peer protocols play an increasingly instrumental role in Internet content distribution. It is therefore important to gain a complete understanding of how these protocols behave in practice and how their operating parameters affect overall system performance. This paper presents the first detailed experimental investigation of the peer selection strategy in the popular BitTorrent protocol. By observing more than 40 nodes in instrumented private torrents, we validate three protocol properties that, though believed to hold, have not been previously demonstrated experimentally: the clustering of similar-bandwidth peers, the effectiveness of BitTorrent's sharing incentives, and the peers' high uplink utilization. In addition, we observe that BitTorrent's modified choking algorithm in seed state provides uniform service to all peers, and that an underprovisioned initial seed leads to absence of peer clustering and less effective sharing incentives. Based on our results, we provide guidelines for seed provisioning by content providers, and discuss a tracker protocol extension that addresses an identified limitation of the protocol.
Wireless Lan to Support Multimedia Communication Using Spread Spectrum Technology
Venue: arXiv cs.NI 2007
Year: 2007

Wireless LAN is currently enjoying rapid deployment in University departments, business offices, hospitals and homes. It becomes an inexpensive technology and allows multiple numbers of the households to simultaneously access the internet while roaming about the house. In the present work, the design and development of a wireless LAN is highlighted which utilizes direct sequence spread spectrum (DSSS) technology at 900MHz RF carrier frequency in its physical layer. This provides enormous security in the physical layer and hence it is very difficult to hack or jam the network. The installation cost is also less due to the use of 900 MHz RF carrier frequency..
Maximum Weighted Sum Rate of Multi-Antenna Broadcast Channels
Venue: arXiv cs.IT 2007
Year: 2007

Recently, researchers showed that dirty paper coding (DPC) is the optimal transmission strategy for multiple-input multiple-output broadcast channels (MIMO-BC). In this paper, we study how to determine the maximum weighted sum of DPC rates through solving the maximum weighted sum rate problem of the dual MIMO multiple access channel (MIMO-MAC) with a sum power constraint. We first simplify the maximum weighted sum rate problem such that enumerating all possible decoding orders in the dual MIMO-MAC is unnecessary. We then design an efficient algorithm based on conjugate gradient projection (CGP) to solve the maximum weighted sum rate problem. Our proposed CGP method utilizes the powerful concept of Hessian conjugacy. We also develop a rigorous algorithm to solve the projection problem. We show that CGP enjoys provable convergence, nice scalability, and great efficiency for large MIMO-BC systems.