OpenRaiser/Intern-Atlas huggingface dataset:
Dimensionally Distributed Learning: Models and Algorithm
Venue: arXiv cs.IT 2008
Year: 2008

This paper introduces a framework for regression with dimensionally distributed data with a fusion center. A cooperative learning algorithm, the iterative conditional expectation algorithm (ICEA), is designed within this framework. The algorithm can effectively discover linear combinations of individual estimators trained by each agent without transferring and storing large amount of data amongst the agents and the fusion center. The convergence of ICEA is explored. Specifically, for a two agent system, each complete round of ICEA is guaranteed to be a non-expansive map on the function space of each agent. The advantages and limitations of ICEA are also discussed for data sets with various distributions and various hidden rules. Moreover, several techniques are also designed to leverage the algorithm to effectively learn more complex hidden rules that are not linearly decomposable.
Energy-Efficient Resource Allocation in Multiuser MIMO Systems: A Game-Theoretic Framework
Venue: arXiv cs.IT 2008
Year: 2008

This paper focuses on the cross-layer issue of resource allocation for energy efficiency in the uplink of a multiuser MIMO wireless communication system. Assuming that all of the transmitters and the uplink receiver are equipped with multiple antennas, the situation considered is that in which each terminal is allowed to vary its transmit power, beamforming vector, and uplink receiver in order to maximize its own utility, which is defined as the ratio of data throughput to transmit power; the case in which non-linear interference cancellation is used at the receiver is also investigated. Applying a game-theoretic formulation, several non-cooperative games for utility maximization are thus formulated, and their performance is compared in terms of achieved average utility, achieved average SINR and average transmit power at the Nash equilibrium. Numerical results show that the use of the proposed cross-layer resource allocation policies brings remarkable advantages to the network performance.
When, why and how to test spreadsheets
Venue: arXiv cs.SE 2008
Year: 2008

Testing is a vital part of software development, and spreadsheets are like any other software in this respect. This paper discusses the testing of spreadsheets in the light of one practitioner's experience. It considers the concept of software testing and how it differs from reviewing, and describes when it might take place. Different types of testing are described, and some techniques for performing them presented. Some of the commonly encountered problems are discussed.
TuLiPA: Towards a Multi-Formalism Parsing Environment for Grammar Engineering
Venue: arXiv cs.CL 2008
Year: 2008

In this paper, we present an open-source parsing environment (Tuebingen Linguistic Parsing Architecture, TuLiPA) which uses Range Concatenation Grammar (RCG) as a pivot formalism, thus opening the way to the parsing of several mildly context-sensitive formalisms. This environment currently supports tree-based grammars (namely Tree-Adjoining Grammars, TAG) and Multi-Component Tree-Adjoining Grammars with Tree Tuples (TT-MCTAG)) and allows computation not only of syntactic structures, but also of the corresponding semantic representations. It is used for the development of a tree-based grammar for German.
An adaptive embedded architecture for real-time Particle Image Velocimetry algorithms
Venue: arXiv cs.AR 2008
Year: 2008

Particle Image Velocimetry (PIV) is a method of im-aging and analysing fields of flows. The PIV tech-niques compute and display all the motion vectors of the field in a resulting image. Speeds more than thou-sand vectors per second can be required, each speed being environment-dependent. Essence of this work is to propose an adaptive FPGA-based system for real-time PIV algorithms. The proposed structure is ge-neric so that this unique structure can be re-used for any PIV applications that uses the cross-correlation technique. The major structure remains unchanged, adaptations only concern the number of processing operations. The required speed (corresponding to the number of vector per second) is obtained thanks to a parallel processing strategy. The image processing designer duplicates the processing modules to distrib-ute the operations. The result is a FPGA-based archi-tecture, which is easily adapted to algorithm specifica-tions without any hardware requirement. The design flow is fast and reliable.
Interface Matching and Combining Techniques for Services Integration
Venue: arXiv cs.OS 2008
Year: 2008

The development of many highly dynamic environments, like pervasive environments, introduces the possibility to use geographically close-related services. Dynamically integrating and unintegrating these services in running applications is a key challenge for this use. In this article, we classify service integration issues according to interfaces exported by services and internal combining techniques. We also propose a contextual integration service, IntegServ, and an interface, Integrable, for developing services.
Square Complex Orthogonal Designs with Low PAPR and Signaling Complexity
Venue: arXiv cs.IT 2008
Year: 2008

Space-Time Block Codes from square complex orthogonal designs (SCOD) have been extensively studied and most of the existing SCODs contain large number of zero. The zeros in the designs result in high peak-to-average power ratio (PAPR) and also impose a severe constraint on hardware implementation of the code when turning off some of the transmitting antennas whenever a zero is transmitted. Recently, rate 1/2 SCODs with no zero entry have been reported for 8 transmit antennas. In this paper, SCODs with no zero entry for $2^a$ transmit antennas whenever $a+1$ is a power of 2, are constructed which includes the 8 transmit antennas case as a special case. More generally, for arbitrary values of $a$, explicit construction of $2^a\times 2^a$ rate $\frac{a+1}{2^a}$ SCODs with the ratio of number of zero entries to the total number of entries equal to $1-\frac{a+1}{2^a}2^{\lfloor log_2(\frac{2^a}{a+1}) \rfloor}$ is reported, whereas for standard known constructions, the ratio is $1-\frac{a+1}{2^a}$. The codes presented do not result in increased signaling complexity. Simulation results show that the codes constructed in this paper outperform the codes using the standard construction under peak power constraint while performing the same under average power constraint.
Linear Coloring and Linear Graphs
Venue: arXiv cs.DM 2008
Year: 2008

Motivated by the definition of linear coloring on simplicial complexes, recently introduced in the context of algebraic topology \cite{Civan}, and the framework through which it was studied, we introduce the linear coloring on graphs. We provide an upper bound for the chromatic number $χ(G)$, for any graph $G$, and show that $G$ can be linearly colored in polynomial time by proposing a simple linear coloring algorithm. Based on these results, we define a new class of perfect graphs, which we call co-linear graphs, and study their complement graphs, namely linear graphs. The linear coloring of a graph $G$ is a vertex coloring such that two vertices can be assigned the same color, if their corresponding clique sets are associated by the set inclusion relation (a clique set of a vertex $u$ is the set of all maximal cliques containing $u$); the linear chromatic number $\mathcalλ(G)$ of $G$ is the least integer $k$ for which $G$ admits a linear coloring with $k$ colors. We show that linear graphs are those graphs $G$ for which the linear chromatic number achieves its theoretical lower bound in every induced subgraph of $G$. We prove inclusion relations between these two classes of graphs and other subclasses of chordal and co-chordal graphs, and also study the structure of the forbidden induced subgraphs of the class of linear graphs.
Analisis Kinerja Sistem Cluster Terhadapa Aplikasi Simulasi Dinamika Molekular NAMD Memanfaatkan Pustaka CHARM++
Venue: arXiv cs.DC 2008
Year: 2008

Tingkat kompleksitas dari program simulasi dinamika molekular membutuhkan mesin pemroses dengan kemampuan yang sangat besar. Mesin-mesin paralel terbukti memiliki potensi untuk menjawab tantangan komputasi ini. Untuk memanfaatkan potensi ini secara maksimal, diperlukan suatu program paralel dengan tingkat efisiensi, efektifitas, skalabilitas, dan ekstensibilitas yang maksimal pula. Program NAMD yang dibahas pada penulisan ini dianggap mampu untuk memenuhi semua kriteria yang diinginkan. Program ini dirancang dengan mengimplementasikan pustaka Charm++ untuk pembagian tugas perhitungan secara paralel. NAMD memiliki sistem automatic load balancing secara periodik yang cerdas, sehingga dapat memaksimalkan penggunaan kemampuan mesin yang tersedia. Program ini juga dirancang secara modular, sehingga dapat dimodifikasi dan ditambah dengan sangat mudah. NAMD menggunakan banyak kombinasi algoritma perhitungan dan tehnik-tehnik numerik lainnya dalam melakukan tugasnya. NAMD 2.5 mengimplementasikan semua tehnik dan persamaan perhitungan yang digunakan dalam dunia simulasi dinamika molekular saat ini. NAMD dapat berjalan diatas berbagai mesin paralel termasuk arsitektur cluster, dengan hasil speedup yang mengejutkan. Tulisan ini akan menjelaskan dan membuktikan kemampuan NAMD secara paralel diatas lima buah mesin cluster. Penulisan ini juga akan memaparkan kinerja NAMD pada beberapa.
Accelerated Option Pricing in Multiple Scenarios
Venue: arXiv cs.CE 2008
Year: 2008

This paper covers a massive acceleration of Monte-Carlo based pricing method for financial products and financial derivatives. The method is applicable in risk management settings, where a financial product has to be priced under a number of potential future scenarios. Instead of starting a separate nested Monte Carlo simulation for each scenario under consideration, the new method covers the utilization of very few representative nested simulations and estimating the product prices at each scenario by a smoothing method based on the state-space. This smoothing technique can be e.g. non-parametric regression or kernel smoothing.
Why Does a Kronecker Model Result in Misleading Capacity Estimates?
Venue: arXiv cs.IT 2008
Year: 2008

Many recent works that study the performance of multi-input multi-output (MIMO) systems in practice assume a Kronecker model where the variances of the channel entries, upon decomposition on to the transmit and the receive eigen-bases, admit a separable form. Measurement campaigns, however, show that the Kronecker model results in poor estimates for capacity. Motivated by these observations, a channel model that does not impose a separable structure has been recently proposed and shown to fit the capacity of measured channels better. In this work, we show that this recently proposed modeling framework can be viewed as a natural consequence of channel decomposition on to its canonical coordinates, the transmit and/or the receive eigen-bases. Using tools from random matrix theory, we then establish the theoretical basis behind the Kronecker mismatch at the low- and the high-SNR extremes: 1) Sparsity of the dominant statistical degrees of freedom (DoF) in the true channel at the low-SNR extreme, and 2) Non-regularity of the sparsity structure (disparities in the distribution of the DoF across the rows and the columns) at the high-SNR extreme.
Eigenvalue bounds, spectral partitioning, and metrical deformations via flows
Venue: arXiv cs.DS 2008
Year: 2008

We present a new method for upper bounding the second eigenvalue of the Laplacian of graphs. Our approach uses multi-commodity flows to deform the geometry of the graph; we embed the resulting metric into Euclidean space to recover a bound on the Rayleigh quotient. Using this, we show that every $n$-vertex graph of genus $g$ and maximum degree $d$ satisfies $λ_2(G) = O((g+1)^3 d/n)$. This recovers the $O(d/n)$ bound of Spielman and Teng for planar graphs, and compares to Kelner's bound of $O((g+1) poly(d)/n)$, but our proof does not make use of conformal mappings or circle packings. We are thus able to extend this to resolve positively a conjecture of Spielman and Teng, by proving that $λ_2(G) = O(d h^6 \log h/n)$ whenever $G$ is $K_h$-minor free. This shows, in particular, that spectral partitioning can be used to recover $O(\sqrt{n})$-sized separators in bounded degree graphs that exclude a fixed minor. We extend this further by obtaining nearly optimal bounds on $λ_2$ for graphs which exclude small-depth minors in the sense of Plotkin, Rao, and Smith. Consequently, we show that spectral algorithms find small separators in a general class of geometric graphs. Moreover, while the standard "sweep" algorithm applied to the second eigenvector may fail to find good quotient cuts in graphs of unbounded degree, our approach produces a vector that works for arbitrary graphs. This yields an alternate proof of the result of Alon, Seymour, and Thomas that every excluded-minor family of graphs has $O(\sqrt{n})$-node balanced separators.
A Public Key Block Cipher Based on Multivariate Quadratic Quasigroups
Venue: arXiv cs.CR 2008
Year: 2008

We have designed a new class of public key algorithms based on quasigroup string transformations using a specific class of quasigroups called multivariate quadratic quasigroups (MQQ). Our public key algorithm is a bijective mapping, it does not perform message expansions and can be used both for encryption and signatures. The public key consist of n quadratic polynomials with n variables where n=140, 160, ... . A particular characteristic of our public key algorithm is that it is very fast and highly parallelizable. More concretely, it has the speed of a typical modern symmetric block cipher - the reason for the phrase "A Public Key Block Cipher" in the title of this paper. Namely the reference C code for the 160-bit variant of the algorithm performs decryption in less than 11,000 cycles (on Intel Core 2 Duo -- using only one processor core), and around 6,000 cycles using two CPU cores and OpenMP 2.0 library. However, implemented in Xilinx Virtex-5 FPGA that is running on 249.4 MHz it achieves decryption throughput of 399 Mbps, and implemented on four Xilinx Virtex-5 chips that are running on 276.7 MHz it achieves encryption throughput of 44.27 Gbps. Compared to fastest RSA implementations on similar FPGA platforms, MQQ algorithm is more than 10,000 times faster.
One shot schemes for decentralized quickest change detection
Venue: arXiv cs.IT 2008
Year: 2008

This work considers the problem of quickest detection with N distributed sensors that receive continuous sequential observations from the environment. These sensors employ cumulative sum (CUSUM) strategies and communicate to a central fusion center by one shot schemes. One shot schemes are schemes in which the sensors communicate with the fusion center only once, after which they must signal a detection. The communication is clearly asynchronous and the case is considered in which the fusion center employs a minimal strategy, which means that it declares an alarm when the first communication takes place. It is assumed that the observations received at the sensors are independent and that the time points at which the appearance of a signal can take place are different. It is shown that there is no loss of performance of one shot schemes as compared to the centralized case in an extended Lorden min-max sense, since the minimum of N CUSUMs is asymptotically optimal as the mean time between false alarms increases without bound.
Computing the nucleolus of weighted voting games
Venue: arXiv cs.GT 2008
Year: 2008

Weighted voting games (WVG) are coalitional games in which an agent's contribution to a coalition is given by his it weight, and a coalition wins if its total weight meets or exceeds a given quota. These games model decision-making in political bodies as well as collaboration and surplus division in multiagent domains. The computational complexity of various solution concepts for weighted voting games received a lot of attention in recent years. In particular, Elkind et al.(2007) studied the complexity of stability-related solution concepts in WVGs, namely, of the core, the least core, and the nucleolus. While they have completely characterized the algorithmic complexity of the core and the least core, for the nucleolus they have only provided an NP-hardness result. In this paper, we solve an open problem posed by Elkind et al. by showing that the nucleolus of WVGs, and, more generally, k-vector weighted voting games with fixed k, can be computed in pseudopolynomial time, i.e., there exists an algorithm that correctly computes the nucleolus and runs in time polynomial in the number of players and the maximum weight. In doing so, we propose a general framework for computing the nucleolus, which may be applicable to a wider of class of games.
Exhaustible sets in higher-type computation
Venue: arXiv cs.LO 2008
Year: 2008

We say that a set is exhaustible if it admits algorithmic universal quantification for continuous predicates in finite time, and searchable if there is an algorithm that, given any continuous predicate, either selects an element for which the predicate holds or else tells there is no example. The Cantor space of infinite sequences of binary digits is known to be searchable. Searchable sets are exhaustible, and we show that the converse also holds for sets of hereditarily total elements in the hierarchy of continuous functionals; moreover, a selection functional can be constructed uniformly from a quantification functional. We prove that searchable sets are closed under intersections with decidable sets, and under the formation of computable images and of finite and countably infinite products. This is related to the fact, established here, that exhaustible sets are topologically compact. We obtain a complete description of exhaustible total sets by developing a computational version of a topological Arzela--Ascoli type characterization of compact subsets of function spaces. We also show that, in the non-empty case, they are precisely the computable images of the Cantor space. The emphasis of this paper is on the theory of exhaustible and searchable sets, but we also briefly sketch applications.
Executable Set Theory and Arithmetic Encodings in Prolog
Venue: arXiv cs.LO 2008
Year: 2008

The paper is organized as a self-contained literate Prolog program that implements elements of an executable finite set theory with focus on combinatorial generation and arithmetic encodings. The complete Prolog code is available at http://logic.csci.unt.edu/tarau/research/2008/pHFS.zip . First, ranking and unranking functions for some "mathematically elegant" data types in the universe of Hereditarily Finite Sets with Urelements are provided, resulting in arithmetic encodings for powersets, hypergraphs, ordinals and choice functions. After implementing a digraph representation of Hereditarily Finite Sets we define {\em decoration functions} that can recover well-founded sets from encodings of their associated acyclic digraphs. We conclude with an encoding of arbitrary digraphs and discuss a concept of duality induced by the set membership relation. In the process, we uncover the surprising possibility of internally sharing isomorphic objects, independently of their language level types and meanings.
Coinductive big-step operational semantics
Venue: arXiv cs.PL 2008
Year: 2008

Using a call-by-value functional language as an example, this article illustrates the use of coinductive definitions and proofs in big-step operational semantics, enabling it to describe diverging evaluations in addition to terminating evaluations. We formalize the connections between the coinductive big-step semantics and the standard small-step semantics, proving that both semantics are equivalent. We then study the use of coinductive big-step semantics in proofs of type soundness and proofs of semantic preservation for compilers. A methodological originality of this paper is that all results have been proved using the Coq proof assistant. We explain the proof-theoretic presentation of coinductive definitions and proofs offered by Coq, and show that it facilitates the discovery and the presentation of the results.
Weighted distance transforms generalized to modules and their computation on point lattices
Venue: arXiv cs.DM 2008
Year: 2008

This paper presents the generalization of weighted distances to modules and their computation through the chamfer algorithm on general point lattices. The first part is dedicated to formalization of definitions and properties (distance, metric, norm) of weighted distances on modules. It resumes tools found in literature to express the weighted distance of any point of a module and to compute optimal weights in the general case to get rotation invariant distances. The second part of this paper proves that, for any point lattice, the sequential two-scan chamfer algorithm produces correct distance maps. Finally, the definitions and computation of weighted distances are applied to the face-centered cubic (FCC) and body-centered cubic (BCC) grids.
9-variable Boolean Functions with Nonlinearity 242 in the Generalized Rotation Class
Venue: arXiv cs.CR 2008
Year: 2008

In 2006, 9-variable Boolean functions having nonlinearity 241, which is strictly greater than the bent concatenation bound of 240, have been discovered in the class of Rotation Symmetric Boolean Functions (RSBFs) by Kavut, Maitra and Yucel. To improve this nonlinearity result, we have firstly defined some subsets of the n-variable Boolean functions as the "generalized classes of k-RSBFs and k-DSBFs (k-Dihedral Symmetric Boolean Functions)", where k is a positive integer dividing n and k-RSBFs is a subset of l-RSBFs if k < l. Secondly, utilizing the steepest-descent like iterative heuristic search algorithm used previously to identify the 9-variable RSBFs with nonlinearity 241, we have made a search within the classes of 3-RSBFs and 3-DSBFs. The search has accomplished to find 9-variable Boolean functions with nonlinearity 242 in both of these classes. It should be emphasized that although the class of 3-RSBFs contains functions with nonlinearity 242; 1-RSBFs or simply RSBFs, which is a subset of 3-RSBFs, does not contain any. This result also shows that the covering radius of the first order Reed-Muller code R(1, 9) is at least equal to 242. Thirdly, motivated by the fact that RSBFs are invariant under a special permutation of the input vector, we have classified all possible permutations up to the linear equivalence of Boolean functions that are invariant under those permutations. Specifically, for 9-variable Boolean functions, 9! possible permutations are classified into 30 classes; and the search algorithm identifies some of these classes as "rich". The rich classes yield new Boolean functions with nonlinearity 242 having different autocorrelation spectra from those of the functions found in the generalized 3-RSBF and 3-DSBF classes.