OpenRaiser/Intern-Atlas huggingface dataset:
$δ$-sequences and Evaluation Codes defined by Plane Valuations at Infinity
Venue: arXiv cs.IT 2008
Year: 2008

We introduce the concept of $δ$-sequence. A $δ$-sequence $Δ$ generates a well-ordered semigroup $S$ in $\mathbb{Z}^2$ or $\mathbb{R}$. We show how to construct (and compute parameters) for the dual code of any evaluation code associated with a weight function defined by $Δ$ from the polynomial ring in two indeterminates to a semigroup $S$ as above. We prove that this is a simple procedure which can be understood by considering a particular class of valuations of function fields of surfaces, called plane valuations at infinity. We also give algorithms to construct an unlimited number of $δ$-sequences of the different existing types, and so this paper provides the tools to know and use a new large set of codes.
Bit-Interleaved Coded Multiple Beamforming with Imperfect CSIT
Venue: arXiv cs.IT 2008
Year: 2008

This paper addresses the performance of bit-interleaved coded multiple beamforming (BICMB) [1], [2] with imperfect knowledge of beamforming vectors. Most studies for limited-rate channel state information at the transmitter (CSIT) assume that the precoding matrix has an invariance property under an arbitrary unitary transform. In BICMB, this property does not hold. On the other hand, the optimum precoder and detector for BICMB are invariant under a diagonal unitary transform. In order to design a limited-rate CSIT system for BICMB, we propose a new distortion measure optimum under this invariance. Based on this new distortion measure, we introduce a new set of centroids and employ the generalized Lloyd algorithm for codebook design. We provide simulation results demonstrating the performance improvement achieved with the proposed distortion measure and the codebook design for various receivers with linear detectors. We show that although these receivers have the same performance for perfect CSIT, their performance varies under imperfect CSIT.
Abstract numeration systems on bounded languages and multiplication by a constant
Venue: arXiv cs.DM 2008
Year: 2008

A set of integers is $S$-recognizable in an abstract numeration system $S$ if the language made up of the representations of its elements is accepted by a finite automaton. For abstract numeration systems built over bounded languages with at least three letters, we show that multiplication by an integer $λ\ge2$ does not preserve $S$-recognizability, meaning that there always exists a $S$-recognizable set $X$ such that $λX$ is not $S$-recognizable. The main tool is a bijection between the representation of an integer over a bounded language and its decomposition as a sum of binomial coefficients with certain properties, the so-called combinatorial numeration system.
Determinacy in a synchronous pi-calculus
Venue: arXiv cs.LO 2008
Year: 2008

The S-pi-calculus is a synchronous pi-calculus which is based on the SL model. The latter is a relaxation of the Esterel model where the reaction to the absence of a signal within an instant can only happen at the next instant. In the present work, we present and characterise a compositional semantics of the S-pi-calculus based on suitable notions of labelled transition system and bisimulation. Based on this semantic framework, we explore the notion of determinacy and the related one of (local) confluence.
Clustering and Feature Selection using Sparse Principal Component Analysis
Venue: arXiv cs.AI 2008
Year: 2008

In this paper, we study the application of sparse principal component analysis (PCA) to clustering and feature selection problems. Sparse PCA seeks sparse factors, or linear combinations of the data variables, explaining a maximum amount of variance in the data while having only a limited number of nonzero coefficients. PCA is often used as a simple clustering technique and sparse factors allow us here to interpret the clusters in terms of a reduced set of variables. We begin with a brief introduction and motivation on sparse PCA and detail our implementation of the algorithm in d'Aspremont et al. (2005). We then apply these results to some classic clustering and feature selection problems arising in biology.
A note on equipartition
Venue: arXiv cs.CG 2008
Year: 2008

The problem of the existence of an equi-partition of a curve in $\R^n$ has recently been raised in the context of computational geometry. The problem is to show that for a (continuous) curve $Γ: [0,1] \to \R^n$ and for any positive integer N, there exist points $t_0=0<t_1<...<t_{N-1}<1=t_N$, such that $d(Γ(t_{i-1}),Γ(t_i))=d(Γ(t_{i}),Γ(t_{i+1}))$ for all $i=1,...,N$, where d is a metric or even a semi-metric (a weaker notion) on $\R^n$. We show here that the existence of such points, in a broader context, is a consequence of Brower's fixed point theorem.
Single-Symbol ML Decodable Distributed STBCs for Partially-Coherent Cooperative Networks
Venue: arXiv cs.IT 2008
Year: 2008

Space-time block codes (STBCs) that are single-symbol decodable (SSD) in a co-located multiple antenna setting need not be SSD in a distributed cooperative communication setting. A relay network with N relays and a single source-destination pair is called a partially-coherent relay channel (PCRC) if the destination has perfect channel state information (CSI) of all the channels and the relays have only the phase information of the source-to-relay channels. In this paper, first, a new set of necessary and sufficient conditions for a STBC to be SSD for co-located multiple antenna communication is obtained. Then, this is extended to a set of necessary and sufficient conditions for a distributed STBC (DSTBC) to be SSD for a PCRC, by identifying the additional conditions. Using this, several SSD DSTBCs for PCRC are identified among the known classes of STBCs. It is proved that even if a SSD STBC for a co-located MIMO channel does not satisfy the additional conditions for the code to be SSD for a PCRC, single-symbol decoding of it in a PCRC gives full-diversity and only coding gain is lost. It is shown that when a DSTBC is SSD for a PCRC, then arbitrary coordinate interleaving of the in-phase and quadrature-phase components of the variables does not disturb its SSD property for PCRC. Finally, it is shown that the possibility of {\em channel phase compensation} operation at the relay nodes using partial CSI at the relays increases the possible rate of SSD DSTBCs from $\frac{2}{N}$ when the relays do not have CSI to 1/2, which is independent of N.
Identifying Small Mean Reverting Portfolios
Venue: arXiv cs.CE 2008
Year: 2008

Given multivariate time series, we study the problem of forming portfolios with maximum mean reversion while constraining the number of assets in these portfolios. We show that it can be formulated as a sparse canonical correlation analysis and study various algorithms to solve the corresponding sparse generalized eigenvalue problems. After discussing penalized parameter estimation procedures, we study the sparsity versus predictability tradeoff and the impact of predictability in various markets.
Spectrum Sensing in Wideband OFDM Cognitive Radios
Venue: arXiv cs.IT 2008
Year: 2008

In this paper, detection of the primary user (PU) signal in an orthogonal frequency division multiplexing (OFDM) based cognitive radio (CR) system is addressed. According to the prior knowledge of the PU signal known to the detector, three detection algorithms based on the Neyman-Pearson philosophy are proposed. In the first case, a Gaussian PU signal with completely known probability density function (PDF) except for its received power is considered. The frequency band that the PU signal resides is also assumed known. Detection is performed individually at each OFDM sub-carrier possibly interfered by the PU signal, and the results are then combined to form a final decision. In the second case, the sub-carriers that the PU signal resides are known. Observations from all possibly interfered sub-carriers are considered jointly to exploit the fact that the presence of a PU signal interferers all of them simultaneously. In the last case, it is assumed no PU signal prior knowledge is available. The detection is involved with a search of the interfered band. The proposed detector is able to detect an abrupt power change when tracing along the frequency axis.
On the Protocol Composition Logic PCL
Venue: arXiv cs.CR 2008
Year: 2008

A recent development in formal security protocol analysis is the Protocol Composition Logic (PCL). We identify a number of problems with this logic as well as with extensions of the logic, as defined in [DDMP05,HSD+05,He05,Dat05,Der06,DDMR07]. The identified problems imply strong restrictions on the scope of PCL, and imply that some currently claimed PCL proofs cannot be proven within the logic, or make use of unsound axioms. Where possible, we propose solutions for these problems.
Cirquent calculus deepened
Venue: arXiv cs.LO 2008
Year: 2008

Cirquent calculus is a new proof-theoretic and semantic framework, whose main distinguishing feature is being based on circuits, as opposed to the more traditional approaches that deal with tree-like objects such as formulas or sequents. Among its advantages are greater efficiency, flexibility and expressiveness. This paper presents a detailed elaboration of a deep-inference cirquent logic, which is naturally and inherently resource conscious. It shows that classical logic, both syntactically and semantically, is just a special, conservative fragment of this more general and, in a sense, more basic logic -- the logic of resources in the form of cirquent calculus. The reader will find various arguments in favor of switching to the new framework, such as arguments showing the insufficiency of the expressive power of linear logic or other formula-based approaches to developing resource logics, exponential improvements over the traditional approaches in both representational and proof complexities offered by cirquent calculus, and more. Among the main purposes of this paper is to provide an introductory-style starting point for what, as the author wishes to hope, might have a chance to become a new line of research in proof theory -- a proof theory based on circuits instead of formulas.
The Topology of Bendless Three-Dimensional Orthogonal Graph Drawing
Venue: arXiv cs.CG 2008
Year: 2008

We consider embeddings of 3-regular graphs into 3-dimensional Cartesian coordinates, in such a way that two vertices are adjacent if and only if two of their three coordinates are equal (that is, if they lie on an axis-parallel line) and such that no three points lie on the same axis-parallel line; we call a graph with such an embedding an xyz graph}. We describe a correspondence between xyz graphs and face-colored embeddings of the graph onto two-dimensional manifolds, and we relate bipartiteness of the xyz graph to orientability of the underlying topological surface. Using this correspondence, we show that planar graphs are xyz graphs if and only if they are bipartite, cubic, and three-connected, and that it is NP-complete to determine whether an arbitrary graph is an xyz graph. We also describe an algorithm with running time O(n 2^{n/2}) for testing whether a given graph is an xyz graph.
An efficient simulation algorithm based on abstract interpretation
Venue: arXiv cs.LO 2008
Year: 2008

A number of algorithms for computing the simulation preorder are available. Let Sigma denote the state space, -> the transition relation and Psim the partition of Sigma induced by simulation equivalence. The algorithms by Henzinger, Henzinger, Kopke and by Bloom and Paige run in O(|Sigma||->|)-time and, as far as time-complexity is concerned, they are the best available algorithms. However, these algorithms have the drawback of a space complexity that is more than quadratic in the size of the state space. The algorithm by Gentilini, Piazza, Policriti--subsequently corrected by van Glabbeek and Ploeger--appears to provide the best compromise between time and space complexity. Gentilini et al.'s algorithm runs in O(|Psim|^2|->|)-time while the space complexity is in O(|Psim|^2 + |Sigma|log|Psim|). We present here a new efficient simulation algorithm that is obtained as a modification of Henzinger et al.'s algorithm and whose correctness is based on some techniques used in applications of abstract interpretation to model checking. Our algorithm runs in O(|Psim||->|)-time and O(|Psim||Sigma|log|Sigma|)-space. Thus, this algorithm improves the best known time bound while retaining an acceptable space complexity that is in general less than quadratic in the size of the state space. An experimental evaluation showed good comparative results with respect to Henzinger, Henzinger and Kopke's algorithm.
Q-adic Transform revisited
Venue: arXiv cs.SC 2008
Year: 2008

We present an algorithm to perform a simultaneous modular reduction of several residues. This algorithm is applied fast modular polynomial multiplication. The idea is to convert the $X$-adic representation of modular polynomials, with $X$ an indeterminate, to a $q$-adic representation where $q$ is an integer larger than the field characteristic. With some control on the different involved sizes it is then possible to perform some of the $q$-adic arithmetic directly with machine integers or floating points. Depending also on the number of performed numerical operations one can then convert back to the $q$-adic or $X$-adic representation and eventually mod out high residues. In this note we present a new version of both conversions: more tabulations and a way to reduce the number of divisions involved in the process are presented. The polynomial multiplication is then applied to arithmetic in small finite field extensions.
On the Satisfiability Threshold and Clustering of Solutions of Random 3-SAT Formulas
Venue: arXiv cs.CC 2008
Year: 2008

We study the structure of satisfying assignments of a random 3-SAT formula. In particular, we show that a random formula of density 4.453 or higher almost surely has no non-trivial "core" assignments. Core assignments are certain partial assignments that can be extended to satisfying assignments, and have been studied recently in connection with the Survey Propagation heuristic for random SAT. Their existence implies the presence of clusters of solutions, and they have been shown to exist with high probability below the satisfiability threshold for k-SAT with k>8, by Achlioptas and Ricci-Tersenghi, STOC 2006. Our result implies that either this does not hold for 3-SAT or the threshold density for satisfiability in 3-SAT lies below 4.453. The main technical tool that we use is a novel simple application of the first moment method.
Common Beliefs and Public Announcements in Strategic Games with Arbitrary Strategy Sets
Venue: arXiv cs.GT 2008
Year: 2008

We provide an epistemic analysis of arbitrary strategic games based on possibility correspondences. We first establish a generic result that links true common beliefs (and, respectively, common knowledge) of players' rationality defined by means of `monotonic' properties, with the iterated elimination of strategies that do not satisfy these properties. It allows us to deduce the customary results concerned with true common beliefs of rationality and iterated elimination of strictly dominated strategies as simple corollaries. This approach relies on Tarski's Fixpoint Theorem. We also provide an axiomatic presentation of this generic result. This allows us to clarify the proof-theoretic principles assumed in players' reasoning. Finally, we provide an alternative characterization of the iterated elimination of strategies based on the concept of a public announcement. It applies to `global properties'. Both classes of properties include the notions of rationalizability and the iterated elimination of strictly dominated strategies.
Optimal encoding on discrete lattice with translational invariant constrains using statistical algorithms
Venue: arXiv cs.IT 2008
Year: 2008

In this paper will be presented methodology of encoding information in valuations of discrete lattice with some translational invariant constrains in asymptotically optimal way. The method is based on finding statistical description of such valuations and changing it into statistical algorithm, which allows to construct deterministically valuation with given statistics. Optimal statistics allow to generate valuations with uniform distribution - we get maximum information capacity this way. It will be shown that we can reach the optimum for one-dimensional models using maximal entropy random walk and that for the general case we can practically get as close to the capacity of the model as we want (found numerically: lost 10^{-10} bit/node for Hard Square). There will be also presented simpler alternative to arithmetic coding method which can be used as cryptosystem and data correction method too.
Differential invariants of a Lie group action: syzygies on a generating set
Venue: arXiv cs.SC 2008
Year: 2008

Given a group action, known by its infinitesimal generators, we exhibit a complete set of syzygies on a generating set of differential invariants. For that we elaborate on the reinterpretation of Cartan's moving frame by Fels and Olver (1999). This provides constructive tools for exploring algebras of differential invariants.
Gradient Descent Bit Flipping Algorithms for Decoding LDPC Codes
Venue: arXiv cs.IT 2008
Year: 2008

A novel class of bit-flipping (BF) algorithms for decoding low-density parity-check (LDPC) codes is presented. The proposed algorithms, which are called gradient descent bit flipping (GDBF) algorithms, can be regarded as simplified gradient descent algorithms. Based on gradient descent formulation, the proposed algorithms are naturally derived from a simple non-linear objective function.
Kerdock Codes for Limited Feedback Precoded MIMO Systems
Venue: arXiv cs.IT 2008
Year: 2008

A codebook based limited feedback strategy is a practical way to obtain partial channel state information at the transmitter in a precoded multiple-input multiple-output (MIMO) wireless system. Conventional codebook designs use Grassmannian packing, equiangular frames, vector quantization, or Fourier based constructions. While the capacity and error rate performance of conventional codebook constructions have been extensively investigated, constructing these codebooks is notoriously difficult relying on techniques such as nonlinear search or iterative algorithms. Further, the resulting codebooks may not have a systematic structure to facilitate storage of the codebook and low search complexity. In this paper, we propose a new systematic codebook design based on Kerdock codes and mutually unbiased bases. The proposed Kerdock codebook consists of multiple mutually unbiased unitary bases matrices with quaternary entries and the identity matrix. We propose to derive the beamforming and precoding codebooks from this base codebook, eliminating the requirement to store multiple codebooks. The propose structure requires little memory to store and, as we show, the quaternary structure facilitates codeword search. We derive the chordal distance for two antenna and four antenna codebooks, showing that the proposed codebooks compare favorably with prior designs. Monte Carlo simulations are used to compare achievable rates and error rates for different codebooks sizes.
An interface group for process components
Venue: arXiv cs.LO 2008
Year: 2008

We take a process component as a pair of an interface and a behaviour. We study the composition of interacting process components in the setting of process algebra. We formalize the interfaces of interacting process components by means of an interface group. An interesting feature of the interface group is that it allows for distinguishing between expectations and promises in interfaces of process components. This distinction comes into play in case components with both client and server behaviour are involved.
Testing Kak's Conjecture on Binary Reciprocal of Primes and Cryptographic Applications
Venue: arXiv cs.CR 2008
Year: 2008

This note considers reciprocal of primes in binary representation and shows that the conjecture that 0s exceed 1s in most cases continues to hold for primes less one million. The conjecture has also been tested for ternary representation with similar results. Some applications of this result to cryptography are discussed.
Minimum-weight double-tree shortcutting for Metric TSP: Bounding the approximation ratio
Venue: arXiv cs.DS 2008
Year: 2008

The Metric Traveling Salesman Problem (TSP) is a classical NP-hard optimization problem. The double-tree shortcutting method for Metric TSP yields an exponentially-sized space of TSP tours, each of which approximates the optimal solution within at most a factor of 2. We consider the problem of finding among these tours the one that gives the closest approximation, i.e.\ the \emph{minimum-weight double-tree shortcutting}. Previously, we gave an efficient algorithm for this problem, and carried out its experimental analysis. In this paper, we address the related question of the worst-case approximation ratio for the minimum-weight double-tree shortcutting method. In particular, we give lower bounds on the approximation ratio in some specific metric spaces: the ratio of 2 in the discrete shortest path metric, 1.622 in the planar Euclidean metric, and 1.666 in the planar Minkowski metric. The first of these lower bounds is tight; we conjecture that the other two bounds are also tight, and in particular that the minimum-weight double-tree method provides a 1.622-approximation for planar Euclidean TSP.
Normalization of IZF with Replacement
Venue: arXiv cs.LO 2008
Year: 2008

ZF is a well investigated impredicative constructive version of Zermelo-Fraenkel set theory. Using set terms, we axiomatize IZF with Replacement, which we call \izfr, along with its intensional counterpart \iizfr. We define a typed lambda calculus $\li$ corresponding to proofs in \iizfr according to the Curry-Howard isomorphism principle. Using realizability for \iizfr, we show weak normalization of $\li$. We use normalization to prove the disjunction, numerical existence and term existence properties. An inner extensional model is used to show these properties, along with the set existence property, for full, extensional \izfr.
Comparing the notions of optimality in CP-nets, strategic games and soft constraints
Venue: arXiv cs.AI 2008
Year: 2008

The notion of optimality naturally arises in many areas of applied mathematics and computer science concerned with decision making. Here we consider this notion in the context of three formalisms used for different purposes in reasoning about multi-agent systems: strategic games, CP-nets, and soft constraints. To relate the notions of optimality in these formalisms we introduce a natural qualitative modification of the notion of a strategic game. We show then that the optimal outcomes of a CP-net are exactly the Nash equilibria of such games. This allows us to use the techniques of game theory to search for optimal outcomes of CP-nets and vice-versa, to use techniques developed for CP-nets to search for Nash equilibria of the considered games. Then, we relate the notion of optimality used in the area of soft constraints to that used in a generalization of strategic games, called graphical games. In particular we prove that for a natural class of soft constraints that includes weighted constraints every optimal solution is both a Nash equilibrium and Pareto efficient joint strategy. For a natural mapping in the other direction we show that Pareto efficient joint strategies coincide with the optimal solutions of soft constraints.