OpenRaiser/Intern-Atlas huggingface dataset:
On the contribution of backward jumps to instruction sequence expressiveness
Venue: arXiv cs.LO 2010
Year: 2010

We investigate the expressiveness of backward jumps in a framework of formalized sequential programming called program algebra. We show that - if expressiveness is measured in terms of the computability of partial Boolean functions - then backward jumps are superfluous. If we, however, want to prevent explosion of the length of programs, then backward jumps are essential.
Methods for the Reconstruction of Parallel Turbo Codes
Venue: arXiv cs.IT 2010
Year: 2010

We present two new algorithms for the reconstruction of turbo codes from a noisy intercepted bitstream. With these algorithms, we were able to reconstruct various turbo codes with realistic parameter sizes. To the best of our knowledge, these are the first algorithms able to recover the whole permutation of a turbo code in the presence of high noise levels.
Asymptotic Optimality of Antidictionary Codes
Venue: arXiv cs.IT 2010
Year: 2010

An antidictionary code is a lossless compression algorithm using an antidictionary which is a set of minimal words that do not occur as substrings in an input string. The code was proposed by Crochemore et al. in 2000, and its asymptotic optimality has been proved with respect to only a specific information source, called balanced binary source that is a binary Markov source in which a state transition occurs with probability 1/2 or 1. In this paper, we prove the optimality of both static and dynamic antidictionary codes with respect to a stationary ergodic Markov source on finite alphabet such that a state transition occurs with probability $p (0 < p \leq 1)$.
Métodos para la Selección y el Ajuste de Características en el Problema de la Detección de Spam
Venue: arXiv cs.IR 2010
Year: 2010

The email is used daily by millions of people to communicate around the globe and it is a mission-critical application for many businesses. Over the last decade, unsolicited bulk email has become a major problem for email users. An overwhelming amount of spam is flowing into users' mailboxes daily. In 2004, an estimated 62% of all email was attributed to spam. Spam is not only frustrating for most email users, it strains the IT infrastructure of organizations and costs businesses billions of dollars in lost productivity. In recent years, spam has evolved from an annoyance into a serious security threat, and is now a prime medium for phishing of sensitive information, as well the spread of malicious software. This work presents a first approach to attack the spam problem. We propose an algorithm that will improve a classifier's results by adjusting its training set data. It improves the document's vocabulary representation by detecting good topic descriptors and discriminators.
The dilation of the Delaunay triangulation is greater than π/2
Venue: arXiv cs.CG 2010
Year: 2010

Consider the Delaunay triangulation T of a set P of points in the plane as a Euclidean graph, in which the weight of every edge is its length. It has long been conjectured that the dilation in T of any pair p, p \in P, which is the ratio of the length of the shortest path from p to p' in T over the Euclidean distance ||pp'||, can be at most π/2 \approx 1.5708. In this paper, we show how to construct point sets in convex position with dilation > 1.5810 and in general position with dilation > 1.5846. Furthermore, we show that a sufficiently large set of points drawn independently from any distribution will in the limit approach the worst-case dilation for that distribution.
Markov Lemma for Countable Alphabets
Venue: arXiv cs.IT 2010
Year: 2010

Strong typicality and the Markov lemma have been used in the proofs of several multiterminal source coding theorems. Since these two tools can be applied to finite alphabets only, the results proved by them are subject to the same limitation. Recently, a new notion of typicality, namely unified typicality, has been defined. It can be applied to both finite or countably infinite alphabets, and it retains the asymptotic equipartition property and the structural properties of strong typicality. In this paper, unified typicality is used to derive a version of the Markov lemma which works on both finite or countably infinite alphabets so that many results in multiterminal source coding can readily be extended. Furthermore, a simple way to verify whether some sequences are jointly typical is shown.
One-Shot Capacity of Discrete Channels
Venue: arXiv cs.IT 2010
Year: 2010

Shannon defined channel capacity as the highest rate at which there exists a sequence of codes of block length $n$ such that the error probability goes to zero as $n$ goes to infinity. In this definition, it is implicit that the block length, which can be viewed as the number of available channel uses, is unlimited. This is not the case when the transmission power must be concentrated on a single transmission, most notably in military scenarios with adversarial conditions or delay-tolerant networks with random short encounters. A natural question arises: how much information can we transmit in a single use of the channel? We give a precise characterization of the one-shot capacity of discrete channels, defined as the maximum number of bits that can be transmitted in a single use of a channel with an error probability that does not exceed a prescribed value. This capacity definition is shown to be useful and significantly different from the zero-error problem statement.
A domain-theoretic investigation of posets of sub-sigma-algebras (extended abstract)
Venue: arXiv cs.LO 2010
Year: 2010

Given a measurable space (X, M) there is a (Galois) connection between sub-sigma-algebras of M and equivalence relations on X. On the other hand equivalence relations on X are closely related to congruences on stochastic relations. In recent work, Doberkat has examined lattice properties of posets of congruences on a stochastic relation and motivated a domain-theoretic investigation of these ordered sets. Here we show that the posets of sub-sigma-algebras of a measurable space do not enjoy desired domain-theoretic properties and that our counterexamples can be applied to the set of smooth equivalence relations on an analytic space, thus giving a rather unsatisfactory answer to Doberkat's question.
Computation with Advice
Venue: arXiv cs.LO 2010
Year: 2010

Computation with advice is suggested as generalization of both computation with discrete advice and Type-2 Nondeterminism. Several embodiments of the generic concept are discussed, and the close connection to Weihrauch reducibility is pointed out. As a novel concept, computability with random advice is studied; which corresponds to correct solutions being guessable with positive probability. In the framework of computation with advice, it is possible to define computational complexity for certain concepts of hypercomputation. Finally, some examples are given which illuminate the interplay of uniform and non-uniform techniques in order to investigate both computability with advice and the Weihrauch lattice.
The descriptive set-theoretic complexity of the set of points of continuity of a multi-valued function (Extended Abstract)
Venue: arXiv cs.CC 2010
Year: 2010

In this article we treat a notion of continuity for a multi-valued function F and we compute the descriptive set-theoretic complexity of the set of all x for which F is continuous at x. We give conditions under which the latter set is either a G_δset or the countable union of G_δsets. Also we provide a counterexample which shows that the latter result is optimum under the same conditions. Moreover we prove that those conditions are necessary in order to obtain that the set of points of continuity of F is Borel i.e., we show that if we drop some of the previous conditions then there is a multi-valued function F whose graph is a Borel set and the set of points of continuity of F is not a Borel set. Finally we give some analogue results regarding a stronger notion of continuity for a multi-valued function. This article is motivated by a question of M. Ziegler in "Real Computation with Least Discrete Advice: A Complexity Theory of Nonuniform Computability with Applications to Linear Algebra", (submitted).
A Local to Global Principle for the Complexity of Riemann Mappings (Extended Abstract)
Venue: arXiv cs.CC 2010
Year: 2010

We show that the computational complexity of Riemann mappings can be bounded by the complexity needed to compute conformal mappings locally at boundary points. As a consequence we get first formally proven upper bounds for Schwarz-Christoffel mappings and, more generally, Riemann mappings of domains with piecewise analytic boundaries.
A Rigorous Extension of the Schönhage-Strassen Integer Multiplication Algorithm Using Complex Interval Arithmetic
Venue: arXiv cs.NA 2010
Year: 2010

Multiplication of n-digit integers by long multiplication requires O(n^2) operations and can be time-consuming. In 1970 A. Schoenhage and V. Strassen published an algorithm capable of performing the task with only O(n log(n)) arithmetic operations over the complex field C; naturally, finite-precision approximations to C are used and rounding errors need to be accounted for. Overall, using variable-precision fixed-point numbers, this results in an O(n(log(n))^(2+Epsilon))-time algorithm. However, to make this algorithm more efficient and practical we need to make use of hardware-based floating-point numbers. How do we deal with rounding errors? and how do we determine the limits of the fixed-precision hardware? Our solution is to use interval arithmetic to guarantee the correctness of results and determine the hardware's limits. We examine the feasibility of this approach and are able to report that 75,000-digit base-256 integers can be handled using double-precision containment sets. This clearly demonstrates that our approach has practical potential; however, at this stage, our implementation does not yet compete with commercial ones, but we are able to demonstrate the feasibility of this technique.
Complete Multi-Representations of Sets in a Computable Measure Space
Venue: arXiv cs.CC 2010
Year: 2010

In a recent paper, two multi-representations for the measurable sets in a computable measure space have been introduced, which prove to be topologically complete w.r.t. certain topological properties. In this contribution, we show them recursively complete w.r.t. computability of measure and set-theoretical operations.
Reconstruction of Causal Networks by Set Covering
Venue: arXiv cs.DS 2010
Year: 2010

We present a method for the reconstruction of networks, based on the order of nodes visited by a stochastic branching process. Our algorithm reconstructs a network of minimal size that ensures consistency with the data. Crucially, we show that global consistency with the data can be achieved through purely local considerations, inferring the neighbourhood of each node in turn. The optimisation problem solved for each individual node can be reduced to a Set Covering Problem, which is known to be NP-hard but can be approximated well in practice. We then extend our approach to account for noisy data, based on the Minimum Description Length principle. We demonstrate our algorithms on synthetic data, generated by an SIR-like epidemiological model.
Simulink based VoIP Analysis
Venue: arXiv cs.NI 2010
Year: 2010

Voice communication over internet not be possible without a reliable data network, this was first available when distributed network topologies were used in conjunction with data packets. Early network used single centre node network in which a single workstation (Server) is responsible for the communication. This posed problems as if there was a fault with the centre node, (workstation) nothing would work. This problem was solved by the distributed system in which reliability increases by spreading the load between many nodes. The idea of packet switching & distributed network were combined, this combination were increased reliability, speed & responsible for voice communication over internet, Voice-over-IP (VoIP)These data packets travel through a packet-switched network such as the Internet and arrive at their destination where they are decompressed using a compatible Codec (audio coder/decoder) and converted back to analogue audio. This paper deals with the Simulink architecture for VoIP network.
To Optimally Design Microstrip Nonuniform Transmission Lines as Lowpass Filters
Venue: arXiv cs.OH 2010
Year: 2010

A method is proposed to optimally design the Microstrip Nonuniform Transmission Line (MNTLs) as lowpass filters. Some electrical and physical restrictions are used to design MNTLs. To optimally design the MNTLs, their strip width is expanded as truncated Fourier series, firstly. Then, the optimum values of the coefficients of the series are obtained through an optimization approach. The performance of the proposed structure is studied by design and fabrication of two lowpass filters of cutoff frequency 2.0 GHz.
A Study on the Interactive "HOPSCOTCH" Game for the Children Using Computer Music Techniques
Venue: arXiv cs.SD 2010
Year: 2010

"Hopscotch" is a world-wide game for children to play since the times in the ancient Roman Empire and China. Here we present a study mainly focused on the research and discussion of the application on the children's well-know edutainment via the physical interactive design to provide the sensing of the times for the conventional hopscotch, which is a new type of experiment for the technology aided edutainment. The innovated hopscotch music game involves the sound samples of various animals and the characters of cartoon, and the algorithmic composition via the development of the music technology based interactive game, to gradually make the children perceive the world of digits, sound, and music. It can guide the growing children's personality and character from disorder into clarity. Furthermore, the traditional teaching materials can be improved via the implementation of the electrical sensing devices, electrical I/O module, and the computer music program Max/MSP, to integrate the interactive computer music with the interactive and immersive soundscapes composition, and the teaching tool with educational gaming is completely accomplished eventually.
On Achievable Rate Regions for Half-Duplex Causal Cognitive Radio Channels
Venue: arXiv cs.IT 2010
Year: 2010

Coding for the causal cognitive radio channel, with the cognitive source subjected to a half-duplex constraint, is studied. A discrete memoryless channel model incorporating the half-duplex constraint is presented, and a new achievable rate region is derived for this channel. It is proved that this rate region contains the previously known causal achievable rate region of \cite{Devroye06} for Gaussian channels.
Mathematical Modeling of Competition in Sponsored Search Market
Venue: arXiv cs.GT 2010
Year: 2010

Sponsored search mechanisms have drawn much attention from both academic community and industry in recent years since the seminal papers of [13] and [14]. However, most of the existing literature concentrates on the mechanism design and analysis within the scope of only one search engine in the market. In this paper we propose a mathematical framework for modeling the interaction of publishers, advertisers and end users in a competitive market. We first consider the monopoly market model and provide optimal solutions for both ex ante and ex post cases, which represents the long-term and short-term revenues of search engines respectively. We then analyze the strategic behaviors of end users and advertisers under duopoly and prove the existence of equilibrium for both search engines to co-exist from ex-post perspective. To show the more general ex ante results, we carry out extensive simulations under different parameter settings. Our analysis and observation in this work can provide useful insight in regulating the sponsored search market and protecting the interests of advertisers and end users.
Rasch-based high-dimensionality data reduction and class prediction with applications to microarray gene expression data
Venue: arXiv cs.AI 2010
Year: 2010

Class prediction is an important application of microarray gene expression data analysis. The high-dimensionality of microarray data, where number of genes (variables) is very large compared to the number of samples (obser- vations), makes the application of many prediction techniques (e.g., logistic regression, discriminant analysis) difficult. An efficient way to solve this prob- lem is by using dimension reduction statistical techniques. Increasingly used in psychology-related applications, Rasch model (RM) provides an appealing framework for handling high-dimensional microarray data. In this paper, we study the potential of RM-based modeling in dimensionality reduction with binarized microarray gene expression data and investigate its prediction ac- curacy in the context of class prediction using linear discriminant analysis. Two different publicly available microarray data sets are used to illustrate a general framework of the approach. Performance of the proposed method is assessed by re-randomization scheme using principal component analysis (PCA) as a benchmark method. Our results show that RM-based dimension reduction is as effective as PCA-based dimension reduction. The method is general and can be applied to the other high-dimensional data problems.
Youpi, a Web-based Astronomical Image Processing Pipeline
Venue: arXiv cs.DC 2010
Year: 2010

Youpi stands for "YOUpi is your processing PIpeline". It is a portable, easy to use web application providing high level functionalities to perform data reduction on scientific FITS images. It is built on top of open source processing tools that are released to the community by Terapix, in order to organize your data on a computer cluster, to manage your processing jobs in real time and to facilitate teamwork by allowing fine-grain sharing of results and data. On the server side, Youpi is written in the Python programming language and uses the Django web framework. On the client side, Ajax techniques are used along with the Prototype and script.aculo.us Javascript librairies.
On the hardness of distance oracle for sparse graph
Venue: arXiv cs.DS 2010
Year: 2010

In this paper we show that set-intersection is harder than distance oracle on sparse graphs. Given a collection of total size n which consists of m sets drawn from universe U, the set-intersection problem is to build a data structure which can answer whether two sets have any intersection. A distance oracle is a data structure which can answer distance queries on a given graph. We show that if one can build distance oracle for sparse graph G=(V,E), which requires s(|V|,|E|) space and answers a (2-ε,c)-approximate distance query in time t(|V|,|E|) where (2-ε) is a multiplicative error and c is a constant additive error, then, set-intersection can be solved in t(m+|U|,n) time using s(m+|U|,n) space.
Predictive PAC learnability: a paradigm for learning from exchangeable input data
Venue: arXiv cs.LG 2010
Year: 2010

Exchangeable random variables form an important and well-studied generalization of i.i.d. variables, however simple examples show that no nontrivial concept or function classes are PAC learnable under general exchangeable data inputs $X_1,X_2,\ldots$. Inspired by the work of Berti and Rigo on a Glivenko--Cantelli theorem for exchangeable inputs, we propose a new paradigm, adequate for learning from exchangeable data: predictive PAC learnability. A learning rule $\mathcal L$ for a function class $\mathscr F$ is predictive PAC if for every $\e,δ>0$ and each function $f\in {\mathscr F}$, whenever $\absσ\geq s(δ,\e)$, we have with confidence $1-δ$ that the expected difference between $f(X_{n+1})$ and the image of $f\vertσ$ under $\mathcal L$ does not exceed $\e$ conditionally on $X_1,X_2,\ldots,X_n$. Thus, instead of learning the function $f$ as such, we are learning to a given accuracy $\e$ the predictive behaviour of $f$ at the future points $X_i(ω)$, $i>n$ of the sample path. Using de Finetti's theorem, we show that if a universally separable function class $\mathscr F$ is distribution-free PAC learnable under i.i.d. inputs, then it is distribution-free predictive PAC learnable under exchangeable inputs, with a slightly worse sample complexity.
The diversity-multiplexing tradeoff of the symmetric MIMO 2-user interference channel
Venue: arXiv cs.IT 2010
Year: 2010

The fundamental diversity-multiplexing tradeoff (DMT) of the quasi-static fading, symmetric $2$-user MIMO interference channel (IC) with channel state information at the transmitters (CSIT) and a short term average power constraint is obtained. The general case is considered where the interference-to-noise ratio (INR) at each receiver scales differently from the signal-to-noise ratio (SNR) at the receivers. The achievability of the DMT is proved by showing that a simple Han-Kobayashi coding scheme can achieve a rate region which is within a constant (independent of SNR) number of bits from a set of upper bounds to the capacity region of the IC. In general, only part of the DMT curve with CSIT can be achieved by coding schemes which do not use any CSIT (No-CSIT). A result in this paper establishes a threshold for the INR beyond which the DMT with CSIT coincides with that with No-CSIT. Our result also settles one of the conjectures made in~\cite{EaOlCv}. Furthermore, the fundamental DMT of a class of non-symmetric ICs with No-CSIT is also obtained wherein the two receivers have different numbers of antennas.
SONoMA: A Service Oriented Network Measurement Architecture
Venue: arXiv cs.NI 2010
Year: 2010

To characterize the structure, dynamics and operational state of the Internet it requires distributed measurements. Although in the last decades several systems capable to do this have been created, the easy access of these infrastructures and orchestration of complex measurements is not solved. We propose a system architecture that combines the flexibility of mature network measurement infrastructures such as PlanetLab or ETOMIC with the general accessibility and popularity of public services like Web based bandwidth measurement or traceroute servers. To realize these requirements we developed a multi-layer architecture based on Web Services and the basic principles of SOA, which is a very popular paradigm in distributed business application development. Our approach opens the door to perform complex network measurements, handles heterogeneous measurement devices, automatically stores the results in a public database and protects against malicious users as well. To demonstrate our concept we developed a public prototype system, called SONoMA.
Detecting Coordination Problems in Collaborative Software Development Environments
Venue: arXiv cs.SE 2010
Year: 2010

Software development is rarely an individual effort and generally involves teams of developers collaborating to generate good reliable code. Among the software code there exist technical dependencies that arise from software components using services from other components. The different ways of assigning the design, development, and testing of these software modules to people can cause various coordination problems among them. We claim that the collaboration of the developers, designers and testers must be related to and governed by the technical task structure. These collaboration practices are handled in what we call Socio-Technical Patterns. The TESNA project (Technical Social Network Analysis) we report on in this paper addresses this issue. We propose a method and a tool that a project manager can use in order to detect the socio-technical coordination problems. We test the method and tool in a case study of a small and innovative software product company.