OpenRaiser/Intern-Atlas huggingface dataset:
Perturbation analysis of an M/M/1 queue in a diffusion random environment
Venue: arXiv cs.NI 2008
Year: 2008

We study in this paper an $M/M/1$ queue whose server rate depends upon the state of an independent Ornstein-Uhlenbeck diffusion process $(X(t))$ so that its value at time $t$ is $μϕ(X(t))$, where $ϕ(x)$ is some bounded function and $μ>0$. We first establish the differential system for the conditional probability density functions of the couple $(L(t),X(t))$ in the stationary regime, where $L(t)$ is the number of customers in the system at time $t$. By assuming that $ϕ(x)$ is defined by $ϕ(x) = 1-\varepsilon ((x\wedge a/\varepsilon)\vee(-b/\varepsilon))$ for some positive real numbers $a$, $b$ and $\varepsilon$, we show that the above differential system has a unique solution under some condition on $a$ and $b$. We then show that this solution is close, in some appropriate sense, to the solution to the differential system obtained when $ϕ$ is replaced with $Φ(x)=1-\varepsilon x$ for sufficiently small $\varepsilon$. We finally perform a perturbation analysis of this latter solution for small $\varepsilon$. This allows us to check at the first order the validity of the so-called reduced service rate approximation, stating that everything happens as if the server rate were constant and equal to $μ(1-\eps\E(X(t)))$.
Inference of Flow Statistics via Packet Sampling in the Internet
Venue: arXiv cs.NI 2008
Year: 2008

We show in this note that by deterministic packet sampling, the tail of the distribution of the original flow size can be obtained by rescaling that of the sampled flow size. To recover information on the flow size distribution lost through packet sampling, we propose some heuristics based on measurements from different backbone IP networks. These heuristic arguments allow us to recover the complete flow size distribution.
Feature Selection By KDDA For SVM-Based MultiView Face Recognition
Venue: arXiv cs.CV 2008
Year: 2008

Applications such as face recognition that deal with high-dimensional data need a mapping technique that introduces representation of low-dimensional features with enhanced discriminatory power and a proper classifier, able to classify those complex features. Most of traditional Linear Discriminant Analysis suffer from the disadvantage that their optimality criteria are not directly related to the classification ability of the obtained feature representation. Moreover, their classification accuracy is affected by the "small sample size" problem which is often encountered in FR tasks. In this short paper, we combine nonlinear kernel based mapping of data called KDDA with Support Vector machine classifier to deal with both of the shortcomings in an efficient and cost effective manner. The proposed here method is compared, in terms of classification accuracy, to other commonly used FR methods on UMIST face database. Results indicate that the performance of the proposed method is overall superior to those of traditional FR approaches, such as the Eigenfaces, Fisherfaces, and D-LDA methods and traditional linear classifiers.
Heterogeneous component interactions: Sensors integration into multimedia applications
Venue: arXiv cs.MM 2008
Year: 2008

Resource-constrained embedded and mobile devices are becoming increasingly common. Since few years, some mobile and ubiquitous devices such as wireless sensor, able to be aware of their physical environment, appeared. Such devices enable proposing applications which adapt to user's need according the context evolution. It implies the collaboration of sensors and software components which differ on their nature and their communication mechanisms. This paper proposes a unified component model in order to easily design applications based on software components and sensors without taking care of their nature. Then it presents a state of the art of communication problems linked to heterogeneous components and proposes an interaction mechanism which ensures information exchanges between wireless sensors and software components.
Branching Bisimilarity with Explicit Divergence
Venue: arXiv cs.LO 2008
Year: 2008

We consider the relational characterisation of branching bisimilarity with explicit divergence. We prove that it is an equivalence and that it coincides with the original definition of branching bisimilarity with explicit divergence in terms of coloured traces. We also establish a correspondence with several variants of an action-based modal logic with until- and divergence modalities.
A randomized polynomial-time algorithm for the Spanning Hypertree Problem on 3-uniform hypergraphs
Venue: arXiv cs.CC 2008
Year: 2008

Consider the problem of determining whether there exists a spanning hypertree in a given k-uniform hypergraph. This problem is trivially in P for k=2, and is NP-complete for k>= 4, whereas for k=3, there exists a polynomial-time algorithm based on Lovasz' theory of polymatroid matching. Here we give a completely different, randomized polynomial-time algorithm in the case k=3. The main ingredients are a Pfaffian formula by Vaintrob and one of the authors (G.M.) for a polynomial that enumerates spanning hypertrees with some signs, and a lemma on the number of roots of polynomials over a finite field.
Bootstrapping Inductive and Coinductive Types in HasCASL
Venue: arXiv cs.LO 2008
Year: 2008

We discuss the treatment of initial datatypes and final process types in the wide-spectrum language HasCASL. In particular, we present specifications that illustrate how datatypes and process types arise as bootstrapped concepts using HasCASL's type class mechanism, and we describe constructions of types of finite and infinite trees that establish the conservativity of datatype and process type declarations adhering to certain reasonable formats. The latter amounts to modifying known constructions from HOL to avoid unique choice; in categorical terminology, this means that we establish that quasitoposes with an internal natural numbers object support initial algebras and final coalgebras for a range of polynomial functors, thereby partially generalising corresponding results from topos theory. Moreover, we present similar constructions in categories of internal complete partial orders in quasitoposes.
Multi-User SISO Precoding based on Generalized Multi-Unitary Decomposition for Single-carrier Transmission in Frequency Selective Channel
Venue: arXiv cs.IT 2008
Year: 2008

In this paper, we propose to exploit the richly scattered multi-path nature of a frequency selective channel to provide additional degrees of freedom for desigining effective precoding schemes for multi-user communications. We design the precoding matrix for multi-user communications based on the Generalized Multi-Unitary Decomposition (GMUD), where the channel matrix H is transformed into P_i*R_r*Q_i^H. An advantage of GMUD is that multiple pairs of unitary matrices P_i and Q_i can be obtained with one single R_r. Since the column of Q_i can be used as the transmission beam of a particular user, multiple solutions of Q_i provide a large selection of transmission beams, which can be exploited to achieve high degrees of orthogonality between the multipaths, as well as between the interfering users. Hence the proposed precoding technique based on GMUD achieves better performance than precoding based on singular value decomposition.
Time series of Internet AS-level topology graphs: four patterns and one model
Venue: arXiv cs.NI 2008
Year: 2008

Researchers have proposed a variety of Internet topology models. However almost all of them focus on generating one graph based on one single static source graph. On the other hand, Internet topology is evolving over time continuously with the addition and deletion of nodes and edges. If a model is based on all the topologies in the past, instead of one of them, it will be more accurate and closer to the real world topology. In this paper, we study the Internet As-level topology time-series from two different sources and find that both of them obey four same dynamic graph patterns. Then we propose a mode that can infer the topology in the future based on all the topologies in the past. Through theoretical and experimental analysis, we prove the topology that our model generates can match both the static and dynamic graph patterns. In addition, the parameters in the model are meaningful. Finally, we theoretically and experimentally prove that these parameters are directly related to some important graph characteristics.
Indoor Channel Measurements and Communications System Design at 60 GHz
Venue: arXiv cs.NI 2008
Year: 2008

This paper presents a brief overview of several studies concerning the indoor wireless communications at 60 GHz performed by the IETR. The characterization and the modeling of the radio propagation channel are based on several measurement campaigns realized with the channel sounder developed at IETR. Some typical residential environments were also simulated by ray tracing and Gaussian Beam Tracking. The obtained results show a good agreement with the similar experimental results. Currently, the IETR is developing a high data rate wireless communication system operating at 60 GHz. The single-carrier architecture of this system is also presented.
On Optimal Linear Redistribution of VCG Payments in Assignment of Heterogeneous Objects
Venue: arXiv cs.GT 2008
Year: 2008

There are p heterogeneous objects to be assigned to n competing agents (n > p) each with unit demand. It is required to design a Groves mechanism for this assignment problem satisfying weak budget balance, individual rationality, and minimizing the budget imbalance. This calls for designing an appropriate rebate function. Our main result is an impossibility theorem which rules out linear rebate functions with non-zero efficiency in heterogeneous object assignment. Motivated by this theorem, we explore two approaches to get around this impossibility. In the first approach, we show that linear rebate functions with non-zero are possible when the valuations for the objects are correlated. In the second approach, we show that rebate functions with non-zero efficiency are possible if linearity is relaxed.
On the Capacity of Partially Cognitive Radios
Venue: arXiv cs.IT 2008
Year: 2008

This paper considers the problem of cognitive radios with partial-message information. Here, an interference channel setting is considered where one transmitter (the "cognitive" one) knows the message of the other ("legitimate" user) partially. An outer bound on the capacity region of this channel is found for the "weak" interference case (where the interference from the cognitive transmitter to the legitimate receiver is weak). This outer bound is shown for both the discrete-memoryless and the Gaussian channel cases. An achievable region is subsequently determined for a mixed interference Gaussian cognitive radio channel, where the interference from the legitimate transmitter to the cognitive receiver is "strong". It is shown that, for a class of mixed Gaussian cognitive radio channels, portions of the outer bound are achievable thus resulting in a characterization of a part of this channel's capacity region.
Cloud Computing and Grid Computing 360-Degree Compared
Venue: arXiv cs.DC 2008
Year: 2008

Cloud Computing has become another buzzword after Web 2.0. However, there are dozens of different definitions for Cloud Computing and there seems to be no consensus on what a Cloud is. On the other hand, Cloud Computing is not a completely new concept; it has intricate connection to the relatively new but thirteen-year established Grid Computing paradigm, and other relevant technologies such as utility computing, cluster computing, and distributed systems in general. This paper strives to compare and contrast Cloud Computing with Grid Computing from various angles and give insights into the essential characteristics of both.
The Generalized Riemann or Henstock Integral Underpinning Multivariate Data Analysis: Application to Faint Structure Finding in Price Processes
Venue: arXiv cs.CE 2008
Year: 2008

Practical data analysis involves many implicit or explicit assumptions about the good behavior of the data, and excludes consideration of various potentially pathological or limit cases. In this work, we present a new general theory of data, and of data processing, to bypass some of these assumptions. The new framework presented is focused on integration, and has direct applicability to expectation, distance, correlation, and aggregation. In a case study, we seek to reveal faint structure in financial data. Our new foundation for data encoding and handling offers increased justification for our conclusions.
Efficient polynomial time algorithms computing industrial-strength primitive roots
Venue: arXiv cs.SC 2008
Year: 2008

E. Bach, following an idea of T. Itoh, has shown how to build a small set of numbers modulo a prime p such that at least one element of this set is a generator of $\pF{p}$\cite{Bach:1997:sppr,Itoh:2001:PPR}. E. Bach suggests also that at least half of his set should be generators. We show here that a slight variant of this set can indeed be made to contain a ratio of primitive roots as close to 1 as necessary. We thus derive several algorithms computing primitive roots correct with very high probability in polynomial time. In particular we present an asymptotically $O^{\sim}(\sqrt{\frac{1}ε}log^1.5(p) + \log^2(p))$ algorithm providing primitive roots of $p$ with probability of correctness greater than $1-ε$ and several $O(log^α(p))$, $α\leq 5.23$ algorithms computing "Industrial-strength" primitive roots with probabilities e.g. greater than the probability of "hardware malfunctions".
An unbreakable cryptosystem
Venue: arXiv cs.CR 2008
Year: 2008

The remarkably long-standing problem of cryptography is to generate completely secure key. It is widely believed that the task cannot be achieved within classical cryptography. However, there is no proof in support of this belief. We present an incredibly simple classical cryptosystem which can generate completely secure key.
Security Policies as Membranes in Systems for Global Computing
Venue: arXiv cs.PL 2008
Year: 2008

We propose a simple global computing framework, whose main concern is code migration. Systems are structured in sites, and each site is divided into two parts: a computing body, and a membrane, which regulates the interactions between the computing body and the external environment. More precisely, membranes are filters which control access to the associated site, and they also rely on the well-established notion of trust between sites. We develop a basic theory to express and enforce security policies via membranes. Initially, these only control the actions incoming agents intend to perform locally. We then adapt the basic theory to encompass more sophisticated policies, where the number of actions an agent wants to perform, and also their order, are considered.
A particle can carry more than one bit of information
Venue: arXiv cs.IT 2008
Year: 2008

It is believed that a particle cannot carry more than one bit of information. It is pointed out that particle or single-particle quantum state can carry more than one bit of information. It implies that minimum energy cost of transmitting a bit will be less than the accepted limit KTlog2.
Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data
Venue: arXiv cs.CR 2008
Year: 2008

We provide formal definitions and efficient secure techniques for - turning noisy information into keys usable for any cryptographic application, and, in particular, - reliably and securely authenticating biometric data. Our techniques apply not just to biometric information, but to any keying material that, unlike traditional cryptographic keys, is (1) not reproducible precisely and (2) not distributed uniformly. We propose two primitives: a "fuzzy extractor" reliably extracts nearly uniform randomness R from its input; the extraction is error-tolerant in the sense that R will be the same even if the input changes, as long as it remains reasonably close to the original. Thus, R can be used as a key in a cryptographic application. A "secure sketch" produces public information about its input w that does not reveal w, and yet allows exact recovery of w given another value that is close to w. Thus, it can be used to reliably reproduce error-prone biometric inputs without incurring the security risk inherent in storing them. We define the primitives to be both formally secure and versatile, generalizing much prior work. In addition, we provide nearly optimal constructions of both primitives for various measures of ``closeness'' of input data, such as Hamming distance, edit distance, and set difference.
Convergence of Min-Sum Message Passing for Quadratic Optimization
Venue: arXiv cs.IT 2008
Year: 2008

We establish the convergence of the min-sum message passing algorithm for minimization of a broad class of quadratic objective functions: those that admit a convex decomposition. Our results also apply to the equivalent problem of the convergence of Gaussian belief propagation.
Linear-programming design and analysis of fast algorithms for Max 2-Sat and Max 2-CSP
Venue: arXiv cs.DM 2008
Year: 2008

The class $(r,2)$-CSP, or simply Max 2-CSP, consists of constraint satisfaction problems with at most two $r$-valued variables per clause. For instances with $n$ variables and $m$ binary clauses, we present an $O(n r^{5+19m/100})$-time algorithm which is the fastest polynomial-space algorithm for many problems in the class, including Max Cut. The method also proves a treewidth bound $\tw(G) \leq (13/75+o(1))m$, which gives a faster Max 2-CSP algorithm that uses exponential space: running in time $\Ostar{2^{(13/75+o(1))m}}$, this is fastest for most problems in Max 2-CSP. Parametrizing in terms of $n$ rather than $m$, for graphs of average degree $d$ we show a simple algorithm running time $\Ostar{2^{(1-\frac{2}{d+1})n}}$, the fastest polynomial-space algorithm known. In combination with ``Polynomial CSPs'' introduced in a companion paper, these algorithms also allow (with an additional polynomial-factor overhead in space and time) counting and sampling, and the solution of problems like Max Bisection that escape the usual CSP framework. Linear programming is key to the design as well as the analysis of the algorithms.
How to Run Mathematica Batch-files in Background ?
Venue: arXiv cs.MS 2008
Year: 2008

Mathematica is a versatile equipment for doing numeric and symbolic computations and it has wide spread applications in all branches of science. Mathematica has a complete consistency to design it at every stage that gives it multilevel capability and helps advanced usage evolve naturally. Mathematica functions work for any precision of number and it can be easily computed with symbols, represented graphically to get the best answer. Mathematica is a robust software development that can be used in any popular operating systems and it can be communicated with external programs by using proper mathlink commands. Sometimes it is quite desirable to run jobs in background of a computer which can take considerable amount of time to finish, and this allows us to do work on other tasks, while keeping the jobs running. Most of us are very familiar to run jobs in background for the programs written in the languages like C, C++, F77, F90, F95, etc. But the way of running jobs, written in a mathematica notebook, in background is quite different from the conventional method. In this article, we explore how to create a mathematica batch-file from a mathematica notebook and run it in background. Here we concentrate our study only for the Unix version, but one can run mathematica programs in background for the Windows version as well by using proper mathematica batch-file.
Using Pseudo-Stochastic Rational Languages in Probabilistic Grammatical Inference
Venue: arXiv cs.LG 2008
Year: 2008

In probabilistic grammatical inference, a usual goal is to infer a good approximation of an unknown distribution P called a stochastic language. The estimate of P stands in some class of probabilistic models such as probabilistic automata (PA). In this paper, we focus on probabilistic models based on multiplicity automata (MA). The stochastic languages generated by MA are called rational stochastic languages; they strictly include stochastic languages generated by PA; they also admit a very concise canonical representation. Despite the fact that this class is not recursively enumerable, it is efficiently identifiable in the limit by using the algorithm DEES, introduced by the authors in a previous paper. However, the identification is not proper and before the convergence of the algorithm, DEES can produce MA that do not define stochastic languages. Nevertheless, it is possible to use these MA to define stochastic languages. We show that they belong to a broader class of rational series, that we call pseudo-stochastic rational languages. The aim of this paper is twofold. First we provide a theoretical study of pseudo-stochastic rational languages, the languages output by DEES, showing for example that this class is decidable within polynomial time. Second, we have carried out a lot of experiments in order to compare DEES to classical inference algorithms such as ALERGIA and MDI. They show that DEES outperforms them in most cases.
Multiaccess Channels with State Known to Some Encoders and Independent Messages
Venue: arXiv cs.IT 2008
Year: 2008

We consider a state-dependent multiaccess channel (MAC) with state non-causally known to some encoders. We derive an inner bound for the capacity region in the general discrete memoryless case and specialize to a binary noiseless case. In the case of maximum entropy channel state, we obtain the capacity region for binary noiseless MAC with one informed encoder by deriving a non-trivial outer bound for this case. For a Gaussian state-dependent MAC with one encoder being informed of the channel state, we present an inner bound by applying a slightly generalized dirty paper coding (GDPC) at the informed encoder that allows for partial state cancellation, and a trivial outer bound by providing channel state to the decoder also. The uninformed encoders benefit from the state cancellation in terms of achievable rates, however, appears that GDPC cannot completely eliminate the effect of the channel state on the achievable rate region, in contrast to the case of all encoders being informed. In the case of infinite state variance, we analyze how the uninformed encoder benefits from the informed encoder's actions using the inner bound and also provide a non-trivial outer bound for this case which is better than the trivial outer bound.
A new function algebra of EXPTIME functions by safe nested recursion
Venue: arXiv cs.CC 2008
Year: 2008

Bellantoni and Cook have given a function-algebra characterization of the polynomial-time computable functions via an unbounded recursion scheme which is called safe recursion. Inspired by their work, we characterize the exponential-time computable functions with the use of a safe variant of nested recursion.