OpenRaiser/Intern-Atlas huggingface dataset:
The Impact of Noise Correlation and Channel Phase Information on the Data-Rate of the Single-Symbol ML Decodable Distributed STBCs
Venue: arXiv cs.IT 2007
Year: 2007

Very recently, we proposed the row-monomial distributed orthogonal space-time block codes (DOSTBCs) and showed that the row-monomial DOSTBCs achieved approximately twice higher bandwidth efficiency than the repetitionbased cooperative strategy [1]. However, we imposed two limitations on the row-monomial DOSTBCs. The first one was that the associated matrices of the codes must be row-monomial. The other was the assumption that the relays did not have any channel state information (CSI) of the channels from the source to the relays, although this CSI could be readily obtained at the relays without any additional pilot signals or any feedback overhead. In this paper, we first remove the row-monomial limitation; but keep the CSI limitation. In this case, we derive an upper bound of the data-rate of the DOSTBC and it is larger than that of the row-monomial DOSTBCs in [1]. Secondly, we abandon the CSI limitation; but keep the row-monomial limitation. Specifically, we propose the row-monomial DOSTBCs with channel phase information (DOSTBCs-CPI) and derive an upper bound of the data-rate of those codes. The rowmonomial DOSTBCs-CPI have higher data-rate than the DOSTBCs and the row-monomial DOSTBCs. Furthermore, we find the actual row-monomial DOSTBCs-CPI which achieve the upper bound of the data-rate.
The Church Synthesis Problem with Parameters
Venue: arXiv cs.LO 2007
Year: 2007

For a two-variable formula ψ(X,Y) of Monadic Logic of Order (MLO) the Church Synthesis Problem concerns the existence and construction of an operator Y=F(X) such that ψ(X,F(X)) is universally valid over Nat. Büchi and Landweber proved that the Church synthesis problem is decidable; moreover, they showed that if there is an operator F that solves the Church Synthesis Problem, then it can also be solved by an operator defined by a finite state automaton or equivalently by an MLO formula. We investigate a parameterized version of the Church synthesis problem. In this version ψ might contain as a parameter a unary predicate P. We show that the Church synthesis problem for P is computable if and only if the monadic theory of <Nat,<,P> is decidable. We prove that the Büchi-Landweber theorem can be extended only to ultimately periodic parameters. However, the MLO-definability part of the Büchi-Landweber theorem holds for the parameterized version of the Church synthesis problem.
Plate-forme Magicien d'Oz pour l'étude de l'apport des ACAs à l'interaction
Venue: arXiv cs.HC 2007
Year: 2007

In order to evaluate the contribution of Embodied (Animated) Conversational Agents (ECAs) to the effectiveness and usability of human-computer interaction, we developed a software platform meant to collect usage data. This platform, which implements the wizard of Oz paradigm, makes it possible to simulate user interfaces integrating ACAs for any Windows software application. It can also save and "replay" a rich interaction trace including user and system events, screen captures, users' speech and eye fixations. This platform has been used to assess users' subjective judgements and reactions to a multimodal online help system meant to facilitate the use of software for the general public (Flash). The online help system is embodied using a 3D talking head (developed by FT R&D) which "says" oral help messages illustrated with Flash screen copies.
Working and Assembly Modes of the Agile Eye
Venue: arXiv cs.RO 2007
Year: 2007

This paper deals with the in-depth kinematic analysis of a special spherical parallel wrist, called the Agile Eye. The Agile Eye is a three-legged spherical parallel robot with revolute joints in which all pairs of adjacent joint axes are orthogonal. Its most peculiar feature, demonstrated in this paper for the first time, is that its (orientation) workspace is unlimited and flawed only by six singularity curves (rather than surfaces). Furthermore, these curves correspond to self-motions of the mobile platform. This paper also demonstrates that, unlike for any other such complex spatial robots, the four solutions to the direct kinematics of the Agile Eye (assembly modes) have a simple geometric relationship with the eight solutions to the inverse kinematics (working modes).
Aides en ligne à l'utilisation de logiciels grand public : problèmes spécifiques de conception et solutions potentielles
Venue: arXiv cs.HC 2007
Year: 2007

The observation that novice users seldom consult online help was made over twenty years ago. This observation still holds nowadays, although online help to the use of software for the general public has greatly improved in usability during this period. The paper first demonstrates the necessity of online help to the use of new software whatever the transparency of the user interface, as whether online help systems are meant to compensate for interface design weaknesses or actually do provide necessary assistance to the discovery of a new software package functionalities is still an unsolved issue. The discussion relies on results of empirical and experimental studies and theoretical arguments. In the second part, we analyse the specific difficulties raised by the design of effective online help systems for current software intended for the general public so as to try and understand the reluctance of novice users to use online help. In the last part, we present and discuss the possible contributions of various approaches to solving this issue. Recent interaction paradigms and techniques are considered, such as, static and dynamic personalisation, contextual online help and new forms of multimodality.
Asymptotic improvement of the Gilbert-Varshamov bound for linear codes
Venue: arXiv cs.IT 2007
Year: 2007

The Gilbert-Varshamov bound states that the maximum size A_2(n,d) of a binary code of length n and minimum distance d satisfies A_2(n,d) >= 2^n/V(n,d-1) where V(n,d) stands for the volume of a Hamming ball of radius d. Recently Jiang and Vardy showed that for binary non-linear codes this bound can be improved to A_2(n,d) >= cn2^n/V(n,d-1) for c a constant and d/n <= 0.499. In this paper we show that certain asymptotic families of linear binary [n,n/2] random double circulant codes satisfy the same improved Gilbert-Varshamov bound.
Raising a Hardness Result
Venue: arXiv cs.AI 2007
Year: 2007

This article presents a technique for proving problems hard for classes of the polynomial hierarchy or for PSPACE. The rationale of this technique is that some problem restrictions are able to simulate existential or universal quantifiers. If this is the case, reductions from Quantified Boolean Formulae (QBF) to these restrictions can be transformed into reductions from QBFs having one more quantifier in the front. This means that a proof of hardness of a problem at level n in the polynomial hierarchy can be split into n separate proofs, which may be simpler than a proof directly showing a reduction from a class of QBFs to the considered problem.
A DH-parameter based condition for 3R orthogonal manipulators to have 4 distinct inverse kinematic solutions
Venue: arXiv cs.RO 2007
Year: 2007

Positioning 3R manipulators may have two or four inverse kinematic solutions (IKS). This paper derives a necessary and sufficient condition for 3R positioning manipulators with orthogonal joint axes to have four distinct IKS. We show that the transition between manipulators with 2 and 4 IKS is defined by the set of manipulators with a quadruple root of their inverse kinematics. The resulting condition is explicit and states that the last link length of the manipulator must be greater than a quantity that depends on three of its remaining DH-parameters. This result is of interest for the design of new manipulators.
Logic Column 19: Symbolic Model Checking for Temporal-Epistemic Logics
Venue: arXiv cs.LO 2007
Year: 2007

This article surveys some of the recent work in verification of temporal epistemic logic via symbolic model checking, focusing on OBDD-based and SAT-based approaches for epistemic logics built on discrete and real-time branching time temporal logics.
Using Data Compressors to Construct Rank Tests
Venue: arXiv cs.DS 2007
Year: 2007

Nonparametric rank tests for homogeneity and component independence are proposed, which are based on data compressors. For homogeneity testing the idea is to compress the binary string obtained by ordering the two joint samples and writing 0 if the element is from the first sample and 1 if it is from the second sample and breaking ties by randomization (extension to the case of multiple samples is straightforward). $H_0$ should be rejected if the string is compressed (to a certain degree) and accepted otherwise. We show that such a test obtained from an ideal data compressor is valid against all alternatives. Component independence is reduced to homogeneity testing by constructing two samples, one of which is the first half of the original and the other is the second half with one of the components randomly permuted.
On P vs. NP, Geometric Complexity Theory, and the Flip I: a high level view
Venue: arXiv cs.CC 2007
Year: 2007

Geometric complexity theory (GCT) is an approach to the $P$ vs. $NP$ and related problems through algebraic geometry and representation theory. This article gives a high-level exposition of the basic plan of GCT based on the principle, called the flip, without assuming any background in algebraic geometry or representation theory.
Open Access does not increase citations for research articles from The Astrophysical Journal
Venue: arXiv cs.DL 2007
Year: 2007

We demonstrate conclusively that there is no "Open Access Advantage" for papers from the Astrophysical Journal. The two to one citation advantage enjoyed by papers deposited in the arXiv e-print server is due entirely to the nature and timing of the deposited papers. This may have implications for other disciplines.
Using RDF to Model the Structure and Process of Systems
Venue: arXiv cs.AI 2007
Year: 2007

Many systems can be described in terms of networks of discrete elements and their various relationships to one another. A semantic network, or multi-relational network, is a directed labeled graph consisting of a heterogeneous set of entities connected by a heterogeneous set of relationships. Semantic networks serve as a promising general-purpose modeling substrate for complex systems. Various standardized formats and tools are now available to support practical, large-scale semantic network models. First, the Resource Description Framework (RDF) offers a standardized semantic network data model that can be further formalized by ontology modeling languages such as RDF Schema (RDFS) and the Web Ontology Language (OWL). Second, the recent introduction of highly performant triple-stores (i.e. semantic network databases) allows semantic network models on the order of $10^9$ edges to be efficiently stored and manipulated. RDF and its related technologies are currently used extensively in the domains of computer science, digital library science, and the biological sciences. This article will provide an introduction to RDF/RDFS/OWL and an examination of its suitability to model discrete element complex systems.
Efficient Algorithms for Node Disjoint Subgraph Homeomorphism Determination
Venue: arXiv cs.DS 2007
Year: 2007

Recently, great efforts have been dedicated to researches on the management of large scale graph based data such as WWW, social networks, biological networks. In the study of graph based data management, node disjoint subgraph homeomorphism relation between graphs is more suitable than (sub)graph isomorphism in many cases, especially in those cases that node skipping and node mismatching are allowed. However, no efficient node disjoint subgraph homeomorphism determination (ndSHD) algorithms have been available. In this paper, we propose two computationally efficient ndSHD algorithms based on state spaces searching with backtracking, which employ many heuristics to prune the search spaces. Experimental results on synthetic data sets show that the proposed algorithms are efficient, require relative little time in most of the testing cases, can scale to large or dense graphs, and can accommodate to more complex fuzzy matching cases.
Matrix-Lifting Semi-Definite Programming for Decoding in Multiple Antenna Systems
Venue: arXiv cs.IT 2007
Year: 2007

This paper presents a computationally efficient decoder for multiple antenna systems. The proposed algorithm can be used for any constellation (QAM or PSK) and any labeling method. The decoder is based on matrix-lifting Semi-Definite Programming (SDP). The strength of the proposed method lies in a new relaxation algorithm applied to the method of Mobasher et al. This results in a reduction of the number of variables from $(NK+1)^2$ to $(2N+K)^2$, where $N$ is the number of antennas and $K$ is the number of constellation points in each real dimension. Since the computational complexity of solving SDP is a polynomial function of the number of variables, we have a significant complexity reduction. Moreover, the proposed method offers a better performance as compared to the best quasi-maximum likelihood decoding methods reported in the literature.
Overlap-free words and spectra of matrices
Venue: arXiv cs.DM 2007
Year: 2007

Overlap-free words are words over the binary alphabet $A=\{a, b\}$ that do not contain factors of the form $xvxvx$, where $x \in A$ and $v \in A^*$. We analyze the asymptotic growth of the number $u_n$ of overlap-free words of length $n$ as $ n \to \infty$. We obtain explicit formulas for the minimal and maximal rates of growth of $u_n$ in terms of spectral characteristics (the lower spectral radius and the joint spectral radius) of certain sets of matrices of dimension $20 \times 20$. Using these descriptions we provide new estimates of the rates of growth that are within 0.4% and $0.03 %$ of their exact values. The best previously known bounds were within 11% and 3% respectively. We then prove that the value of $u_n$ actually has the same rate of growth for ``almost all'' natural numbers $n$. This ``average'' growth is distinct from the maximal and minimal rates and can also be expressed in terms of a spectral quantity (the Lyapunov exponent). We use this expression to estimate it. In order to obtain our estimates, we introduce new algorithms to compute spectral characteristics of sets of matrices. These algorithms can be used in other contexts and are of independent interest.
Toward Psycho-robots
Venue: arXiv cs.AI 2007
Year: 2007

We try to perform geometrization of psychology by representing mental states, <<ideas>>, by points of a metric space, <<mental space>>. Evolution of ideas is described by dynamical systems in metric mental space. We apply the mental space approach for modeling of flows of unconscious and conscious information in the human brain. In a series of models, Models 1-4, we consider cognitive systems with increasing complexity of psychological behavior determined by structure of flows of ideas. Since our models are in fact models of the AI-type, one immediately recognizes that they can be used for creation of AI-systems, which we call psycho-robots, exhibiting important elements of human psyche. Creation of such psycho-robots may be useful improvement of domestic robots. At the moment domestic robots are merely simple working devices (e.g. vacuum cleaners or lawn mowers) . However, in future one can expect demand in systems which be able not only perform simple work tasks, but would have elements of human self-developing psyche. Such AI-psyche could play an important role both in relations between psycho-robots and their owners as well as between psycho-robots. Since the presence of a huge numbers of psycho-complexes is an essential characteristic of human psychology, it would be interesting to model them in the AI-framework.
Improved Linear Parallel Interference Cancellers
Venue: arXiv cs.IT 2007
Year: 2007

In this paper, taking the view that a linear parallel interference canceller (LPIC) can be seen as a linear matrix filter, we propose new linear matrix filters that can result in improved bit error performance compared to other LPICs in the literature. The motivation for the proposed filters arises from the possibility of avoiding the generation of certain interference and noise terms in a given stage that would have been present in a conventional LPIC (CLPIC). In the proposed filters, we achieve such avoidance of the generation of interference and noise terms in a given stage by simply making the diagonal elements of a certain matrix in that stage equal to zero. Hence, the proposed filters do not require additional complexity compared to the CLPIC, and they can allow achieving a certain error performance using fewer LPIC stages. We also extend the proposed matrix filter solutions to a multicarrier DS-CDMA system, where we consider two types of receivers. In one receiver (referred to as Type-I receiver), LPIC is performed on each subcarrier first, followed by multicarrier combining (MCC). In the other receiver (called Type-II receiver), MCC is performed first, followed by LPIC. We show that in both Type-I and Type-II receivers, the proposed matrix filters outperform other matrix filters. Also, Type-II receiver performs better than Type-I receiver because of enhanced accuracy of the interference estimates achieved due to frequency diversity offered by MCC.
Triangulating the Real Projective Plane
Venue: arXiv cs.CG 2007
Year: 2007

We consider the problem of computing a triangulation of the real projective plane P2, given a finite point set S={p1, p2,..., pn} as input. We prove that a triangulation of P2 always exists if at least six points in S are in general position, i.e., no three of them are collinear. We also design an algorithm for triangulating P2 if this necessary condition holds. As far as we know, this is the first computational result on the real projective plane.
Joint power control and user scheduling in multicell wireless networks: Capacity scaling laws
Venue: arXiv cs.IT 2007
Year: 2007

We address the optimization of the sum rate performance in multicell interference-limited singlehop networks where access points are allowed to cooperate in terms of joint resource allocation. The resource allocation policies considered here combine power control and user scheduling. Although very promising from a conceptual point of view, the optimization of the sum of per-link rates hinges, in principle, on tough issues such as computational complexity and the requirement for heavy receiver-to-transmitter channel information feedback across all network cells. In this paper, we show that, in fact, distributed algorithms are actually obtainable in the asymptotic regime where the numbers of users per cell is allowed to grow large. Additionally, using extreme value theory, we provide scaling laws for upper and lower bounds for the network capacity (sum of single user rates over all cells), corresponding to zero-interference and worst-case interference scenarios. We show that the scaling is either dominated by path loss statistics or by small-scale fading, depending on the regime and user location scenario. We show that upper and lower rate bounds behave in fact identically, asymptotically. This remarkable result suggests not only that distributed resource allocation is practically possible but also that the impact of multicell interference on the capacity (in terms of scaling) actually vanishes asymptotically.
Co-Betweenness: A Pairwise Notion of Centrality
Venue: arXiv cs.NI 2007
Year: 2007

Betweenness centrality is a metric that seeks to quantify a sense of the importance of a vertex in a network graph in terms of its "control" on the distribution of information along geodesic paths throughout that network. This quantity however does not capture how different vertices participate together in such control. In order to allow for the uncovering of finer details in this regard, we introduce here an extension of betweenness centrality to pairs of vertices, which we term co-betweenness, that provides the basis for quantifying various analogous pairwise notions of importance and control. More specifically, we motivate and define a precise notion of co-betweenness, we present an efficient algorithm for its computation, extending the algorithm of Brandes in a natural manner, and we illustrate the utilization of this co-betweenness on a handful of different communication networks. From these real-world examples, we show that the co-betweenness allows one to identify certain vertices which are not the most central vertices but which, nevertheless, act as important actors in the relaying and dispatching of information in the network.
Towards the Secrecy Capacity of the Gaussian MIMO Wire-tap Channel: The 2-2-1 Channel
Venue: arXiv cs.IT 2007
Year: 2007

We find the secrecy capacity of the 2-2-1 Gaussian MIMO wire-tap channel, which consists of a transmitter and a receiver with two antennas each, and an eavesdropper with a single antenna. We determine the secrecy capacity of this channel by proposing an achievable scheme and then developing a tight upper bound that meets the proposed achievable secrecy rate. We show that, for this channel, Gaussian signalling in the form of beam-forming is optimal, and no pre-processing of information is necessary.
Resampling methods for parameter-free and robust feature selection with mutual information
Venue: arXiv cs.LG 2007
Year: 2007

Combining the mutual information criterion with a forward feature selection strategy offers a good trade-off between optimality of the selected feature subset and computation time. However, it requires to set the parameter(s) of the mutual information estimator and to determine when to halt the forward procedure. These two choices are difficult to make because, as the dimensionality of the subset increases, the estimation of the mutual information becomes less and less reliable. This paper proposes to use resampling methods, a K-fold cross-validation and the permutation test, to address both issues. The resampling methods bring information about the variance of the estimator, information which can then be used to automatically set the parameter and to calculate a threshold to stop the forward procedure. The procedure is illustrated on a synthetic dataset as well as on real-world examples.
Guessing Facets: Polytope Structure and Improved LP Decoding
Venue: arXiv cs.IT 2007
Year: 2007

In this paper we investigate the structure of the fundamental polytope used in the Linear Programming decoding introduced by Feldman, Karger and Wainwright. We begin by showing that for expander codes, every fractional pseudocodeword always has at least a constant fraction of non-integral bits. We then prove that for expander codes, the active set of any fractional pseudocodeword is smaller by a constant fraction than the active set of any codeword. We further exploit these geometrical properties to devise an improved decoding algorithm with the same complexity order as LP decoding that provably performs better, for any blocklength. It proceeds by guessing facets of the polytope, and then resolving the linear program on these facets. While the LP decoder succeeds only if the ML codeword has the highest likelihood over all pseudocodewords, we prove that the proposed algorithm, when applied to suitable expander codes, succeeds unless there exist a certain number of pseudocodewords, all adjacent to the ML codeword on the LP decoding polytope, and with higher likelihood than the ML codeword. We then describe an extended algorithm, still with polynomial complexity, that succeeds as long as there are at most polynomially many pseudocodewords above the ML codeword.