OpenRaiser/Intern-Atlas huggingface dataset:
Evolutionary Hessian Learning: Forced Optimal Covariance Adaptive Learning (FOCAL)
Venue: arXiv cs.NE 2011
Year: 2011

The Covariance Matrix Adaptation Evolution Strategy (CMA-ES) has been the most successful Evolution Strategy at exploiting covariance information; it uses a form of Principle Component Analysis which, under certain conditions, is suggested to converge to the correct covariance matrix, formulated as the inverse of the mathematically well-defined Hessian matrix. However, in practice, there exist conditions where CMA-ES converges to the global optimum (accomplishing its primary goal) while it does not learn the true covariance matrix (missing an auxiliary objective), likely due to step-size deficiency. These circumstances can involve high-dimensional landscapes with large condition numbers. This paper introduces a novel technique entitled Forced Optimal Covariance Adaptive Learning (FOCAL), with the explicit goal of determining the Hessian at the global basin of attraction. It begins by introducing theoretical foundations to the inverse relationship between the learned covariance and the Hessian matrices. FOCAL is then introduced and demonstrated to retrieve the Hessian matrix with high fidelity on both model landscapes and experimental Quantum Control systems, which are observed to possess a non-separable, non-quadratic search landscape. The recovered Hessian forms are corroborated by physical knowledge of the systems. This study constitutes an example for Natural Computing successfully serving other branches of natural sciences, and introducing at the same time a powerful generic method for any high-dimensional continuous search seeking landscape information.
Intractability of the Minimum-Flip Supertree problem and its variants
Venue: arXiv cs.CC 2011
Year: 2011

Computing supertrees is a central problem in phylogenetics. The supertree method that is by far the most widely used today was introduced in 1992 and is called Matrix Representation with Parsimony analysis (MRP). Matrix Representation using Flipping (MRF)}, which was introduced in 2002, is an interesting variant of MRP: MRF is arguably more relevant that MRP and various efficient implementations of MRF have been presented. From a theoretical point of view, implementing MRF or MRP is solving NP-hard optimization problems. The aim of this paper is to study the approximability and the fixed-parameter tractability of the optimization problem corresponding to MRF, namely Minimum-Flip Supertree. We prove strongly negative results.
Selective data collection in vehicular networks for traffic control applications
Venue: arXiv cs.NI 2011
Year: 2011

Vehicular sensor network (VSN) is an emerging technology, which combines wireless communication offered by vehicular ad hoc networks (VANET) with sensing devices installed in vehicles. VSN creates a huge opportunity to extend the road-side sensor infrastructure of existing traffic control systems. The efficient use of the wireless communication medium is one of the basic issues in VSN applications development. This paper introduces a novel method of selective data collection for traffic control applications, which provides a significant reduction in data amounts transmitted through VSN. The underlying idea is to detect the necessity of data transfers on the basis of uncertainty determination of the traffic control decisions. According to the proposed approach, sensor data are transmitted from vehicles to the control node only at selected time moments. Data collected in VSN are processed using on-line traffic simulation technique, which enables traffic flow prediction, performance evaluation of control strategies and uncertainty estimation. If precision of the resulting information is insufficient, the optimal control strategy cannot be derived without ambiguity. As a result the control decision becomes uncertain and it is a signal informing that new traffic data from VSN are necessary to provide more precise prediction and to reduce the uncertainty of decision. The proposed method can be applied in traffic control systems of different types e.g. traffic signals, variable speed limits, and dynamic route guidance. The effectiveness of this method is illustrated in an experimental study on traffic control at signalised intersection.
Using Artificial Bee Colony Algorithm for MLP Training on Earthquake Time Series Data Prediction
Venue: arXiv cs.NE 2011
Year: 2011

Nowadays, computer scientists have shown the interest in the study of social insect's behaviour in neural networks area for solving different combinatorial and statistical problems. Chief among these is the Artificial Bee Colony (ABC) algorithm. This paper investigates the use of ABC algorithm that simulates the intelligent foraging behaviour of a honey bee swarm. Multilayer Perceptron (MLP) trained with the standard back propagation algorithm normally utilises computationally intensive training algorithms. One of the crucial problems with the backpropagation (BP) algorithm is that it can sometimes yield the networks with suboptimal weights because of the presence of many local optima in the solution space. To overcome ABC algorithm used in this work to train MLP learning the complex behaviour of earthquake time series data trained by BP, the performance of MLP-ABC is benchmarked against MLP training with the standard BP. The experimental result shows that MLP-ABC performance is better than MLP-BP for time series data.
Transformation Networks: How Innovation and the Availability of Technology can Increase Economic Performance
Venue: arXiv cs.SI 2011
Year: 2011

A transformation network describes how one set of resources can be transformed into another via technological processes. Transformation networks in economics are useful because they can highlight areas for future innovations, both in terms of new products, new production techniques, or better efficiency. They also make it easy to detect areas where an economy might be fragile. In this paper, we use computational simulations to investigate how the density of a transformation network affects the economic performance, as measured by the gross domestic product (GDP), of an artificial economy. Our results show that on average, the GDP of our economy increases as the density of the transformation network increases. We also find that while the average performance increases, the maximum possible performance decreases and the minimum possible performance increases.
Greedy routing on networks of mobile agents
Venue: arXiv cs.NI 2011
Year: 2011

In this paper, we design a greedy routing on networks of mobile agents. In the greedy routing algorithm, every time step a packet in agent $i$ is delivered to the agent $j$ whose distance from the destination is shortest among searched neighbors of agent $i$. Based on the greedy routing, we study the traffic dynamics and traffic-driven epidemic spreading on networks of mobile agents. We find that the transportation capacity of networks and the epidemic threshold increase as the communication radius increases. For moderate moving speed, the transportation capacity of networks is the highest and the epidemic threshold maintains a large value. These results can help controlling the traffic congestion and epidemic spreading on mobile networks.
NACS: non-overlapping AP's caching scheme to reduce handoff in 802.11 wireless LAN
Venue: arXiv cs.NI 2011
Year: 2011

With the escalation of the IEEE 802.11 based wireless networks, voice over IP and analogous applications are also used over wireless networks. Recently, the wireless LAN systems are spaciously deployed for public Internet services. In public wireless LAN systems, reliable user authentication and mobility support are indispensable issues. When a mobile device budges out the range of one access point (AP) and endeavor to connect to new AP, it performs handoff. Contemporarily, PNC and SNC were proposed to propagate the MN context to the entire neighboring AP's on the wireless network with the help of neighbor graph. In this paper, we proposed a non-overlapping AP's caching scheme (NACS), which propagates the mobile node context to those AP's which do not overlap with the current AP. To capture the topology of non-overlapping AP's in the wireless network, non-overlapping graph (NOG) is generated at each AP. Simulation results shows that NACS reduces the signaling cost of propagating the MN context to the neighbor AP's in the wireless network.
Computing the Matched Filter in Linear Time
Venue: arXiv cs.IT 2011
Year: 2011

A fundamental problem in wireless communication is the time-frequency shift (TFS) problem: Find the time-frequency shift of a signal in a noisy environment. The shift is the result of time asynchronization of a sender with a receiver, and of non-zero speed of a sender with respect to a receiver. A classical solution of a discrete analog of the TFS problem is called the matched filter algorithm. It uses a pseudo-random waveform S(t) of the length p, and its arithmetic complexity is O(p^{2} \cdot log (p)), using fast Fourier transform. In these notes we introduce a novel approach of designing new waveforms that allow faster matched filter algorithm. We use techniques from group representation theory to design waveforms S(t), which enable us to introduce two fast matched filter (FMF) algorithms, called the flag algorithm, and the cross algorithm. These methods solve the TFS problem in O(p\cdot log (p)) operations. We discuss applications of the algorithms to mobile communication, GPS, and radar.
Cryptanalyzing a chaos-based image encryption algorithm using alternate structure
Venue: arXiv cs.CR 2011
Year: 2011

Recently, a chaos-based image encryption algorithm using alternate structure (IEAS) was proposed. This paper focuses on differential cryptanalysis of the algorithm and finds that some properties of IEAS can support a differential attack to recover equivalent secret key with a little small number of known plain-images. Detailed approaches of the cryptanalysis for cryptanalyzing IEAS of the lower round number are presented and the breaking method can be extended to the case of higher round number. Both theoretical analysis and experiment results are provided to support vulnerability of IEAS against differential attack. In addition, some other security defects of IEAS, including insensitivity with respect to changes of plain-images and insufficient size of key space, are also reported.
Analysis of Bitcoin Pooled Mining Reward Systems
Venue: arXiv cs.DC 2011
Year: 2011

In this paper we describe the various scoring systems used to calculate rewards of participants in Bitcoin pooled mining, explain the problems each were designed to solve and analyze their respective advantages and disadvantages.
Comments on "Capacity with explicit delay guarantees for generic sources over correlated Rayleigh channel"
Venue: arXiv cs.NI 2011
Year: 2011

We address a major flaw in the abovementioned paper, which proposes to calculate effective capacity of random channels by the use of central limit theorem. We analytically show that the authors are incorrect in finding the effective capacity by first taking the limit of cumulative random process rather than taking the limit of moment generating function of the same process. We later quantify our results over a correlated ON-OFF process.
Tight lower bounds for online labeling problem
Venue: arXiv cs.DS 2011
Year: 2011

We consider the file maintenance problem (also called the online labeling problem) in which n integer items from the set {1,...,r} are to be stored in an array of size m >= n. The items are presented sequentially in an arbitrary order, and must be stored in the array in sorted order (but not necessarily in consecutive locations in the array). Each new item must be stored in the array before the next item is received. If r<=m then we can simply store item j in location j but if r>m then we may have to shift the location of stored items to make space for a newly arrived item. The algorithm is charged each time an item is stored in the array, or moved to a new location. The goal is to minimize the total number of such moves done by the algorithm. This problem is non-trivial when n=<m<r. In the case that m=Cn for some C>1, algorithms for this problem with cost O(log(n)^2) per item have been given [IKR81, Wil92, BCD+02]. When m=n, algorithms with cost O(log(n)^3) per item were given [Zha93, BS07]. In this paper we prove lower bounds that show that these algorithms are optimal, up to constant factors. Previously, the only lower bound known for this range of parameters was a lower bound of Ω(log(n)^2) for the restricted class of smooth algorithms [DSZ05a, Zha93]. We also provide an algorithm for the sparse case: If the number of items is polylogarithmic in the array size then the problem can be solved in amortized constant time per item.
Testing $k$-Modal Distributions: Optimal Algorithms via Reductions
Venue: arXiv cs.DS 2011
Year: 2011

We give highly efficient algorithms, and almost matching lower bounds, for a range of basic statistical problems that involve testing and estimating the L_1 distance between two k-modal distributions $p$ and $q$ over the discrete domain $\{1,\dots,n\}$. More precisely, we consider the following four problems: given sample access to an unknown k-modal distribution $p$, Testing identity to a known or unknown distribution: 1. Determine whether $p = q$ (for an explicitly given k-modal distribution $q$) versus $p$ is $\eps$-far from $q$; 2. Determine whether $p=q$ (where $q$ is available via sample access) versus $p$ is $\eps$-far from $q$; Estimating $L_1$ distance ("tolerant testing'') against a known or unknown distribution: 3. Approximate $d_{TV}(p,q)$ to within additive $\eps$ where $q$ is an explicitly given k-modal distribution $q$; 4. Approximate $d_{TV}(p,q)$ to within additive $\eps$ where $q$ is available via sample access. For each of these four problems we give sub-logarithmic sample algorithms, that we show are tight up to additive $\poly(k)$ and multiplicative $\polylog\log n+\polylog k$ factors. Thus our bounds significantly improve the previous results of \cite{BKR:04}, which were for testing identity of distributions (items (1) and (2) above) in the special cases k=0 (monotone distributions) and k=1 (unimodal distributions) and required $O((\log n)^3)$ samples. As our main conceptual contribution, we introduce a new reduction-based approach for distribution-testing problems that lets us obtain all the above results in a unified way. Roughly speaking, this approach enables us to transform various distribution testing problems for k-modal distributions over $\{1,\dots,n\}$ to the corresponding distribution testing problems for unrestricted distributions over a much smaller domain $\{1,\dots,\ell\}$ where $\ell = O(k \log n).$
Web Accessibility - A timely recognized challenge
Venue: arXiv cs.CY 2011
Year: 2011

Web Accessibility for disabled people has posed a challenge to the civilized societies that claim to uphold the principles of equal opportunity and nondiscrimination. Certain concrete measures have been taken to narrow down the digital divide between normal and disabled users of Internet technology. The efforts have resulted in enactment of legislations and laws and mass awareness about the discriminatory nature of the accessibility issue, besides the efforts have resulted in the development of commensurate technological tools to develop and test the Web accessibility. World Wide Web consortium's (W3C) Web Accessibility Initiative (WAI) has framed a comprehensive document comprising of set of guidelines to make the Web sites accessible to the users with disabilities. This paper is about the issues and aspects surrounding Web Accessibility. The details and scope are kept limited to comply with the aim of the paper which is to create awareness and to provide basis for in-depth investigation.
Modeling overall energy consumption in Wireless Sensor Networks
Venue: arXiv cs.NI 2011
Year: 2011

Minimizing the energy consumption of a wireless sensor network application is crucial for effective realization of the intended application in terms of cost, lifetime, and functionality. However, the minimizing task is hardly possible as no overall energy cost function is available for optimization. Optimizing a specific component of the total energy cost does not help in reducing the total energy cost as this reduction may be negated by an increase in the energy consumption of other components of the application. Recently we proposed Hierarchy Energy Driven Architecture as a robust architecture that takes into account all principal energy constituents of wireless sensor network applications. Based on the proposed architecture, this paper presents a single overall model and proposes a feasible formulation to express the overall energy consumption of a generic wireless sensor network application in terms of its energy constituents. The formulation offers a concrete expression for evaluating the performance of a wireless sensor network application, optimizing its constituent's operations, and designing more energy-efficient applications. The paper also presents simulation results to demonstrate the feasibility of our model and energy formulation
Query Answering under Matching Dependencies for Data Cleaning: Complexity and Algorithms
Venue: arXiv cs.DB 2011
Year: 2011

Matching dependencies (MDs) have been recently introduced as declarative rules for entity resolution (ER), i.e. for identifying and resolving duplicates in relational instance $D$. A set of MDs can be used as the basis for a possibly non-deterministic mechanism that computes a duplicate-free instance from $D$. The possible results of this process are the clean, "minimally resolved instances" (MRIs). There might be several MRIs for $D$, and the "resolved answers" to a query are those that are shared by all the MRIs. We investigate the problem of computing resolved answers. We look at various sets of MDs, developing syntactic criteria for determining (in)tractability of the resolved answer problem, including a dichotomy result. For some tractable classes of MDs and conjunctive queries, we present a query rewriting methodology that can be used to retrieve the resolved answers. We also investigate connections with "consistent query answering", deriving further tractability results for MD-based ER.
Random Context and Semi-Conditional Insertion-Deletion Systems
Venue: arXiv cs.FL 2011
Year: 2011

In this article we introduce the operations of insertion and deletion working in a random-context and semi-conditional manner. We show that the conditional use of rules strictly increase the computational power. In the case of semi-conditional insertion-deletion systems context-free insertion and deletion rules of one symbol are sufficient to get the computational completeness. In the random context case our results expose an asymmetry between the computational power of insertion and deletion rules: systems of size $(2,0,0; 1,1,0)$ are computationally complete, while systems of size $(1,1,0;2,0,0)$ (and more generally of size $(1,1,0;p,1,1)$) are not. This is particularly interesting because other control mechanisms like graph-control or matrix control used together with insertion-deletion systems do not present such asymmetry.
Your browsing behavior for a Big Mac: Economics of Personal Information Online
Venue: arXiv cs.HC 2011
Year: 2011

Most online services (Google, Facebook etc.) operate by providing a service to users for free, and in return they collect and monetize personal information (PI) of the users. This operational model is inherently economic, as the "good" being traded and monetized is PI. This model is coming under increased scrutiny as online services are moving to capture more PI of users, raising serious privacy concerns. However, little is known on how users valuate different types of PI while being online, as well as the perceptions of users with regards to exploitation of their PI by online service providers. In this paper, we study how users valuate different types of PI while being online, while capturing the context by relying on Experience Sampling. We were able to extract the monetary value that 168 participants put on different pieces of PI. We find that users value their PI related to their offline identities more (3 times) than their browsing behavior. Users also value information pertaining to financial transactions and social network interactions more than activities like search and shopping. We also found that while users are overwhelmingly in favor of exchanging their PI in return for improved online services, they are uncomfortable if these same providers monetize their PI.
On the optimal frequency selectivity to maximize multiuser diversity in an OFDMA scheduling system
Venue: arXiv cs.IT 2011
Year: 2011

We consider an orthogonal frequency division multiple access (OFDMA) scheduling system. A scheduling unit block consists of contiguous multiple subcarriers. Users are scheduled based on their block average throughput in a proportional fair way. The multiuser diversity gain increases with the degree and dynamic range of channel fluctuations. %Lack of diversity in a limited frequency selective channel may decrease the sum rate. However, a decrease of the block average throughput in a too much selective channel may lessen the sum rate as well. In this paper, we first study optimal channel selectivity in view of maximizing the maximum of the block average throughput of an arbitrary user. Based on this study, we then propose a method to determine a per-user optimal cyclic delay when cyclic delay diversity (CDD) is used to enhance the sum rate by increasing channel selectivity for a limited fluctuating channel. We show that the proposed technique achieves better performance than a conventional fixed cyclic delay scheme and that the throughput is very close to the optimal sum rate possible with CDD.
Document Clustering based on Topic Maps
Venue: arXiv cs.IR 2011
Year: 2011

Importance of document clustering is now widely acknowledged by researchers for better management, smart navigation, efficient filtering, and concise summarization of large collection of documents like World Wide Web (WWW). The next challenge lies in semantically performing clustering based on the semantic contents of the document. The problem of document clustering has two main components: (1) to represent the document in such a form that inherently captures semantics of the text. This may also help to reduce dimensionality of the document, and (2) to define a similarity measure based on the semantic representation such that it assigns higher numerical values to document pairs which have higher semantic relationship. Feature space of the documents can be very challenging for document clustering. A document may contain multiple topics, it may contain a large set of class-independent general-words, and a handful class-specific core-words. With these features in mind, traditional agglomerative clustering algorithms, which are based on either Document Vector model (DVM) or Suffix Tree model (STC), are less efficient in producing results with high cluster quality. This paper introduces a new approach for document clustering based on the Topic Map representation of the documents. The document is being transformed into a compact form. A similarity measure is proposed based upon the inferred information through topic maps data and structures. The suggested method is implemented using agglomerative hierarchal clustering and tested on standard Information retrieval (IR) datasets. The comparative experiment reveals that the proposed approach is effective in improving the cluster quality.