OpenRaiser/Intern-Atlas huggingface dataset:
A Multi-Channel Diversity Based MAC Protocol for Power-Constrained Cognitive Ad Hoc Networks
Venue: arXiv cs.IT 2011
Year: 2011

One of the major challenges in the medium access control (MAC) protocol design over cognitive Ad Hoc networks (CAHNs) is how to efficiently utilize multiple opportunistic channels, which vary dynamically and are subject to limited power resources. To overcome this challenge, in this paper we first propose a novel diversity technology called \emph{Multi-Channel Diversity} (MCD), allowing each secondary node to use multiple channels simultaneously with only one radio per node under the upperbounded power. Using the proposed MCD, we develop a MCD based MAC (MCD-MAC) protocol, which can efficiently utilize available channel resources through joint power-channel allocation. Particularly, we convert the joint power-channel allocation to the Multiple-Choice Knapsack Problem, such that we can obtain the optimal transmission strategy to maximize the network throughput through dynamic programming. Simulation results show that our proposed MCD-MAC protocol can significantly increase the network throughput as compared to the existing protocols.
Semantic Solutions to Program Analysis Problems
Venue: arXiv cs.PL 2011
Year: 2011

Problems in program analysis can be solved by developing novel program semantics and deriving abstractions conventionally. For over thirty years, higher-order program analysis has been sold as a hard problem. Its solutions have required ingenuity and complex models of approximation. We claim that this difficulty is due to premature focus on abstraction and propose a new approach that emphasizes semantics. Its simplicity enables new analyses that are beyond the current state of the art.
Detecting emergent processes in cellular automata with excess information
Venue: arXiv cs.IT 2011
Year: 2011

Many natural processes occur over characteristic spatial and temporal scales. This paper presents tools for (i) flexibly and scalably coarse-graining cellular automata and (ii) identifying which coarse-grainings express an automaton's dynamics well, and which express its dynamics badly. We apply the tools to investigate a range of examples in Conway's Game of Life and Hopfield networks and demonstrate that they capture some basic intuitions about emergent processes. Finally, we formalize the notion that a process is emergent if it is better expressed at a coarser granularity.
Online Assignment Algorithms for Dynamic Bipartite Graphs
Venue: arXiv cs.DC 2011
Year: 2011

This paper analyzes the problem of assigning weights to edges incrementally in a dynamic complete bipartite graph consisting of producer and consumer nodes. The objective is to minimize the overall cost while satisfying certain constraints. The cost and constraints are functions of attributes of the edges, nodes and online service requests. Novelty of this work is that it models real-time distributed resource allocation using an approach to solve this theoretical problem. This paper studies variants of this assignment problem where the edges, producers and consumers can disappear and reappear or their attributes can change over time. Primal-Dual algorithms are used for solving these problems and their competitive ratios are evaluated.
Dynamic Interference Mitigation for Generalized Partially Connected Quasi-static MIMO Interference Channel
Venue: arXiv cs.IT 2011
Year: 2011

Recent works on MIMO interference channels have shown that interference alignment can significantly increase the achievable degrees of freedom (DoF) of the network. However, most of these works have assumed a fully connected interference graph. In this paper, we investigate how the partial connectivity can be exploited to enhance system performance in MIMO interference networks. We propose a novel interference mitigation scheme which introduces constraints for the signal subspaces of the precoders and decorrelators to mitigate "many" interference nulling constraints at a cost of "little" freedoms in precoder and decorrelator design so as to extend the feasibility region of the interference alignment scheme. Our analysis shows that the proposed algorithm can significantly increase system DoF in symmetric partially connected MIMO interference networks. We also compare the performance of the proposed scheme with various baselines and show via simulations that the proposed algorithms could achieve significant gain in the system performance of randomly connected interference networks.
Recalling of Images using Hopfield Neural Network Model
Venue: arXiv cs.NE 2011
Year: 2011

In the present paper, an effort has been made for storing and recalling images with Hopfield Neural Network Model of auto-associative memory. Images are stored by calculating a corresponding weight matrix. Thereafter, starting from an arbitrary configuration, the memory will settle on exactly that stored image, which is nearest to the starting configuration in terms of Hamming distance. Thus given an incomplete or corrupted version of a stored image, the network is able to recall the corresponding original image. The storing of the objects has been performed according to the Hopfield algorithm explained below. Once the net has completely learnt this set of input patterns, a set of testing patterns containing degraded images will be given to the net. Then the Hopfield net will tend to recall the closest matching pattern for the given degraded image. The simulated results show that Hopfield model is the best for storing and recalling images.
WiMAX Based 60 GHz Millimeter-Wave Communication for Intelligent Transport System Applications
Venue: arXiv cs.IT 2011
Year: 2011

With the successful worldwide deployment of 3rd generation mobile communication, security aspects are ensured partly. Researchers are now looking for 4G mobile for its deployment with high data rate, enhanced security and reliability so that world should look for CALM, Continuous Air interface for Long and Medium range communication. This CALM will be a reliable high data rate secured mobile communication to be deployed for car to car communication (C2C) for safety application. This paper reviewed the WiMAX ,& 60 GHz RF carrier for C2C. The system is tested at SMIT laboratory with multimedia transmission and reception. With proper deployment of this 60 GHz system on vehicles, the existing commercial products for 802.11P will be required to be replaced or updated soon .
Rapid Learning with Stochastic Focus of Attention
Venue: arXiv cs.LG 2011
Year: 2011

We present a method to stop the evaluation of a decision making process when the result of the full evaluation is obvious. This trait is highly desirable for online margin-based machine learning algorithms where a classifier traditionally evaluates all the features for every example. We observe that some examples are easier to classify than others, a phenomenon which is characterized by the event when most of the features agree on the class of an example. By stopping the feature evaluation when encountering an easy to classify example, the learning algorithm can achieve substantial gains in computation. Our method provides a natural attention mechanism for learning algorithms. By modifying Pegasos, a margin-based online learning algorithm, to include our attentive method we lower the number of attributes computed from $n$ to an average of $O(\sqrt{n})$ features without loss in prediction accuracy. We demonstrate the effectiveness of Attentive Pegasos on MNIST data.
A Scalable Module System
Venue: arXiv cs.LO 2011
Year: 2011

Symbolic and logic computation systems ranging from computer algebra systems to theorem provers are finding their way into science, technology, mathematics and engineering. But such systems rely on explicitly or implicitly represented mathematical knowledge that needs to be managed to use such systems effectively. While mathematical knowledge management (MKM) "in the small" is well-studied, scaling up to large, highly interconnected corpora remains difficult. We hold that in order to realize MKM "in the large", we need representation languages and software architectures that are designed systematically with large-scale processing in mind. Therefore, we have designed and implemented the MMT language -- a module system for mathematical theories. MMT is designed as the simplest possible language that combines a module system, a foundationally uncommitted formal semantics, and web-scalable implementations. Due to a careful choice of representational primitives, MMT allows us to integrate existing representation languages for formal mathematical knowledge in a simple, scalable formalism. In particular, MMT abstracts from the underlying mathematical and logical foundations so that it can serve as a standardized representation format for a formal digital library. Moreover, MMT systematically separates logic-dependent and logic-independent concerns so that it can serve as an interface layer between computation systems and MKM systems.
Secure Position Verification for Wireless Sensor Networks in Noisy Channels
Venue: arXiv cs.DC 2011
Year: 2011

Position verification in wireless sensor networks (WSNs) is quite tricky in presence of attackers (malicious sensor nodes), who try to break the verification protocol by reporting their incorrect positions (locations) during the verification stage. In the literature of WSNs, most of the existing methods of position verification have used trusted verifiers, which are in fact vulnerable to attacks by malicious nodes. They also depend on some distance estimation techniques, which are not accurate in noisy channels (mediums). In this article, we propose a secure position verification scheme for WSNs in noisy channels without relying on any trusted entities. Our verification scheme detects and filters out all malicious nodes from the network with very high probability.
Topics in Matrix Sampling Algorithms
Venue: arXiv cs.DS 2011
Year: 2011

We study three fundamental problems of Linear Algebra, lying in the heart of various Machine Learning applications, namely: 1)"Low-rank Column-based Matrix Approximation". We are given a matrix A and a target rank k. The goal is to select a subset of columns of A and, by using only these columns, compute a rank k approximation to A that is as good as the rank k approximation that would have been obtained by using all the columns; 2) "Coreset Construction in Least-Squares Regression". We are given a matrix A and a vector b. Consider the (over-constrained) least-squares problem of minimizing ||Ax-b||, over all vectors x in D. The domain D represents the constraints on the solution and can be arbitrary. The goal is to select a subset of the rows of A and b and, by using only these rows, find a solution vector that is as good as the solution vector that would have been obtained by using all the rows; 3) "Feature Selection in K-means Clustering". We are given a set of points described with respect to a large number of features. The goal is to select a subset of the features and, by using only this subset, obtain a k-partition of the points that is as good as the partition that would have been obtained by using all the features. We present novel algorithms for all three problems mentioned above. Our results can be viewed as follow-up research to a line of work known as "Matrix Sampling Algorithms". [Frieze, Kanna, Vempala, 1998] presented the first such algorithm for the Low-rank Matrix Approximation problem. Since then, such algorithms have been developed for several other problems, e.g. Graph Sparsification and Linear Equation Solving. Our contributions to this line of research are: (i) improved algorithms for Low-rank Matrix Approximation and Regression (ii) algorithms for a new problem domain (K-means Clustering).
On the cryptanalysis of the generalized simultaneous conjugacy search problem and the security of the Algebraic Eraser
Venue: arXiv cs.CR 2011
Year: 2011

The Algebraic Eraser (AE) is a cryptographic primitive that can be used to obscure information in certain algebraic cryptosystems. The Colored Burau Key Agreement Protocol (CBKAP), which is built on the AE, was introduced by I. Anshel, M. Anshel, D. Goldfeld, and S. Lemieux in 2006 as a protocol suitable for use on platforms with constrained computational resources, such as RFID and wireless sensors. In 2009 A. Myasnikov and A. Ushnakov proposed an attack on CBKAP that attempts to defeat the generalized simultaneous conjugacy search problem, which is the public-key computational problem underlying CBKAP. In this paper we investigate the effectiveness of this attack. Our findings are that success of the attack only comes from applying it to short keys, and that with appropriate keys the attack fails in 100% of cases and does not pose a threat against CBKAP. Moreover, the attack makes assumptions about CBKAP that do not hold in practical implementations, and thus does not represent a threat to the use of CBKAP in applications.
Interpreting Graph Cuts as a Max-Product Algorithm
Venue: arXiv cs.LG 2011
Year: 2011

The maximum a posteriori (MAP) configuration of binary variable models with submodular graph-structured energy functions can be found efficiently and exactly by graph cuts. Max-product belief propagation (MP) has been shown to be suboptimal on this class of energy functions by a canonical counterexample where MP converges to a suboptimal fixed point (Kulesza & Pereira, 2008). In this work, we show that under a particular scheduling and damping scheme, MP is equivalent to graph cuts, and thus optimal. We explain the apparent contradiction by showing that with proper scheduling and damping, MP always converges to an optimal fixed point. Thus, the canonical counterexample only shows the suboptimality of MP with a particular suboptimal choice of schedule and damping. With proper choices, MP is optimal.
Wireless MIMO Switching with Network Coding
Venue: arXiv cs.IT 2011
Year: 2011

In a generic switching problem, a switching pattern consists of a one-to-one mapping from a set of inputs to a set of outputs (i.e., a permutation). We propose and investigate a wireless switching framework in which a multi-antenna relay is responsible for switching traffic among a set of $N$ stations. We refer to such a relay as a MIMO switch. With beamforming and linear detection, the MIMO switch controls which stations are connected to which other stations. Each beamforming matrix realizes a permutation pattern among the stations. We refer to the corresponding permutation matrix as a switch matrix. By scheduling a set of different switch matrices, full connectivity among the stations can be established. In this paper, we focus on "fair switching" in which equal amounts of traffic are to be delivered for all $N(N-1)$ ordered pairs of stations. In particular, we investigate how the system throughput can be maximized. In general, for large $N$ the number of possible switch matrices (i.e., permutations) is huge, making the scheduling problem combinatorially challenging. We show that for the cases of N=4 and 5, only a subset of $N-1$ switch matrices need to be considered in the scheduling problem to achieve good throughput. We conjecture that this will be the case for large $N$ as well. This conjecture, if valid, implies that for practical purposes, fair-switching scheduling is not an intractable problem. We also investigate MIMO switching with physical-layer network coding in this paper. We find that it can improve throughput appreciably.
Excess entropy in natural language: present state and perspectives
Venue: arXiv cs.IT 2011
Year: 2011

We review recent progress in understanding the meaning of mutual information in natural language. Let us define words in a text as strings that occur sufficiently often. In a few previous papers, we have shown that a power-law distribution for so defined words (a.k.a. Herdan's law) is obeyed if there is a similar power-law growth of (algorithmic) mutual information between adjacent portions of texts of increasing length. Moreover, the power-law growth of information holds if texts describe a complicated infinite (algorithmically) random object in a highly repetitive way, according to an analogous power-law distribution. The described object may be immutable (like a mathematical or physical constant) or may evolve slowly in time (like cultural heritage). Here we reflect on the respective mathematical results in a less technical way. We also discuss feasibility of deciding to what extent these results apply to the actual human communication.
Testing Odd-Cycle-Freeness in Boolean Functions
Venue: arXiv cs.DS 2011
Year: 2011

Call a function f : F_2^n -> {0,1} odd-cycle-free if there are no x_1, ..., x_k in F_2^n with k an odd integer such that f(x_1) = ... = f(x_k) = 1 and x_1 + ... + x_k = 0. We show that one can distinguish odd-cycle-free functions from those eps-far from being odd-cycle-free by making poly(1/eps) queries to an evaluation oracle. To obtain this result, we use connections between basic Fourier analysis and spectral graph theory to show that one can reduce testing odd-cycle-freeness of Boolean functions to testing bipartiteness of dense graphs. Our work forms part of a recent sequence of works that shows connections between testability of properties of Boolean functions and of graph properties. We also prove that there is a canonical tester for odd-cycle-freeness making poly(1/eps) queries, meaning that the testing algorithm operates by picking a random linear subspace of dimension O(log 1/eps) and then checking if the restriction of the function to the subspace is odd-cycle-free or not. The test is analyzed by studying the effect of random subspace restriction on the Fourier coefficients of a function. Our work implies that testing odd-cycle-freeness using a canonical tester instead of an arbitrary tester incurs no more than a polynomial blowup in the query complexity. The question of whether a canonical tester with polynomial blowup exists for all linear-invariant properties remains an open problem.
Evaluating the Efficiency of Asynchronous Systems with FASE
Venue: arXiv cs.LO 2011
Year: 2011

In this paper, we present FASE (Faster Asynchronous Systems Evaluation), a tool for evaluating the worst-case efficiency of asynchronous systems. The tool is based on some well-established results in the setting of a timed process algebra (PAFAS: a Process Algebra for Faster Asynchronous Systems). To show the applicability of FASE to concrete meaningful examples, we consider three implementations of a bounded buffer and use FASE to automatically evaluate their worst-case efficiency. We finally contrast our results with previous ones where the efficiency of the same implementations has already been considered.
Development of Active Pixel Photodiode Sensors for Gamma Camera Application
Venue: arXiv cs.OH 2011
Year: 2011

We designed new photodiodes sensors including current mirror amplifiers. These photodiodes have been fabricated using a CMOS 0.6 micrometers process from Austria Micro System (AMS). The Photodiode areas are respectiveley 1mm x 1mm and 0.4mm x 0.4mm with fill factor 98 % and total chip area is 2 square millimetres. The sensor pixels show a logarithmic response in illumination and are capable of detecting very low blue light (less than 0.5 lux) . These results allow to use our sensor in new Gamma Camera solid-state concept.
A Generic Signaling Framework for Seamless Mobility in Heterogeneous Wireless Networks
Venue: arXiv cs.NI 2011
Year: 2011

In recent years several wireless communication standards have been developed and more are expected, each with different scope in terms of spatial coverage, radio access capabilities, and mobility support. Heterogeneous networks combine multiple of these radio interfaces both in network infrastructure and in user equipment which requires a new multi-radio framework, enabling mobility and handover management for multiple RATs. The use of heterogeneous networks can capitalize on the overlapping coverage and allow user devices to take advantage of the fact that there are multiple radio interfaces. This paper presents the functional architecture for such a framework and proposes a generic signaling exchange applicable to a range of different handover management protocols that enables seamless mobility. The interworking of radio resource management, access selection and mobility management is defined in a generic and modular way, which is extensible for future protocols and standards.
Taking the redpill: Artificial Evolution in native x86 systems
Venue: arXiv cs.NE 2011
Year: 2011

In analogon to successful artificial evolution simulations as Tierra or avida, this text presents a way to perform artificial evolution in a native x86 system. The implementation of the artificial chemistry and first results of statistical experiments are presented.
Efficient Image Transmission Through Analog Error Correction
Venue: arXiv cs.MM 2011
Year: 2011

This paper presents a new paradigm for image transmission through analog error correction codes. Conventional schemes rely on digitizing images through quantization (which inevitably causes significant bandwidth expansion) and transmitting binary bit-streams through digital error correction codes (which do not automatically differentiate the different levels of significance among the bits). To strike a better overall performance in terms of transmission efficiency and quality, we propose to use a single analog error correction code in lieu of digital quantization, digital code and digital modulation. The key is to get analog coding right. We show that this can be achieved by cleverly exploiting an elegant "butterfly" property of chaotic systems. Specifically, we demonstrate a tail-biting triple-branch baker's map code and its maximum-likelihood decoding algorithm. Simulations show that the proposed analog code can actually outperform digital turbo code, one of the best codes known to date. The results and findings discussed in this paper speak volume for the promising potential of analog codes, in spite of their rather short history.
Convergence Time Analysis of Quantized Gossip Consensus on Digraphs
Venue: arXiv cs.SY 2011
Year: 2011

We have recently proposed quantized gossip algorithms which solve the consensus and averaging problems on directed graphs with the least restrictive connectivity requirements. In this paper we study the convergence time of these algorithms. To this end, we investigate the shrinking time of the smallest interval that contains all states for the consensus algorithm, and the decay time of a suitable Lyapunov function for the averaging algorithm. The investigation leads us to characterizing the convergence time by the hitting time in certain special Markov chains. We simplify the structures of state transition by considering the special case of complete graphs, where every edge can be activated with an equal probability, and derive polynomial upper bounds on convergence time.
Internet of Things: Applications and Challenges in Technology and Standardization
Venue: arXiv cs.CY 2011
Year: 2011

The phrase Internet of Things (IoT) heralds a vision of the future Internet where connecting physical things, from banknotes to bicycles, through a network will let them take an active part in the Internet, exchanging information about themselves and their surroundings. This will give immediate access to information about the physical world and the objects in it leading to innovative services and increase in efficiency and productivity. This paper studies the state-of-the-art of IoT and presents the key technological drivers,potential applications, challenges and future research areas in the domain of IoT. IoT definitions from different perspective in academic and industry communities are also discussed and compared. Finally some major issues of future research in IoT are identified and discussed briefly.