OpenRaiser/Intern-Atlas huggingface dataset:
DDNFS: a Distributed Digital Notary File System
Venue: arXiv cs.CR 2011
Year: 2011

Safeguarding online communications using public key cryptography is a well-established practice today, but with the increasing reliance on `faceless', solely online entities one of the core aspects of public key cryptography is becoming a substantial problem in practice: Who can we trust to introduce us to and vouch for some online party whose public key we see for the first time? Most existing certification models lack flexibility and have come under attack repeatedly in recent years, and finding practical improvements has a high priority. We propose that the real-world concept of a notary or certifying witness can be adapted to today's online environment quite easily, and that such a system when combined with peer-to-peer technologies for defense in depth is a viable alternative to monolithic trust infrastructures. Instead of trusting assurances from a single party, integrity certifications (and data replication) can be provided among a group of independent parties in a peer-to-peer fashion. As the likelihood of all such assurance providers being subverted at the very same time is very much less than that of a single party, overall robustness is improved. This paper presents the design and the implementation of our prototype online notary system where independent computer notaries provide integrity certification and highly-available replicated storage, and discusses how this online notary system handles some common threat patterns.
Method for reducing of noise by improving signal-to-noise-ratio in wireless LAN
Venue: arXiv cs.NI 2011
Year: 2011

The signal to noise ratio (SNR) is one of the important measures for reducing the noise.A technique that uses a linear prediction error filter (LPEF) and an adaptive digital filter (ADF) to achieve noise reduction in a speech and image degraded by additive background noise is proposed. Since a speech signal can be represented as the stationary signal over a short interval of time, most of speech signal can be predicted by the LPEF. This estimation is performed by the ADF which is used as system identification. Noise reduction is achieved by subtracting the reconstructed noise from the speech degraded by additive background noise. Most of the MR image accelerating methods suffers from degradation of acquired images, which is often correlated with the degree of acceleration. However, Wideband MRI is a novel technique that transcends such flaws.In this paper we proposed LPEF and ADF for reducing the noise in speech and also we demonstrate that Wideband MRI is capable of obtaining images with identical quality as conventional MR images in terms of SNR in wireless LAN.
Power aware physical model for 3d IC's
Venue: arXiv cs.ET 2011
Year: 2011

In this work we have proposed a geometric model that is employed to devise a scheme for identifying the hotspots and zones in a chip. These spots or zone need to be guarded thermally to ensure performance and reliability of the chip. The model namely continuous unit sphere model has been presented taking into account that the 3D region of the chip is uniform, thereby reflecting on the possible locations of heat sources and the target observation points. The experimental results for the - continuous domain establish that a region which does not contain any heat sources may become hotter than the regions containing the thermal sources. Thus a hotspot may appear away from the active sources, and placing heat sinks on the active thermal sources alone may not suffice to tackle thermal imbalance. Power management techniques aid in obtaining a uniform power profile throughout the chip, but we propose an algorithm using minimum bipartite matching where we try to move the sources minimally (with minimum perturbation in the chip floor plan) near cooler points (blocks) to obtain a uniform power profile due to diffusion of heat from hotter point to cooler ones.
Compressed Membership for NFA (DFA) with Compressed Labels is in NP (P)
Venue: arXiv cs.FL 2011
Year: 2011

In this paper, a compressed membership problem for finite automata, both deterministic and non-deterministic, with compressed transition labels is studied. The compression is represented by straight-line programs (SLPs), i.e. context-free grammars generating exactly one string. A novel technique of dealing with SLPs is introduced: the SLPs are recompressed, so that substrings of the input text are encoded in SLPs labelling the transitions of the NFA (DFA) in the same way, as in the SLP representing the input text. To this end, the SLPs are locally decompressed and then recompressed in a uniform way. Furthermore, such recompression induces only small changes in the automaton, in particular, the size of the automaton remains polynomial. Using this technique it is shown that the compressed membership for NFA with compressed labels is in NP, thus confirming the conjecture of Plandowski and Rytter and extending the partial result of Lohrey and Mathissen; as it is already known, that this problem is NP-hard, we settle its exact computational complexity. Moreover, the same technique applied to the compressed membership for DFA with compressed labels yields that this problem is in P; for this problem, only trivial upper-bound PSPACE was known.
A Variant of Azuma's Inequality for Martingales with Subgaussian Tails
Venue: arXiv cs.LG 2011
Year: 2011

We provide a variant of Azuma's concentration inequality for martingales, in which the standard boundedness requirement is replaced by the milder requirement of a subgaussian tail.
An MDL framework for sparse coding and dictionary learning
Venue: arXiv cs.IT 2011
Year: 2011

The power of sparse signal modeling with learned over-complete dictionaries has been demonstrated in a variety of applications and fields, from signal processing to statistical inference and machine learning. However, the statistical properties of these models, such as under-fitting or over-fitting given sets of data, are still not well characterized in the literature. As a result, the success of sparse modeling depends on hand-tuning critical parameters for each data and application. This work aims at addressing this by providing a practical and objective characterization of sparse models by means of the Minimum Description Length (MDL) principle -- a well established information-theoretic approach to model selection in statistical inference. The resulting framework derives a family of efficient sparse coding and dictionary learning algorithms which, by virtue of the MDL principle, are completely parameter free. Furthermore, such framework allows to incorporate additional prior information to existing models, such as Markovian dependencies, or to define completely new problem formulations, including in the matrix analysis area, in a natural way. These virtues will be demonstrated with parameter-free algorithms for the classic image denoising and classification problems, and for low-rank matrix recovery in video applications.
Parallel Binomial American Option Pricing with (and without) Transaction Costs
Venue: arXiv cs.DC 2011
Year: 2011

We present a parallel algorithm that computes the ask and bid prices of an American option when proportional transaction costs apply to the trading of the underlying asset. The algorithm computes the prices on recombining binomial trees, and is designed for modern multi-core processors. Although parallel option pricing has been well studied, none of the existing approaches takes transaction costs into consideration. The algorithm that we propose partitions a binomial tree into blocks. In any round of computation a block is further partitioned into regions which are assigned to distinct processors. To minimise load imbalance the assignment of nodes to processors is dynamically adjusted before each new round starts. Synchronisation is required both within a round and between two successive rounds. The parallel speedup of the algorithm is proportional to the number of processors used. The parallel algorithm was implemented in C/C++ via POSIX Threads, and was tested on a machine with 8 processors. In the pricing of an American put option, the parallel speedup against an efficient sequential implementation was 5.26 using 8 processors and 1500 time steps, achieving a parallel efficiency of 65.75%.
Applying statistical methods to text steganography
Venue: arXiv cs.CR 2011
Year: 2011

This paper presents a survey of text steganography methods used for hid- ing secret information inside some covertext. Widely known hiding techniques (such as translation based steganography, text generating and syntactic embed- ding) and detection are considered. It is shown that statistical analysis has an important role in text steganalysis.
An Efficient Fuzzy Clustering-Based Approach for Intrusion Detection
Venue: arXiv cs.DB 2011
Year: 2011

The need to increase accuracy in detecting sophisticated cyber attacks poses a great challenge not only to the research community but also to corporations. So far, many approaches have been proposed to cope with this threat. Among them, data mining has brought on remarkable contributions to the intrusion detection problem. However, the generalization ability of data mining-based methods remains limited, and hence detecting sophisticated attacks remains a tough task. In this thread, we present a novel method based on both clustering and classification for developing an efficient intrusion detection system (IDS). The key idea is to take useful information exploited from fuzzy clustering into account for the process of building an IDS. To this aim, we first present cornerstones to construct additional cluster features for a training set. Then, we come up with an algorithm to generate an IDS based on such cluster features and the original input features. Finally, we experimentally prove that our method outperforms several well-known methods.
Proactive Algorithms for Job Shop Scheduling with Probabilistic Durations
Venue: arXiv cs.AI 2011
Year: 2011

Most classical scheduling formulations assume a fixed and known duration for each activity. In this paper, we weaken this assumption, requiring instead that each duration can be represented by an independent random variable with a known mean and variance. The best solutions are ones which have a high probability of achieving a good makespan. We first create a theoretical framework, formally showing how Monte Carlo simulation can be combined with deterministic scheduling algorithms to solve this problem. We propose an associated deterministic scheduling problem whose solution is proved, under certain conditions, to be a lower bound for the probabilistic problem. We then propose and investigate a number of techniques for solving such problems based on combinations of Monte Carlo simulation, solutions to the associated deterministic problem, and either constraint programming or tabu search. Our empirical results demonstrate that a combination of the use of the associated deterministic problem and Monte Carlo simulation results in algorithms that scale best both in terms of problem size and uncertainty. Further experiments point to the correlation between the quality of the deterministic solution and the quality of the probabilistic solution as a major factor responsible for this success.
The Language of Search
Venue: arXiv cs.AI 2011
Year: 2011

This paper is concerned with a class of algorithms that perform exhaustive search on propositional knowledge bases. We show that each of these algorithms defines and generates a propositional language. Specifically, we show that the trace of a search can be interpreted as a combinational circuit, and a search algorithm then defines a propositional language consisting of circuits that are generated across all possible executions of the algorithm. In particular, we show that several versions of exhaustive DPLL search correspond to such well-known languages as FBDD, OBDD, and a precisely-defined subset of d-DNNF. By thus mapping search algorithms to propositional languages, we provide a uniform and practical framework in which successful search techniques can be harnessed for compilation of knowledge into various languages of interest, and a new methodology whereby the power and limitations of search algorithms can be understood by looking up the tractability and succinctness of the corresponding propositional languages.
Understanding Algorithm Performance on an Oversubscribed Scheduling Application
Venue: arXiv cs.AI 2011
Year: 2011

The best performing algorithms for a particular oversubscribed scheduling application, Air Force Satellite Control Network (AFSCN) scheduling, appear to have little in common. Yet, through careful experimentation and modeling of performance in real problem instances, we can relate characteristics of the best algorithms to characteristics of the application. In particular, we find that plateaus dominate the search spaces (thus favoring algorithms that make larger changes to solutions) and that some randomization in exploration is critical to good performance (due to the lack of gradient information on the plateaus). Based on our explanations of algorithm performance, we develop a new algorithm that combines characteristics of the best performers; the new algorithms performance is better than the previous best. We show how hypothesis driven experimentation and search modeling can both explain algorithm performance and motivate the design of a new algorithm.
Phase Transition for Random Quantified XOR-Formulas
Venue: arXiv cs.AI 2011
Year: 2011

The QXORSAT problem is the quantified version of the satisfiability problem XORSAT in which the connective exclusive-or is used instead of the usual or. We study the phase transition associated with random QXORSAT instances. We give a description of this phase transition in the case of one alternation of quantifiers, thus performing an advanced practical and theoretical study on the phase transition of a quantified roblem.
Multi-Issue Negotiation with Deadlines
Venue: arXiv cs.MA 2011
Year: 2011

This paper studies bilateral multi-issue negotiation between self-interested autonomous agents. Now, there are a number of different procedures that can be used for this process; the three main ones being the package deal procedure in which all the issues are bundled and discussed together, the simultaneous procedure in which the issues are discussed simultaneously but independently of each other, and the sequential procedure in which the issues are discussed one after another. Since each of them yields a different outcome, a key problem is to decide which one to use in which circumstances. Specifically, we consider this question for a model in which the agents have time constraints (in the form of both deadlines and discount factors) and information uncertainty (in that the agents do not know the opponents utility function). For this model, we consider issues that are both independent and those that are interdependent and determine equilibria for each case for each procedure. In so doing, we show that the package deal is in fact the optimal procedure for each party. We then go on to show that, although the package deal may be computationally more complex than the other two procedures, it generates Pareto optimal outcomes (unlike the other two), it has similar earliest and latest possible times of agreement to the simultaneous procedure (which is better than the sequential procedure), and that it (like the other two procedures) generates a unique outcome only under certain conditions (which we define).
ELCA Evaluation for Keyword Search on Probabilistic XML Data
Venue: arXiv cs.DB 2011
Year: 2011

As probabilistic data management is becoming one of the main research focuses and keyword search is turning into a more popular query means, it is natural to think how to support keyword queries on probabilistic XML data. With regards to keyword query on deterministic XML documents, ELCA (Exclusive Lowest Common Ancestor) semantics allows more relevant fragments rooted at the ELCAs to appear as results and is more popular compared with other keyword query result semantics (such as SLCAs). In this paper, we investigate how to evaluate ELCA results for keyword queries on probabilistic XML documents. After defining probabilistic ELCA semantics in terms of possible world semantics, we propose an approach to compute ELCA probabilities without generating possible worlds. Then we develop an efficient stack-based algorithm that can find all probabilistic ELCA results and their ELCA probabilities for a given keyword query on a probabilistic XML document. Finally, we experimentally evaluate the proposed ELCA algorithm and compare it with its SLCA counterpart in aspects of result effectiveness, time and space efficiency, and scalability.
Are Minds Computable?
Venue: arXiv cs.AI 2011
Year: 2011

This essay explores the limits of Turing machines concerning the modeling of minds and suggests alternatives to go beyond those limits.
Towards cross-lingual alerting for bursty epidemic events
Venue: arXiv cs.CL 2011
Year: 2011

Background: Online news reports are increasingly becoming a source for event based early warning systems that detect natural disasters. Harnessing the massive volume of information available from multilingual newswire presents as many challenges as opportunities due to the patterns of reporting complex spatiotemporal events. Results: In this article we study the problem of utilising correlated event reports across languages. We track the evolution of 16 disease outbreaks using 5 temporal aberration detection algorithms on text-mined events classified according to disease and outbreak country. Using ProMED reports as a silver standard, comparative analysis of news data for 13 languages over a 129 day trial period showed improved sensitivity, F1 and timeliness across most models using cross-lingual events. We report a detailed case study analysis for Cholera in Angola 2010 which highlights the challenges faced in correlating news events with the silver standard. Conclusions: The results show that automated health surveillance using multilingual text mining has the potential to turn low value news into high value alerts if informed choices are used to govern the selection of models and data sources. An implementation of the C2 alerting algorithm using multilingual news is available at the BioCaster portal http://born.nii.ac.jp/?page=globalroundup.
Multi-tier Network Performance Analysis using a Shotgun Cellular System
Venue: arXiv cs.IT 2011
Year: 2011

This paper studies the carrier-to-interference ratio (CIR) and carrier-to-interference-plus-noise ratio (CINR) performance at the mobile station (MS) within a multi-tier network composed of M tiers of wireless networks, with each tier modeled as the homogeneous n-dimensional (n-D, n=1,2, and 3) shotgun cellular system, where the base station (BS) distribution is given by the homogeneous Poisson point process in n-D. The CIR and CINR at the MS in a single tier network are thoroughly analyzed to simplify the analysis of the multi-tier network. For the multi-tier network with given system parameters, the following are the main results of this paper: (1) semi-analytical expressions for the tail probabilities of CIR and CINR; (2) a closed form expression for the tail probability of CIR in the range [1,Infinity); (3) a closed form expression for the tail probability of an approximation to CIR in the entire range [0,Infinity); (4) a lookup table based approach for obtaining the tail probability of CINR, and (5) the study of the effect of shadow fading and BSs with ideal sectorized antennas on the CIR and CINR. Based on these results, it is shown that, in a practical cellular system, the installation of additional wireless networks (microcells, picocells and femtocells) with low power BSs over the already existing macrocell network will always improve the CINR performance at the MS.
Biological Computation as the Revolution of Complex Engineered Systems
Venue: arXiv cs.OH 2011
Year: 2011

Provided that there is no theoretical frame for complex engineered systems (CES) as yet, this paper claims that bio-inspired engineering can help provide such a frame. Within CES bio-inspired systems play a key role. The disclosure from bio-inspired systems and biological computation has not been sufficiently worked out, however. Biological computation is to be taken as the processing of information by living systems that is carried out in polynomial time, i.e., efficiently; such processing however is grasped by current science and research as an intractable problem (for instance, the protein folding problem). A remark is needed here: P versus NP problems should be well defined and delimited but biological computation problems are not. The shift from conventional engineering to bio-inspired engineering needs bring the subject (or problem) of computability to a new level. Within the frame of computation, so far, the prevailing paradigm is still the Turing-Church thesis. In other words, conventional engineering is still ruled by the Church-Turing thesis (CTt). However, CES is ruled by CTt, too. Contrarily to the above, we shall argue here that biological computation demands a more careful thinking that leads us towards hypercomputation. Bio-inspired engineering and CES thereafter, must turn its regard toward biological computation. Thus, biological computation can and should be taken as the ground for engineering complex non-linear systems. Biological systems do compute in terms of hypercomputation, indeed. If so, then the focus is not algorithmic or computational complexity but computation-beyond-the-Church-Turing-barrier. We claim that we need a new computational theory that encompasses biological processes wherein the Turing-Church thesis is but a particular case.
Faster and Low Power Twin Precision Multiplier
Venue: arXiv cs.AR 2011
Year: 2011

In this work faster unsigned multiplication has been achieved by using a combination of High Performance Multiplication [HPM] column reduction technique and implementing a N-bit multiplier using 4 N/2-bit multipliers (recursive multiplication) and acceleration of the final addition using a hybrid adder. Low power has been achieved by using clock gating technique. Based on the proposed technique 16 and 32-bit multipliers are developed. The performance of the proposed multiplier is analyzed by evaluating the delay, area and power, with TCBNPHP 90 nm process technology on interconnect and layout using Cadence NC launch, RTL compiler and ENCOUNTER tools. The results show that the 32-bit proposed multiplier is as much as 22% faster, occupies only 3% more area and consumes 30% lesser power with respect to the recently reported twin precision multiplier.
Effective Steganography Detection Based On Data Compression
Venue: arXiv cs.CR 2011
Year: 2011

This article describes novel text steganalysis method. The archiver "Bzip2" used for detection stegotext generated by Texto stegosystem. Experiments show that proposed approach gets better performance than typical existing methods. The detection accuracy exceeds 99.98% for text segments with size 400 bytes.
Network Clustering Approximation Algorithm Using One Pass Black Box Sampling
Venue: arXiv cs.SI 2011
Year: 2011

Finding a good clustering of vertices in a network, where vertices in the same cluster are more tightly connected than those in different clusters, is a useful, important, and well-studied task. Many clustering algorithms scale well, however they are not designed to operate upon internet-scale networks with billions of nodes or more. We study one of the fastest and most memory efficient algorithms possible - clustering based on the connected components in a random edge-induced subgraph. When defining the cost of a clustering to be its distance from such a random clustering, we show that this surprisingly simple algorithm gives a solution that is within an expected factor of two or three of optimal with either of two natural distance functions. In fact, this approximation guarantee works for any problem where there is a probability distribution on clusterings. We then examine the behavior of this algorithm in the context of social network trust inference.