OpenRaiser/Intern-Atlas huggingface dataset:
Universal MMSE Filtering With Logarithmic Adaptive Regret
Venue: arXiv cs.LG 2011
Year: 2011

We consider the problem of online estimation of a real-valued signal corrupted by oblivious zero-mean noise using linear estimators. The estimator is required to iteratively predict the underlying signal based on the current and several last noisy observations, and its performance is measured by the mean-square-error. We describe and analyze an algorithm for this task which: 1. Achieves logarithmic adaptive regret against the best linear filter in hindsight. This bound is assyptotically tight, and resolves the question of Moon and Weissman [1]. 2. Runs in linear time in terms of the number of filter coefficients. Previous constructions required at least quadratic time.
Catching the k-NAESAT Threshold
Venue: arXiv cs.DM 2011
Year: 2011

The best current estimates of the thresholds for the existence of solutions in random constraint satisfaction problems ('CSPs') mostly derive from the first and the second moment method. Yet apart from a very few exceptional cases these methods do not quite yield matching upper and lower bounds. According to deep but non-rigorous arguments from statistical mechanics, this discrepancy is due to a change in the geometry of the set of solutions called condensation that occurs shortly before the actual threshold for the existence of solutions (Krzakala, Montanari, Ricci-Tersenghi, Semerjian, Zdeborova: PNAS 2007). To cope with condensation, physicists have developed a sophisticated but non-rigorous formalism called Survey Propagation (Mezard, Parisi, Zecchina: Science 2002). This formalism yields precise conjectures on the threshold values of many random CSPs. Here we develop a new Survey Propagation inspired second moment method for the random k-NAESAT problem, which is one of the standard benchmark problems in the theory of random CSPs. This new technique allows us to overcome the barrier posed by condensation rigorously. We prove that the threshold for the existence of solutions in random $k$-NAESAT is $2^{k-1}\ln2-(\frac{\ln2}2+\frac14)+\eps_k$, where $|\eps_k| \le 2^{-(1-o_k(1))k}$, thereby verifying the statistical mechanics conjecture for this problem.
Hash function based secret sharing scheme designs
Venue: arXiv cs.CR 2011
Year: 2011

Secret sharing schemes create an effective method to safeguard a secret by dividing it among several participants. By using hash functions and the herding hashes technique, we first set up a (t+1, n) threshold scheme which is perfect and ideal, and then extend it to schemes for any general access structure. The schemes can be further set up as proactive or verifiable if necessary. The setup and recovery of the secret is efficient due to the fast calculation of the hash function. The proposed scheme is flexible because of the use of existing hash functions.
A Compressed Self-Index for Genomic Databases
Venue: arXiv cs.DS 2011
Year: 2011

Advances in DNA sequencing technology will soon result in databases of thousands of genomes. Within a species, individuals' genomes are almost exact copies of each other; e.g., any two human genomes are 99.9% the same. Relative Lempel-Ziv (RLZ) compression takes advantage of this property: it stores the first genome uncompressed or as an FM-index, then compresses the other genomes with a variant of LZ77 that copies phrases only from the first genome. RLZ achieves good compression and supports fast random access; in this paper we show how to support fast search as well, thus obtaining an efficient compressed self-index.
Speculative Parallel Evaluation Of Classification Trees On GPGPU Compute Engines
Venue: arXiv cs.DC 2011
Year: 2011

We examine the problem of optimizing classification tree evaluation for on-line and real-time applications by using GPUs. Looking at trees with continuous attributes often used in image segmentation, we first put the existing algorithms for serial and data-parallel evaluation on solid footings. We then introduce a speculative parallel algorithm designed for single instruction, multiple data (SIMD) architectures commonly found in GPUs. A theoretical analysis shows how the run times of data and speculative decompositions compare assuming independent processors. To compare the algorithms in the SIMD environment, we implement both on a CUDA 2.0 architecture machine and compare timings to a serial CPU implementation. Various optimizations and their effects are discussed, and results are given for all algorithms. Our specific tests show a speculative algorithm improves run time by 25% compared to a data decomposition.
Robust Interactive Learning
Venue: arXiv cs.LG 2011
Year: 2011

In this paper we propose and study a generalization of the standard active-learning model where a more general type of query, class conditional query, is allowed. Such queries have been quite useful in applications, but have been lacking theoretical understanding. In this work, we characterize the power of such queries under two well-known noise models. We give nearly tight upper and lower bounds on the number of queries needed to learn both for the general agnostic setting and for the bounded noise model. We further show that our methods can be made adaptive to the (unknown) noise rate, with only negligible loss in query complexity.
Universal Lossless Data Compression Via Binary Decision Diagrams
Venue: arXiv cs.IT 2011
Year: 2011

A binary string of length $2^k$ induces the Boolean function of $k$ variables whose Shannon expansion is the given binary string. This Boolean function then is representable via a unique reduced ordered binary decision diagram (ROBDD). The given binary string is fully recoverable from this ROBDD. We exhibit a lossless data compression algorithm in which a binary string of length a power of two is compressed via compression of the ROBDD associated to it as described above. We show that when binary strings of length $n$ a power of two are compressed via this algorithm, the maximal pointwise redundancy/sample with respect to any s-state binary information source has the upper bound $(4\log_2s+16+o(1))/\log_2n $. To establish this result, we exploit a result of Liaw and Lin stating that the ROBDD representation of a Boolean function of $k$ variables contains a number of vertices on the order of $(2+o(1))2^{k}/k$.
Particle Swarm Optimization Framework for Low Power Testing of VLSI Circuits
Venue: arXiv cs.NE 2011
Year: 2011

Power dissipation in sequential circuits is due to increased toggling count of Circuit under Test, which depends upon test vectors applied. If successive test vectors sequences have more toggling nature then it is sure that toggling rate of flip flops is higher. Higher toggling for flip flops results more power dissipation. To overcome this problem, one method is to use GA to have test vectors of high fault coverage in short interval, followed by Hamming distance management on test patterns. This approach is time consuming and needs more efforts. Another method which is purposed in this paper is a PSO based Frame Work to optimize power dissipation. Here target is to set the entire test vector in a frame for time period 'T', so that the frame consists of all those vectors strings which not only provide high fault coverage but also arrange vectors in frame to produce minimum toggling.
Throughput Performance of 2$\times$2 Mimo LTE Downlink in a Spatial Correlation Based Microcellular Channel for Wireless Broadband Networks
Venue: arXiv cs.NI 2011
Year: 2011

Multiple Input Multiple Output (MIMO) technology is going to be a viable alternative for future generation wireless broadband services in order to meet the striving requirements for throughput and system robustness. In Long Term Evolution (LTE), MIMO technologies have been broadly used to get better downlink peak rate, cell coverage, as well as average cell throughput. In the present paper a 2x2 MIMO is taken as baseline configuration for a LTE downlink under a Microcellular propagation scenario considering a non physical correlation based channel with Poor and rich scattering environment. The throughput capacity of the downlink is obtained for poor and rich scattering environments. Besides, two vital aspects of MIMO technique viz Spatial Multiplexing (SM) and Transmit Diversity (TD) are investigated in order to see their effect on throughput of the system. The effect of parameters like Speed of mobile station, number of Multipath, Rician factor (K) on throughput of such systems is reported and discussed. The investigations reported in this paper helps in estimating the throughput capacity of LTE downlink under SM and TD mode.
Framework Architecture for WLAN Testbed
Venue: arXiv cs.NI 2011
Year: 2011

There has been a tremendous effort in improving wireless LAN for supporting the demanding multimedia application. Many new protocols or ideas have been proposed and proved by using a mathematical model or running a simulation program. That is satisfactory but these proposed designs might not work in the real world situation. Testbed is an option to alleviate this gap and present the opportunity to see the real problem and ensure that the design works. A framework architecture for building a testbed to test a new concept or design is presented in this paper. The framework is designed in the modularity style in such a way that can be easily exchanged or modified. A testbed based on the framework that implements the polling based mechanism has been created and the results have shown that the QoS of the real time traffic can be maintained in the presence of the high non-real time traffic.
Aspects of Assembly and Cascaded Aspects of Assembly: Logical and Temporal Properties
Venue: arXiv cs.SE 2011
Year: 2011

Highly dynamic computing environments, like ubiquitous and pervasive computing environments, require frequent adaptation of applications. This has to be done in a timely fashion, and the adaptation process must be as fast as possible and mastered. Moreover the adaptation process has to ensure a consistent result when finished whereas adaptations to be implemented cannot be anticipated at design time. In this paper we present our mechanism for self-adaptation based on the aspect oriented programming paradigm called Aspect of Assembly (AAs). Using AAs: (1) the adaptations process is fast and its duration is mastered; (2) adaptations' entities are independent of each other thanks to the weaver logical merging mechanism; and (3) the high variability of the software infrastructure can be managed using a mono or multi-cycle weaving approach.
The UWB Solution for Multimedia Traffic in Wireless Sensor Networks
Venue: arXiv cs.NI 2011
Year: 2011

Several researches are focused on the QoS (Quality of Service) and Energy consumption in wireless Multimedia Sensor Networks. Those research projects invest in theory and practice in order to extend the spectrum of use of norms, standards and technologies which are emerged in wireless communications. The performance of these technologies is strongly related to domains of use and limitations of their characteristics. In this paper, we give a comparison of ZigBee technology, most widely used in sensor networks, and UWB (Ultra Wide Band) which presents itself as competitor that present in these work better results for audiovisual applications with medium-range and high throughput.
Choosing the best resource by method of mamdani
Venue: arXiv cs.DC 2011
Year: 2011

A method for selecting the best service for the storage of information by Mamdani.
Ensuring message embedding in wet paper steganography
Venue: arXiv cs.CR 2011
Year: 2011

Syndrome coding has been proposed by Crandall in 1998 as a method to stealthily embed a message in a cover-medium through the use of bounded decoding. In 2005, Fridrich et al. introduced wet paper codes to improve the undetectability of the embedding by nabling the sender to lock some components of the cover-data, according to the nature of the cover-medium and the message. Unfortunately, almost all existing methods solving the bounded decoding syndrome problem with or without locked components have a non-zero probability to fail. In this paper, we introduce a randomized syndrome coding, which guarantees the embedding success with probability one. We analyze the parameters of this new scheme in the case of perfect codes.
Optimizing Local Capacity of Wireless Ad Hoc Networks
Venue: arXiv cs.NI 2011
Year: 2011

In this work, we evaluate local capacity of wireless ad hoc networks with several medium access protocols and identify the most optimal protocol. We define local capacity as the average information rate received by a receiver randomly located in the network. We analyzed grid pattern protocols where simultaneous transmitters are positioned in a regular grid pattern, pure ALOHA protocols where simultaneous transmitters are dispatched according to a uniform Poisson distribution and exclusion protocols where simultaneous transmitters are dispatched according to an exclusion rule such as node coloring and carrier sense protocols. Our analysis allows us to conjecture that local capacity is optimal when simultaneous transmitters are positioned in a grid pattern based on equilateral triangles and our results show that this optimal local capacity is at most double the local capacity of simple ALOHA protocol. Our results also show that node coloring and carrier sense protocols approach the optimal local capacity by an almost negligible difference.
Optimum Partition Parameter of Divide-and-Conquer Algorithm for Solving Closest-Pair Problem
Venue: arXiv cs.CG 2011
Year: 2011

Divide and Conquer is a well known algorithmic procedure for solving many kinds of problem. In this procedure, the problem is partitioned into two parts until the problem is trivially solvable. Finding the distance of the closest pair is an interesting topic in computer science. With divide and conquer algorithm we can solve closest pair problem. Here also the problem is partitioned into two parts until the problem is trivially solvable. But it is theoretically and practically observed that sometimes partitioning the problem space into more than two parts can give better performances. In this paper, a new proposal is given that dividing the problem space into (n) number of parts can give better result while divide and conquer algorithm is used for solving the closest pair of point's problem.
Achievable Rates for a Two-Relay Network with Relays-Transmitter Feedbacks
Venue: arXiv cs.IT 2011
Year: 2011

We consider a relay network with two relays and two feedback links from the relays to the sender. To obtain the achievability results, we use the compress-and-forward and the decode-and-forward strategies to superimpose facility and cooperation analogue to what proposed by Cover and El Gamal for a relay channel. In addition to random binning, we use deterministic binning to perform restricted decoding. We show how to use the feedback links for cooperation between the sender and the relays to transmit the information which is compressed in the sender and the relays.
Value, Variety and Viability: Designing For Co-creation in a Complex System of Direct and Indirect (goods) Service Value Proposition
Venue: arXiv cs.SY 2011
Year: 2011

While service-dominant logic proposes that all "Goods are a distribution mechanism for service provision" (FP3), there is a need to understand when and why a firm would utilise direct or indirect (goods) service provision, and the interactions between them, to co-create value with the customer. Three longitudinal case studies in B2B equipment-based 'complex service' systems were analysed to gain an understanding of customers' co-creation activities to achieve outcomes. We found the nature of value, degree of contextual variety and the firm's legacy viability to be viability threats. To counter this, the firm uses (a) Direct Service Provision for Scalability and Replicability, (b) Indirect Service Provision for variety absorption and co-creating emotional value and customer experience and (c) designing direct and indirect provision for Scalability and Absorptive Resources of the customer. The co-creation of complex multidimensional value could be delivered through different value propositions of the firm. The research proposes a value-centric way of understanding the interactions between direct and indirect service provision in the design of the firm's value proposition and proposes a viable systems approach towards reorganising the firm. The study provides a way for managers to understand the effectiveness (rather than efficiency) of the firm in co-creating value as a major issue in the design of complex socio-technical systems. Goods are often designed within the domain of engineering and product design, often placing human activity as a supporting role to the equipment. Through an SDLogic lens, this study considers the design of both equipment and human activity on an equal footing for value co-creation with the customer, and it yielded interesting results on when direct provisioning (goods) should be redesigned, considering all activities equally.
Finite State Machine Based Evaluation Model for Web Service Reliability Analysis
Venue: arXiv cs.SE 2011
Year: 2011

Now-a-days they are very much considering about the changes to be done at shorter time since the reaction time needs are decreasing every moment. Business Logic Evaluation Model (BLEM) are the proposed solution targeting business logic automation and facilitating business experts to write sophisticated business rules and complex calculations without costly custom programming. BLEM is powerful enough to handle service manageability issues by analyzing and evaluating the computability and traceability and other criteria of modified business logic at run time. The web service and QOS grows expensively based on the reliability of the service. Hence the service provider of today things that reliability is the major factor and any problem in the reliability of the service should overcome then and there in order to achieve the expected level of reliability. In our paper we propose business logic evaluation model for web service reliability analysis using Finite State Machine (FSM) where FSM will be extended to analyze the reliability of composed set of service i.e., services under composition, by analyzing reliability of each participating service of composition with its functional work flow process. FSM is exploited to measure the quality parameters. If any change occurs in the business logic the FSM will automatically measure the reliability.
Graded CTL Model Checking for Test Generation
Venue: arXiv cs.LO 2011
Year: 2011

Recently there has been a great attention from the scientific community towards the use of the model-checking technique as a tool for test generation in the simulation field. This paper aims to provide a useful mean to get more insights along these lines. By applying recent results in the field of graded temporal logics, we present a new efficient model-checking algorithm for Hierarchical Finite State Machines (HSM), a well established symbolism long and widely used for representing hierarchical models of discrete systems. Performing model-checking against specifications expressed using graded temporal logics has the peculiarity of returning more counterexamples within a unique run. We think that this can greatly improve the efficacy of automatically getting test cases. In particular we verify two different models of HSM against branching time temporal properties.
Optimal Crowdsourcing Contests
Venue: arXiv cs.GT 2011
Year: 2011

We study the design and approximation of optimal crowdsourcing contests. Crowdsourcing contests can be modeled as all-pay auctions because entrants must exert effort up-front to enter. Unlike all-pay auctions where a usual design objective would be to maximize revenue, in crowdsourcing contests, the principal only benefits from the submission with the highest quality. We give a theory for optimal crowdsourcing contests that mirrors the theory of optimal auction design: the optimal crowdsourcing contest is a virtual valuation optimizer (the virtual valuation function depends on the distribution of contestant skills and the number of contestants). We also compare crowdsourcing contests with more conventional means of procurement. In this comparison, crowdsourcing contests are relatively disadvantaged because the effort of losing contestants is wasted. Nonetheless, we show that crowdsourcing contests are 2-approximations to conventional methods for a large family of "regular" distributions, and 4-approximations, otherwise.
Intelligent Distributed Production Control
Venue: arXiv cs.SY 2011
Year: 2011

This editorial introduces the special issue of the Springer journal, Journal of Intelligent Manufacturing, on intelligent distributed production control. This special issue contains selected papers presented at the 13th IFAC Symposium on Information Control Problems in Manufacturing - INCOM'2009 (Bakhtadze and Dolgui, 2009). The papers in this special issue were selected because of their high quality and their specific way of addressing the variety of issues dealing with intelligent distributed production control. Previous global discussions about the state of the art in intelligent distributed production control are provided, as well as exploratory guidelines for future research in this area.
Practical Distributed Control Synthesis
Venue: arXiv cs.LO 2011
Year: 2011

Classic distributed control problems have an interesting dichotomy: they are either trivial or undecidable. If we allow the controllers to fully synchronize, then synthesis is trivial. In this case, controllers can effectively act as a single controller with complete information, resulting in a trivial control problem. But when we eliminate communication and restrict the supervisors to locally available information, the problem becomes undecidable. In this paper we argue in favor of a middle way. Communication is, in most applications, expensive, and should hence be minimized. We therefore study a solution that tries to communicate only scarcely and, while allowing communication in order to make joint decision, favors local decisions over joint decisions that require communication.
Synthesis of Switching Rules for Ensuring Reachability Properties of Sampled Linear Systems
Venue: arXiv cs.LO 2011
Year: 2011

We consider here systems with piecewise linear dynamics that are periodically sampled with a given period τ . At each sampling time, the mode of the system, i.e., the parameters of the linear dynamics, can be switched, according to a switching rule. Such systems can be modelled as a special form of hybrid automata, called "switched systems", that are automata with an infinite real state space. The problem is to find a switching rule that guarantees the system to still be in a given area V at the next sampling time, and so on indefinitely. In this paper, we will consider two approaches: the indirect one that abstracts the system under the form of a finite discrete event system, and the direct one that works on the continuous state space. Our methods rely on previous works, but we specialize them to a simplified context (linearity, periodic switching instants, absence of control input), which is motivated by the features of a focused case study: a DC-DC boost converter built by electronics laboratory SATIE (ENS Cachan). Our enhanced methods allow us to treat successfully this real-life example.