OpenRaiser/Intern-Atlas huggingface dataset:
Concavity of entropy under thinning
Venue: arXiv cs.IT 2009
Year: 2009

Building on the recent work of Johnson (2007) and Yu (2008), we prove that entropy is a concave function with respect to the thinning operation T_a. That is, if X and Y are independent random variables on Z_+ with ultra-log-concave probability mass functions, then H(T_a X+T_{1-a} Y)>= a H(X)+(1-a)H(Y), 0 <= a <= 1, where H denotes the discrete entropy. This is a discrete analogue of the inequality (h denotes the differential entropy) h(sqrt(a) X + sqrt{1-a} Y)>= a h(X)+(1-a) h(Y), 0 <= a <= 1, which holds for continuous X and Y with finite variances and is equivalent to Shannon's entropy power inequality. As a consequence we establish a special case of a conjecture of Shepp and Olkin (1981).
Undirected Graphs of Entanglement 3
Venue: arXiv cs.GT 2009
Year: 2009

Entanglement is a complexity measure of digraphs that origins in fixed-point logics. Its combinatorial purpose is to measure the nested depth of cycles in digraphs. We address the problem of characterizing the structure of graphs of entanglement at most $k$. Only partial results are known so far: digraphs for $k=1$, and undirected graphs for $k=2$. In this paper we investigate the structure of undirected graphs for $k=3$. Our main tool is the so-called \emph{Tutte's decomposition} of 2-connected graphs into cycles and 3-connected components into a tree-like fashion. We shall give necessary conditions on Tutte's tree to be a tree decomposition of a 2-connected graph of entanglement 3.
Opportunistic Multiuser Scheduling in a Three State Markov-modeled Downlink
Venue: arXiv cs.NI 2009
Year: 2009

We consider the downlink of a cellular system and address the problem of multiuser scheduling with partial channel information. In our setting, the channel of each user is modeled by a three-state Markov chain. The scheduler indirectly estimates the channel via accumulated Automatic Repeat Request (ARQ) feedback from the scheduled users and uses this information in future scheduling decisions. Using a Partially Observable Markov Decision Process (POMDP), we formulate a throughput maximization problem that is an extension of our previous work where the channels were modeled using two states. We recall the greedy policy that was shown to be optimal and easy to implement in the two state case and study the implementation structure of the greedy policy in the considered downlink. We classify the system into two types based on the channel statistics and obtain round robin structures for the greedy policy for each system type. We obtain performance bounds for the downlink system using these structures and study the conditions under which the greedy policy is optimal.
Absdet-Pseudo-Codewords and Perm-Pseudo-Codewords: Definitions and Properties
Venue: arXiv cs.IT 2009
Year: 2009

The linear-programming decoding performance of a binary linear code crucially depends on the structure of the fundamental cone of the parity-check matrix that describes the code. Towards a better understanding of fundamental cones and the vectors therein, we introduce the notion of absdet-pseudo-codewords and perm-pseudo-codewords: we give the definitions, we discuss some simple examples, and we list some of their properties.
A Near-Optimal Algorithm for L1-Difference
Venue: arXiv cs.DS 2009
Year: 2009

We give the first L_1-sketching algorithm for integer vectors which produces nearly optimal sized sketches in nearly linear time. This answers the first open problem in the list of open problems from the 2006 IITK Workshop on Algorithms for Data Streams. Specifically, suppose Alice receives a vector x in {-M,...,M}^n and Bob receives y in {-M,...,M}^n, and the two parties share randomness. Each party must output a short sketch of their vector such that a third party can later quickly recover a (1 +/- eps)-approximation to ||x-y||_1 with 2/3 probability given only the sketches. We give a sketching algorithm which produces O(eps^{-2}log(1/eps)log(nM))-bit sketches in O(n*log^2(nM)) time, independent of eps. The previous best known sketching algorithm for L_1 is due to [Feigenbaum et al., SICOMP 2002], which achieved the optimal sketch length of O(eps^{-2}log(nM)) bits but had a running time of O(n*log(nM)/eps^2). Notice that our running time is near-linear for every eps, whereas for sufficiently small values of eps, the running time of the previous algorithm can be as large as quadratic. Like their algorithm, our sketching procedure also yields a small-space, one-pass streaming algorithm which works even if the entries of x,y are given in arbitrary order.
A Distributed Software Architecture for Collaborative Teleoperation based on a VR Platform and Web Application Interoperability
Venue: arXiv cs.HC 2009
Year: 2009

Augmented Reality and Virtual Reality can provide to a Human Operator (HO) a real help to complete complex tasks, such as robot teleoperation and cooperative teleassistance. Using appropriate augmentations, the HO can interact faster, safer and easier with the remote real world. In this paper, we present an extension of an existing distributed software and network architecture for collaborative teleoperation based on networked human-scaled mixed reality and mobile platform. The first teleoperation system was composed by a VR application and a Web application. However the 2 systems cannot be used together and it is impossible to control a distant robot simultaneously. Our goal is to update the teleoperation system to permit a heterogeneous collaborative teleoperation between the 2 platforms. An important feature of this interface is based on different Mobile platforms to control one or many robots.
The equality problem for infinite words generated by primitive morphisms
Venue: arXiv cs.FL 2009
Year: 2009

We study the equality problem for infinite words obtained by iterating morphisms. In particular, we give a practical algorithm to decide whether or not two words generated by primitive morphisms are equal.
A Fundamental Characterization of Stability in Broadcast Queueing Systems
Venue: arXiv cs.NI 2009
Year: 2009

Stability with respect to a given scheduling policy has become an important issue for wireless communication systems, but it is hard to prove in particular scenarios. In this paper two simple conditions for stability in broadcast channels are derived, which are easy to check. Heuristically, the conditions imply that if the queue length in the system becomes large, the rate allocation is always the solution of a weighted sum rate maximization problem. Furthermore, the change of the weight factors between two time slots becomes smaller and the weight factors of the users, whose queues are bounded while the other queues expand, tend to zero. Then it is shown that for any mean arrival rate vector inside the ergodic achievable rate region the system is stable in the strong sense when the given scheduling policy complies with the conditions. In this case the policy is so-called throughput-optimal. Subsequently, some results on the necessity of the presented conditions are provided. Finally, in several application examples it is shown that the results in the paper provide a convenient way to verify the throughput-optimal policies.
Interference Relay Channels - Part I: Transmission Rates
Venue: arXiv cs.IT 2009
Year: 2009

We analyze the performance of a system composed of two interfering point-to-point links where the transmitters can exploit a common relay to improve their individual transmission rate. When the relay uses the amplify-and-forward protocol we prove that it is not always optimal (in some sense defined later on) to exploit all the relay transmit power and derive the corresponding optimal amplification factor. For the case of the decode-and-forward protocol, already investigated in [1], we show that this protocol, through the cooperation degree between each transmitter and the relay, is the only one that naturally introduces a game between the transmitters. For the estimate-and-forward protocol, we derive two rate regions for the general case of discrete interference relay channels (IRCs) and specialize these results to obtain the Gaussian case; these regions correspond to two compression schemes at the relay, having different resolution levels. These schemes are compared analytically in some special cases. All the results mentioned are illustrated by simulations, given in this part, and exploited to study power allocation games in multi-band IRCs in the second part of this two-part paper.
A Methodology for Learning Players' Styles from Game Records
Venue: arXiv cs.AI 2009
Year: 2009

We describe a preliminary investigation into learning a Chess player's style from game records. The method is based on attempting to learn features of a player's individual evaluation function using the method of temporal differences, with the aid of a conventional Chess engine architecture. Some encouraging results were obtained in learning the styles of two recent Chess world champions, and we report on our attempt to use the learnt styles to discriminate between the players from game records by trying to detect who was playing white and who was playing black. We also discuss some limitations of our approach and propose possible directions for future research. The method we have presented may also be applicable to other strategic games, and may even be generalisable to other domains where sequences of agents' actions are recorded.
On Finding Directed Trees with Many Leaves
Venue: arXiv cs.DM 2009
Year: 2009

The Rooted Maximum Leaf Outbranching problem consists in finding a spanning directed tree rooted at some prescribed vertex of a digraph with the maximum number of leaves. Its parameterized version asks if there exists such a tree with at least $k$ leaves. We use the notion of $s-t$ numbering to exhibit combinatorial bounds on the existence of spanning directed trees with many leaves. These combinatorial bounds allow us to produce a constant factor approximation algorithm for finding directed trees with many leaves, whereas the best known approximation algorithm has a $\sqrt{OPT}$-factor. We also show that Rooted Maximum Leaf Outbranching admits a quadratic kernel, improving over the cubic kernel given by Fernau et al.
Fast dynamics in Internet topology: preliminary observations and explanations
Venue: arXiv cs.NI 2009
Year: 2009

By focusing on what can be observed by running traceroute-like measurements at a high frequency from a single monitor to a fixed destination set, we show that the observed view of the topology is constantly evolving at a pace much higher than expected. Repeated measurements discover new IP addresses at a constant rate, for long period of times (up to several months). In order to provide explanations, we study this phenomenon both at the IP, and at the Autonomous System levels. We show that this renewal of IP addresses is partially caused by a BGP routing dynamics, altering paths between existing ASes. Furthermore, we conjecture that an intra AS routing dynamics is another cause of this phenomenon.
A simple algorithm for decoding both errors and erasures of Reed-Solomon codes
Venue: arXiv cs.IT 2009
Year: 2009

A simple algorithm for decoding both errors and erasures of Reed-Solomon codes is described.
Measurement of eDonkey Activity with Distributed Honeypots
Venue: arXiv cs.NI 2009
Year: 2009

Collecting information about user activity in peer-to-peer systems is a key but challenging task. We describe here a distributed platform for doing so on the eDonkey network, relying on a group of honeypot peers which claim to have certain files and log queries they receive for these files. We then conduct some measurements with typical scenarios and use the obtained data to analyze the impact of key parameters like measurement duration, number of honeypots involved, and number of advertised files. This illustrates both the possible uses of our measurement system, and the kind of data one may collect using it.
HybridMiner: Mining Maximal Frequent Itemsets Using Hybrid Database Representation Approach
Venue: arXiv cs.DB 2009
Year: 2009

In this paper we present a novel hybrid (arraybased layout and vertical bitmap layout) database representation approach for mining complete Maximal Frequent Itemset (MFI) on sparse and large datasets. Our work is novel in terms of scalability, item search order and two horizontal and vertical projection techniques. We also present a maximal algorithm using this hybrid database representation approach. Different experimental results on real and sparse benchmark datasets show that our approach is better than previous state of art maximal algorithms.
Decision Problems for Nash Equilibria in Stochastic Games
Venue: arXiv cs.GT 2009
Year: 2009

We analyse the computational complexity of finding Nash equilibria in stochastic multiplayer games with $ω$-regular objectives. While the existence of an equilibrium whose payoff falls into a certain interval may be undecidable, we single out several decidable restrictions of the problem. First, restricting the search space to stationary, or pure stationary, equilibria results in problems that are typically contained in PSPACE and NP, respectively. Second, we show that the existence of an equilibrium with a binary payoff (i.e. an equilibrium where each player either wins or loses with probability 1) is decidable. We also establish that the existence of a Nash equilibrium with a certain binary payoff entails the existence of an equilibrium with the same payoff in pure, finite-state strategies.
A Subsequence-Histogram Method for Generic Vocabulary Recognition over Deletion Channels
Venue: arXiv cs.IT 2009
Year: 2009

We consider the problem of recognizing a vocabulary--a collection of words (sequences) over a finite alphabet--from a potential subsequence of one of its words. We assume the given subsequence is received through a deletion channel as a result of transmission of a random word from one of the two generic underlying vocabularies. An exact maximum a posterior (MAP) solution for this problem counts the number of ways a given subsequence can be derived from particular subsets of candidate vocabularies, requiring exponential time or space. We present a polynomial approximation algorithm for this problem. The algorithm makes no prior assumption about the rules and patterns governing the structure of vocabularies. Instead, through off-line processing of vocabularies, it extracts data regarding regularity patterns in the subsequences of each vocabulary. In the recognition phase, the algorithm just uses this data, called subsequence-histogram, to decide in favor of one of the vocabularies. We provide examples to demonstrate the performance of the algorithm and show that it can achieve the same performance as MAP in some situations. Potential applications include bioinformatics, storage systems, and search engines.
State complexity of orthogonal catenation
Venue: arXiv cs.FL 2009
Year: 2009

A language $L$ is the orthogonal catenation of languages $L_1$ and $L_2$ if every word of $L$ can be written in a unique way as a catenation of a word in $L_1$ and a word in $L_2$. We establish a tight bound for the state complexity of orthogonal catenation of regular languages. The bound is smaller than the bound for arbitrary catenation.
Tailored business solutions by workflow technologies
Venue: arXiv cs.SE 2009
Year: 2009

VISP (Virtual Internet Service Provider) is an IST-STREP project, which is conducting research in the field of these new technologies, targeted to telecom/ISP companies. One of the first tasks of the VISP project is to identify the most appropriate technologies in order to construct the VISP platform. This paper presents the most significant results in the field of choreography and orchestration, two key domains that must accompany process modeling in the construction of a workflow environment.
On one method of boundary value problem regularization by passage to the limit
Venue: arXiv cs.NA 2009
Year: 2009

For one class of boundary value problem depending on small parameter for which numerical methods for their solution are actually inapplicable, procedure of limiting problem acquisition which is much easier and which solution as much as close to the initial solution is described.
Introduction to Machine Learning: Class Notes 67577
Venue: arXiv cs.LG 2009
Year: 2009

Introduction to Machine learning covering Statistical Inference (Bayes, EM, ML/MaxEnt duality), algebraic and spectral methods (PCA, LDA, CCA, Clustering), and PAC learning (the Formal model, VC dimension, Double Sampling theorem).
Quantum theory can be collectively verified
Venue: arXiv cs.OH 2009
Year: 2009

No theory of physics has been collectively scientifically verified in an experiment so far. It is pointed out that probabilistic structure of quantum theory can be collectively scientifically verified in an experiment. It is also argued that experimentalist point of view quantum theory is a complete theory.
Output Width Signal Control In Asynchronous Digital Systems Using External Clock Signal
Venue: arXiv cs.OH 2009
Year: 2009

In present paper, I propose a method for resolving the timing delays for output signals from an asynchronous sequential system. It will be used an example of an asynchronous sequential system that will set up an output signal when an input signal will be set up. The width of the output signal depends on the input signal width, and in this case it is very short. There are many synthesis methods, like using a RC group system, a monostable system in design of the asynchronous digital system or using an external clock signal, CK. In this paper will be used an external clock signal, CK.
Output Width Signal Control In Asynchronous Digital Systems Using Monostable Circuits
Venue: arXiv cs.OH 2009
Year: 2009

In present paper, I propose a method for resolving the timing delays for output signals from an asynchronous sequential system. It will be used an example of an asynchronous sequential system that will set up an output signal when an input signal will be set up. The width of the output signal depends on the input signal width, and in this case it is very short. There are many synthesis methods, like using a RC group system, a monostable system in design of the asynchronous digital system or using an external clock signal, CK. In this paper will be used a monostable circuit.
On the Approximability of Geometric and Geographic Generalization and the Min-Max Bin Covering Problem
Venue: arXiv cs.DS 2009
Year: 2009

We study the problem of abstracting a table of data about individuals so that no selection query can identify fewer than k individuals. We show that it is impossible to achieve arbitrarily good polynomial-time approximations for a number of natural variations of the generalization technique, unless P = NP, even when the table has only a single quasi-identifying attribute that represents a geographic or unordered attribute: Zip-codes: nodes of a planar graph generalized into connected subgraphs GPS coordinates: points in R2 generalized into non-overlapping rectangles Unordered data: text labels that can be grouped arbitrarily. In addition to impossibility results, we provide approximation algorithms for these difficult single-attribute generalization problems, which, of course, apply to multiple-attribute instances with one that is quasi-identifying. We show theoretically and experimentally that our approximation algorithms can come reasonably close to optimal solutions. Incidentally, the generalization problem for unordered data can be viewed as a novel type of bin packing problem--min-max bin covering--which may be of independent interest.
Approximate Triangle Counting
Venue: arXiv cs.DS 2009
Year: 2009

Triangle counting is an important problem in graph mining. Clustering coefficients of vertices and the transitivity ratio of the graph are two metrics often used in complex network analysis. Furthermore, triangles have been used successfully in several real-world applications. However, exact triangle counting is an expensive computation. In this paper we present the analysis of a practical sampling algorithm for counting triangles in graphs. Our analysis yields optimal values for the sampling rate, thus resulting in tremendous speedups ranging from \emph{2800}x to \emph{70000}x when applied to real-world networks. At the same time the accuracy of the estimation is excellent. Our contributions include experimentation on graphs with several millions of nodes and edges, where we show how practical our proposed method is. Finally, our algorithm's implementation is a part of the \pegasus library (Code and datasets are available at (http://www.cs.cmu.edu/~ctsourak/).) a Peta-Graph Mining library implemented in Hadoop, the open source version of Mapreduce.
Internet Traffic Periodicities and Oscillations: A Brief Review
Venue: arXiv cs.NI 2009
Year: 2009

Internet traffic displays many persistent periodicities (oscillations) on a large range of time scales. This paper describes the measurement methodology to detect Internet traffic periodicities and also describes the main periodicities in Internet traffic.
On Capacity Computation for the Two-User Binary Multiple-Access Channel
Venue: arXiv cs.IT 2009
Year: 2009

This paper deals with the problem of computing the boundary of the capacity region for the memoryless two-user binary-input binary-output multiple-access channel ((2,2;2)-MAC), or equivalently, the computation of input probability distributions maximizing weighted sum-rate. This is equivalent to solving a difficult nonconvex optimization problem. For a restricted class of (2,2;2)-MACs and weight vectors, it is shown that, depending on an ordering property of the channel matrix, the optimal solution is located on the boundary, or the objective function has at most one stationary point in the interior of the domain. For this, the problem is reduced to a pseudoconcave one-dimensional optimization and the single-user problem.
HONEI: A collection of libraries for numerical computations targeting multiple processor architectures
Venue: arXiv cs.MS 2009
Year: 2009

We present HONEI, an open-source collection of libraries offering a hardware oriented approach to numerical calculations. HONEI abstracts the hardware, and applications written on top of HONEI can be executed on a wide range of computer architectures such as CPUs, GPUs and the Cell processor. We demonstrate the flexibility and performance of our approach with two test applications, a Finite Element multigrid solver for the Poisson problem and a robust and fast simulation of shallow water waves. By linking against HONEI's libraries, we achieve a twofold speedup over straight forward C++ code using HONEI's SSE backend, and additional 3-4 and 4-16 times faster execution on the Cell and a GPU. A second important aspect of our approach is that the full performance capabilities of the hardware under consideration can be exploited by adding optimised application-specific operations to the HONEI libraries. HONEI provides all necessary infrastructure for development and evaluation of such kernels, significantly simplifying their development.
DNA-Inspired Information Concealing
Venue: arXiv cs.IT 2009
Year: 2009

Protection of the sensitive content is crucial for extensive information sharing. We present a technique of information concealing, based on introduction and maintenance of families of repeats. Repeats in DNA constitute a basic obstacle for its reconstruction by hybridization.