OpenRaiser/Intern-Atlas huggingface dataset:
The myth of equidistribution for high-dimensional simulation
Venue: arXiv cs.MS 2010
Year: 2010

A pseudo-random number generator (RNG) might be used to generate w-bit random samples in d dimensions if the number of state bits is at least dw. Some RNGs perform better than others and the concept of equidistribution has been introduced in the literature in order to rank different RNGs. We define what it means for a RNG to be (d,w)-equidistributed, and then argue that (d,w)-equidistribution is not necessarily a desirable property.
Distribution of Cognitive Load in Web Search
Venue: arXiv cs.HC 2010
Year: 2010

The search task and the system both affect the demand on cognitive resources during information search. In some situations, the demands may become too high for a person. This article has a three-fold goal. First, it presents and critiques methods to measure cognitive load. Second, it explores the distribution of load across search task stages. Finally, it seeks to improve our understanding of factors affecting cognitive load levels in information search. To this end, a controlled Web search experiment with forty-eight participants was conducted. Interaction logs were used to segment search tasks semi-automatically into task stages. Cognitive load was assessed using a new variant of the dual-task method. Average cognitive load was found to vary by search task stages. It was significantly higher during query formulation and user description of a relevant document as compared to examining search results and viewing individual documents. Semantic information shown next to the search results lists in one of the studied interfaces was found to decrease mental demands during query formulation and examination of the search results list. These findings demonstrate that changes in dynamic cognitive load can be detected within search tasks. Dynamic assessment of cognitive load is of core interest to information science because it enriches our understanding of cognitive demands imposed on people engaged in the search process by a task and the interactive information retrieval system employed.
Fractal Weyl law for Linux Kernel Architecture
Venue: arXiv cs.CE 2010
Year: 2010

We study the properties of spectrum and eigenstates of the Google matrix of a directed network formed by the procedure calls in the Linux Kernel. Our results obtained for various versions of the Linux Kernel show that the spectrum is characterized by the fractal Weyl law established recently for systems of quantum chaotic scattering and the Perron-Frobenius operators of dynamical maps. The fractal Weyl exponent is found to be $ν\approx 0.63$ that corresponds to the fractal dimension of the network $d \approx 1.2$. The eigenmodes of the Google matrix of Linux Kernel are localized on certain principal nodes. We argue that the fractal Weyl law should be generic for directed networks with the fractal dimension $d<2$.
Using vector divisions in solving linear complementarity problem
Venue: arXiv cs.NA 2010
Year: 2010

The linear complementarity problem is to find vector $z$ in $\mathrm{IR}^{n}$ satisfying $z^{T}(Mz+q)=0$, $Mz+q\geqslant0,$ $z\geqslant0$, where $M$ as a matrix and $q$ as a vector, are given data; this problem becomes in present the subject of much important research because it arises in many areas and it includes important fields, we cite for example the linear and nonlinear programming, the convex quadratic programming and the variational inequalities problems, ... It is known that the linear complementarity problem is completely equivalent to solving nonlinear equation $F(x)=0$ with $F$ is a function from $\mathrm{IR}^{n}$ into itself defined by $F(x)=(M+I)x+(M-I)|x|+q$. In this paper we propose a globally convergent hybrid algorithm for solving this equation; this method is based on an algorithm given by Shi \cite{Y. Shi}, he uses vector divisions with the secant method; but for using this method we must have a function continuous with partial derivatives on an open set of $\mathrm{IR}^{n}$; so we built a sequence of functions $\tilde{F}(p,x)\in C^{\infty}$ which converges uniformly to the function $F(x)$; and we show that finding the zero of the function $F$ is completely equivalent to finding the zero of the sequence of the functions $\tilde{F}(p,x)$. We close our paper with some numerical simulation examples to illustrate our theoretical results.
RAmM Algorithm(Simplex)
Venue: arXiv cs.CR 2010
Year: 2010

The evolution of encryption algorithms have led to the development of very complicated and highly versatile algorithms that sacrifice efficiency for better and harder to decrypt results. But by the application of a genetic schema to the encryption of data, a new structure can be created. Genetic methods and procedures are lethal in the way they handle and manipulate data. The RAmM algorithm uses four genetic operations that have been developed specifically for encryption of data. The operations are Replication, Augmentation, Mutation and Multiplication. The proper application of these methods according to the rules that have been found to be the best for getting optimal and correct results produces a "fingerprint" that is unique to a pair of <data , key>. This means that every single data entry can only be decrypted by using the correct set of key. The application of the RAmM algorithm is in the field of image encryption and restoration. The boundary and the pixel values are separately encrypted to produce a very genuine sequence that is never understood to be an image. The beauty of the procedure is that the entire image can be reproduced without any color loss or loss of pixel quality.
Encoding points on hyperelliptic curves over finite fields in deterministic polynomial time
Venue: arXiv cs.CR 2010
Year: 2010

We present families of (hyper)elliptic curve which admit an efficient deterministic encoding function.
On The Power of Tree Projections: Structural Tractability of Enumerating CSP Solutions
Venue: arXiv cs.AI 2010
Year: 2010

The problem of deciding whether CSP instances admit solutions has been deeply studied in the literature, and several structural tractability results have been derived so far. However, constraint satisfaction comes in practice as a computation problem where the focus is either on finding one solution, or on enumerating all solutions, possibly projected to some given set of output variables. The paper investigates the structural tractability of the problem of enumerating (possibly projected) solutions, where tractability means here computable with polynomial delay (WPD), since in general exponentially many solutions may be computed. A general framework based on the notion of tree projection of hypergraphs is considered, which generalizes all known decomposition methods. Tractability results have been obtained both for classes of structures where output variables are part of their specification, and for classes of structures where computability WPD must be ensured for any possible set of output variables. These results are shown to be tight, by exhibiting dichotomies for classes of structures having bounded arity and where the tree decomposition method is considered.
A Wireless Sensor Network Air Pollution Monitoring System
Venue: arXiv cs.NI 2010
Year: 2010

Sensor networks are currently an active research area mainly due to the potential of their applications. In this paper we investigate the use of Wireless Sensor Networks (WSN) for air pollution monitoring in Mauritius. With the fast growing industrial activities on the island, the problem of air pollution is becoming a major concern for the health of the population. We proposed an innovative system named Wireless Sensor Network Air Pollution Monitoring System (WAPMS) to monitor air pollution in Mauritius through the use of wireless sensors deployed in huge numbers around the island. The proposed system makes use of an Air Quality Index (AQI) which is presently not available in Mauritius. In order to improve the efficiency of WAPMS, we have designed and implemented a new data aggregation algorithm named Recursive Converging Quartiles (RCQ). The algorithm is used to merge data to eliminate duplicates, filter out invalid readings and summarise them into a simpler form which significantly reduce the amount of data to be transmitted to the sink and thus saving energy. For better power management we used a hierarchical routing protocol in WAPMS and caused the motes to sleep during idle time.
Adaptive and Secure Routing Protocol for Emergency Mobile Ad Hoc Networks
Venue: arXiv cs.NI 2010
Year: 2010

The nature of Mobile Ad hoc NETworks (MANETs) makes them suitable to be utilized in the context of an extreme emergency for all involved rescue teams. We use the term emergency MANETs (eMANETs) in order to describe next generation IP-based networks, which are deployed in emergency cases such as forest fires and terrorist attacks. The main goal within the realm of eMANETs is to provide emergency workers with intelligent devices such as smart phones and PDAs. This technology allows communication "islets" to be established between the members of the same or different emergency teams (policemen, firemen, paramedics). In this article, we discuss an adaptive and secure routing protocol developed for the purposes of eMANETs. We evaluate the performance of the protocol by comparing it with other widely used routing protocols for MANETs. We finally show that the overhead introduced due to security considerations is affordable to support secure ad-hoc communications among lightweight devices.
General Model for Infrastructure Multi-channel Wireless LANs
Venue: arXiv cs.NI 2010
Year: 2010

In this paper we develop an integrated model for request mechanism and data transmission in multi-channel wireless local area networks. We calculated the performance parameters for single and multi-channel wireless networks when the channel is noisy. The proposed model is general it can be applied to different wireless networks such as IEEE802.11x, IEEE802.16, CDMA operated networks and Hiperlan\2.
Architecture for Cooperative Prefetching in P2P Video-on- Demand System
Venue: arXiv cs.MM 2010
Year: 2010

Most P2P VoD schemes focused on service architectures and overlays optimization without considering segments rarity and the performance of prefetching strategies. As a result, they cannot better support VCRoriented service in heterogeneous environment having clients using free VCR controls. Despite the remarkable popularity in VoD systems, there exist no prior work that studies the performance gap between different prefetching strategies. In this paper, we analyze and understand the performance of different prefetching strategies. Our analytical characterization brings us not only a better understanding of several fundamental tradeoffs in prefetching strategies, but also important insights on the design of P2P VoD system. On the basis of this analysis, we finally proposed a cooperative prefetching strategy called "cooching". In this strategy, the requested segments in VCR interactivities are prefetched into session beforehand using the information collected through gossips. We evaluate our strategy through extensive simulations. The results indicate that the proposed strategy outperforms the existing prefetching mechanisms.
Class Based Admission Control by Complete Partitioning -Video on Demand Server
Venue: arXiv cs.NI 2010
Year: 2010

In the next generation network (NGN) environment specific consideration is on bandwidth minimization, because this reduces the cost of network. In response to the growing market demand for multimedia traffic transmission, NGN concept has been produced. The next generation network provides multimedia services over high speed networks, which supports DVD quality video on demand. Although it has numerous advantages, more exploration of the large-scale deployment video on demand is still needed. The focus of the research presented in this paper is a class based admission control by the complete partitioning of the video on demand server. In this paper we present analytically and by simulation how the blockage probability of the server significantly affects the on demand video request and the service. We also present how the blockage probability affects the performance of the video on demand server.
Power-Efficient Ultra-Wideband Waveform Design Considering Radio Channel Effects
Venue: arXiv cs.IT 2010
Year: 2010

This paper presents a power-efficient mask-constrained ultra-wideband (UWB) waveform design with radio channel effects taken into consideration. Based on a finite impulse response (FIR) filter, we develop a convex optimization model with respect to the autocorrelation of the filter coefficients to optimize the transmitted signal power spectrum, subject to a regulatory emission mask. To improve power efficiency, effects of transmitter radio frequency (RF) components are included in the optimization of the transmitter-output waveform, and radio propagation effects are considered for optimizing at the receiver. Optimum coefficients of the FIR filter are obtained through spectral factorization of their autocorrelations. Simulation results show that the proposed method is able to maximize the transmitted UWB signal power under mask constraints set by regulatory authorities, while mitigating the power loss caused by channel attenuations.
The Cerny conjecture for one-cluster automata with prime length cycle
Venue: arXiv cs.FL 2010
Year: 2010

We prove the Cerny conjecture for one-cluster automata with prime length cycle. Consequences are given for the hybrid Road-coloring-Cerny conjecture for digraphs with a proper cycle of prime length.
MLET: A Power Efficient Approach for TCAM Based, IP Lookup Engines in Internet Routers
Venue: arXiv cs.NI 2010
Year: 2010

Routers are one of the important entities in computer networks specially the Internet. Forwarding IP packets is a valuable and vital function in Internet routers. Routers extract destination IP address from packets and lookup those addresses in their own routing table. This task is called IP lookup. Internet address lookup is a challenging problem due to the increasing routing table sizes. Ternary Content-Addressable Memories (TCAMs) are becoming very popular for designing high-throughput address lookup-engines on routers: they are fast, cost-effective and simple to manage. Despite the TCAMs speed, their high power consumption is their major drawback. In this paper, Multilevel Enabling Technique (MLET), a power efficient TCAM based hardware architecture has been proposed. This scheme is employed after an Espresso-II minimization algorithm to achieve lower power consumption. The performance evaluation of the proposed approach shows that it can save considerable amount of routing table's power consumption.
Simulations of Weighted Tree Automata
Venue: arXiv cs.FL 2010
Year: 2010

Simulations of weighted tree automata (wta) are considered. It is shown how such simulations can be decomposed into simpler functional and dual functional simulations also called forward and backward simulations. In addition, it is shown in several cases (fields, commutative rings, Noetherian semirings, semiring of natural numbers) that all equivalent wta M and N can be joined by a finite chain of simulations. More precisely, in all mentioned cases there exists a single wta that simulates both M and N. Those results immediately yield decidability of equivalence provided that the semiring is finitely (and effectively) presented.
On a new class of additive (splitting) operator-difference schemes
Venue: arXiv cs.NA 2010
Year: 2010

Many applied time-dependent problems are characterized by an additive representation of the problem operator. Additive schemes are constructed using such a splitting and associated with the transition to a new time level on the basis of the solution of more simple problems for the individual operators in the additive decomposition. We consider a new class of additive schemes for problems with additive representation of the operator at the time derivative. In this paper we construct and study the vector operator-difference schemes, which are characterized by a transition from one initial the evolution equation to a system of such equations.
Modelling Nonlinear Sequence Generators in terms of Linear Cellular Automata
Venue: arXiv cs.CR 2010
Year: 2010

In this work, a wide family of LFSR-based sequence generators, the so-called Clock-Controlled Shrinking Generators (CCSGs), has been analyzed and identified with a subset of linear Cellular Automata (CA). In fact, a pair of linear models describing the behavior of the CCSGs can be derived. The algorithm that converts a given CCSG into a CA-based linear model is very simple and can be applied to CCSGs in a range of practical interest. The linearity of these cellular models can be advantageously used in two different ways: (a) for the analysis and/or cryptanalysis of the CCSGs and (b) for the reconstruction of the output sequence obtained from this kind of generators.
Typical Sequences for Polish Alphabets
Venue: arXiv cs.IT 2010
Year: 2010

The notion of typical sequences plays a key role in the theory of information. Central to the idea of typicality is that a sequence $x_1, x_2, ..., x_n$ that is $P_X$-typical should, loosely speaking, have an empirical distribution that is in some sense close to the distribution $P_X$. The two most common notions of typicality are that of strong (letter) typicality and weak (entropy) typicality. While weak typicality allows one to apply many arguments that can be made with strongly typical arguments, some arguments for strong typicality cannot be generalized to weak typicality. In this paper, we consider an alternate definition of typicality, namely one based on the weak* topology and that is applicable to Polish alphabets (which includes $\reals^n$). This notion is a generalization of strong typicality in the sense that it degenerates to strong typicality in the finite alphabet case, and can also be applied to mixed and continuous distributions. Furthermore, it is strong enough to prove a Markov lemma, and thus can be used to directly prove a more general class of results than weak typicality. As an example of this technique, we directly prove achievability for Gel'fand-Pinsker channels with input constraints for a large class of alphabets and channels without first proving a finite alphabet result and then resorting to delicate quantization arguments. While this large class does not include Gaussian distributions with power constraints, it is shown to be straightforward to recover this case by considering a sequence of truncated Gaussian distributions.
Classical BI: Its Semantics and Proof Theory
Venue: arXiv cs.LO 2010
Year: 2010

We present Classical BI (CBI), a new addition to the family of bunched logics which originates in O'Hearn and Pym's logic of bunched implications BI. CBI differs from existing bunched logics in that its multiplicative connectives behave classically rather than intuitionistically (including in particular a multiplicative version of classical negation). At the semantic level, CBI-formulas have the normal bunched logic reading as declarative statements about resources, but its resource models necessarily feature more structure than those for other bunched logics; principally, they satisfy the requirement that every resource has a unique dual. At the proof-theoretic level, a very natural formalism for CBI is provided by a display calculus à la Belnap, which can be seen as a generalisation of the bunched sequent calculus for BI. In this paper we formulate the aforementioned model theory and proof theory for CBI, and prove some fundamental results about the logic, most notably completeness of the proof theory with respect to the semantics.
Fastest Distributed Consensus Averaging Problem on Perfect and Complete n-ary Tree networks
Venue: arXiv cs.IT 2010
Year: 2010

Solving fastest distributed consensus averaging problem (i.e., finding weights on the edges to minimize the second-largest eigenvalue modulus of the weight matrix) over networks with different topologies is one of the primary areas of research in the field of sensor networks and one of the well known networks in this issue is tree network. Here in this work we present analytical solution for the problem of fastest distributed consensus averaging algorithm by means of stratification and semidefinite programming, for two particular types of tree networks, namely perfect and complete n-ary tree networks. Our method in this paper is based on convexity of fastest distributed consensus averaging problem, and inductive comparing of the characteristic polynomials initiated by slackness conditions in order to find the optimal weights. Also the optimal weights for the edges of certain types of branches such as perfect and complete n-ary tree branches are determined independently of rest of the network.
Low Rank Matrix-Valued Chernoff Bounds and Approximate Matrix Multiplication
Venue: arXiv cs.DS 2010
Year: 2010

In this paper we develop algorithms for approximating matrix multiplication with respect to the spectral norm. Let A\in{\RR^{n\times m}} and B\in\RR^{n \times p} be two matrices and \eps>0. We approximate the product A^\top B using two down-sampled sketches, \tilde{A}\in\RR^{t\times m} and \tilde{B}\in\RR^{t\times p}, where t\ll n such that \norm{\tilde{A}^\top \tilde{B} - A^\top B} \leq \eps \norm{A}\norm{B} with high probability. We use two different sampling procedures for constructing \tilde{A} and \tilde{B}; one of them is done by i.i.d. non-uniform sampling rows from A and B and the other is done by taking random linear combinations of their rows. We prove bounds that depend only on the intrinsic dimensionality of A and B, that is their rank and their stable rank; namely the squared ratio between their Frobenius and operator norm. For achieving bounds that depend on rank we employ standard tools from high-dimensional geometry such as concentration of measure arguments combined with elaborate \eps-net constructions. For bounds that depend on the smaller parameter of stable rank this technology itself seems weak. However, we show that in combination with a simple truncation argument is amenable to provide such bounds. To handle similar bounds for row sampling, we develop a novel matrix-valued Chernoff bound inequality which we call low rank matrix-valued Chernoff bound. Thanks to this inequality, we are able to give bounds that depend only on the stable rank of the input matrices...
Evolving Genes to Balance a Pole
Venue: arXiv cs.AI 2010
Year: 2010

We discuss how to use a Genetic Regulatory Network as an evolutionary representation to solve a typical GP reinforcement problem, the pole balancing. The network is a modified version of an Artificial Regulatory Network proposed a few years ago, and the task could be solved only by finding a proper way of connecting inputs and outputs to the network. We show that the representation is able to generalize well over the problem domain, and discuss the performance of different models of this kind.
Upper oriented chromatic number of undirected graphs and oriented colorings of product graphs
Venue: arXiv cs.DM 2010
Year: 2010

The oriented chromatic number of an oriented graph $\vec G$ is the minimum order of an oriented graph $\vev H$ such that $\vec G$ admits a homomorphism to $\vev H$. The oriented chromatic number of an undirected graph $G$ is then the greatest oriented chromatic number of its orientations. In this paper, we introduce the new notion of the upper oriented chromatic number of an undirected graph $G$, defined as the minimum order of an oriented graph $\vev U$ such that every orientation $\vec G$ of $G$ admits a homomorphism to $\vec U$. We give some properties of this parameter, derive some general upper bounds on the ordinary and upper oriented chromatic numbers of Cartesian, strong, direct and lexicographic products of graphs, and consider the particular case of products of paths.