OpenRaiser/Intern-Atlas huggingface dataset:
Design and implementation of real time AES-128 on real time operating system for multiple FPGA communication
Venue: arXiv cs.AR 2012
Year: 2012

Security is the most important part in data communication system, where more randomization in secret keys increases the security as well as complexity of the cryptography algorithms. As a result in recent dates these algorithms are compensating with enormous memory spaces and large execution time on hardware platform. Field programmable gate arrays (FPGAs), provide one of the major alternative in hardware platform scenario due to its reconfiguration nature, low price and marketing speed. In FPGA based embedded system we can use embedded processor to execute particular algorithm with the inclusion of a real time operating System (RTOS), where threads may reduce resource utilization and time consumption. A process in the runtime is separated in different smaller tasks which are executed by the scheduler to meet the real time dead line using RTOS. In this paper we demonstrate the design and implementation of a 128-bit Advanced Encryption Standard (AES) both symmetric key encryption and decryption algorithm by developing suitable hardware and software design on Xilinx Spartan- 3E (XC3S500E-FG320) device using an Xilkernel RTOS, the implementation has been tested successfully The system is optimized in terms of execution speed and hardware utilization.
P(l)aying for Synchronization
Venue: arXiv cs.FL 2012
Year: 2012

Two topics are presented: synchronization games and synchronization costs. In a synchronization game on a deterministic finite automaton, there are two players, Alice and Bob, whose moves alternate. Alice wants to synchronize the given automaton, while Bob aims to make her task as hard as possible. We answer a few natural questions related to such games. Speaking about synchronization costs, we consider deterministic automata in which each transition has a certain price. The problem is whether or not a given automaton can be synchronized within a given budget. We determine the complexity of this problem. We also formulate a few open questions.
Approximation Algorithms for Semi-random Graph Partitioning Problems
Venue: arXiv cs.DS 2012
Year: 2012

In this paper, we propose and study a new semi-random model for graph partitioning problems. We believe that it captures many properties of real--world instances. The model is more flexible than the semi-random model of Feige and Kilian and planted random model of Bui, Chaudhuri, Leighton and Sipser. We develop a general framework for solving semi-random instances and apply it to several problems of interest. We present constant factor bi-criteria approximation algorithms for semi-random instances of the Balanced Cut, Multicut, Min Uncut, Sparsest Cut and Small Set Expansion problems. We also show how to almost recover the optimal solution if the instance satisfies an additional expanding condition. Our algorithms work in a wider range of parameters than most algorithms for previously studied random and semi-random models. Additionally, we study a new planted algebraic expander model and develop constant factor bi-criteria approximation algorithms for graph partitioning problems in this model.
Flip Distance Between Two Triangulations of a Point-Set is NP-complete
Venue: arXiv cs.CG 2012
Year: 2012

Given two triangulations of a convex polygon, computing the minimum number of flips required to transform one to the other is a long-standing open problem. It is not known whether the problem is in P or NP-complete. We prove that two natural generalizations of the problem are NP-complete, namely computing the minimum number of flips between two triangulations of (1) a polygon with holes; (2) a set of points in the plane.
Relaxed Half-Stochastic Belief Propagation
Venue: arXiv cs.AR 2012
Year: 2012

Low-density parity-check codes are attractive for high throughput applications because of their low decoding complexity per bit, but also because all the codeword bits can be decoded in parallel. However, achieving this in a circuit implementation is complicated by the number of wires required to exchange messages between processing nodes. Decoding algorithms that exchange binary messages are interesting for fully-parallel implementations because they can reduce the number and the length of the wires, and increase logic density. This paper introduces the Relaxed Half-Stochastic (RHS) decoding algorithm, a binary message belief propagation (BP) algorithm that achieves a coding gain comparable to the best known BP algorithms that use real-valued messages. We derive the RHS algorithm by starting from the well-known Sum-Product algorithm, and then derive a low-complexity version suitable for circuit implementation. We present extensive simulation results on two standardized codes having different rates and constructions, including low bit error rate results. These simulations show that RHS can be an advantageous replacement for the existing state-of-the-art decoding algorithms when targeting fully-parallel implementations.
Public Data Integration with WebSmatch
Venue: arXiv cs.DL 2012
Year: 2012

Integrating open data sources can yield high value information but raises major problems in terms of metadata extraction, data source integration and visualization of integrated data. In this paper, we describe WebSmatch, a flexible environment for Web data integration, based on a real, end-to-end data integration scenario over public data from Data Publica. WebSmatch supports the full process of importing, refining and integrating data sources and uses third party tools for high quality visualization. We use a typical scenario of public data integration which involves problems not solved by currents tools: poorly structured input data sources (XLS files) and rich visualization of integrated data.
Most Relevant Explanation: Properties, Algorithms, and Evaluations
Venue: arXiv cs.AI 2012
Year: 2012

Most Relevant Explanation (MRE) is a method for finding multivariate explanations for given evidence in Bayesian networks [12]. This paper studies the theoretical properties of MRE and develops an algorithm for finding multiple top MRE solutions. Our study shows that MRE relies on an implicit soft relevance measure in automatically identifying the most relevant target variables and pruning less relevant variables from an explanation. The soft measure also enables MRE to capture the intuitive phenomenon of explaining away encoded in Bayesian networks. Furthermore, our study shows that the solution space of MRE has a special lattice structure which yields interesting dominance relations among the solutions. A K-MRE algorithm based on these dominance relations is developed for generating a set of top solutions that are more representative. Our empirical results show that MRE methods are promising approaches for explanation in Bayesian networks.
Exploring compact reinforcement-learning representations with linear regression
Venue: arXiv cs.LG 2012
Year: 2012

This paper presents a new algorithm for online linear regression whose efficiency guarantees satisfy the requirements of the KWIK (Knows What It Knows) framework. The algorithm improves on the complexity bounds of the current state-of-the-art procedure in this setting. We explore several applications of this algorithm for learning compact reinforcement-learning representations. We show that KWIK linear regression can be used to learn the reward function of a factored MDP and the probabilities of action outcomes in Stochastic STRIPS and Object Oriented MDPs, none of which have been proven to be efficiently learnable in the RL setting before. We also combine KWIK linear regression with other KWIK learners to learn larger portions of these models, including experiments on learning factored MDP transition and reward functions together.
Interpretation and Generalization of Score Matching
Venue: arXiv cs.LG 2012
Year: 2012

Score matching is a recently developed parameter learning method that is particularly effective to complicated high dimensional density models with intractable partition functions. In this paper, we study two issues that have not been completely resolved for score matching. First, we provide a formal link between maximum likelihood and score matching. Our analysis shows that score matching finds model parameters that are more robust with noisy training data. Second, we develop a generalization of score matching. Based on this generalization, we further demonstrate an extension of score matching to models of discrete data.
MAP Estimation of Semi-Metric MRFs via Hierarchical Graph Cuts
Venue: arXiv cs.AI 2012
Year: 2012

We consider the task of obtaining the maximum a posteriori estimate of discrete pairwise random fields with arbitrary unary potentials and semimetric pairwise potentials. For this problem, we propose an accurate hierarchical move making strategy where each move is computed efficiently by solving an st-MINCUT problem. Unlike previous move making approaches, e.g. the widely used a-expansion algorithm, our method obtains the guarantees of the standard linear programming (LP) relaxation for the important special case of metric labeling. Unlike the existing LP relaxation solvers, e.g. interior-point algorithms or tree-reweighted message passing, our method is significantly faster as it uses only the efficient st-MINCUT algorithm in its design. Using both synthetic and real data experiments, we show that our technique outperforms several commonly used algorithms.
Constraint Processing in Lifted Probabilistic Inference
Venue: arXiv cs.AI 2012
Year: 2012

First-order probabilistic models combine representational power of first-order logic with graphical models. There is an ongoing effort to design lifted inference algorithms for first-order probabilistic models. We analyze lifted inference from the perspective of constraint processing and, through this viewpoint, we analyze and compare existing approaches and expose their advantages and limitations. Our theoretical results show that the wrong choice of constraint processing method can lead to exponential increase in computational complexity. Our empirical tests confirm the importance of constraint processing in lifted inference. This is the first theoretical and empirical study of constraint processing in lifted inference.
First-Order Mixed Integer Linear Programming
Venue: arXiv cs.LO 2012
Year: 2012

Mixed integer linear programming (MILP) is a powerful representation often used to formulate decision-making problems under uncertainty. However, it lacks a natural mechanism to reason about objects, classes of objects, and relations. First-order logic (FOL), on the other hand, excels at reasoning about classes of objects, but lacks a rich representation of uncertainty. While representing propositional logic in MILP has been extensively explored, no theory exists yet for fully combining FOL with MILP. We propose a new representation, called first-order programming or FOP, which subsumes both FOL and MILP. We establish formal methods for reasoning about first order programs, including a sound and complete lifted inference procedure for integer first order programs. Since FOP can offer exponential savings in representation and proof size compared to FOL, and since representations and proofs are never significantly longer in FOP than in FOL, we anticipate that inference in FOP will be more tractable than inference in FOL for corresponding problems.
Learning Continuous-Time Social Network Dynamics
Venue: arXiv cs.SI 2012
Year: 2012

We demonstrate that a number of sociology models for social network dynamics can be viewed as continuous time Bayesian networks (CTBNs). A sampling-based approximate inference method for CTBNs can be used as the basis of an expectation-maximization procedure that achieves better accuracy in estimating the parameters of the model than the standard method of moments algorithmfromthe sociology literature. We extend the existing social network models to allow for indirect and asynchronous observations of the links. A Markov chain Monte Carlo sampling algorithm for this new model permits estimation and inference. We provide results on both a synthetic network (for verification) and real social network data.
Detectability of Symbol Manipulation by an Amplify-and-Forward Relay
Venue: arXiv cs.IT 2012
Year: 2012

This paper studies the problem of detecting a potential malicious relay node by a source node that relies on the relay to forward information to other nodes. The channel model of two source nodes simultaneously sending symbols to a relay is considered. The relay is contracted to forward the symbols that it receives back to the sources in the amplify-and-forward manner. However there is a chance that the relay may send altered symbols back to the sources. Each source attempts to individually detect such malicious acts of the relay by comparing the empirical distribution of the symbols that it receives from the relay conditioned on its own transmitted symbols with known stochastic characteristics of the channel. It is shown that maliciousness of the relay can be asymptotically detected with sufficient channel observations if and only if the channel satisfies a non-manipulable condition, which can be easily checked. As a result, the non-manipulable condition provides us a clear-cut criterion to determine the detectability of the aforementioned class of symbol manipulation attacks potentially conducted by the relay.
Efficient Packet Forwarding in Mesh Network
Venue: arXiv cs.NI 2012
Year: 2012

Wireless Mesh Network (WMN) is a multi hop low cost, with easy maintenance robust network providing reliable service coverage. WMNs consist of mesh routers and mesh clients. In this architecture, while static mesh routers form the wireless backbone, mesh clients access the network through mesh routers as well as directly meshing with each other. Different from traditional wireless networks, WMN is dynamically self-organized and self-configured. In other words, the nodes in the mesh network automatically establish and maintain network connectivity. Over the years researchers have worked, to reduce the redundancy in broadcasting packet in the mesh network in the wireless domain for providing reliable service coverage, the source node deserves to broadcast or flood the control packets. The redundant control packet consumes the bandwidth of the wireless medium and significantly reduces the average throughput and consequently reduces the overall system performance. In this paper I study the optimization problem in Wireless Mesh Networks. We have proposed a novel approach to reduce the broadcast redundant packet in the wireless mesh network. Also we have shown, a novel procedure to forward the control packet to the destination nodes and efficiently minimize the transmitted control packet in the wireless mesh cloud, that covers the domain.
Forecasting of Indian Rupee (INR) / US Dollar (USD) Currency Exchange Rate Using Artificial Neural Network
Venue: arXiv cs.NE 2012
Year: 2012

A large part of the workforce, and growing every day, is originally from India. India one of the second largest populations in the world, they have a lot to offer in terms of jobs. The sheer number of IT workers makes them a formidable travelling force as well, easily picking up employment in English speaking countries. The beginning of the economic crises since 2008 September, many Indians have return homeland, and this has had a substantial impression on the Indian Rupee (INR) as liken to the US Dollar (USD). We are using numerational knowledge based techniques for forecasting has been proved highly successful in present time. The purpose of this paper is to examine the effects of several important neural network factors on model fitting and forecasting the behaviours. In this paper, Artificial Neural Network has successfully been used for exchange rate forecasting. This paper examines the effects of the number of inputs and hidden nodes and the size of the training sample on the in-sample and out-of-sample performance. The Indian Rupee (INR) / US Dollar (USD) is used for detailed examinations. The number of input nodes has a greater impact on performance than the number of hidden nodes, while a large number of observations do reduce forecast errors.
An Adaptive Watermarking Technique for the copyright of digital images and Digital Image Protection
Venue: arXiv cs.MM 2012
Year: 2012

The Internet as a whole does not use secure links, thus information in transit may be vulnerable to interruption as well. The important of reducing a chance of the information being detected during the transmission is being an issue in the real world now days. The Digital watermarking method provides for the quick and inexpensive distribution of digital information over the Internet. This method provides new ways of ensuring the sufficient protection of copyright holders in the intellectual property dispersion process. The property of digital watermarking images allows insertion of additional data in the image without altering the value of the image.In this paper investigate the following relevant concepts and terminology, history of watermarks and the properties of a watermarking system and applications. We are proposing edge detection using Gabor Filters. In this paper we are proposed least significant bit (LSB) substitution method to encrypt the message in the watermark image file. The benefits of the LSB are its simplicity to embed the bits of the message directly into the LSB plane of cover-image and many techniques using these methods. The LSB does not result in a human perceptible difference because the amplitude of the change is little therefore the human eye the resulting stego image will look identical to the cover image and this allows high perceptual transparency of the LSB. The spatial domain technique LSB substitution it would be able to use a pseudo-random number generator to determine the pixels to be used for embedding based on a given key. We are using DCT transform watermark algorithms based on robustness. The watermarking robustness have been calculated by the Peak Signal to Noise Ratio (PSNR) and Normalized cross correlation (NC) is used to quantify by the similarity between the real watermark and after extracting watermark.
Density Sensitive Hashing
Venue: arXiv cs.IR 2012
Year: 2012

Nearest neighbors search is a fundamental problem in various research fields like machine learning, data mining and pattern recognition. Recently, hashing-based approaches, e.g., Locality Sensitive Hashing (LSH), are proved to be effective for scalable high dimensional nearest neighbors search. Many hashing algorithms found their theoretic root in random projection. Since these algorithms generate the hash tables (projections) randomly, a large number of hash tables (i.e., long codewords) are required in order to achieve both high precision and recall. To address this limitation, we propose a novel hashing algorithm called {\em Density Sensitive Hashing} (DSH) in this paper. DSH can be regarded as an extension of LSH. By exploring the geometric structure of the data, DSH avoids the purely random projections selection and uses those projective functions which best agree with the distribution of the data. Extensive experimental results on real-world data sets have shown that the proposed method achieves better performance compared to the state-of-the-art hashing approaches.
Inapproximability After Uniqueness Phase Transition in Two-Spin Systems
Venue: arXiv cs.CC 2012
Year: 2012

A two-state spin system is specified by a 2 x 2 matrix A = {A_{0,0} A_{0,1}, A_{1,0} A_{1,1}} = {β1, 1 γ} where β, γ\ge 0. Given an input graph G=(V,E), the partition function Z_A(G) of a system is defined as Z_A(G) = \sum_{σ: V -> {0,1}} \prod_{(u,v) \in E} A_{σ(u), σ(v)} We prove inapproximability results for the partition function in the region specified by the non-uniqueness condition from phase transition for the Gibbs measure. More specifically, assuming NP \ne RP, for any fixed β, γin the unit square, there is no randomized polynomial-time algorithm that approximates Z_A(G) for d-regular graphs G with relative error ε= 10^{-4}, if d = Ω(Δ(β,γ)), where Δ(β,γ) > 1/(1-βγ) is the uniqueness threshold. Up to a constant factor, this hardness result confirms the conjecture that the uniqueness phase transition coincides with the transition from computational tractability to intractability for Z_A(G). We also show a matching inapproximability result for a region of parameters β, γoutside the unit square, and all our results generalize to partition functions with an external field.
The Hush Cryptosystem
Venue: arXiv cs.CR 2012
Year: 2012

In this paper we describe a new cryptosystem we call "The Hush Cryptosystem" for hiding encrypted data in innocent Arabic sentences. The main purpose of this cryptosystem is to fool observer-supporting software into thinking that the encrypted data is not encrypted at all. We employ a modified Word Substitution Method known as the Grammatical Substitution Method in our cryptosystem. We also make use of Hidden Markov Models. We test our cryptosystem using a computer program written in the Java Programming Language. Finally, we test the output of our cryptosystem using statistical tests.
Automating Open Fault Correction in Integrated Circuits via Field Induced Diffusion Limited Aggregation
Venue: arXiv cs.ET 2012
Year: 2012

We perform studies on electric field induced diffusion limited aggregation of conductive particles dispersed in a non conductive medium. The bridges formed across gaps between electrodes with an electric field in between due to the aggregation mechanism provides a means to automate the correction of open interconnect faults for integrated circuit application. We derive an expression for the bridging time and describe the mechanics of bridge formation with the above application in mind.
Bridge the Gap: Measuring and Analyzing Technical Data for Social Trust between Smartphones
Venue: arXiv cs.NI 2012
Year: 2012

Mobiles are nowadays the most relevant communication devices in terms of quantity and flexibility. Like in most MANETs ad-hoc communication between two mobile phones requires mutual trust between the devices. A new way of establishing this trust conducts social trust from technically measurable data (e.g., interaction logs). To explore the relation between social and technical trust, we conduct a large-scale survey with more than 217 Android users and analyze their anonymized call and message logs. We show that a reliable a priori trust value for a mobile system can be derived from common social communication metrics.
Multiple Identifications in Multi-Armed Bandits
Venue: arXiv cs.LG 2012
Year: 2012

We study the problem of identifying the top $m$ arms in a multi-armed bandit game. Our proposed solution relies on a new algorithm based on successive rejects of the seemingly bad arms, and successive accepts of the good ones. This algorithmic contribution allows to tackle other multiple identifications settings that were previously out of reach. In particular we show that this idea of successive accepts and rejects applies to the multi-bandit best arm identification problem.
SportSense: Real-Time Detection of NFL Game Events from Twitter
Venue: arXiv cs.SI 2012
Year: 2012

We report our experience in building a working system, SportSense (http://www.sportsense.us), which exploits Twitter users as human sensors of the physical world to detect events in real-time. Using the US National Football League (NFL) games as a case study, we report in-depth measurement studies of the delay and post rate of tweets, and their dependence on other properties. We subsequently develop a novel event detection method based on these findings, and demonstrate that it can effectively and accurately extract game events using open access Twitter data. SportSense has been evolving during the 2010-11 and 2011-12 NFL seasons and is able to recognize NFL game big plays in 30 to 90 seconds with 98% true positive, and 9% false positive rates. Using a smart electronic TV program guide, we show that SportSense can utilize human sensors to empower novel services.