OpenRaiser/Intern-Atlas huggingface dataset:
On Minimax Robust Detection of Stationary Gaussian Signals in White Gaussian Noise
Venue: arXiv cs.IT 2010
Year: 2010

The problem of detecting a wide-sense stationary Gaussian signal process embedded in white Gaussian noise, where the power spectral density of the signal process exhibits uncertainty, is investigated. The performance of minimax robust detection is characterized by the exponential decay rate of the miss probability under a Neyman-Pearson criterion with a fixed false alarm probability, as the length of the observation interval grows without bound. A dominance condition is identified for the uncertainty set of spectral density functions, and it is established that, under the dominance condition, the resulting minimax problem possesses a saddle point, which is achievable by the likelihood ratio tests matched to a so-called dominated power spectral density in the uncertainty set. No convexity condition on the uncertainty set is required to establish this result.
The Role of Boolean Function in Fractal Formation and it s Application to CDMA Wireless Communication
Venue: arXiv cs.NI 2010
Year: 2010

In this paper, a new transformation is generated from a three variable Boolean function 3, which is used to produce a self-similar fractal pattern of dimension 1.58. This very fractal pattern is used to reconstruct the whole structural position of resources in wireless CDMA network. This reconstruction minimizes the number of resources in the network and so naturally network consumption costs are getting reduced. Now -a -days resource controlling and cost minimization are still a severe problem in wireless CDMA network. To overcome this problem fractal pattern produced in our research provides a complete solution of structural position of resources in this Wireless CDMA Network.
On the (Im)possibility of Preserving Utility and Privacy in Personalized Social Recommendations
Venue: arXiv cs.DS 2010
Year: 2010

With the recent surge of social networks like Facebook, new forms of recommendations have become possible -- personalized recommendations of ads, content, and even new social and product connections based on one's social interactions. In this paper, we study whether "social recommendations", or recommendations that utilize a user's social network, can be made without disclosing sensitive links between users. More precisely, we quantify the loss in utility when existing recommendation algorithms are modified to satisfy a strong notion of privacy called differential privacy. We propose lower bounds on the minimum loss in utility for any recommendation algorithm that is differentially private. We also propose two recommendation algorithms that satisfy differential privacy, analyze their performance in comparison to the lower bound, both analytically and experimentally, and show that good private social recommendations are feasible only for a few users in the social network or for a lenient setting of privacy parameters.
HyberLoc: Providing Physical Layer Location Privacy in Hybrid Sensor Networks
Venue: arXiv cs.IT 2010
Year: 2010

In many hybrid wireless sensor networks' applications, sensor nodes are deployed in hostile environments where trusted and un-trusted nodes co-exist. In anchor-based hybrid networks, it becomes important to allow trusted nodes to gain full access to the location information transmitted in beacon frames while, at the same time, prevent un-trusted nodes from using this information. The main challenge is that un-trusted nodes can measure the physical signal transmitted from anchor nodes, even if these nodes encrypt their transmission. Using the measured signal strength, un-trusted nodes can still tri-laterate the location of anchor nodes. In this paper, we propose HyberLoc, an algorithm that provides anchor physical layer location privacy in anchor-based hybrid sensor networks. The idea is for anchor nodes to dynamically change their transmission power following a certain probability distribution, degrading the localization accuracy at un-trusted nodes while maintaining high localization accuracy at trusted nodes. Given an average power constraint, our analysis shows that the discretized exponential distribution is the distribution that maximizes location uncertainty at the untrusted nodes. Detailed evaluation through analysis, simulation, and implementation shows that HyberLoc gives trusted nodes up to 3.5 times better localization accuracy as compared to untrusted nodes.
Electronic Geometry Textbook: A Geometric Textbook Knowledge Management System
Venue: arXiv cs.AI 2010
Year: 2010

Electronic Geometry Textbook is a knowledge management system that manages geometric textbook knowledge to enable users to construct and share dynamic geometry textbooks interactively and efficiently. Based on a knowledge base organizing and storing the knowledge represented in specific languages, the system implements interfaces for maintaining the data representing that knowledge as well as relations among those data, for automatically generating readable documents for viewing or printing, and for automatically discovering the relations among knowledge data. An interface has been developed for users to create geometry textbooks with automatic checking, in real time, of the consistency of the structure of each resulting textbook. By integrating an external geometric theorem prover and an external dynamic geometry software package, the system offers the facilities for automatically proving theorems and generating dynamic figures in the created textbooks. This paper provides a comprehensive account of the current version of Electronic Geometry Textbook.
Using Smith Normal Forms and mu-Bases to Compute all the Singularities of Rational Planar Curves
Venue: arXiv cs.CG 2010
Year: 2010

We prove the conjecture of Chen, Wang and Liu in [8] concerning how to calculate the parameter values corresponding to all the singu- larities, including the infinitely near singularities, of rational planar curves from the Smith normal forms of certain Bezout resultant ma- trices derived from mu-bases.
New Attack Strategy for the Shrinking Generator
Venue: arXiv cs.CR 2010
Year: 2010

This work shows that the cryptanalysis of the shrinking generator requires fewer intercepted bits than what indicated by the linear complexity. Indeed, whereas the linear complexity of shrunken sequences is between $A \cdot 2^(S-2)$ and $A \cdot 2^(S-1)$, we claim that the initial states of both component registers are easily computed with less than $A \cdot S$ shrunken bits. Such a result is proven thanks to the definition of shrunken sequences as interleaved sequences. Consequently, it is conjectured that this statement can be extended to all interleaved sequences. Furthermore, this paper confirms that certain bits of the interleaved sequences have a greater strategic importance than others, which may be considered as a proof of weakness of interleaved generators.
Joint Structured Models for Extraction from Overlapping Sources
Venue: arXiv cs.AI 2010
Year: 2010

We consider the problem of jointly training structured models for extraction from sources whose instances enjoy partial overlap. This has important applications like user-driven ad-hoc information extraction on the web. Such applications present new challenges in terms of the number of sources and their arbitrary pattern of overlap not seen by earlier collective training schemes applied on two sources. We present an agreement-based learning framework and alternatives within it to trade-off tractability, robustness to noise, and extent of agreement. We provide a principled scheme to discover low-noise agreement sets in unlabeled data across the sources. Through extensive experiments over 58 real datasets, we establish that our method of additively rewarding agreement over maximal segments of text provides the best trade-offs, and also scores over alternatives such as collective inference, staged training, and multi-view learning.
Using Linear Difference Equations to Model Nonlinear Cryptographic Sequences
Venue: arXiv cs.CR 2010
Year: 2010

A new class of linear sequence generators based on cellular automata is here introduced in order to model several nonlinear keystream generators with practical applications in symmetric cryptography. The output sequences are written as solutions of linear difference equations, and three basic properties (period, linear complexity and number of different output sequences) are analyzed.
The Formulator MathML Editor Project: User-Friendly Authoring of Content Markup Documents
Venue: arXiv cs.DL 2010
Year: 2010

Implementation of an editing process for Content MathML formulas in common visual style is a real challenge for a software developer who does not really want the user to have to understand the structure of Content MathML in order to edit an expression, since it is expected that users are often not that technically minded. In this paper, we demonstrate how this aim is achieved in the context of the Formulator project and discuss features of this MathML editor, which provides a user with a WYSIWYG editing style while authoring MathML documents with Content or mixed markup. We also present the approach taken to enhance availability of the MathML editor to end-users, demonstrating an online version of the editor that runs inside a Web browser.
Personnalisation de bases de données multidimensionnelles
Venue: arXiv cs.DB 2010
Year: 2010

This paper deals with decision support systems resting on multidimensional modelling of data. Moreover, we intend to offer a set of concepts and mechanisms for personalized multidimensional database specifications. This personalization consists in associating weights to different components of a multidimensional schema. Personalization specifications are specified through the use of a language based on the principle of Event Condition Action. This personalisation determines multidimensional data display as well as their analyses (with the use of drilling or rotating operations).
Construction graphique d'entrepôts et de magasins de données
Venue: arXiv cs.DB 2010
Year: 2010

Nowadays, decisional systems have became a significant research topic in databases. Data warehouses and data marts are the main elements of such systems. This paper presents our decisional support system. We present graphical interfaces which help the administrator to build data warehouses and data marts. We present a data warehouse building interface based on an object-oriented conceptual model. This model allows the warehouse data historisation at three levels: attribute, class and environment. Also, we present a data mart building interface which allows warehouse data to be reorganised through a multidimensional object-oriented model.
Statistical Learning in Automated Troubleshooting: Application to LTE Interference Mitigation
Venue: arXiv cs.LG 2010
Year: 2010

This paper presents a method for automated healing as part of off-line automated troubleshooting. The method combines statistical learning with constraint optimization. The automated healing aims at locally optimizing radio resource management (RRM) or system parameters of cells with poor performance in an iterative manner. The statistical learning processes the data using Logistic Regression (LR) to extract closed form (functional) relations between Key Performance Indicators (KPIs) and Radio Resource Management (RRM) parameters. These functional relations are then processed by an optimization engine which proposes new parameter values. The advantage of the proposed formulation is the small number of iterations required by the automated healing method to converge, making it suitable for off-line implementation. The proposed method is applied to heal an Inter-Cell Interference Coordination (ICIC) process in a 3G Long Term Evolution (LTE) network which is based on soft-frequency reuse scheme. Numerical simulations illustrate the benefits of the proposed approach.
Performance Analysis of Cognitive Radio Systems under QoS Constraints and Channel Uncertainty
Venue: arXiv cs.IT 2010
Year: 2010

In this paper, performance of cognitive transmission over time-selective flat fading channels is studied under quality of service (QoS) constraints and channel uncertainty. Cognitive secondary users (SUs) are assumed to initially perform channel sensing to detect the activities of the primary users, and then attempt to estimate the channel fading coefficients through training. Energy detection is employed for channel sensing, and different minimum mean-square-error (MMSE) estimation methods are considered for channel estimation. In both channel sensing and estimation, erroneous decisions can be made, and hence, channel uncertainty is not completely eliminated. In this setting, performance is studied and interactions between channel sensing and estimation are investigated. Following the channel sensing and estimation tasks, SUs engage in data transmission. Transmitter, being unaware of the channel fading coefficients, is assumed to send the data at fixed power and rate levels that depend on the channel sensing results. Under these assumptions, a state-transition model is constructed by considering the reliability of the transmissions, channel sensing decisions and their correctness, and the evolution of primary user activity which is modeled as a two-state Markov process. In the data transmission phase, an average power constraint on the secondary users is considered to limit the interference to the primary users, and statistical limitations on the buffer lengths are imposed to take into account the QoS constraints of the secondary traffic. The maximum throughput under these statistical QoS constraints is identified by finding the effective capacity of the cognitive radio channel. Numerical results are provided for the power and rate policies.
Observation of implicit complexity by non confluence
Venue: arXiv cs.CC 2010
Year: 2010

We propose to consider non confluence with respect to implicit complexity. We come back to some well known classes of first-order functional program, for which we have a characterization of their intentional properties, namely the class of cons-free programs, the class of programs with an interpretation, and the class of programs with a quasi-interpretation together with a termination proof by the product path ordering. They all correspond to PTIME. We prove that adding non confluence to the rules leads to respectively PTIME, NPTIME and PSPACE. Our thesis is that the separation of the classes is actually a witness of the intentional properties of the initial classes of programs.
Church => Scott = Ptime: an application of resource sensitive realizability
Venue: arXiv cs.LO 2010
Year: 2010

We introduce a variant of linear logic with second order quantifiers and type fixpoints, both restricted to purely linear formulas. The Church encodings of binary words are typed by a standard non-linear type `Church,' while the Scott encodings (purely linear representations of words) are by a linear type `Scott.' We give a characterization of polynomial time functions, which is derived from (Leivant and Marion 93): a function is computable in polynomial time if and only if it can be represented by a term of type Church => Scott. To prove soundness, we employ a resource sensitive realizability technique developed by Hofmann and Dal Lago.
Feature Selection with Conjunctions of Decision Stumps and Learning from Microarray Data
Venue: arXiv cs.LG 2010
Year: 2010

One of the objectives of designing feature selection learning algorithms is to obtain classifiers that depend on a small number of attributes and have verifiable future performance guarantees. There are few, if any, approaches that successfully address the two goals simultaneously. Performance guarantees become crucial for tasks such as microarray data analysis due to very small sample sizes resulting in limited empirical evaluation. To the best of our knowledge, such algorithms that give theoretical bounds on the future performance have not been proposed so far in the context of the classification of gene expression data. In this work, we investigate the premise of learning a conjunction (or disjunction) of decision stumps in Occam's Razor, Sample Compression, and PAC-Bayes learning settings for identifying a small subset of attributes that can be used to perform reliable classification tasks. We apply the proposed approaches for gene identification from DNA microarray data and compare our results to those of well known successful approaches proposed for the task. We show that our algorithm not only finds hypotheses with much smaller number of genes while giving competitive classification accuracy but also have tight risk guarantees on future performance unlike other approaches. The proposed approaches are general and extensible in terms of both designing novel algorithms and application to other domains.
A chaos-based approach for information hiding security
Venue: arXiv cs.CR 2010
Year: 2010

This paper introduces a new framework for data hiding security. Contrary to the existing ones, the approach introduced here is not based on probability theory. In this paper, a scheme is considered as secure if its behavior is proven unpredictable. The objective of this study is to enrich the existing notions of data hiding security with a new rigorous and practicable one. This new definition of security is based on the notion of topological chaos. It could be used to reinforce the confidence on a scheme previously proven as secure by other approaches and it could also be used to study some classes of attacks that currently cannot be studied by the existing security approaches. After presenting the theoretical framework of the study, a concrete example is detailed in order to show how our approach can be applied.
Integrating multiple sources to answer questions in Algebraic Topology
Venue: arXiv cs.SC 2010
Year: 2010

We present in this paper an evolution of a tool from a user interface for a concrete Computer Algebra system for Algebraic Topology (the Kenzo system), to a front-end allowing the interoperability among different sources for computation and deduction. The architecture allows the system not only to interface several systems, but also to make them cooperate in shared calculations.
Watching Systems in graphs: an extension of Identifying Codes
Venue: arXiv cs.DM 2010
Year: 2010

We introduce the notion of watching systems in graphs, which is a generalization of that of identifying codes. We give some basic properties of watching systems, an upper bound on the minimum size of a watching system, and results on the graphs which achieve this bound; we also study the cases of the paths and cycles, and give complexity results.
On Estimating the First Frequency Moment of Data Streams
Venue: arXiv cs.DS 2010
Year: 2010

Estimating the first moment of a data stream defined as $F_1 = \sum_{i \in \{1, 2, \ldots, n\}} \abs{f_i}$ to within $1 \pm ε$-relative error with high probability is a basic and influential problem in data stream processing. A tight space bound of $O(ε^{-2} \log (mM))$ is known from the work of [Kane-Nelson-Woodruff-SODA10]. However, all known algorithms for this problem require per-update stream processing time of $Ω(ε^{-2})$, with the only exception being the algorithm of [Ganguly-Cormode-RANDOM07] that requires per-update processing time of $O(\log^2(mM)(\log n))$ albeit with sub-optimal space $O(ε^{-3}\log^2(mM))$. In this paper, we present an algorithm for estimating $F_1$ that achieves near-optimality in both space and update processing time. The space requirement is $O(ε^{-2}(\log n + (\log ε^{-1})\log(mM)))$ and the per-update processing time is $O( (\log n)\log (ε^{-1}))$.
Software Design Document, Testing, Deployment and Configuration Management of the IUfA's UUIS -- a Team 3 COMP5541-W10 Project Approach
Venue: arXiv cs.SE 2010
Year: 2010

The purpose of this document is to provide technical specifications concerned to the Design of the University Unified Inventory System - Web Portal, of the UIfA. The Team of Developers used a Feedback Waterfall approach to build up the system, under an Object Oriented paradigm. The architectural model followed was the Model-View-Controller, mixed with a Mapper layer between the database and the Model. Some of the patterns utilized in the developing of the System were the Observer Pattern, the Command Pattern, and the Mapper Pattern.
On Building a Knowledge Base for Stability Theory
Venue: arXiv cs.AI 2010
Year: 2010

A lot of mathematical knowledge has been formalized and stored in repositories by now: different mathematical theorems and theories have been taken into consideration and included in mathematical repositories. Applications more distant from pure mathematics, however --- though based on these theories --- often need more detailed knowledge about the underlying theories. In this paper we present an example Mizar formalization from the area of electrical engineering focusing on stability theory which is based on complex analysis. We discuss what kind of special knowledge is necessary here and which amount of this knowledge is included in existing repositories.
Improving Overhead Computation and pre-processing Time for Grid Scheduling System
Venue: arXiv cs.DC 2010
Year: 2010

Computational Grid is enormous environments with heterogeneous resources and stable infrastructures among other Internet-based computing systems. However, the managing of resources in such systems has its special problems. Scheduler systems need to get last information about participant nodes from information centers for the purpose of firmly job scheduling. In this paper, we focus on online updating resource information centers with processed and provided data based on the assumed hierarchical model. A hybrid knowledge extraction method has been used to classifying grid nodes based on prediction of jobs' features. An affirmative point of this research is that scheduler systems don't waste extra time for getting up-to-date information of grid nodes. The experimental result shows the advantages of our approach compared to other conservative methods, especially due to its ability to predict the behavior of nodes based on comprehensive data tables on each node.
The New Embedded System Design Methodology For Improving Design Process Performance
Venue: arXiv cs.OH 2010
Year: 2010

Time-to-market pressure and productivity gap force vendors and researchers to improve embedded system design methodology. Current used design method, Register Transfer Level (RTL), is no longer be adequate to comply with embedded system design necessity. It needs a new methodology for facing the lack of RTL. In this paper, a new methodology of hardware embedded system modeling process is designed for improving design process performance using Transaction Level Modeling (TLM). TLM is a higher abstraction design concept model above RTL model. Parameters measured include design process time and accuracy of design. For implementing RTL model used Avalon and Wishbone buses, both are System on Chip bus. Performance improvement measured by comparing TLM and RTL model process. The experiment results show performance improvements for Avalon RTL using new design methodology are 1,03 for 3-tiers, 1,47 for 4-tiers and 1,69 for 5-tiers. Performance improvements for Wishbone RTL are 1,12 for 3-tiers, 1,17 for 4-tiers and 1,34 for 5-tiers. These results show the trend of design process improvement.