OpenRaiser/Intern-Atlas huggingface dataset:
On Two Dimensional Orthogonal Knapsack Problem
Venue: arXiv cs.DS 2008
Year: 2008

In this paper, we study the following knapsack problem: Given a list of squares with profits, we are requested to pack a sublist of them into a rectangular bin (not a unit square bin) to make profits in the bin as large as possible. We first observe there is a Polynomial Time Approximation Scheme (PTAS) for the problem of packing weighted squares into rectangular bins with large resources, then apply the PTAS to the problem of packing squares with profits into a rectangular bin and get a $\frac65+ε$ approximation algorithm.
On the Convexity of the MSE Region of Single-Antenna Users
Venue: arXiv cs.IT 2008
Year: 2008

We prove convexity of the sum-power constrained mean square error (MSE) region in case of two single-antenna users communicating with a multi-antenna base station. Due to the MSE duality this holds both for the vector broadcast channel and the dual multiple access channel. Increasing the number of users to more than two, we show by means of a simple counter-example that the resulting MSE region is not necessarily convex any longer, even under the assumption of single-antenna users. In conjunction with our former observation that the two user MSE region is not necessarily convex for two multi-antenna users, this extends and corrects the hitherto existing notion of the MSE region geometry.
On the approximability of minmax (regret) network optimization problems
Venue: arXiv cs.CC 2008
Year: 2008

In this paper the minmax (regret) versions of some basic polynomially solvable deterministic network problems are discussed. It is shown that if the number of scenarios is unbounded, then the problems under consideration are not approximable within $\log^{1-ε} K$ for any $ε>0$ unless NP $\subseteq$ DTIME$(n^{\mathrm{poly} \log n})$, where $K$ is the number of scenarios.
Channel State Feedback Schemes for Multiuser MIMO-OFDM Downlink
Venue: arXiv cs.IT 2008
Year: 2008

Channel state feedback schemes for the MIMO broadcast downlink have been widely studied in the frequency-flat case. This work focuses on the more relevant frequency selective case, where some important new aspects emerge. We consider a MIMO-OFDM broadcast channel and compare achievable ergodic rates under three channel state feedback schemes: analog feedback, direction quantized feedback and "time-domain" channel quantized feedback. The first two schemes are direct extensions of previously proposed schemes. The third scheme is novel, and it is directly inspired by rate-distortion theory of Gaussian correlated sources. For each scheme we derive the conditions under which the system achieves full multiplexing gain. The key difference with respect to the widely treated frequency-flat case is that in MIMO-OFDM the frequency-domain channel transfer function is a Gaussian correlated source. The new time-domain quantization scheme takes advantage of the channel frequency correlation structure and outperforms the other schemes. Furthermore, it is by far simpler to implement than complicated spherical vector quantization. In particular, we observe that no structured codebook design and vector quantization is actually needed for efficient channel state information feedback.
Semi-continuous Sized Types and Termination
Venue: arXiv cs.PL 2008
Year: 2008

Some type-based approaches to termination use sized types: an ordinal bound for the size of a data structure is stored in its type. A recursive function over a sized type is accepted if it is visible in the type system that recursive calls occur just at a smaller size. This approach is only sound if the type of the recursive function is admissible, i.e., depends on the size index in a certain way. To explore the space of admissible functions in the presence of higher-kinded data types and impredicative polymorphism, a semantics is developed where sized types are interpreted as functions from ordinals into sets of strongly normalizing terms. It is shown that upper semi-continuity of such functions is a sufficient semantic criterion for admissibility. To provide a syntactical criterion, a calculus for semi-continuous functions is developed.
Issues in Strategic Decision Modelling
Venue: arXiv cs.HC 2008
Year: 2008

[Spreadsheet] Models are invaluable tools for strategic planning. Models help key decision makers develop a shared conceptual understanding of complex decisions, identify sensitivity factors and test management scenarios. Different modelling approaches are specialist areas in themselves. Model development can be onerous, expensive, time consuming, and often bewildering. It is also an iterative process where the true magnitude of the effort, time and data required is often not fully understood until well into the process. This paper explores the traditional approaches to strategic planning modelling commonly used in organisations and considers the application of a real-options approach to match and benefit from the increasing uncertainty in today's rapidly changing world.
Woven Graph Codes: Asymptotic Performances and Examples
Venue: arXiv cs.IT 2008
Year: 2008

Constructions of woven graph codes based on constituent block and convolutional codes are studied. It is shown that within the random ensemble of such codes based on $s$-partite, $s$-uniform hypergraphs, where $s$ depends only on the code rate, there exist codes satisfying the Varshamov-Gilbert (VG) and the Costello lower bound on the minimum distance and the free distance, respectively. A connection between regular bipartite graphs and tailbiting codes is shown. Some examples of woven graph codes are presented. Among them an example of a rate $R_{\rm wg}=1/3$ woven graph code with $d_{\rm free}=32$ based on Heawood's bipartite graph and containing $n=7$ constituent rate $R^{c}=2/3$ convolutional codes with overall constraint lengths $ν^{c}=5$ is given. An encoding procedure for woven graph codes with complexity proportional to the number of constituent codes and their overall constraint length $ν^{c}$ is presented.
Discrete schemes for Gaussian curvature and their convergence
Venue: arXiv cs.CV 2008
Year: 2008

In this paper, several discrete schemes for Gaussian curvature are surveyed. The convergence property of a modified discrete scheme for the Gaussian curvature is considered. Furthermore, a new discrete scheme for Gaussian curvature is resented. We prove that the new scheme converges at the regular vertex with valence not less than 5. By constructing a counterexample, we also show that it is impossible for building a discrete scheme for Gaussian curvature which converges over the regular vertex with valence 4. Finally, asymptotic errors of several discrete scheme for Gaussian curvature are compared.
P is a proper subset of NP
Venue: arXiv cs.CC 2008
Year: 2008

The purpose of this article is to examine and limit the conditions in which the P complexity class could be equivalent to the NP complexity class. Proof is provided by demonstrating that as the number of clauses in a NP-complete problem approaches infinity, the number of input sets processed per computation performed also approaches infinity when solved by a polynomial time solution. It is then possible to determine that the only deterministic optimization of a NP-complete problem that could prove P = NP would be one that examines no more than a polynomial number of input sets for a given problem. It is then shown that subdividing the set of all possible input sets into a representative polynomial search partition is a problem in the FEXP complexity class. The findings of this article are combined with the findings of other articles in this series of 4 articles. The final conclusion will be demonstrated that P =/= NP.
A Survey of Quantum Programming Languages: History, Methods, and Tools
Venue: arXiv cs.PL 2008
Year: 2008

Quantum computer programming is emerging as a new subject domain from multidisciplinary research in quantum computing, computer science, mathematics (especially quantum logic, lambda calculi, and linear logic), and engineering attempts to build the first non-trivial quantum computer. This paper briefly surveys the history, methods, and proposed tools for programming quantum computers circa late 2007. It is intended to provide an extensive but non-exhaustive look at work leading up to the current state-of-the-art in quantum computer programming. Further, it is an attempt to analyze the needed programming tools for quantum programmers, to use this analysis to predict the direction in which the field is moving, and to make recommendations for further development of quantum programming language tools.
Approximating L1-distances between mixture distributions using random projections
Venue: arXiv cs.DS 2008
Year: 2008

We consider the problem of computing L1-distances between every pair ofcprobability densities from a given family. We point out that the technique of Cauchy random projections (Indyk'06) in this context turns into stochastic integrals with respect to Cauchy motion. For piecewise-linear densities these integrals can be sampled from if one can sample from the stochastic integral of the function x->(1,x). We give an explicit density function for this stochastic integral and present an efficient sampling algorithm. As a consequence we obtain an efficient algorithm to approximate the L1-distances with a small relative error. For piecewise-polynomial densities we show how to approximately sample from the distributions resulting from the stochastic integrals. This also results in an efficient algorithm to approximate the L1-distances, although our inability to get exact samples worsens the dependence on the parameters.
Hash Property and Fixed-rate Universal Coding Theorems
Venue: arXiv cs.IT 2008
Year: 2008

The aim of this paper is to prove the achievability of fixed-rate universal coding problems by using our previously introduced notion of hash property. These problems are the fixed-rate lossless universal source coding problem and the fixed-rate universal channel coding problem. Since an ensemble of sparse matrices satisfies the hash property requirement, it is proved that we can construct universal codes by using sparse matrices.
Geometric Data Analysis, From Correspondence Analysis to Structured Data Analysis (book review)
Venue: arXiv cs.AI 2008
Year: 2008

Review of: Brigitte Le Roux and Henry Rouanet, Geometric Data Analysis, From Correspondence Analysis to Structured Data Analysis, Kluwer, Dordrecht, 2004, xi+475 pp.
Immune System Approaches to Intrusion Detection - A Review
Venue: arXiv cs.NE 2008
Year: 2008

The use of artificial immune systems in intrusion detection is an appealing concept for two reasons. Firstly, the human immune system provides the human body with a high level of protection from invading pathogens, in a robust, self-organised and distributed manner. Secondly, current techniques used in computer security are not able to cope with the dynamic and increasingly complex nature of computer systems and their security. It is hoped that biologically inspired approaches in this area, including the use of immune-based systems will be able to meet this challenge. Here we review the algorithms used, the development of the systems and the outcome of their implementation. We provide an introduction and analysis of the key developments within this field, in addition to making suggestions for future research.
Interference-Assisted Secret Communication
Venue: arXiv cs.IT 2008
Year: 2008

Wireless communication is susceptible to adversarial eavesdropping due to the broadcast nature of the wireless medium. In this paper it is shown how eavesdropping can be alleviated by exploiting the superposition property of the wireless medium. A wiretap channel with a helping interferer (WT-HI), in which a transmitter sends a confidential message to its intended receiver in the presence of a passive eavesdropper, and with the help of an independent interferer, is considered. The interferer, which does not know the confidential message, helps in ensuring the secrecy of the message by sending independent signals. An achievable secrecy rate for the WT-HI is given. The results show that interference can be exploited to assist secrecy in wireless communications. An important example of the Gaussian case, in which the interferer has a better channel to the intended receiver than to the eavesdropper, is considered. In this situation, the interferer can send a (random) codeword at a rate that ensures that it can be decoded and subtracted from the received signal by the intended receiver but cannot be decoded by the eavesdropper. Hence, only the eavesdropper is interfered with and the secrecy level of the confidential message is increased.
Fast k Nearest Neighbor Search using GPU
Venue: arXiv cs.CV 2008
Year: 2008

The recent improvements of graphics processing units (GPU) offer to the computer vision community a powerful processing platform. Indeed, a lot of highly-parallelizable computer vision problems can be significantly accelerated using GPU architecture. Among these algorithms, the k nearest neighbor search (KNN) is a well-known problem linked with many applications such as classification, estimation of statistical properties, etc. The main drawback of this task lies in its computation burden, as it grows polynomially with the data size. In this paper, we show that the use of the NVIDIA CUDA API accelerates the search for the KNN up to a factor of 120.
Multiterminal source coding with complementary delivery
Venue: arXiv cs.IT 2008
Year: 2008

A coding problem for correlated information sources is investigated. Messages emitted from two correlated sources are jointly encoded, and delivered to two decoders. Each decoder has access to one of the two messages to enable it to reproduce the other message. The rate-distortion function for the coding problem and its interesting properties are clarified.
A classification of invasive patterns in AOP
Venue: arXiv cs.PL 2008
Year: 2008

Aspect-Oriented Programming (AOP) improves modularity by encapsulating crosscutting concerns into aspects. Some mechanisms to compose aspects allow invasiveness as a mean to integrate concerns. Invasiveness means that AOP languages have unrestricted access to program properties. Such kind of languages are interesting because they allow performing complex operations and better introduce functionalities. In this report we present a classification of invasive patterns in AOP. This classification characterizes the aspects invasive behavior and allows developers to abstract about the aspect incidence over the program they crosscut.
Prediciendo el generador cuadratico (in Spanish)
Venue: arXiv cs.CR 2008
Year: 2008

Let p be a prime and a, c be integers such that a<>0 mod p. The quadratic generator is a sequence (u_n) of pseudorandom numbers defined by u_{n+1}=a*(u_n)^2+c mod p. In this article we probe that if we know sufficiently many of the most significant bits of two consecutive values u_n, u_{n+1}, then we can compute the seed u_0 except for a small number of exceptional values. ----- Sean p un primo, a y c enteros tales que a<>0 mod p. El generador cuadratico es una sucesion (u_n) de numeros pseudoaleatorios definidos por la relacion u_{n+1}=a*(u_n)^2+c mod p. En este trabajo demostramos que si conocemos un numero suficientemente grande de los bits mas significativos para dos valores consecutivos u_n, u_{n+1}, entonces podemos descubrir en tiempo polinomial la semilla u_0, excepto para un conjunto pequeno de valores excepcionales.
Object Re-Use & Exchange: A Resource-Centric Approach
Venue: arXiv cs.DL 2008
Year: 2008

The OAI Object Reuse and Exchange (OAI-ORE) framework recasts the repository-centric notion of digital object to a bounded aggregation of Web resources. In this manner, digital library content is more integrated with the Web architecture, and thereby more accessible to Web applications and clients. This generalized notion of an aggregation that is independent of repository containment conforms more closely with notions in eScience and eScholarship, where content is distributed across multiple services and databases. We provide a motivation for the OAI-ORE project, review previous interoperability efforts, describe draft ORE specifications and report on promising results from early experimentation that illustrate improved interoperability and reuse of digital objects.
On the Expressiveness and Complexity of ATL
Venue: arXiv cs.LO 2008
Year: 2008

ATL is a temporal logic geared towards the specification and verification of properties in multi-agents systems. It allows to reason on the existence of strategies for coalitions of agents in order to enforce a given property. In this paper, we first precisely characterize the complexity of ATL model-checking over Alternating Transition Systems and Concurrent Game Structures when the number of agents is not fixed. We prove that it is Δ^P_2 - and Δ^P_?_3-complete, depending on the underlying multi-agent model (ATS and CGS resp.). We also consider the same problems for some extensions of ATL. We then consider expressiveness issues. We show how ATS and CGS are related and provide translations between these models w.r.t. alternating bisimulation. We also prove that the standard definition of ATL (built on modalities "Next", "Always" and "Until") cannot express the duals of its modalities: it is necessary to explicitely add the modality "Release".
A Critique of a Polynomial-time SAT Solver Devised by Sergey Gubin
Venue: arXiv cs.CC 2008
Year: 2008

This paper refutes the validity of the polynomial-time algorithm for solving satisfiability proposed by Sergey Gubin. Gubin introduces the algorithm using 3-SAT and eventually expands it to accept a broad range of forms of the Boolean satisfiability problem. Because 3-SAT is NP-complete, the algorithm would have implied P = NP, had it been correct. Additionally, this paper refutes the correctness of his polynomial-time reduction of SAT to 2-SAT.
Intelligence gathering by capturing the social processes within prisons
Venue: arXiv cs.CY 2008
Year: 2008

We present a prototype system that can be used to capture longitudinal socialising processes by recording people's encounters in space. We argue that such a system can usefully be deployed in prisons and other detention facilities in order help intelligence analysts assess the behaviour or terrorist and organised crime groups, and their potential relationships. Here we present the results of a longitudinal study, carried out with civilians, which demonstrates the capabilities of our system.
Visibly Tree Automata with Memory and Constraints
Venue: arXiv cs.LO 2008
Year: 2008

Tree automata with one memory have been introduced in 2001. They generalize both pushdown (word) automata and the tree automata with constraints of equality between brothers of Bogaert and Tison. Though it has a decidable emptiness problem, the main weakness of this model is its lack of good closure properties. We propose a generalization of the visibly pushdown automata of Alur and Madhusudan to a family of tree recognizers which carry along their (bottom-up) computation an auxiliary unbounded memory with a tree structure (instead of a symbol stack). In other words, these recognizers, called Visibly Tree Automata with Memory (VTAM) define a subclass of tree automata with one memory enjoying Boolean closure properties. We show in particular that they can be determinized and the problems like emptiness, membership, inclusion and universality are decidable for VTAM. Moreover, we propose several extensions of VTAM whose transitions may be constrained by different kinds of tests between memories and also constraints a la Bogaert and Tison comparing brother subtrees in the tree in input. We show that some of these classes of constrained VTAM keep the good closure and decidability properties, and we demonstrate their expressiveness with relevant examples of tree languages.
Multicast Capacity of Optical WDM Packet Ring for Hotspot Traffic
Venue: arXiv cs.IT 2008
Year: 2008

Packet-switching WDM ring networks with a hotspot transporting unicast, multicast, and broadcast traffic are important components of high-speed metropolitan area networks. For an arbitrary multicast fanout traffic model with uniform, hotspot destination, and hotspot source packet traffic, we analyze the maximum achievable long-run average packet throughput, which we refer to as \textit{multicast capacity}, of bi-directional shortest-path routed WDM rings. We identify three segments that can experience the maximum utilization, and thus, limit the multicast capacity. We characterize the segment utilization probabilities through bounds and approximations, which we verify through simulations. We discover that shortest-path routing can lead to utilization probabilities above one half for moderate to large portions of hotspot source multi- and broadcast traffic, and consequently multicast capacities of less than two simultaneous packet transmissions. We outline a one-copy routing strategy that guarantees a multicast capacity of at least two simultaneous packet transmissions for arbitrary hotspot source traffic.
Coalitions in Cooperative Wireless Networks
Venue: arXiv cs.GT 2008
Year: 2008

Cooperation between rational users in wireless networks is studied using coalitional game theory. Using the rate achieved by a user as its utility, it is shown that the stable coalition structure, i.e., set of coalitions from which users have no incentives to defect, depends on the manner in which the rate gains are apportioned among the cooperating users. Specifically, the stability of the grand coalition (GC), i.e., the coalition of all users, is studied. Transmitter and receiver cooperation in an interference channel (IC) are studied as illustrative cooperative models to determine the stable coalitions for both flexible (transferable) and fixed (non-transferable) apportioning schemes. It is shown that the stable sum-rate optimal coalition when only receivers cooperate by jointly decoding (transferable) is the GC. The stability of the GC depends on the detector when receivers cooperate using linear multiuser detectors (non-transferable). Transmitter cooperation is studied assuming that all receivers cooperate perfectly and that users outside a coalition act as jammers. The stability of the GC is studied for both the case of perfectly cooperating transmitters (transferrable) and under a partial decode-and-forward strategy (non-transferable). In both cases, the stability is shown to depend on the channel gains and the transmitter jamming strengths.
From formal proofs to mathematical proofs: a safe, incremental way for building in first-order decision procedures
Venue: arXiv cs.LO 2008
Year: 2008

We investigate here a new version of the Calculus of Inductive Constructions (CIC) on which the proof assistant Coq is based: the Calculus of Congruent Inductive Constructions, which truly extends CIC by building in arbitrary first-order decision procedures: deduction is still in charge of the CIC kernel, while computation is outsourced to dedicated first-order decision procedures that can be taken from the shelves provided they deliver a proof certificate. The soundness of the whole system becomes an incremental property following from the soundness of the certificate checkers and that of the kernel. A detailed example shows that the resulting style of proofs becomes closer to that of the working mathematician.