0000000000161219
AUTHOR
Ilja Kucevalovs
Quantum Queries on Permutations
K. Iwama and R. Freivalds considered query algorithms where the black box contains a permutation. Since then several authors have compared quantum and deterministic query algorithms for permutations. It turns out that the case of \(n\)-permutations where \(n\) is an odd number is difficult. There was no example of a permutation problem where quantization can save half of the queries for \((2m+1)\)-permutations if \(m\ge 2\). Even for \((2m)\)-permutations with \(m\ge 2\), the best proved advantage of quantum query algorithms is the result by Iwama/Freivalds where the quantum query complexity is \(m\) but the deterministic query complexity is \((2m-1)\). We present a group of \(5\)-permutati…
On the Influence of Technology on Learning Processes
Probabilistic computations and frequency computations were invented for the same purpose, namely, to study possible advantages of technology involving random choices. Recently several authors have discovered close relationships of these generalizations of deterministic computations to computations taking advice. Various forms of computation taking advice were studied by Karp and Lipton [1], Damm and Holzer [2], and Freivalds [3]. In the present paper, we apply the nonconstructive, probabilistic, and frequency methods to an inductive inference paradigm originally due to Gold [4] and investigate their impact on the resulting learning models. Several trade-offs with respect to the resulting l…
Frequency Prediction of Functions
Prediction of functions is one of processes considered in inductive inference. There is a "black box" with a given total function f in it. The result of the inductive inference machine F( ) is expected to be f(n+1). Deterministic and probabilistic prediction of functions has been widely studied. Frequency computation is a mechanism used to combine features of deterministic and probabilistic algorithms. Frequency computation has been used for several types of inductive inference, especially, for learning via queries. We study frequency prediction of functions and show that that there exists an interesting hierarchy of predictable classes of functions.