OpenRaiser/Intern-Atlas huggingface dataset:
Braid Group Cryptography
Venue: arXiv cs.CR 2008
Year: 2008

In the last decade, a number of public key cryptosystems based on com- binatorial group theoretic problems in braid groups have been proposed. We survey these cryptosystems and some known attacks on them. This survey includes: Basic facts on braid groups and on the Garside normal form of its elements, some known algorithms for solving the word problem in the braid group, the major public-key cryptosystems based on the braid group, and some of the known attacks on these cryptosystems. We conclude with a discussion of future directions (which includes also a description of cryptosystems which are based on other non-commutative groups).
Lambda-RBAC: Programming with Role-Based Access Control
Venue: arXiv cs.PL 2008
Year: 2008

We study mechanisms that permit program components to express role constraints on clients, focusing on programmatic security mechanisms, which permit access controls to be expressed, in situ, as part of the code realizing basic functionality. In this setting, two questions immediately arise: (1) The user of a component faces the issue of safety: is a particular role sufficient to use the component? (2) The component designer faces the dual issue of protection: is a particular role demanded in all execution paths of the component? We provide a formal calculus and static analysis to answer both questions.
Ranking forestry journals using the h-index
Venue: arXiv cs.DL 2008
Year: 2008

An expert ranking of forestry journals was compared with journal impact factors and h-indices computed from the ISI Web of Science and internet-based data. Citations reported by Google Scholar appear to offer the most efficient way to rank all journals objectively, in a manner consistent with other indicators. This h-index exhibited a high correlation with the journal impact factor (r=0.92), but is not confined to journals selected by any particular commercial provider. A ranking of 180 forestry journals is presented, on the basis of this index.
Cell mapping description for digital control system with quantization effect
Venue: arXiv cs.OH 2008
Year: 2008

Quantization problem in digital control system have attracted more and more attention in these years. Normally, a quantized variable is regarded as a perturbed copy of the unquantized variable in the research of quantization effect, but this model has shown many obvious disadvantages in control system analysis and design process. In this paper, we give a new model for quantization based 'cell mapping' concept. This cell model could clearly describe the global dynamics of quantized digital system. Then some important characteristics of control system like controllability are analyzed by this model. The finite precision control design method based on cell concept is also presented.
Polytope Representations for Linear-Programming Decoding of Non-Binary Linear Codes
Venue: arXiv cs.IT 2008
Year: 2008

In previous work, we demonstrated how decoding of a non-binary linear code could be formulated as a linear-programming problem. In this paper, we study different polytopes for use with linear-programming decoding, and show that for many classes of codes these polytopes yield a complexity advantage for decoding. These representations lead to polynomial-time decoders for a wide variety of classical non-binary linear codes.
Staring at Economic Aggregators through Information Lenses
Venue: arXiv cs.IT 2008
Year: 2008

It is hard to exaggerate the role of economic aggregators -- functions that summarize numerous and / or heterogeneous data -- in economic models since the early XX$^{th}$ century. In many cases, as witnessed by the pioneering works of Cobb and Douglas, these functions were information quantities tailored to economic theories, i.e. they were built to fit economic phenomena. In this paper, we look at these functions from the complementary side: information. We use a recent toolbox built on top of a vast class of distortions coined by Bregman, whose application field rivals metrics' in various subfields of mathematics. This toolbox makes it possible to find the quality of an aggregator (for consumptions, prices, labor, capital, wages, etc.), from the standpoint of the information it carries. We prove a rather striking result. From the informational standpoint, well-known economic aggregators do belong to the \textit{optimal} set. As common economic assumptions enter the analysis, this large set shrinks, and it essentially ends up \textit{exactly fitting} either CES, or Cobb-Douglas, or both. To summarize, in the relevant economic contexts, one could not have crafted better some aggregator from the information standpoint. We also discuss global economic behaviors of optimal information aggregators in general, and present a brief panorama of the links between economic and information aggregators. Keywords: Economic Aggregators, CES, Cobb-Douglas, Bregman divergences
Topology and Ambiguity in Omega Context Free Languages
Venue: arXiv cs.LO 2008
Year: 2008

We study the links between the topological complexity of an omega context free language and its degree of ambiguity. In particular, using known facts from classical descriptive set theory, we prove that non Borel omega context free languages which are recognized by Büchi pushdown automata have a maximum degree of ambiguity. This result implies that degrees of ambiguity are really not preserved by the operation of taking the omega power of a finitary context free language. We prove also that taking the adherence or the delta-limit of a finitary language preserves neither unambiguity nor inherent ambiguity. On the other side we show that methods used in the study of omega context free languages can also be applied to study the notion of ambiguity in infinitary rational relations accepted by Büchi 2-tape automata and we get first results in that direction.
Blind decoding of Linear Gaussian channels with ISI, capacity, error exponent, universality
Venue: arXiv cs.IT 2008
Year: 2008

A new straightforward universal blind detection algorithm for linear Gaussian channel with ISI is given. A new error exponent is derived, which is better than Gallager's random coding error exponent.
Capacity of The Discrete-Time Non-Coherent Memoryless Rayleigh Fading Channels at Low SNR
Venue: arXiv cs.IT 2008
Year: 2008

The capacity of a discrete-time memoryless channel, in which successive symbols fade independently, and where the channel state information (CSI) is neither available at the transmitter nor at the receiver, is considered at low SNR. We derive a closed form expression of the optimal capacity-achieving input distribution at low signal-to-noise ratio (SNR) and give the exact capacity of a non-coherent channel at low SNR. The derived relations allow to better understanding the capacity of non-coherent channels at low SNR and bring an analytical answer to the peculiar behavior of the optimal input distribution observed in a previous work by Abou Faycal, Trott and Shamai. Then, we compute the non-coherence penalty and give a more precise characterization of the sub-linear term in SNR. Finally, in order to better understand how the optimal input varies with SNR, upper and lower bounds on the capacity-achieving input are given.
Distributed Power Allocation Strategies for Parallel Relay Networks
Venue: arXiv cs.IT 2008
Year: 2008

We consider a source-destination pair assisted by parallel regenerative decode-and-forward relays operating in orthogonal channels. We investigate distributed power allocation strategies for this system with limited channel state information at the source and the relay nodes. We first propose a distributed decision mechanism for each relay to individually make its decision on whether to forward the source data. The decision mechanism calls for each relay that is able to decode the information from the source to compare its relay-to-destination channel gain with a given threshold. We identify the optimum distributed power allocation strategy that minimizes the total transmit power while providing a target signal-to-noise ratio at the destination with a target outage probability. The strategy dictates the optimum choices for the source power as well as the threshold value at the relays. Next, we consider two simpler distributed power allocation strategies, namely the passive source model where the source power and the relay threshold are fixed, and the single relay model where only one relay is allowed to forward the source data. These models are motivated by limitations on the available channel state information as well as ease of implementation as compared to the optimum distributed strategy. Simulation results are presented to demonstrate the performance of the proposed distributed power allocation schemes. Specifically, we observe significant power savings with proposed methods as compared to random relay selection.
On the Robustness of the Delay-Based Fingerprint Embedding Scheme
Venue: arXiv cs.MM 2008
Year: 2008

The delay-based fingerprint embedding was recently proposed to support more users in secure media distribution scenario. In this embedding scheme, some users are assigned the same fingerprint code with only different embedding delay. The algorithm's robustness against collusion attacks is investigated. However, its robustness against common desynchronization attacks, e.g., cropping and time shifting, is not considered. In this paper, desynchronization attacks are used to break the delay-based fingerprint embedding algorithm. To improve the robustness, two means are proposed to keep the embedded fingerprint codes synchronized, i.e., adding a synchronization fingerprint and adopting the relative delay to detect users. Analyses and experiments are given to show the improvements.
On Multipath Fading Channels at High SNR
Venue: arXiv cs.IT 2008
Year: 2008

This paper studies the capacity of discrete-time multipath fading channels. It is assumed that the number of paths is finite, i.e., that the channel output is influenced by the present and by the L previous channel inputs. A noncoherent channel model is considered where neither transmitter nor receiver are cognizant of the fading's realization, but both are aware of its statistic. The focus is on capacity at high signal-to-noise ratios (SNR). In particular, the capacity pre-loglog - defined as the limiting ratio of the capacity to loglog SNR as SNR tends to infinity - is studied. It is shown that, irrespective of the number paths L, the capacity pre-loglog is 1.
Distributed Source Coding for Interactive Function Computation
Venue: arXiv cs.IT 2008
Year: 2008

A two-terminal interactive distributed source coding problem with alternating messages for function computation at both locations is studied. For any number of messages, a computable characterization of the rate region is provided in terms of single-letter information measures. While interaction is useless in terms of the minimum sum-rate for lossless source reproduction at one or both locations, the gains can be arbitrarily large for function computation even when the sources are independent. For a class of sources and functions, interaction is shown to be useless, even with infinite messages, when a function has to be computed at only one location, but is shown to be useful, if functions have to be computed at both locations. For computing the Boolean AND function of two independent Bernoulli sources at both locations, an achievable infinite-message sum-rate with infinitesimal-rate messages is derived in terms of a two-dimensional definite integral and a rate-allocation curve. A general framework for multiterminal interactive function computation based on an information exchange protocol which successively switches among different distributed source coding configurations is developed. For networks with a star topology, multiple rounds of interactive coding is shown to decrease the scaling law of the total network rate by an order of magnitude as the network grows.
A linear-non-linear model for a computational call-by-value lambda calculus (extended abstract)
Venue: arXiv cs.LO 2008
Year: 2008

We give a categorical semantics for a call-by-value linear lambda calculus. Such a lambda calculus was used by Selinger and Valiron as the backbone of a functional programming language for quantum computation. One feature of this lambda calculus is its linear type system, which includes a duplicability operator "!" as in linear logic. Another main feature is its call-by-value reduction strategy, together with a side-effect to model probabilistic measurements. The "!" operator gives rise to a comonad, as in the linear logic models of Seely, Bierman, and Benton. The side-effects give rise to a monad, as in Moggi's computational lambda calculus. It is this combination of a monad and a comonad that makes the present paper interesting. We show that our categorical semantics is sound and complete.
The What, Who, Where, When, Why and How of Context-Awareness
Venue: arXiv cs.HC 2008
Year: 2008

The understanding of context and context-awareness is very important for the areas of handheld and ubiquitous computing. Unfortunately, at present, there has not been a satisfactory definition of these two concepts that would lead to a more effective communication in humancomputer interaction. As a result, on the one hand, application designers are not able to choose what context to use in their applications and on the other, they cannot determine the type of context-awareness behaviours their applications should exhibit. In this work, we aim to provide answers to some fundamental questions that could enlighten us on the definition of context and its functionality.
An Addendum to "How Good is PSK for Peak-Limited Fading Channels in the Low-SNR Regime?"
Venue: arXiv cs.IT 2008
Year: 2008

A proof is provided of the operational achievability of $R_\mathrm{rt}$ by the recursive training scheme in \cite{zhang07:it}, for general wide-sense stationary and ergodic Rayleigh fading processes.
LDPC Codes Which Can Correct Three Errors Under Iterative Decoding
Venue: arXiv cs.IT 2008
Year: 2008

In this paper, we provide necessary and sufficient conditions for a column-weight-three LDPC code to correct three errors when decoded using Gallager A algorithm. We then provide a construction technique which results in a code satisfying the above conditions. We also provide numerical assessment of code performance via simulation results.
Alternating Hierarchies for Time-Space Tradeoffs
Venue: arXiv cs.CC 2008
Year: 2008

Nepomnjascii's Theorem states that for all 0 <= ε< 1 and k > 0 the class of languages recognized in nondeterministic time n^k and space n^ε, NTISP[n^k, n^ε], is contained in the linear time hierarchy. By considering restrictions on the size of the universal quantifiers in the linear time hierarchy, this paper refines Nepomnjascii's result to give a sub- hierarchy, Eu-LinH, of the linear time hierarchy that is contained in NP and which contains NTISP[n^k, n^ε]. Hence, Eu-LinH contains NL and SC. This paper investigates basic structural properties of Eu-LinH. Then the relationships between Eu-LinH and the classes NL, SC, and NP are considered to see if they can shed light on the NL = NP or SC = NP questions. Finally, a new hierarchy, zeta -LinH, is defined to reduce the space requirements needed for the upper bound on Eu-LinH.
Fast Integer Multiplication using Modular Arithmetic
Venue: arXiv cs.SC 2008
Year: 2008

We give an $O(N\cdot \log N\cdot 2^{O(\log^*N)})$ algorithm for multiplying two $N$-bit integers that improves the $O(N\cdot \log N\cdot \log\log N)$ algorithm by Schönhage-Strassen. Both these algorithms use modular arithmetic. Recently, Fürer gave an $O(N\cdot \log N\cdot 2^{O(\log^*N)})$ algorithm which however uses arithmetic over complex numbers as opposed to modular arithmetic. In this paper, we use multivariate polynomial multiplication along with ideas from Fürer's algorithm to achieve this improvement in the modular setting. Our algorithm can also be viewed as a $p$-adic version of Fürer's algorithm. Thus, we show that the two seemingly different approaches to integer multiplication, modular and complex arithmetic, are similar.
A Central Limit Theorem for the SNR at the Wiener Filter Output for Large Dimensional Signals
Venue: arXiv cs.IT 2008
Year: 2008

Consider the quadratic form $β= {\bf y}^* ({\bf YY}^* + ρ{\bf I})^{-1} {\bf y}$ where $ρ$ is a positive number, where ${\bf y}$ is a random vector and ${\bf Y}$ is a $N \times K$ random matrix both having independent elements with different variances, and where ${\bf y}$ and ${\bf Y}$ are independent. Such quadratic forms represent the Signal to Noise Ratio at the output of the linear Wiener receiver for multi dimensional signals frequently encountered in wireless communications and in array processing. Using well known results of Random Matrix Theory, the quadratic form $β$ can be approximated with a known deterministic real number $\barβ_K$ in the asymptotic regime where $K\to\infty$ and $K/N \to α> 0$. This paper addresses the problem of convergence of $β$. More specifically, it is shown here that $\sqrt{K}(β- \barβ_K)$ behaves for large $K$ like a Gaussian random variable which variance is provided.
Asynchronous Remote Medical Consultation for Ghana
Venue: arXiv cs.HC 2008
Year: 2008

Computer-mediated communication systems can be used to bridge the gap between doctors in underserved regions with local shortages of medical expertise and medical specialists worldwide. To this end, we describe the design of a prototype remote consultation system intended to provide the social, institutional and infrastructural context for sustained, self-organizing growth of a globally-distributed Ghanaian medical community. The design is grounded in an iterative design process that included two rounds of extended design fieldwork throughout Ghana and draws on three key design principles (social networks as a framework on which to build incentives within a self-organizing network; optional and incremental integration with existing referral mechanisms; and a weakly-connected, distributed architecture that allows for a highly interactive, responsive system despite failures in connectivity). We discuss initial experiences from an ongoing trial deployment in southern Ghana.
Online variants of the cross-entropy method
Venue: arXiv cs.LG 2008
Year: 2008

The cross-entropy method is a simple but efficient method for global optimization. In this paper we provide two online variants of the basic CEM, together with a proof of convergence.
A One-Way Function Based On The Extended Euclidean Algorithm
Venue: arXiv cs.CR 2008
Year: 2008

A problem based on the Extended Euclidean Algorithm applied to a class of polynomials with many factors is presented and believed to be hard. If so, it is a one-way function well suited for applications in digital signicatures.
On the relationship between the structural and socioacademic communities of a coauthorship network
Venue: arXiv cs.DL 2008
Year: 2008

This article presents a study that compares detected structural communities in a coauthorship network to the socioacademic characteristics of the scholars that compose the network. The coauthorship network was created from the bibliographic record of a multi-institution, interdisciplinary research group focused on the study of sensor networks and wireless communication. Four different community detection algorithms were employed to assign a structural community to each scholar in the network: leading eigenvector, walktrap, edge betweenness and spinglass. Socioacademic characteristics were gathered from the scholars and include such information as their academic department, academic affiliation, country of origin, and academic position. A Pearson's $χ^2$ test, with a simulated Monte Carlo, revealed that structural communities best represent groupings of individuals working in the same academic department and at the same institution. A generalization of this result suggests that, even in interdisciplinary, multi-institutional research groups, coauthorship is primarily driven by departmental and institutional affiliation.
String algorithms and data structures
Venue: arXiv cs.DS 2008
Year: 2008

The string-matching field has grown at a such complicated stage that various issues come into play when studying it: data structure and algorithmic design, database principles, compression techniques, architectural features, cache and prefetching policies. The expertise nowadays required to design good string data structures and algorithms is therefore transversal to many computer science fields and much more study on the orchestration of known, or novel, techniques is needed to make progress in this fascinating topic. This survey is aimed at illustrating the key ideas which should constitute, in our opinion, the current background of every index designer. We also discuss the positive features and drawback of known indexing schemes and algorithms, and devote much attention to detail research issues and open problems both on the theoretical and the experimental side.
MRI/TRUS data fusion for prostate brachytherapy. Preliminary results
Venue: arXiv cs.OH 2008
Year: 2008

Prostate brachytherapy involves implanting radioactive seeds (I125 for instance) permanently in the gland for the treatment of localized prostate cancers, e.g., cT1c-T2a N0 M0 with good prognostic factors. Treatment planning and seed implanting are most often based on the intensive use of transrectal ultrasound (TRUS) imaging. This is not easy because prostate visualization is difficult in this imaging modality particularly as regards the apex of the gland and from an intra- and interobserver variability standpoint. Radioactive seeds are implanted inside open interventional MR machines in some centers. Since MRI was shown to be sensitive and specific for prostate imaging whilst open MR is prohibitive for most centers and makes surgical procedures very complex, this work suggests bringing the MR virtually in the operating room with MRI/TRUS data fusion. This involves providing the physician with bi-modality images (TRUS plus MRI) intended to improve treatment planning from the data registration stage. The paper describes the method developed and implemented in the PROCUR system. Results are reported for a phantom and first series of patients. Phantom experiments helped characterize the accuracy of the process. Patient experiments have shown that using MRI data linked with TRUS data improves TRUS image segmentation especially regarding the apex and base of the prostate. This may significantly modify prostate volume definition and have an impact on treatment planning.
The Two User Gaussian Compound Interference Channel
Venue: arXiv cs.IT 2008
Year: 2008

We introduce the two user finite state compound Gaussian interference channel and characterize its capacity region to within one bit. The main contributions involve both novel inner and outer bounds. The inner bound is multilevel superposition coding, but the decoding of the levels is opportunistic, depending on the channel state. The genie aided outer bound is motivated by the typical error events of the achievable scheme.
Online-concordance "Perekhresni stezhky" ("The Cross-Paths"), a novel by Ivan Franko
Venue: arXiv cs.CL 2008
Year: 2008

In the article, theoretical principles and practical realization for the compilation of the concordance to "Perekhresni stezhky" ("The Cross-Paths"), a novel by Ivan Franko, are described. Two forms for the context presentation are proposed. The electronic version of this lexicographic work is available online.
Nonregenerative MIMO Relaying with Optimal Transmit Antenna Selection
Venue: arXiv cs.IT 2008
Year: 2008

We derive optimal SNR-based transmit antenna selection rules at the source and relay for the nonregenerative half duplex MIMO relay channel. While antenna selection is a suboptimal form of beamforming, it has the advantage that the optimization is tractable and can be implemented with only a few bits of feedback from the destination to the source and relay. We compare the bit error rate of optimal antenna selection at both the source and relay to other proposed beamforming techniques and propose methods for performing the necessary limited feedback.