OpenRaiser/Intern-Atlas huggingface dataset:
Doppler Spread Estimation by Tracking the Delay-Subspace for OFDM Systems in Doubly Selective Fading Channels
Venue: arXiv cs.IT 2008
Year: 2008

A novel maximum Doppler spread estimation algorithm for OFDM systems with comb-type pilot pattern is presented in this paper. By tracking the drifting delay subspace of time-varying multipath channels, a Doppler dependent parameter can be accurately measured and further expanded and transformed into a non-linear high-order polynomial equation, from which the maximum Doppler spread is readily solved by resorting to the Newton's method. Its performance is demonstrated by simulations.
Solving the P/NP Problem under Intrinsic Uncertainty
Venue: arXiv cs.CC 2008
Year: 2008

Heisenberg's uncertainty principle states that it is not possible to compute both the position and momentum of an electron with absolute certainty. However, this computational limitation, which is central to quantum mechanics, has no counterpart in theoretical computer science. Here, I will show that we can distinguish between the complexity classes P and NP when we consider intrinsic uncertainty in our computations, and take uncertainty about whether a bit belongs to the program code or machine input into account. Given intrinsic uncertainty, every output is uncertain, and computations become meaningful only in combination with a confidence level. In particular, it is impossible to compute solutions with absolute certainty as this requires infinite run-time. Considering intrinsic uncertainty, I will present a function that is in NP but not in P, and thus prove that P is a proper subset of NP. I will also show that all traditional hard decision problems have polynomial-time algorithms that provide solutions with confidence under uncertainty.
The Design of Sparse Antenna Array
Venue: arXiv cs.IT 2008
Year: 2008

The aim of antenna array synthesis is to achieve a desired radiation pattern with the minimum number of antenna elements. In this paper the antenna synthesis problem is studied from a totally new perspective. One of the key principles of compressive sensing is that the signal to be sensed should be sparse or compressible. This coincides with the requirement of minimum number of element in the antenna array synthesis problem. In this paper the antenna element of the array can be efficiently reduced via compressive sensing, which shows a great improvement to the existing antenna synthesis method. Moreover, the desired radiation pattern can be achieved in a very computation time which is even shorter than the existing method. Numerical examples are presented to show the high efficiency of the proposed method.
MMOGs as Social Experiments: the Case of Environmental Laws
Venue: arXiv cs.CY 2008
Year: 2008

In this paper we argue that Massively Multiplayer Online Games (MMOGs), also known as Large Games are an interesting research tool for policy experimentation. One of the major problems with lawmaking is that testing the laws is a difficult enterprise. Here we show that the concept of an MMOG can be used to experiment with environmental laws on a large scale, provided that the MMOG is a real game, i.e., it is fun, addictive, presents challenges that last, etc.. We present a detailed game concept as an initial step.
A maximum entropy approach to OFDM channel estimation
Venue: arXiv cs.IT 2008
Year: 2008

In this work, a new Bayesian framework for OFDM channel estimation is proposed. Using Jaynes' maximum entropy principle to derive prior information, we successively tackle the situations when only the channel delay spread is a priori known, then when it is not known. Exploitation of the time-frequency dimensions are also considered in this framework, to derive the optimal channel estimation associated to some performance measure under any state of knowledge. Simulations corroborate the optimality claim and always prove as good or better in performance than classical estimators.
Distributed Constrained Optimization with Semicoordinate Transformations
Venue: arXiv cs.NE 2008
Year: 2008

Recent work has shown how information theory extends conventional full-rationality game theory to allow bounded rational agents. The associated mathematical framework can be used to solve constrained optimization problems. This is done by translating the problem into an iterated game, where each agent controls a different variable of the problem, so that the joint probability distribution across the agents' moves gives an expected value of the objective function. The dynamics of the agents is designed to minimize a Lagrangian function of that joint distribution. Here we illustrate how the updating of the Lagrange parameters in the Lagrangian is a form of automated annealing, which focuses the joint distribution more and more tightly about the joint moves that optimize the objective function. We then investigate the use of ``semicoordinate'' variable transformations. These separate the joint state of the agents from the variables of the optimization problem, with the two connected by an onto mapping. We present experiments illustrating the ability of such transformations to facilitate optimization. We focus on the special kind of transformation in which the statistically independent states of the agents induces a mixture distribution over the optimization variables. Computer experiment illustrate this for $k$-sat constraint satisfaction problems and for unconstrained minimization of $NK$ functions.
Mining Complex Hydrobiological Data with Galois Lattices
Venue: arXiv cs.AI 2008
Year: 2008

We have used Galois lattices for mining hydrobiological data. These data are about macrophytes, that are macroscopic plants living in water bodies. These plants are characterized by several biological traits, that own several modalities. Our aim is to cluster the plants according to their common traits and modalities and to find out the relations between traits. Galois lattices are efficient methods for such an aim, but apply on binary data. In this article, we detail a few approaches we used to transform complex hydrobiological data into binary data and compare the first results obtained thanks to Galois lattices.
Modular difference logic is hard
Venue: arXiv cs.CC 2008
Year: 2008

In connection with machine arithmetic, we are interested in systems of constraints of the form x + k \leq y + k'. Over integers, the satisfiability problem for such systems is polynomial time. The problem becomes NP complete if we restrict attention to the residues for a fixed modulus N.
Symbolic Backwards-Reachability Analysis for Higher-Order Pushdown Systems
Venue: arXiv cs.CC 2008
Year: 2008

Higher-order pushdown systems (PDSs) generalise pushdown systems through the use of higher-order stacks, that is, a nested "stack of stacks" structure. These systems may be used to model higher-order programs and are closely related to the Caucal hierarchy of infinite graphs and safe higher-order recursion schemes. We consider the backwards-reachability problem over higher-order Alternating PDSs (APDSs), a generalisation of higher-order PDSs. This builds on and extends previous work on pushdown systems and context-free higher-order processes in a non-trivial manner. In particular, we show that the set of configurations from which a regular set of higher-order APDS configurations is reachable is regular and computable in n-EXPTIME. In fact, the problem is n-EXPTIME-complete. We show that this work has several applications in the verification of higher-order PDSs, such as linear-time model-checking, alternation-free mu-calculus model-checking and the computation of winning regions of reachability games.
The Application of Fuzzy Logic to Collocation Extraction
Venue: arXiv cs.CL 2008
Year: 2008

Collocations are important for many tasks of Natural language processing such as information retrieval, machine translation, computational lexicography etc. So far many statistical methods have been used for collocation extraction. Almost all the methods form a classical crisp set of collocation. We propose a fuzzy logic approach of collocation extraction to form a fuzzy set of collocations in which each word combination has a certain grade of membership for being collocation. Fuzzy logic provides an easy way to express natural language into fuzzy logic rules. Two existing methods; Mutual information and t-test have been utilized for the input of the fuzzy inference system. The resulting membership function could be easily seen and demonstrated. To show the utility of the fuzzy logic some word pairs have been examined as an example. The working data has been based on a corpus of about one million words contained in different novels constituting project Gutenberg available on www.gutenberg.org. The proposed method has all the advantages of the two methods, while overcoming their drawbacks. Hence it provides a better result than the two methods.
Applying Practice to Theory
Venue: arXiv cs.CC 2008
Year: 2008

How can complexity theory and algorithms benefit from practical advances in computing? We give a short overview of some prior work using practical computing to attack problems in computational complexity and algorithms, informally describe how linear program solvers may be used to help prove new lower bounds for satisfiability, and suggest a research program for developing new understanding in circuit complexity.
Best-Effort Strategies for Losing States
Venue: arXiv cs.GT 2008
Year: 2008

We consider games played on finite graphs, whose goal is to obtain a trace belonging to a given set of winning traces. We focus on those states from which Player 1 cannot force a win. We explore and compare several criteria for establishing what is the preferable behavior of Player 1 from those states. Along the way, we prove several results of theoretical and practical interest, such as a characterization of admissible strategies, which also provides a simple algorithm for computing such strategies for various common goals, and the equivalence between the existence of positional winning strategies and the existence of positional subgame perfect strategies.
Protection Schemes for Two Link Failures in Optical Networks
Venue: arXiv cs.IT 2008
Year: 2008

In this paper we develop network protection schemes against two link failures in optical networks. The motivation behind this work is the fact that the majority of all available links in an optical network suffer from single and double link failures. In the proposed network protection schemes, NPS2-I and NPS2-II, we deploy network coding and reduced capacity on the working paths to provide backup protection paths. In addition, we demonstrate the encoding and decoding aspects of the proposed schemes.
A Divergence Formula for Randomness and Dimension
Venue: arXiv cs.CC 2008
Year: 2008

If $S$ is an infinite sequence over a finite alphabet $Σ$ and $β$ is a probability measure on $Σ$, then the {\it dimension} of $ S$ with respect to $β$, written $\dim^β(S)$, is a constructive version of Billingsley dimension that coincides with the (constructive Hausdorff) dimension $\dim(S)$ when $β$ is the uniform probability measure. This paper shows that $\dim^β(S)$ and its dual $\Dim^β(S)$, the {\it strong dimension} of $S$ with respect to $β$, can be used in conjunction with randomness to measure the similarity of two probability measures $α$ and $β$ on $Σ$. Specifically, we prove that the {\it divergence formula} \[ \dim^β(R) = \Dim^β(R) =\frac{\CH(α)}{\CH(α) + \D(α|| β)} \] holds whenever $α$ and $β$ are computable, positive probability measures on $Σ$ and $R \in Σ^\infty$ is random with respect to $α$. In this formula, $\CH(α)$ is the Shannon entropy of $α$, and $\D(α||β)$ is the Kullback-Leibler divergence between $α$ and $β$. We also show that the above formula holds for all sequences $R$ that are $α$-normal (in the sense of Borel) when $\dim^β(R)$ and $\Dim^β(R)$ are replaced by the more effective finite-state dimensions $\dimfs^β(R)$ and $\Dimfs^β(R)$. In the course of proving this, we also prove finite-state compression characterizations of $\dimfs^β(S)$ and $\Dimfs^β(S)$.
Action Theory Evolution
Venue: arXiv cs.AI 2008
Year: 2008

Like any other logical theory, domain descriptions in reasoning about actions may evolve, and thus need revision methods to adequately accommodate new information about the behavior of actions. The present work is about changing action domain descriptions in propositional dynamic logic. Its contribution is threefold: first we revisit the semantics of action theory contraction that has been done in previous work, giving more robust operators that express minimal change based on a notion of distance between Kripke-models. Second we give algorithms for syntactical action theory contraction and establish their correctness w.r.t. our semantics. Finally we state postulates for action theory contraction and assess the behavior of our operators w.r.t. them. Moreover, we also address the revision counterpart of action theory change, showing that it benefits from our semantics for contraction.
Ferrers Dimension and Boxicity
Venue: arXiv cs.DM 2008
Year: 2008

This note explores the relation between the boxicity of undirected graphs and the Ferrers dimension of digraphs.
A TLA+ Proof System
Venue: arXiv cs.LO 2008
Year: 2008

We describe an extension to the TLA+ specification language with constructs for writing proofs and a proof environment, called the Proof Manager (PM), to checks those proofs. The language and the PM support the incremental development and checking of hierarchically structured proofs. The PM translates a proof into a set of independent proof obligations and calls upon a collection of back-end provers to verify them. Different provers can be used to verify different obligations. The currently supported back-ends are the tableau prover Zenon and Isabelle/TLA+, an axiomatisation of TLA+ in Isabelle/Pure. The proof obligations for a complete TLA+ proof can also be used to certify the theorem in Isabelle/TLA+.
GPU-Based Interactive Visualization of Billion Point Cosmological Simulations
Venue: arXiv cs.GR 2008
Year: 2008

Despite the recent advances in graphics hardware capabilities, a brute force approach is incapable of interactively displaying terabytes of data. We have implemented a system that uses hierarchical level-of-detailing for the results of cosmological simulations, in order to display visually accurate results without loading in the full dataset (containing over 10 billion points). The guiding principle of the program is that the user should not be able to distinguish what they are seeing from a full rendering of the original data. Furthermore, by using a tree-based system for levels of detail, the size of the underlying data is limited only by the capacity of the IO system containing it.
The List-Decoding Size of Reed-Muller Codes
Venue: arXiv cs.IT 2008
Year: 2008

In this work we study the list-decoding size of Reed-Muller codes. Given a received word and a distance parameter, we are interested in bounding the size of the list of Reed-Muller codewords that are within that distance from the received word. Previous bounds of Gopalan, Klivans and Zuckerman \cite{GKZ08} on the list size of Reed-Muller codes apply only up to the minimum distance of the code. In this work we provide asymptotic bounds for the list-decoding size of Reed-Muller codes that apply for {\em all} distances. Additionally, we study the weight distribution of Reed-Muller codes. Prior results of Kasami and Tokura \cite{KT70} on the structure of Reed-Muller codewords up to twice the minimum distance, imply bounds on the weight distribution of the code that apply only until twice the minimum distance. We provide accumulative bounds for the weight distribution of Reed-Muller codes that apply to {\em all} distances.
Phase transition for Local Search on planted SAT
Venue: arXiv cs.DS 2008
Year: 2008

The Local Search algorithm (or Hill Climbing, or Iterative Improvement) is one of the simplest heuristics to solve the Satisfiability and Max-Satisfiability problems. It is a part of many satisfiability and max-satisfiability solvers, where it is used to find a good starting point for a more sophisticated heuristics, and to improve a candidate solution. In this paper we give an analysis of Local Search on random planted 3-CNF formulas. We show that if there is k<7/6 such that the clause-to-variable ratio is less than k ln(n) (n is the number of variables in a CNF) then Local Search whp does not find a satisfying assignment, and if there is k>7/6 such that the clause-to-variable ratio is greater than k ln(n)$ then the local search whp finds a satisfying assignment. As a byproduct we also show that for any constant r there is g such that Local Search applied to a random (not necessarily planted) 3-CNF with clause-to-variable ratio r produces an assignment that satisfies at least gn clauses less than the maximal number of satisfiable clauses.
Sensitivity Analysis Using a Fixed Point Interval Iteration
Venue: arXiv cs.NA 2008
Year: 2008

Proving the existence of a solution to a system of real equations is a central issue in numerical analysis. In many situations, the system of equations depend on parameters which are not exactly known. It is then natural to aim proving the existence of a solution for all values of these parameters in some given domains. This is the aim of the parametrization of existence tests. A new parametric existence test based on the Hansen-Sengupta operator is presented and compared to a similar one based on the Krawczyk operator. It is used as a basis of a fixed point iteration dedicated to rigorous sensibility analysis of parametric systems of equations.
An experimental analysis of Lemke-Howson algorithm
Venue: arXiv cs.DS 2008
Year: 2008

We present an experimental investigation of the performance of the Lemke-Howson algorithm, which is the most widely used algorithm for the computation of a Nash equilibrium for bimatrix games. Lemke-Howson algorithm is based upon a simple pivoting strategy, which corresponds to following a path whose endpoint is a Nash equilibrium. We analyze both the basic Lemke-Howson algorithm and a heuristic modification of it, which we designed to cope with the effects of a 'bad' initial choice of the pivot. Our experimental findings show that, on uniformly random games, the heuristics achieves a linear running time, while the basic Lemke-Howson algorithm runs in time roughly proportional to a polynomial of degree seven. To conduct the experiments, we have developed our own implementation of Lemke-Howson algorithm, which turns out to be significantly faster than state-of-the-art software. This allowed us to run the algorithm on a much larger set of data, and on instances of much larger size, compared with previous work.
The Capacity of Ad hoc Networks under Random Packet Losses
Venue: arXiv cs.IT 2008
Year: 2008

We consider the problem of determining asymptotic bounds on the capacity of a random ad hoc network. Previous approaches assumed a link layer model in which if a transmitter-receiver pair can communicate with each other, i.e., the Signal to Interference and Noise Ratio (SINR) is above a certain threshold, then every transmitted packet is received error-free by the receiver thereby. Using this model, the per node capacity of the network was shown to be $Θ(\frac{1}{\sqrt{n\log{n}}})$. In reality, for any finite link SINR, there is a non-zero probability of erroneous reception of the packet. We show that in a large network, as the packet travels an asymptotically large number of hops from source to destination, the cumulative impact of packet losses over intermediate links results in a per-node throughput of only $O(\frac{1}{n})$. We then propose a new scheduling scheme to counter this effect. The proposed scheme provides tight guarantees on end-to-end packet loss probability, and improves the per-node throughput to $Ω(\frac{1}{\sqrt{n} ({\log{n}})^{\frac{α{+2}}{2(α-2)}}})$ where $α>2$ is the path loss exponent.
Solving package dependencies: from EDOS to Mancoosi
Venue: arXiv cs.SE 2008
Year: 2008

Mancoosi (Managing the Complexity of the Open Source Infrastructure) is an ongoing research project funded by the European Union for addressing some of the challenges related to the "upgrade problem" of interdependent software components of which Debian packages are prototypical examples. Mancoosi is the natural continuation of the EDOS project which has already contributed tools for distribution-wide quality assurance in Debian and other GNU/Linux distributions. The consortium behind the project consists of several European public and private research institutions as well as some commercial GNU/Linux distributions from Europe and South America. Debian is represented by a small group of Debian Developers who are working in the ranks of the involved universities to drive and integrate back achievements into Debian. This paper presents relevant results from EDOS in dependency management and gives an overview of the Mancoosi project and its objectives, with a particular focus on the prospective benefits for Debian.
Determinacy and Decidability of Reachability Games with Partial Observation on Both Sides
Venue: arXiv cs.GT 2008
Year: 2008

We prove two determinacy and decidability results about two-players stochastic reachability games with partial observation on both sides and finitely many states, signals and actions.
Benchmarking the solar dynamo with Maxima
Venue: arXiv cs.SE 2008
Year: 2008

Recently, Jouve et al(A&A, 2008) published the paper that presents the numerical benchmark for the solar dynamo models. Here, I would like to show a way how to get it with help of computer algebra system Maxima. This way was used in our paper (Pipin & Seehafer, A&A 2008, in print) to test some new ideas in the large-scale stellar dynamos. In the present paper I complement the dynamo benchmark with the standard test that address the problem of the free-decay modes in the sphere which is submerged in vacuum.
Ensuring Query Compatibility with Evolving XML Schemas
Venue: arXiv cs.PL 2008
Year: 2008

During the life cycle of an XML application, both schemas and queries may change from one version to another. Schema evolutions may affect query results and potentially the validity of produced data. Nowadays, a challenge is to assess and accommodate the impact of theses changes in rapidly evolving XML applications. This article proposes a logical framework and tool for verifying forward/backward compatibility issues involving schemas and queries. First, it allows analyzing relations between schemas. Second, it allows XML designers to identify queries that must be reformulated in order to produce the expected results across successive schema versions. Third, it allows examining more precisely the impact of schema changes over queries, therefore facilitating their reformulation.
Joint Adaptive Modulation Coding and Cooperative ARQ over Relay Channels-Applications to Land Mobile Satellite Communications
Venue: arXiv cs.IT 2008
Year: 2008

In a cooperative relay network, a relay node (R) facilitates data transmission to the destination node (D), when the latter is unable to decode the source node (S) data correctly. This paper considers such a system model and presents a cross-layer approach to jointly design adaptive modulation and coding (AMC) at the physical layer and cooperative truncated automatic repeat request (ARQ) protocol at the data link layer. We first derive a closed form expression for the spectral efficiency of the joint cooperative ARQ-AMC scheme. Aiming at maximizing this performance measure, we then optimize two AMC schemes for S-D and R-D links, which directly satisfy a prescribed packet loss rate constraint. As an interesting application, we also consider the problem of joint link adaptation and blockage mitigation in land mobile satellite communications (LMSC). We also present a new relay-assisted transmission protocol for LMSC, which delivers the source data to the destination via the relaying link, when the S-D channel is in outage. Numerical results indicate that the proposed schemes noticeably enhances the spectral efficiency compared to a system, which uses a conventional ARQ-AMC scheme at the S-D link, or a system which employs an optimized fixed rate cooperative-ARQ protocol.