Search results for "algorithm."
showing 10 items of 4617 documents
On the impact of forgetting on learning machines
1995
People tend not to have perfect memories when it comes to learning, or to anything else for that matter. Most formal studies of learning, however, assume a perfect memory. Some approaches have restricted the number of items that could be retained. We introduce a complexity theoretic accounting of memory utilization by learning machines. In our new model, memory is measured in bits as a function of the size of the input. There is a hierarchy of learnability based on increasing memory allotment. The lower bound results are proved using an unusual combination of pumping and mutual recursion theorem arguments. For technical reasons, it was necessary to consider two types of memory : long and sh…
On the Cryptanalysis of Two Cryptographic Algorithms That Utilize Chaotic Neural Networks
2015
This paper deals with the security and efficiency issues of two cipher algorithms which utilize the principles of Chaotic Neural Networks (CNNs). The two algorithms that we consider are (1) the CNN-Hash, which is a one-way hash function based on the Piece-Wise Linear Chaotic Map (PWLCM) and the One-Way Coupled Map Lattice (OCML), and (2) the Delayed CNN-Based Encryption (DCBE), which is an encryption algorithm based on the delayed CNN. Although both of these cipher algorithms have their own salient characteristics, our analysis shows that, unfortunately, the CNN-Hash is not secure because it is neither Second-Preimage resistant nor collision resistant. Indeed, one can find a collision with …
A solution to the stochastic point location problem in metalevel nonstationary environments.
2008
This paper reports the first known solution to the stochastic point location (SPL) problem when the environment is nonstationary. The SPL problem involves a general learning problem in which the learning mechanism (which could be a robot, a learning automaton, or, in general, an algorithm) attempts to learn a "parameter," for example, lambda*, within a closed interval. However, unlike the earlier reported results, we consider the scenario when the learning is to be done in a nonstationary setting. For each guess, the environment essentially informs the mechanism, possibly erroneously (i.e., with probability p), which way it should move to reach the unknown point. Unlike the results availabl…
Scavenger – A Framework for Efficient Evaluation of Dynamic and Modular Algorithms
2015
Machine Learning methods and algorithms are often highly modular in the sense that they rely on a large number of subalgorithms that are in principle interchangeable. For example, it is often possible to use various kinds of pre- and post-processing and various base classifiers or regressors as components of the same modular approach. We propose a framework, called Scavenger, that allows evaluating whole families of conceptually similar algorithms efficiently. The algorithms are represented as compositions, couplings and products of atomic subalgorithms. This allows partial results to be cached and shared between different instances of a modular algorithm, so that potentially expensive part…
Parallel Calculation of CCSDT and Mk-MRCCSDT Energies.
2010
A scheme for the parallel calculation of energies at the coupled-cluster singles, doubles, and triples (CCSDT) level of theory, several approximate iterative CCSDT schemes (CCSDT-1a, CCSDT-1b, CCSDT-2, CCSDT-3, and CC3), and for the state-specific multireference coupled-cluster ansatz suggested by Mukherjee with a full treatment of triple excitations (Mk-MRCCSDT) is presented. The proposed scheme is based on the adaptation of a highly efficient serial coupled-cluster code leading to a communication-minimized implementation by parallelizing the time-determining steps. The parallel algorithm is tailored for affordable cluster architectures connected by standard communication networks such as …
High precision quantum query algorithm for computing AND-based boolean functions
2010
Quantum algorithms can be analyzed in a query model to compute Boolean functions. Function input is provided in a black box, and the aim is to compute the function value using as few queries to the black box as possible. The complexity of the algorithm is measured by the number of queries on the worst-case input. In this paper we consider computing AND Boolean function. First, we present a quantum algorithm for AND of two bits. Our algorithm uses one quantum query and correct result is obtained with a probability p=4/5, that improves previous results. The main result is generalization of our approach to design efficient quantum algorithms for computing composite function AND(f1,f2) where fi…
Boosting Textual Compression in Optimal Linear Time
2005
We provide a general boosting technique for Textual Data Compression. Qualitatively, it takes a good compression algorithm and turns it into an algorithm with a better compression performance guarantee. It displays the following remarkable properties: (a) it can turn any memoryless compressor into a compression algorithm that uses the “best possible” contexts; (b) it is very simple and optimal in terms of time; and (c) it admits a decompression algorithm again optimal in time. To the best of our knowledge, this is the first boosting technique displaying these properties.Technically, our boosting technique builds upon three main ingredients: the Burrows--Wheeler Transform, the Suffix Tree d…
Two-way quantum and classical machines with small memory for online minimization problems
2019
We consider online algorithms. Typically the model is investigated with respect to competitive ratio. In this paper, we explore algorithms with small memory. We investigate two-way automata as a model for online algorithms with restricted memory. We focus on quantum and classical online algorithms. We show that there are problems that can be better solved by two-way automata with quantum and classical states than classical two-way automata in the case of sublogarithmic memory (sublinear size).
An improved quantum query algorithm for computing AND Boolean function
2010
We consider the quantum query model for computing Boolean functions. The definition of the function is known, but a black box contains the input X = (x 1 , x 2 , …, x n ). Black box can be accessed by querying x i values. The goal is to develop an algorithm, which would compute the function value for arbitrary input using as few queries to the black box as possible. We present two different quantum query algorithms for computing the basic Boolean function — logical AND of two bits. Both algorithms use only one query to determine the function value. Correct answer probability for the first algorithm is 80%, but for the second algorithm it is 90%. To compute this function with the same probab…
Robust Synchronization-Based Graph Clustering
2013
Complex graph data now arises in various fields like social networks, protein-protein interaction networks, ecosystems, etc. To reveal the underlying patterns in graphs, an important task is to partition them into several meaningful clusters. The question is: how can we find the natural partitions of a complex graph which truly reflect the intrinsic patterns? In this paper, we propose RSGC, a novel approach to graph clustering. The key philosophy of RSGC is to consider graph clustering as a dynamic process towards synchronization. For each vertex, it is viewed as an oscillator and interacts with other vertices according to the graph connection information. During the process towards synchro…