OpenRaiser/Intern-Atlas huggingface dataset:
Good Concatenated Code Ensembles for the Binary Erasure Channel
Venue: arXiv cs.IT 2009
Year: 2009

In this work, we give good concatenated code ensembles for the binary erasure channel (BEC). In particular, we consider repeat multiple-accumulate (RMA) code ensembles formed by the serial concatenation of a repetition code with multiple accumulators, and the hybrid concatenated code (HCC) ensembles recently introduced by Koller et al. (5th Int. Symp. on Turbo Codes & Rel. Topics, Lausanne, Switzerland) consisting of an outer multiple parallel concatenated code serially concatenated with an inner accumulator. We introduce stopping sets for iterative constituent code oriented decoding using maximum a posteriori erasure correction in the constituent codes. We then analyze the asymptotic stopping set distribution for RMA and HCC ensembles and show that their stopping distance hmin, defined as the size of the smallest nonempty stopping set, asymptotically grows linearly with the block length. Thus, these code ensembles are good for the BEC. It is shown that for RMA code ensembles, contrary to the asymptotic minimum distance dmin, whose growth rate coefficient increases with the number of accumulate codes, the hmin growth rate coefficient diminishes with the number of accumulators. We also consider random puncturing of RMA code ensembles and show that for sufficiently high code rates, the asymptotic hmin does not grow linearly with the block length, contrary to the asymptotic dmin, whose growth rate coefficient approaches the Gilbert-Varshamov bound as the rate increases. Finally, we give iterative decoding thresholds for the different code ensembles to compare the convergence properties.
One-Counter Markov Decision Processes
Venue: arXiv cs.GT 2009
Year: 2009

We study the computational complexity of central analysis problems for One-Counter Markov Decision Processes (OC-MDPs), a class of finitely-presented, countable-state MDPs. OC-MDPs are equivalent to a controlled extension of (discrete-time) Quasi-Birth-Death processes (QBDs), a stochastic model studied heavily in queueing theory and applied probability. They can thus be viewed as a natural ``adversarial'' version of a classic stochastic model. Alternatively, they can also be viewed as a natural probabilistic/controlled extension of classic one-counter automata. OC-MDPs also subsume (as a very restricted special case) a recently studied MDP model called ``solvency games'' that model a risk-averse gambling scenario. Basic computational questions about these models include ``termination'' questions and ``limit'' questions, such as the following: does the controller have a ``strategy'' (or ``policy'') to ensure that the counter (which may for example count the number of jobs in the queue) will hit value 0 (the empty queue) almost surely (a.s.)? Or that it will have infinite limsup value, a.s.? Or, that it will hit value 0 in selected terminal states, a.s.? Or, in case these are not satisfied a.s., compute the maximum (supremum) such probability over all strategies. We provide new upper and lower bounds on the complexity of such problems. For some of them we present a polynomial-time algorithm, whereas for others we show PSPACE- or BH-hardness and give an EXPTIME upper bound. Our upper bounds combine techniques from the theory of MDP reward models, the theory of random walks, and a variety of automata-theoretic methods.
Universal Structures and the logic of Forbidden Patterns
Venue: arXiv cs.LO 2009
Year: 2009

Forbidden Patterns Problems (FPPs) are a proper generalisation of Constraint Satisfaction Problems (CSPs). However, we show that when the input is connected and belongs to a class which has low tree-depth decomposition (e.g. structure of bounded degree, proper minor closed class and more generally class of bounded expansion) any FPP becomes a CSP. This result can also be rephrased in terms of expressiveness of the logic MMSNP, introduced by Feder and Vardi in relation with CSPs. Our proof generalises that of a recent paper by Nesetril and Ossona de Mendez. Note that our result holds in the general setting of problems over arbitrary relational structures (not just for graphs).
New technologies for high speed computer networks: a wavelet approach
Venue: arXiv cs.NI 2009
Year: 2009

Indoor multpropagation channel is modeled by the Kaiser electromagnetic wavelet. A method for channel characterization is proposed by modeling all the reflections of indoor propagation in a kernel function instead of its impulse response. This lead us to consider a fractal modulation scheme in which Kaiser wavelets substitute the traditional sinusoidal carrier.
Approximate counting with a floating-point counter
Venue: arXiv cs.DS 2009
Year: 2009

Memory becomes a limiting factor in contemporary applications, such as analyses of the Webgraph and molecular sequences, when many objects need to be counted simultaneously. Robert Morris [Communications of the ACM, 21:840--842, 1978] proposed a probabilistic technique for approximate counting that is extremely space-efficient. The basic idea is to increment a counter containing the value $X$ with probability $2^{-X}$. As a result, the counter contains an approximation of $\lg n$ after $n$ probabilistic updates stored in $\lg\lg n$ bits. Here we revisit the original idea of Morris, and introduce a binary floating-point counter that uses a $d$-bit significand in conjunction with a binary exponent. The counter yields a simple formula for an unbiased estimation of $n$ with a standard deviation of about $0.6\cdot n2^{-d/2}$, and uses $d+\lg\lg n$ bits. We analyze the floating-point counter's performance in a general framework that applies to any probabilistic counter, and derive practical formulas to assess its accuracy.
P vs NP Problem in the field anthropology
Venue: arXiv cs.OH 2009
Year: 2009

An attempt of a new kind of complexity anthropology is considered.
On the Complexity of Submodular Function Minimisation on Diamonds
Venue: arXiv cs.DS 2009
Year: 2009

Let $(L; \sqcap, \sqcup)$ be a finite lattice and let $n$ be a positive integer. A function $f : L^n \to \mathbb{R}$ is said to be submodular if $f(\tup{a} \sqcap \tup{b}) + f(\tup{a} \sqcup \tup{b}) \leq f(\tup{a}) + f(\tup{b})$ for all $\tup{a}, \tup{b} \in L^n$. In this paper we study submodular functions when $L$ is a diamond. Given oracle access to $f$ we are interested in finding $\tup{x} \in L^n$ such that $f(\tup{x}) = \min_{\tup{y} \in L^n} f(\tup{y})$ as efficiently as possible. We establish a min--max theorem, which states that the minimum of the submodular function is equal to the maximum of a certain function defined over a certain polyhedron; and a good characterisation of the minimisation problem, i.e., we show that given an oracle for computing a submodular $f : L^n \to \mathbb{Z}$ and an integer $m$ such that $\min_{\tup{x} \in L^n} f(\tup{x}) = m$, there is a proof of this fact which can be verified in time polynomial in $n$ and $\max_{\tup{t} \in L^n} \log |f(\tup{t})|$; and a pseudo-polynomial time algorithm for the minimisation problem, i.e., given an oracle for computing a submodular $f : L^n \to \mathbb{Z}$ one can find $\min_{\tup{t} \in L^n} f(\tup{t})$ in time bounded by a polynomial in $n$ and $\max_{\tup{t} \in L^n} |f(\tup{t})|$.
FastLMFI: An Efficient Approach for Local Maximal Patterns Propagation and Maximal Patterns Superset Checking
Venue: arXiv cs.DB 2009
Year: 2009

Maximal frequent patterns superset checking plays an important role in the efficient mining of complete Maximal Frequent Itemsets (MFI) and maximal search space pruning. In this paper we present a new indexing approach, FastLMFI for local maximal frequent patterns (itemset) propagation and maximal patterns superset checking. Experimental results on different sparse and dense datasets show that our work is better than the previous well known progressive focusing technique. We have also integrated our superset checking approach with an existing state of the art maximal itemsets algorithm Mafia, and compare our results with current best maximal itemsets algorithms afopt-max and FP (zhu)-max. Our results outperform afopt-max and FP (zhu)-max on dense (chess and mushroom) datasets on almost all support thresholds, which shows the effectiveness of our approach.
Introducing Partial Matching Approach in Association Rules for Better Treatment of Missing Values
Venue: arXiv cs.DB 2009
Year: 2009

Handling missing values in training datasets for constructing learning models or extracting useful information is considered to be an important research task in data mining and knowledge discovery in databases. In recent years, lot of techniques are proposed for imputing missing values by considering attribute relationships with missing value observation and other observations of training dataset. The main deficiency of such techniques is that, they depend upon single approach and do not combine multiple approaches, that why they are less accurate. To improve the accuracy of missing values imputation, in this paper we introduce a novel partial matching concept in association rules mining, which shows better results as compared to full matching concept that we described in our previous work. Our imputation technique combines the partial matching concept in association rules with k-nearest neighbor approach. Since this is a hybrid technique, therefore its accuracy is much better than as compared to those techniques which depend upon single approach. To check the efficiency of our technique, we also provide detail experimental results on number of benchmark datasets which show better results as compared to previous approaches.
Optimistic Initialization and Greediness Lead to Polynomial Time Learning in Factored MDPs - Extended Version
Venue: arXiv cs.AI 2009
Year: 2009

In this paper we propose an algorithm for polynomial-time reinforcement learning in factored Markov decision processes (FMDPs). The factored optimistic initial model (FOIM) algorithm, maintains an empirical model of the FMDP in a conventional way, and always follows a greedy policy with respect to its model. The only trick of the algorithm is that the model is initialized optimistically. We prove that with suitable initialization (i) FOIM converges to the fixed point of approximate value iteration (AVI); (ii) the number of steps when the agent makes non-near-optimal decisions (with respect to the solution of AVI) is polynomial in all relevant quantities; (iii) the per-step costs of the algorithm are also polynomial. To our best knowledge, FOIM is the first algorithm with these properties. This extended version contains the rigorous proofs of the main theorem. A version of this paper appeared in ICML'09.
Some Proxy Signature and Designated verifier Signature Schemes over Braid Groups
Venue: arXiv cs.CR 2009
Year: 2009

Braids groups provide an alternative to number theoretic public cryptography and can be implemented quite efficiently. The paper proposes five signature schemes: Proxy Signature, Designated Verifier, Bi-Designated Verifier, Designated Verifier Proxy Signature And Bi-Designated Verifier Proxy Signature scheme based on braid groups. We also discuss the security aspects of each of the proposed schemes.
VRAC: Virtual Raw Anchor Coordinates Routing in Sensor Networks -- Concepts and Experimental Protocol
Venue: arXiv cs.NI 2009
Year: 2009

In order to make full use of geographic routing techniques developed for large scale networks, nodes must be localized. However, localization and virtual localization techniques in sensor networks are dependent either on expensive and sometimes unavailable hardware (e.g. GPS) or on sophisticated localization calculus (e.g. triangulation) which are both error-prone and with a costly overhead. Instead of localizing nodes in a traditional 2-dimensional space, we intend to use directly the raw distance to a set of anchors to route messages in the multi-dimensional space. This should enable us to use any geographic routing protocol in a robust and efficient manner in a very large range of scenarios.
On the Ambiguity of Commercial Open Source
Venue: arXiv cs.OH 2009
Year: 2009

Open source and commercial applications used to be two separate worlds. The former was the work of amateurs who had little interest in making a profit, while the latter was only profit oriented and was produced by big companies. Nowadays open source is a threat and an opportunity to serious businesses of all kinds, generating good profits while delivering low costs products to customers. The competition between commercial and open source software has impacted the industry and the society as a whole. But in the last years, the markets for commercial and open source software are converging rapidly and it is interesting to resume and discuss the implications of this new paradigm, taking into account arguments pro and against it.
Mesh
Venue: arXiv cs.OH 2009
Year: 2009

Whether you just want to take a peek of a remote computer status, or you want to install the latest version of a software on several workstations, you can do all of this from your computer. The networks are growing, the time spent administering the workstations increases and the number of repetitive tasks is going sky high. But here comes MESH to take that load off your shoulders. And because of SMS commands you can take this "command center" wherever you will go. Just connect a GSM phone to the computer (using a cable, IrDA or Bluetooth) and lock/restart/shutdown computers from your LAN with the push of a cell phone button. You can even create your own SMS commands. This is MESH - the network administrator's Swiss knife
Failover of Software Services with State Replication
Venue: arXiv cs.SE 2009
Year: 2009

Computing systems are becoming more and more complex and assuming more and more responsibilities in all sectors of human activity. Applications do not run locally on a single computer any more. A lot of today's applications are built as distributed system; with services on different computers communicating with each other. Distributed systems arise everywhere. The Internet is one of the best-known distributed systems and used by nearly everyone today. It is obvious that we are more and more dependent on computer services. Many people expect to be able to buy things like clothing or electronic equipment even at night on the Internet. Computers are expected to be operational and available 7 days a week, 24 hours a day. Downtime, even for maintenance, is no longer acceptable.
Automated Epilepsy Diagnosis Using Interictal Scalp EEG
Venue: arXiv cs.AI 2009
Year: 2009

Approximately over 50 million people worldwide suffer from epilepsy. Traditional diagnosis of epilepsy relies on tedious visual screening by highly trained clinicians from lengthy EEG recording that contains the presence of seizure (ictal) activities. Nowadays, there are many automatic systems that can recognize seizure-related EEG signals to help the diagnosis. However, it is very costly and inconvenient to obtain long-term EEG data with seizure activities, especially in areas short of medical resources. We demonstrate in this paper that we can use the interictal scalp EEG data, which is much easier to collect than the ictal data, to automatically diagnose whether a person is epileptic. In our automated EEG recognition system, we extract three classes of features from the EEG data and build Probabilistic Neural Networks (PNNs) fed with these features. We optimize the feature extraction parameters and combine these PNNs through a voting mechanism. As a result, our system achieves an impressive 94.07% accuracy, which is very close to reported human recognition accuracy by experienced medical professionals.
On Smoothed Analysis of Quicksort and Hoare's Find
Venue: arXiv cs.DS 2009
Year: 2009

We provide a smoothed analysis of Hoare's find algorithm and we revisit the smoothed analysis of quicksort. Hoare's find algorithm - often called quickselect - is an easy-to-implement algorithm for finding the k-th smallest element of a sequence. While the worst-case number of comparisons that Hoare's find needs is quadratic, the average-case number is linear. We analyze what happens between these two extremes by providing a smoothed analysis of the algorithm in terms of two different perturbation models: additive noise and partial permutations. Moreover, we provide lower bounds for the smoothed number of comparisons of quicksort and Hoare's find for the median-of-three pivot rule, which usually yields faster algorithms than always selecting the first element: The pivot is the median of the first, middle, and last element of the sequence. We show that median-of-three does not yield a significant improvement over the classic rule: the lower bounds for the classic rule carry over to median-of-three.
Decentralized Coding Algorithms for Distributed Storage in Wireless Sensor Networks
Venue: arXiv cs.IT 2009
Year: 2009

We consider large-scale wireless sensor networks with $n$ nodes, out of which k are in possession, (e.g., have sensed or collected in some other way) k information packets. In the scenarios in which network nodes are vulnerable because of, for example, limited energy or a hostile environment, it is desirable to disseminate the acquired information throughout the network so that each of the n nodes stores one (possibly coded) packet so that the original k source packets can be recovered, locally and in a computationally simple way from any k(1 + ε) nodes for some small ε> 0. We develop decentralized Fountain codes based algorithms to solve this problem. Unlike all previously developed schemes, our algorithms are truly distributed, that is, nodes do not know n, k or connectivity in the network, except in their own neighborhoods, and they do not maintain any routing tables.
Java Technology : a Strategic Solution for Interactive Distributed Applications
Venue: arXiv cs.DC 2009
Year: 2009

In a world demanding the best performance from financial investments, distributed applications occupy the first place among the proposed solutions. This particularity is due to their distributed architecture which is able to acheives high performance. Currently, many research works aim to develop tools that facilitate the implementation of such applications. The urgent need for such applications in all areas pushes researchers to accelerate this process. However, the lack of standardization results in the absence of strategic decisions taken by computer science community. In this article, we argue that Java technology represents an elegant compromise ahead of the list of the currently available solutions. In fact, by promoting the independence of hardware and software, Java technology makes it possible to overcome pitfalls that are inherent to the creation of distributed applications.
On the Power of Randomization in Algorithmic Mechanism Design
Venue: arXiv cs.GT 2009
Year: 2009

In many settings the power of truthful mechanisms is severely bounded. In this paper we use randomization to overcome this problem. In particular, we construct an FPTAS for multi-unit auctions that is truthful in expectation, whereas there is evidence that no polynomial-time truthful deterministic mechanism provides an approximation ratio better than 2. We also show for the first time that truthful in expectation polynomial-time mechanisms are \emph{provably} stronger than polynomial-time universally truthful mechanisms. Specifically, we show that there is a setting in which: (1) there is a non-polynomial time truthful mechanism that always outputs the optimal solution, and that (2) no universally truthful randomized mechanism can provide an approximation ratio better than 2 in polynomial time, but (3) an FPTAS that is truthful in expectation exists.
Ingénierie système d'un système d'information d'entreprise centré sur le produit basée sur un cadre de modélisation multi-échelles : application à un cas d'étude de l'AIP lorrain
Venue: arXiv cs.SE 2009
Year: 2009

Through its projects, the ?Atelier Inter-établissements de Productique Lorrain? (AIPL), as the owner and contractor of rank 1, is committed to provide his customers (teachers, training courses, students etc...) credible teaching materials at the scale of a real industrial flexible production of goods and services. In this changing context, its managerial team has chosen to suppress the CIM concept, which proposes an integrated enterprise, to steering distributed system information (SI), heterogeneous, autonomous and scalable depending on the ephemeral cooperation between industrial partners who now exchanges information and material flows. These aspects are studied in research on CRAN (Centre de Recherche en Automatique de Nancy ? Research Centre for Automatic Control) as part of a thesis based on the recursive aspect of systems and their models and their multi-scale aspects and multi-views, in a Model-Based-System-Engineering (MBSE) methodology proposal of an System-Engineering (SE) focused on the product. To validate this research, a MBSE has been implemented on a case study to AIPL: the "eLearning in eProduction? project.
Bounds on series-parallel slowdown
Venue: arXiv cs.DC 2009
Year: 2009

We use activity networks (task graphs) to model parallel programs and consider series-parallel extensions of these networks. Our motivation is two-fold: the benefits of series-parallel activity networks and the modelling of programming constructs, such as those imposed by current parallel computing environments. Series-parallelisation adds precedence constraints to an activity network, usually increasing its makespan (execution time). The slowdown ratio describes how additional constraints affect the makespan. We disprove an existing conjecture positing a bound of two on the slowdown when workload is not considered. Where workload is known, we conjecture that 4/3 slowdown is always achievable, and prove our conjecture for small networks using max-plus algebra. We analyse a polynomial-time algorithm showing that achieving 4/3 slowdown is in exp-APX. Finally, we discuss the implications of our results.
Feasibility Conditions for Interference Alignment
Venue: arXiv cs.IT 2009
Year: 2009

The degrees of freedom of MIMO interference networks with constant channel coefficients are not known in general. Determining the feasibility of a linear interference alignment solution is a key step toward solving this open problem. Our approach in this paper is to view the alignment problem as a system of bilinear equations and determine its solvability by comparing the number of equations and the number of variables. To this end, we divide interference alignment problems into two classes - proper and improper. An interference alignment problem is called proper if the number of equations does not exceed the number of variables. Otherwise, it is called improper. Examples are presented to support the intuition that for generic channel matrices, proper systems are almost surely feasible and improper systems are almost surely infeasible.
A Generalized Cut-Set Bound
Venue: arXiv cs.IT 2009
Year: 2009

In this paper, we generalize the well known cut-set bound to the problem of lossy transmission of functions of arbitrarily correlated sources over a discrete memoryless multiterminal network.
Adaptive Learning with Binary Neurons
Venue: arXiv cs.AI 2009
Year: 2009

A efficient incremental learning algorithm for classification tasks, called NetLines, well adapted for both binary and real-valued input patterns is presented. It generates small compact feedforward neural networks with one hidden layer of binary units and binary output units. A convergence theorem ensures that solutions with a finite number of hidden units exist for both binary and real-valued input patterns. An implementation for problems with more than two classes, valid for any binary classifier, is proposed. The generalization error and the size of the resulting networks are compared to the best published results on well-known classification benchmarks. Early stopping is shown to decrease overfitting, without improving the generalization performance.