OpenRaiser/Intern-Atlas huggingface dataset:
A hierarchy of behavioral equivalences in the $π$-calculus with noisy channels
Venue: arXiv cs.LO 2008
Year: 2008

The $π$-calculus is a process algebra where agents interact by sending communication links to each other via noiseless communication channels. Taking into account the reality of noisy channels, an extension of the $π$-calculus, called the $π_N$-calculus, has been introduced recently. In this paper, we present an early transitional semantics of the $π_N$-calculus, which is not a directly translated version of the late semantics of $π_N$, and then extend six kinds of behavioral equivalences consisting of reduction bisimilarity, barbed bisimilarity, barbed equivalence, barbed congruence, bisimilarity, and full bisimilarity into the $π_N$-calculus. Such behavioral equivalences are cast in a hierarchy, which is helpful to verify behavioral equivalence of two agents. In particular, we show that due to the noisy nature of channels, the coincidence of bisimilarity and barbed equivalence, as well as the coincidence of full bisimilarity and barbed congruence, in the $π$-calculus does not hold in $π_N$.
Quantized Multimode Precoding in Spatially Correlated Multi-Antenna Channels
Venue: arXiv cs.IT 2008
Year: 2008

Multimode precoding, where the number of independent data-streams is adapted optimally, can be used to maximize the achievable throughput in multi-antenna communication systems. Motivated by standardization efforts embraced by the industry, the focus of this work is on systematic precoder design with realistic assumptions on the spatial correlation, channel state information (CSI) at the transmitter and the receiver, and implementation complexity. For spatial correlation of the channel matrix, we assume a general channel model, based on physical principles, that has been verified by many recent measurement campaigns. We also assume a coherent receiver and knowledge of the spatial statistics at the transmitter along with the presence of an ideal, low-rate feedback link from the receiver to the transmitter. The reverse link is used for codebook-index feedback and the goal of this work is to construct precoder codebooks, adaptable in response to the statistical information, such that the achievable throughput is significantly enhanced over that of a fixed, non-adaptive, i.i.d. codebook design. We illustrate how a codebook of semiunitary precoder matrices localized around some fixed center on the Grassmann manifold can be skewed in response to the spatial correlation via low-complexity maps that can rotate and scale submanifolds on the Grassmann manifold. The skewed codebook in combination with a lowcomplexity statistical power allocation scheme is then shown to bridge the gap in performance between a perfect CSI benchmark and an i.i.d. codebook design.
A path following algorithm for the graph matching problem
Venue: arXiv cs.CV 2008
Year: 2008

We propose a convex-concave programming approach for the labeled weighted graph matching problem. The convex-concave programming formulation is obtained by rewriting the weighted graph matching problem as a least-square problem on the set of permutation matrices and relaxing it to two different optimization problems: a quadratic convex and a quadratic concave optimization problem on the set of doubly stochastic matrices. The concave relaxation has the same global minimum as the initial graph matching problem, but the search for its global minimum is also a hard combinatorial problem. We therefore construct an approximation of the concave problem solution by following a solution path of a convex-concave problem obtained by linear interpolation of the convex and concave formulations, starting from the convex relaxation. This method allows to easily integrate the information on graph label similarities into the optimization problem, and therefore to perform labeled weighted graph matching. The algorithm is compared with some of the best performing graph matching methods on four datasets: simulated graphs, QAPLib, retina vessel images and handwritten chinese characters. In all cases, the results are competitive with the state-of-the-art.
Picking up the Pieces: Self-Healing in Reconfigurable Networks
Venue: arXiv cs.DS 2008
Year: 2008

We consider the problem of self-healing in networks that are reconfigurable in the sense that they can change their topology during an attack. Our goal is to maintain connectivity in these networks, even in the presence of repeated adversarial node deletion, by carefully adding edges after each attack. We present a new algorithm, DASH, that provably ensures that: 1) the network stays connected even if an adversary deletes up to all nodes in the network; and 2) no node ever increases its degree by more than 2 log n, where n is the number of nodes initially in the network. DASH is fully distributed; adds new edges only among neighbors of deleted nodes; and has average latency and bandwidth costs that are at most logarithmic in n. DASH has these properties irrespective of the topology of the initial network, and is thus orthogonal and complementary to traditional topology-based approaches to defending against attack. We also prove lower-bounds showing that DASH is asymptotically optimal in terms of minimizing maximum degree increase over multiple attacks. Finally, we present empirical results on power-law graphs that show that DASH performs well in practice, and that it significantly outperforms naive algorithms in reducing maximum degree increase. We also present empirical results on performance of our algorithms and a new heuristic with regard to stretch (increase in shortest path lengths).
Modular Compilation of a Synchronous Language
Venue: arXiv cs.PL 2008
Year: 2008

Synchronous languages rely on formal methods to ease the development of applications in an efficient and reusable way. Formal methods have been advocated as a means of increasing the reliability of systems, especially those which are safety or business critical. It is still difficult to develop automatic specification and verification tools due to limitations like state explosion, undecidability, etc... In this work, we design a new specification model based on a reactive synchronous approach. Then, we benefit from a formal framework well suited to perform compilation and formal validation of systems. In practice, we design and implement a special purpose language (LE) and its two semantics: the ehavioral semantics helps us to define a program by the set of its behaviors and avoid ambiguousness in programs' interpretation; the execution equational semantics allows the modular compilation of programs into software and hardware targets (c code, vhdl code, fpga synthesis, observers). Our approach is pertinent considering the two main requirements of critical realistic applications: the modular compilation allows us to deal with large systems, the model-based approach provides us with formal validation.
Dichotomy Results for Fixed-Point Existence Problems for Boolean Dynamical Systems
Venue: arXiv cs.CC 2008
Year: 2008

A complete classification of the computational complexity of the fixed-point existence problem for boolean dynamical systems, i.e., finite discrete dynamical systems over the domain {0, 1}, is presented. For function classes F and graph classes G, an (F, G)-system is a boolean dynamical system such that all local transition functions lie in F and the underlying graph lies in G. Let F be a class of boolean functions which is closed under composition and let G be a class of graphs which is closed under taking minors. The following dichotomy theorems are shown: (1) If F contains the self-dual functions and G contains the planar graphs then the fixed-point existence problem for (F, G)-systems with local transition function given by truth-tables is NP-complete; otherwise, it is decidable in polynomial time. (2) If F contains the self-dual functions and G contains the graphs having vertex covers of size one then the fixed-point existence problem for (F, G)-systems with local transition function given by formulas or circuits is NP-complete; otherwise, it is decidable in polynomial time.
Robustness Evaluation of Two CCG, a PCFG and a Link Grammar Parsers
Venue: arXiv cs.CL 2008
Year: 2008

Robustness in a parser refers to an ability to deal with exceptional phenomena. A parser is robust if it deals with phenomena outside its normal range of inputs. This paper reports on a series of robustness evaluations of state-of-the-art parsers in which we concentrated on one aspect of robustness: its ability to parse sentences containing misspelled words. We propose two measures for robustness evaluation based on a comparison of a parser's output for grammatical input sentences and their noisy counterparts. In this paper, we use these measures to compare the overall robustness of the four evaluated parsers, and we present an analysis of the decline in parser performance with increasing error levels. Our results indicate that performance typically declines tens of percentage units when parsers are presented with texts containing misspellings. When it was tested on our purpose-built test set of 443 sentences, the best parser in the experiment (C&C parser) was able to return exactly the same parse tree for the grammatical and ungrammatical sentences for 60.8%, 34.0% and 14.9% of the sentences with one, two or three misspelled words respectively.
Analysis of Prime Reciprocal Sequences in Base 10
Venue: arXiv cs.CR 2008
Year: 2008

Prime reciprocals have applications in coding and cryptography and for generation of random sequences. This paper investigates the structural redundancy of prime reciprocals in base 10 in a manner that parallels an earlier study for binary prime reciprocals. Several different kinds of structural relationships amongst the digits in reciprocal sequences are classified with respect to the digit in the least significant place of the prime. It is also shown that the frequency of digit 0 exceeds that of every other digit when the entire set of prime reciprocal sequences is considered.
Spanners of Additively Weighted Point Sets
Venue: arXiv cs.CG 2008
Year: 2008

We study the problem of computing geometric spanners for (additively) weighted point sets. A weighted point set is a set of pairs $(p,r)$ where $p$ is a point in the plane and $r$ is a real number. The distance between two points $(p_i,r_i)$ and $(p_j,r_j)$ is defined as $|p_ip_j|-r_i-r_j$. We show that in the case where all $r_i$ are positive numbers and $|p_ip_j|\geq r_i+r_j$ for all $i,j$ (in which case the points can be seen as non-intersecting disks in the plane), a variant of the Yao graph is a $(1+ε)$-spanner that has a linear number of edges. We also show that the Additively Weighted Delaunay graph (the face-dual of the Additively Weighted Voronoi diagram) has constant spanning ratio. The straight line embedding of the Additively Weighted Delaunay graph may not be a plane graph. We show how to compute a plane embedding that also has a constant spanning ratio.
High Performance Cooperative Transmission Protocols Based on Multiuser Detection and Network Coding
Venue: arXiv cs.IT 2008
Year: 2008

Cooperative transmission is an emerging communication technique that takes advantage of the broadcast nature of wireless channels. However, due to low spectral efficiency and the requirement of orthogonal channels, its potential for use in future wireless networks is limited. In this paper, by making use of multiuser detection (MUD) and network coding, cooperative transmission protocols with high spectral efficiency, diversity order, and coding gain are developed. Compared with the traditional cooperative transmission protocols with single-user detection, in which the diversity gain is only for one source user, the proposed MUD cooperative transmission protocols have the merit that the improvement of one user's link can also benefit the other users. In addition, using MUD at the relay provides an environment in which network coding can be employed. The coding gain and high diversity order can be obtained by fully utilizing the link between the relay and the destination. From the analysis and simulation results, it is seen that the proposed protocols achieve higher diversity gain, better asymptotic efficiency, and lower bit error rate, compared to traditional MUD schemes and to existing cooperative transmission protocols. From the simulation results, the performance of the proposed scheme is near optimal as the performance gap is 0.12dB for average bit error rate (BER) 10^{-6} and 1.04dB for average BER 10^(-3), compared to two performance upper bounds.
Quantified Propositional Logspace Reasoning
Venue: arXiv cs.LO 2008
Year: 2008

In this paper, we develop a quantified propositional proof systems that corresponds to logarithmic-space reasoning. We begin by defining a class SigmaCNF(2) of quantified formulas that can be evaluated in log space. Then our new proof system GL^* is defined as G_1^* with cuts restricted to SigmaCNF(2) formulas and no cut formula that is not quantifier free contains a free variable that does not appear in the final formula. To show that GL^* is strong enough to capture log space reasoning, we translate theorems of VL into a family of tautologies that have polynomial-size GL^* proofs. VL is a theory of bounded arithmetic that is known to correspond to logarithmic-space reasoning. To do the translation, we find an appropriate axiomatization of VL, and put VL proofs into a new normal form. To show that GL^* is not too strong, we prove the soundness of GL^* in such a way that it can be formalized in VL. This is done by giving a logarithmic-space algorithm that witnesses GL^* proofs.
A Molecular Model for Communication through a Secrecy System
Venue: arXiv cs.CR 2008
Year: 2008

Codes have been used for centuries to convey secret information.To a cryptanalyst, the interception of a code is only the first step in recovering a secret message.Deoxyribonucleic acid (DNA) is a biological and molecular code.Through the work of Marshall Nirenberg and others, DNA is now understood to specify for amino acids in triplet codes of bases.The possibilty of DNA encoding secret information in a natural language is explored, since a code is expected to have a distinct mathematical solution.
Source Code Protection for Applications Written in Microsoft Excel and Google Spreadsheet
Venue: arXiv cs.SE 2008
Year: 2008

Spreadsheets are used to develop application software that is distributed to users. Unfortunately, the users often have the ability to change the programming statements ("source code") of the spreadsheet application. This causes a host of problems. By critically examining the suitability of spreadsheet computer programming languages for application development, six "application development features" are identified, with source code protection being the most important. We investigate the status of these features and discuss how they might be implemented in the dominant Microsoft Excel spreadsheet and in the new Google Spreadsheet. Although Google Spreadsheet currently provides no source code control, its web-centric delivery model offers technical advantages for future provision of a rich set of features. Excel has a number of tools that can be combined to provide "pretty good protection" of source code, but weak passwords reduce its robustness. User access to Excel source code must be considered a programmer choice rather than an attribute of the spreadsheet.
Improved lower bound for deterministic broadcasting in radio networks
Venue: arXiv cs.DM 2008
Year: 2008

We consider the problem of deterministic broadcasting in radio networks when the nodes have limited knowledge about the topology of the network. We show that for every deterministic broadcasting protocol there exists a network, of radius 2, for which the protocol takes at least $Ω(\sqrt{n}) rounds for completing the broadcast. Our argument can be extended to prove a lower bound of Omega(\sqrt{nD}) rounds for broadcasting in radio networks of radius D. This resolves one of the open problems posed in [29], where in the authors proved a lower bound of $Ω(n^{1/4}) rounds for broadcasting in constant diameter networks. We prove the new lower $Ω(\sqrt{n})$ bound for a special family of radius 2 networks. Each network of this family consists of O(\sqrt{n}) components which are connected to each other via only the source node. At the heart of the proof is a novel simulation argument, which essentially says that any arbitrarily complicated strategy of the source node can be simulated by the nodes of the networks, if the source node just transmits partial topological knowledge about some component instead of arbitrary complicated messages. To the best of our knowledge this type of simulation argument is novel and may be useful in further improving the lower bound or may find use in other applications. Keywords: radio networks, deterministic broadcast, lower bound, advice string, simulation, selective families, limited topological knowledge.
On the Double Coset Membership Problem for Permutation Groups
Venue: arXiv cs.CC 2008
Year: 2008

We show that the Double Coset Membership problem for permutation groups possesses perfect zero-knowledge proofs.
On the Relation Between the Index Coding and the Network Coding Problems
Venue: arXiv cs.IT 2008
Year: 2008

In this paper we show that the Index Coding problem captures several important properties of the more general Network Coding problem. An instance of the Index Coding problem includes a server that holds a set of information messages $X=\{x_1,...,x_k\}$ and a set of receivers $R$. Each receiver has some side information, known to the server, represented by a subset of $X$ and demands another subset of $X$. The server uses a noiseless communication channel to broadcast encodings of messages in $X$ to satisfy the receivers' demands. The goal of the server is to find an encoding scheme that requires the minimum number of transmissions. We show that any instance of the Network Coding problem can be efficiently reduced to an instance of the Index Coding problem. Our reduction shows that several important properties of the Network Coding problem carry over to the Index Coding problem. In particular, we prove that both scalar linear and vector linear codes are insufficient for achieving the minimal number of transmissions.
Multi-Layer Perceptrons and Symbolic Data
Venue: arXiv cs.NE 2008
Year: 2008

In some real world situations, linear models are not sufficient to represent accurately complex relations between input variables and output variables of a studied system. Multilayer Perceptrons are one of the most successful non-linear regression tool but they are unfortunately restricted to inputs and outputs that belong to a normed vector space. In this chapter, we propose a general recoding method that allows to use symbolic data both as inputs and outputs to Multilayer Perceptrons. The recoding is quite simple to implement and yet provides a flexible framework that allows to deal with almost all practical cases. The proposed method is illustrated on a real world data set.
A data-driven functional projection approach for the selection of feature ranges in spectra with ICA or cluster analysis
Venue: arXiv cs.NE 2008
Year: 2008

Prediction problems from spectra are largely encountered in chemometry. In addition to accurate predictions, it is often needed to extract information about which wavelengths in the spectra contribute in an effective way to the quality of the prediction. This implies to select wavelengths (or wavelength intervals), a problem associated to variable selection. In this paper, it is shown how this problem may be tackled in the specific case of smooth (for example infrared) spectra. The functional character of the spectra (their smoothness) is taken into account through a functional variable projection procedure. Contrarily to standard approaches, the projection is performed on a basis that is driven by the spectra themselves, in order to best fit their characteristics. The methodology is illustrated by two examples of functional projection, using Independent Component Analysis and functional variable clustering, respectively. The performances on two standard infrared spectra benchmarks are illustrated.
The Case for Structured Random Codes in Network Capacity Theorems
Venue: arXiv cs.IT 2008
Year: 2008

Random coding arguments are the backbone of most channel capacity achievability proofs. In this paper, we show that in their standard form, such arguments are insufficient for proving some network capacity theorems: structured coding arguments, such as random linear or lattice codes, attain higher rates. Historically, structured codes have been studied as a stepping stone to practical constructions. However, Körner and Marton demonstrated their usefulness for capacity theorems through the derivation of the optimal rate region of a distributed functional source coding problem. Here, we use multicasting over finite field and Gaussian multiple-access networks as canonical examples to demonstrate that even if we want to send bits over a network, structured codes succeed where simple random codes fail. Beyond network coding, we also consider distributed computation over noisy channels and a special relay-type problem.
Approximability Distance in the Space of H-Colourability Problems
Venue: arXiv cs.CC 2008
Year: 2008

A graph homomorphism is a vertex map which carries edges from a source graph to edges in a target graph. We study the approximability properties of the Weighted Maximum H-Colourable Subgraph problem (MAX H-COL). The instances of this problem are edge-weighted graphs G and the objective is to find a subgraph of G that has maximal total edge weight, under the condition that the subgraph has a homomorphism to H; note that for H=K_k this problem is equivalent to MAX k-CUT. To this end, we introduce a metric structure on the space of graphs which allows us to extend previously known approximability results to larger classes of graphs. Specifically, the approximation algorithms for MAX CUT by Goemans and Williamson and MAX k-CUT by Frieze and Jerrum can be used to yield non-trivial approximation results for MAX H-COL. For a variety of graphs, we show near-optimality results under the Unique Games Conjecture. We also use our method for comparing the performance of Frieze & Jerrum's algorithm with Hastad's approximation algorithm for general MAX 2-CSP. This comparison is, in most cases, favourable to Frieze & Jerrum.
Distributed Compression for the Uplink of a Backhaul-Constrained Coordinated Cellular Network
Venue: arXiv cs.IT 2008
Year: 2008

We consider a backhaul-constrained coordinated cellular network. That is, a single-frequency network with $N+1$ multi-antenna base stations (BSs) that cooperate in order to decode the users' data, and that are linked by means of a common lossless backhaul, of limited capacity $\mathrm{R}$. To implement receive cooperation, we propose distributed compression: $N$ BSs, upon receiving their signals, compress them using a multi-source lossy compression code. Then, they send the compressed vectors to a central BS, which performs users' decoding. Distributed Wyner-Ziv coding is proposed to be used, and is optimally designed in this work. The first part of the paper is devoted to a network with a unique multi-antenna user, that transmits a predefined Gaussian space-time codeword. For such a scenario, the compression codebooks at the BSs are optimized, considering the user's achievable rate as the performance metric. In particular, for $N = 1$ the optimum codebook distribution is derived in closed form, while for $N>1$ an iterative algorithm is devised. The second part of the contribution focusses on the multi-user scenario. For it, the achievable rate region is obtained by means of the optimum compression codebooks for sum-rate and weighted sum-rate, respectively.