Search

The classical coding theorem in Kolmogorov complexity states that if an $n$-bit string $x$ is sampled with probability $\delta$ by an algorithm with prefix-free domain then K$(x) \leq \log(1/\delta) + O(1)$. In a recent work, Lu and Oliveira [LO21] established an unconditional time-bounded version of this result, by showing that if $x$ can be efficiently sampled with probability $\delta$ then rKt$(x) = O(\log(1/\delta)) + O(\log n)$, where rKt denotes the randomized analogue of Levin's Kt complexity. Unfortunately, this result is often insufficient when transferring applications of the classical coding theorem to the time-bounded setting, as it achieves a $O(\log(1/\delta))$ bound instead of the information-theoretic optimal $\log(1/\delta)$. We show a coding theorem for rKt with a factor of $2$. As in previous work, our coding theorem is efficient in the sense that it provides a polynomial-time probabilistic algorithm that, when given $x$, the code of the sampler, and $\delta$, it outputs, with probability $\ge 0.99$, a probabilistic representation of $x$ that certifies this rKt complexity bound. Assuming the security of cryptographic pseudorandom generators, we show that no efficient coding theorem can achieve a bound of the form rKt$(x) \leq (2 - o(1)) \cdot \log(1/\delta) +$ poly$(\log n)$. Under a weaker assumption, we exhibit a gap between efficient coding theorems and existential coding theorems with near-optimal parameters. We consider pK$^t$ complexity [GKLO22], a variant of rKt where the randomness is public and the time bound is fixed. We observe the existence of an optimal coding theorem for pK$^t$, and employ this result to establish an unconditional version of a theorem of Antunes and Fortnow [AF09] which characterizes the worst-case running times of languages that are in average polynomial-time over all P-samplable distributions., Comment: Full version of a paper to be presented at ICALP 2022

We study connections between expansion in bipartite graphs and efficient online matching modeled via several games. In the basic game, an opponent switches {\em on} and {\em off} nodes on the left side and, at any moment, at most $K$ nodes may be on. Each time a node is switched on, it must be irrevocably matched with one of its neighbors. A bipartite graph has $e$-expansion up to $K$ if every set $S$ of at most $K$ left nodes has at least $e\#S$ neighbors. If all left nodes have degree $D$ and $e$ is close to $D$, then the graph is a lossless expander. We show that lossless expanders allow for a polynomial time strategy in the above game, and, furthermore, with a slight modification, they allow a strategy running in time $O(D \log N)$, where $N$ is the number of left nodes. Using this game and a few related variants, we derive applications in data structures and switching networks. Namely, (a) 1-query bitprobe storage schemes for dynamic sets (previous schemes work only for static sets),(b) explicit space- and time-efficient storage schemes for static and dynamic sets with non-adaptive access to memory (the first fully dynamic dictionary with non-adaptive probing using almost optimal space), and (c) non-explicit constant depth non-blocking $N$-connectors with poly$(\log N)$ time path finding algorithms whose size is optimal within a factor of $O(\log N)$ (previous connectors are double-exponentially slower)., Comment: The exposition has been improved and a few minor issues have been fixed

The paper proposes open problems in classical Kolmogorov complexity. Each problem is presented with background information and thus the article also surveys some recent studies in the area., Comment: The paper has appeared in the Open Problems column of SIGACT News

Bauwens and Zimand [BZ 2019] have shown that lossless expanders have an interesting online matching property. The result appears in an implicit form in [BZ 2019]. We present an explicit version of this property which is directly amenable to typical applications, prove it in a self-contained manner that clarifies the role of some parameters, and give two applications. A $(K, \epsilon)$ lossless expander is a bipartite graph such that any subset $S$ of size at most $K$ of nodes on the left side of the bipartition has at least $(1-\epsilon) D |S|$ neighbors, where $D$ is the left degree.The main result is that any such graph, after a slight modification, admits $(1-O(\epsilon)D, 1)$ online matching up to size $K$. This means that for any sequence $S=(x_1, \ldots, x_K)$ of nodes on the left side of the bipartition, one can assign in an online manner to each node $x_i$ in $S$ a set $A_i$ consisting of $(1-O(\epsilon))$ fraction of its neighbors so that the sets $A_1, \ldots, A_K$ are pairwise disjoint. "Online manner" refers to the fact that, for every $i$, the set of nodes assigned to $x_i$ only depends on the nodes assigned to $x_1, \ldots, x_{i-1}$. The first application concerns storage schemes for representing a set $S$, so that a membership query "Is $x \in S$?" can be answered probabilistically by reading a single bit. All the previous one-probe storage schemes were for a static set $S$. We show that a lossless expander can be used to construct a one-probe storage scheme for dynamic sets, i.e., sets in which elements can be inserted and deleted without affecting the representation of other elements. The second application is about non-blocking networks., Comment: Abstract shortened to meet arxiv requirements

We put forth new models for universal channel coding. Unlike standard codes which are designed for a specific type of channel, our most general universal code makes communication resilient on every channel, provided the noise level is below the tolerated bound, where the noise level t of a channel is the logarithm of its ambiguity (the maximum number of strings that can be distorted into a given one). The other more restricted universal codes still work for large classes of natural channels. In a universal code, encoding is channel-independent, but the decoding function knows the type of channel. We allow the encoding and the decoding functions to share randomness, which is unavailable to the channel. There are two scenarios for the type of attack that a channel can perform. In the oblivious scenario, codewords belong to an additive group and the channel distorts a codeword by adding a vector from a fixed set. The selection is based on the message and the encoding function, but not on the codeword. In the Hamming scenario, the channel knows the codeword and is fully adversarial. For a universal code, there are two parameters of interest: the rate, which is the ratio between the message length k and the codeword length n, and the number of shared random bits. We show the existence in both scenarios of universal codes with rate 1-t/n - o(1), which is optimal modulo the o(1) term. The number of shared random bits is O(log n) in the oblivious scenario, and O(n) in the Hamming scenario, which, for typical values of the noise level, we show to be optimal, modulo the constant hidden in the O() notation. In both scenarios, the universal encoding is done in time polynomial in n, but the channel-dependent decoding procedures are in general not efficient. For some weaker classes of channels we construct universal codes with polynomial-time encoding and decoding., Comment: Removed the mentioning of online matching, which is not used here

In a lossless compression system with target lengths, a compressor ${\cal C}$ maps an integer $m$ and a binary string $x$ to an $m$-bit code $p$, and if $m$ is sufficiently large, a decompressor ${\cal D}$ reconstructs $x$ from $p$. We call a pair $(m,x)$ $\textit{achievable}$ for $({\cal C},{\cal D})$ if this reconstruction is successful. We introduce the notion of an optimal compressor ${\cal C}_\text{opt}$, by the following universality property: For any compressor-decompressor pair $({\cal C}, {\cal D})$, there exists a decompressor ${\cal D}'$ such that if $(m,x)$ is achievable for $({\cal C},{\cal D})$, then $(m+\Delta, x)$ is achievable for $({\cal C}_\text{opt}, {\cal D}')$, where $\Delta$ is some small value called the overhead. We show that there exists an optimal compressor that has only polylogarithmic overhead and works in probabilistic polynomial time. Differently said, for any pair $({\cal C}, {\cal D})$, no matter how slow ${\cal C}$ is, or even if ${\cal C}$ is non-computable, ${\cal C}_{\text{opt}}$ is a fixed compressor that in polynomial time produces codes almost as short as those of ${\cal C}$. The cost is that the corresponding decompressor is slower. We also show that each such optimal compressor can be used for distributed compression, in which case it can achieve optimal compression rates, as given in the Slepian-Wolf theorem, and even for the Kolmogorov complexity variant of this theorem. Moreover, the overhead is logarithmic in the number of sources, and unlike previous implementations of Slepian-Wolf coding, meaningful compression can still be achieved if the number of sources is much larger than the length of the compressed strings., Comment: 26 pages

A fundamental question that has been studied in cryptography and in information theory is whether two parties can communicate confidentially using exclusively an open channel. We consider the model in which the two parties hold inputs that are correlated in a certain sense. This model has been studied extensively in information theory, and communication protocols have been designed which exploit the correlation to extract from the inputs a shared secret key. However, all the existing protocols are not universal in the sense that they require that the two parties also know some attributes of the correlation. In other words, they require that each party knows something about the other party's input. We present a protocol that does not require any prior additional information. It uses space-bounded Kolmogorov complexity to measure correlation and it allows the two legal parties to obtain a common key that looks random to an eavesdropper that observes the communication and is restricted to use a bounded amount of space for the attack. Thus the protocol achieves complexity-theoretical security, but it does not use any unproven result from computational complexity. On the negative side, the protocol is not efficient in the sense that the computation of the two legal parties uses more space than the space allowed to the adversary., Comment: Several small errors have been fixed and the presentation has been improved, following the reviewers' observations

Romashchenko and Zimand~\cite{rom-zim:c:mutualinfo} have shown that if we partition the set of pairs $(x,y)$ of $n$-bit strings into combinatorial rectangles, then $I(x:y) \geq I(x:y \mid t(x,y)) - O(\log n)$, where $I$ denotes mutual information in the Kolmogorov complexity sense, and $t(x,y)$ is the rectangle containing $(x,y)$. We observe that this inequality can be extended to coverings with rectangles which may overlap. The new inequality essentially states that in case of a covering with combinatorial rectangles, $I(x:y) \geq I(x:y \mid t(x,y)) - \log \rho - O(\log n)$, where $t(x,y)$ is any rectangle containing $(x,y)$ and $\rho$ is the thickness of the covering, which is the maximum number of rectangles that overlap. We discuss applications to communication complexity of protocols that are nondeterministic, or randomized, or Arthur-Merlin, and also to the information complexity of interactive protocols., Comment: 15 pages, 1 figure

We show that the mutual information, in the sense of Kolmogorov complexity, of any pair of strings $x$ and $y$ is equal, up to logarithmic precision, to the length of the longest shared secret key that two parties, one having $x$ and the complexity profile of the pair and the other one having $y$ and the complexity profile of the pair, can establish via a probabilistic protocol with interaction on a public channel. For $\ell > 2$, the longest shared secret that can be established from a tuple of strings $(x_1, \ldots , x_\ell)$ by $\ell$ parties, each one having one component of the tuple and the complexity profile of the tuple, is equal, up to logarithmic precision, to the complexity of the tuple minus the minimum communication necessary for distributing the tuple to all parties. We establish the communication complexity of secret key agreement protocols that produce a secret key of maximal length, for protocols with public randomness. We also show that if the communication complexity drops below the established threshold, then only very short secret keys can be obtained., Comment: 39 pages, 2 figures. A brief version of this work has been presented at 45th International Colloquium on Automata, Languages, and Programming (ICALP), Prague, July 10-13, 2018

Distributed compression is the task of compressing correlated data by several parties, each one possessing one piece of data and acting separately. The classical Slepian-Wolf theorem (D. Slepian, J. K. Wolf, IEEE Transactions on Inf. Theory, 1973) shows that if data is generated by independent draws from a joint distribution, that is by a memoryless stochastic process, then distributed compression can achieve the same compression rates as centralized compression when the parties act together. Recently, the author (M. Zimand, STOC 2017) has obtained an analogue version of the Slepian-Wolf theorem in the framework of Algorithmic Information Theory (also known as Kolmogorov complexity). The advantage over the classical theorem, is that the AIT version works for individual strings, without any assumption regarding the generative process. The only requirement is that the parties know the complexity profile of the input strings, which is a simple quantitative measure of the data correlation. The goal of this paper is to present in an accessible form that omits some technical details the main ideas from the reference (M. Zimand, STOC 2017).

It is impossible to effectively modify a string in order to increase its Kolmogorov complexity. But is it possible to construct a few strings, not longer than the input string, so that most of them have larger complexity? We show that the answer is yes. We present an algorithm that on input a string $x$ of length $n$ returns a list with $O(n^2)$ many strings, all of length $n$, such that 99\% of them are more complex than $x$, provided the complexity of $x$ is less than $n - \log \log n - O(1)$. We obtain similar results for other parameters, including a polynomial-time construction., Comment: This version corrects a bug in the previous version, which unfortunately is published in the proceedings of STACS 2017. Theorem 1.1 holds with parameters that are slightly weaker than previously claimed

Alice and Bob are given two correlated n-bit strings x_1 and, respectively, x_2, which they want to losslessly compress and send to Zack. They can either collaborate by sharing their strings, or work separately. We show that there is no disadvantage in the second scenario: Alice and Bob, without knowing the other party's string, can achieve almost optimal compression in the sense of Kolmogorov complexity. Furthermore, compression takes polynomial time and can be made at any combination of lengths that satisfy some necessary conditions (modulo additive polylog terms). More precisely, there exist probabilistic algorithms E_1, E_2, and deterministic algorithm D, with E_1 and E_2 running in polynomial time, having the following behavior: if n_1, n_2 are two integers satisfying n_1 + n_2 \geq C(x_1,x_2), n_1 \geq C(x_1 | x_2), n_2 \geq C(x_2 | x_1), then for i \in {1,2}, E_i on input x_i and n_i outputs a string of length n_i + \polylog n such that D on input E_1(x_1), E_2(x_2) reconstructs (x_1,x_2) with high probability (where C(x) denotes the plain Kolmogorov complexity of x, and C(x \mid y) is the complexity of x conditioned by y). Our main result is more general, as it deals with the compression of any constant number of correlated strings. It is an analog in the framework of algorithmic information theory of the classic Slepian-Wolf Theorem, a fundamental result in network information theory, in which x_1 and x_2 are realizations of two discrete random variables formed by drawing independently n times from a joint distribution. Also, in the classical result, the decompressor needs to know the joint distribution of the sources. In our result no type of independence is assumed and the decompressor does not have any apriori information about the sources that are compressed, and it still is the case that distributed compression is on a par with centralized compression., Comment: Accepted at STOC 2017. This revision has a few minor changes

An index $e$ in a numbering of partial-recursive functions is called minimal if every lesser index computes a different function from $e$. Since the 1960's it has been known that, in any reasonable programming language, no effective procedure determines whether or not a given index is minimal. We investigate whether the task of determining minimal indices can be solved in an approximate sense. Our first question, regarding the set of minimal indices, is whether there exists an algorithm which can correctly label 1 out of $k$ indices as either minimal or non-minimal. Our second question, regarding the function which computes minimal indices, is whether one can compute a short list of candidate indices which includes a minimal index for a given program. We give some negative results and leave the possibility of positive results as open questions.

A $c$-short program for a string $x$ is a description of $x$ of length at most $C(x) + c$, where $C(x)$ is the Kolmogorov complexity of $x$. We show that there exists a randomized algorithm that constructs a list of $n$ elements that contains a $O(\log n)$-short program for $x$. We also show a polynomial-time randomized construction that achieves the same list size for $O(\log^2 n)$-short programs. These results beat the lower bounds shown by Bauwens et al. \cite{bmvz:c:shortlist} for deterministic constructions of such lists. We also prove tight lower bounds for the main parameters of our result. The constructions use only $O(\log n)$ ($O(\log^2 n)$ for the polynomial-time result) random bits . Thus using only few random bits it is possible to do tasks that cannot be done by any deterministic algorithm regardless of its running time.

We show that if DTIME[2^O(n)] is not included in DSPACE[2^o(n)], then, for every set B in PSPACE/poly, all strings x in B of length n can be represented by a string compressed(x) of length at most log(|B^{=n}|)+O(log n), such that a polynomial-time algorithm, given compressed(x), can distinguish x from all the other strings in B^{=n}. Modulo the O(log n) additive term, this achieves the information-theoretic optimum for string compression. We also observe that optimal compression is not possible for sets more complex than PSPACE/poly because for any time-constructible superpolynomial function t, there is a set A computable in space t(n) such that at least one string x of length n requires compressed(x) to be of length 2 log(|A^=n|)., Comment: submitted to Theory of Computing Systems

Bauwens, Mahklin, Vereshchagin and Zimand [ECCC TR13-007] and Teutsch [arxiv:1212.6104] have shown that given a string x it is possible to construct in polynomial time a list containing a short description of it. We simplify their technique and present a shorter proof of this result.

Given a machine $U$, a $c$-short program for $x$ is a string $p$ such that $U(p)=x$ and the length of $p$ is bounded by $c$ + (the length of a shortest program for $x$). We show that for any standard Turing machine, it is possible to compute in polynomial time on input $x$ a list of polynomial size guaranteed to contain a O$(\log |x|)$-short program for $x$. We also show that there exists a computable function that maps every $x$ to a list of size $|x|^2$ containing a O$(1)$-short program for $x$. This is essentially optimal because we prove that for each such function there is a $c$ and infinitely many $x$ for which the list has size at least $c|x|^2$. Finally we show that for some standard machines, computable functions generating lists with $0$-short programs, must have infinitely often list sizes proportional to $2^{|x|}$.

One of the earliest and best-known application of the probabilistic method is the proof of existence of a 2 log n$-Ramsey graph, i.e., a graph with n nodes that contains no clique or independent set of size 2 log n. The explicit construction of such a graph is a major open problem. We show that a reasonable hardness assumption implies that in polynomial time one can construct a list containing polylog(n) graphs such that most of them are 2 log n-Ramsey.

Symmetry of information establishes a relation between the information that x has about y (denoted I(x : y)) and the information that y has about x (denoted I(y : x)). In classical information theory, the two are exactly equal, but in algorithmical information theory, there is a small excess quantity of information that differentiates the two terms, caused by the necessity of packaging information in a way that makes it accessible to algorithms. It was shown in [Zim11] that in the case of strings with simple complexity (that is the Kolmogorov complexity of their Kolmogorov complexity is small), the relevant information can be packed in a very economical way, which leads to a tighter relation between I(x : y) and I(y : x) than the one provided in the classical symmetry-of-information theorem of Kolmogorov and Levin. We give here a simpler proof of this result, using a suggestion of Alexander Shen. This result implies a van Lambalgen- type theorem for finite strings and plain complexity: If x is c-random and y is c-random relative to x, then xy is O(c)-random. We show that a similar result holds for prefix-free complexity and weak-K-randomness., Comment: Revised form of a paper communicated at WTCS 2012, Feb. 2012, Auckland, New Zealand

We establish tight bounds on the amount on nonuniformity that is necessary for extracting a string with randomness rate 1 from a single source of randomness with lower randomness rate. More precisely, as instantiations of more general results, we show that while O(1) amount of advice regarding the source is not enough for extracting a string with randomness rate 1 from a source string with constant subunitary random rate, \omega(1) amount of advice is., Comment: This is a part of the conference paper from CCC 2011. It corrects an erroneus result from there, namely Theorem 4.8 (the new version has weaker parameters)

We show that if DTIME[2^{O(n)}] is not included in DSPACE[2^{o(n)}], then, for every set B in PSPACE, all strings x in B of length n can be represented by a string compressed(x) of length at most log (|B^{=n}|) + O(log n), such that a polynomial-time algorithm, given compressed(x), can distinguish x from all the other strings in B^{=n}. Modulo the O(log n) additive trem, this achieves the information-theoretical optimum for string compression.

Randomness extraction is the process of constructing a source of randomness of high quality from one or several sources of randomness of lower quality. The problem can be modeled using probability distributions and min-entropy to measure their quality and also by using individual strings and Kolmogorov complexity to measure their quality. Complexity theorists are more familiar with the first approach. In this paper we survey the second approach. We present the connection between extractors and Kolmogorov extractors and the basic positive and negative results concerning Kolmogorov complexity extraction., Comment: Revised form of survey paper published in SIGACT News, Dec. 2010. A few corrections and references have been added

We prove a strong Symmetry of Information relation for random strings (in the sense of Kolmogorov complexity) and establish tight bounds on the amount on nonuniformity that is necessary for extracting a string with randomness rate 1 from a single source of randomness. More precisely, as instantiations of more general results, we show: (1) For all n-bit random strings x and y, x is random conditioned by y if and only if y is random conditioned by x, and (2) while O(1) amount of advice regarding the source is not enough for extracting a string with randomness rate 1 from a source string with constant random rate, \omega(1) amount of advice is. The proofs use Kolmogorov extractors as the main technical device., Comment: To appear in the proceedings of CCC 2011

The paper gives estimations for the sizes of the the following sets: (1) the set of strings that have a given dependency with a fixed string, (2) the set of strings that are pairwise \alpha independent, (3) the set of strings that are mutually \alpha independent. The relevant definitions are as follows: C(x) is the Kolmogorov complexity of the string x. A string y has \alpha -dependency with a string x if C(y) - C(y|x) \geq \alpha. A set of strings {x_1, \ldots, x_t} is pairwise \alpha-independent if for all i different from j, C(x_i) - C(x_i | x_j) \leq \alpha. A tuple of strings (x_1, \ldots, x_t) is mutually \alpha-independent if C(x_{\pi(1)} \ldots x_{\pi(t)}) \geq C(x_1) + \ldots + C(x_t) - \alpha, for every permutation \pi of [t].

The paper studies randomness extraction from sources with bounded independence and the issue of independence amplification of sources, using the framework of Kolmogorov complexity. The dependency of strings $x$ and $y$ is ${\rm dep}(x,y) = \max\{C(x) - C(x \mid y), C(y) - C(y\mid x)\}$, where $C(\cdot)$ denotes the Kolmogorov complexity. It is shown that there exists a computable Kolmogorov extractor $f$ such that, for any two $n$-bit strings with complexity $s(n)$ and dependency $\alpha(n)$, it outputs a string of length $s(n)$ with complexity $s(n)- \alpha(n)$ conditioned by any one of the input strings. It is proven that the above are the optimal parameters a Kolmogorov extractor can achieve. It is shown that independence amplification cannot be effectively realized. Specifically, if (after excluding a trivial case) there exist computable functions $f_1$ and $f_2$ such that ${\rm dep}(f_1(x,y), f_2(x,y)) \leq \beta(n)$ for all $n$-bit strings $x$ and $y$ with ${\rm dep}(x,y) \leq \alpha(n)$, then $\beta(n) \geq \alpha(n) - O(\log n)$.

It is shown that from two strings that are partially random and independent (in the sense of Kolmogorov complexity) it is possible to effectively construct polynomially many strings that are random and pairwise independent. If the two initial strings are random, then the above task can be performed in polynomial time. It is also possible to construct in polynomial time a random string, from two strings that have constant randomness rate., Comment: CiE 2009, Heidelberg

An infinite binary sequence has randomness rate at least $\sigma$ if, for almost every $n$, the Kolmogorov complexity of its prefix of length $n$ is at least $\sigma n$. It is known that for every rational $\sigma \in (0,1)$, on one hand, there exists sequences with randomness rate $\sigma$ that can not be effectively transformed into a sequence with randomness rate higher than $\sigma$ and, on the other hand, any two independent sequences with randomness rate $\sigma$ can be transformed into a sequence with randomness rate higher than $\sigma$. We show that the latter result holds even if the two input sequences have linear dependency (which, informally speaking, means that all prefixes of length $n$ of the two sequences have in common a constant fraction of their information). The similar problem is studied for finite strings. It is shown that from any two strings with sufficiently large Kolmogorov complexity and sufficiently small dependence, one can effectively construct a string that is random even conditioned by any one of the input strings.

Two objects are independent if they do not affect each other. Independence is well-understood in classical information theory, but less in algorithmic information theory. Working in the framework of algorithmic information theory, the paper proposes two types of independence for arbitrary infinite binary sequences and studies their properties. Our two proposed notions of independence have some of the intuitive properties that one naturally expects. For example, for every sequence $x$, the set of sequences that are independent (in the weaker of the two senses) with $x$ has measure one. For both notions of independence we investigate to what extent pairs of independent sequences, can be effectively constructed via Turing reductions (from one or more input sequences). In this respect, we prove several impossibility results. For example, it is shown that there is no effective way of producing from an arbitrary sequence with positive constructive Hausdorff dimension two sequences that are independent (even in the weaker type of independence) and have super-logarithmic complexity. Finally, a few conjectures and open questions are discussed.

The randomness rate of an infinite binary sequence is characterized by the sequence of ratios between the Kolmogorov complexity and the length of the initial segments of the sequence. It is known that there is no uniform effective procedure that transforms one input sequence into another sequence with higher randomness rate. By contrast, we display such a uniform effective procedure having as input two independent sequences with positive but arbitrarily small constant randomness rate. Moreover the transformation is a truth-table reduction and the output has randomness rate arbitrarily close to 1., Comment: Theorem 4.15 replaced with a weaker version; several other minor changes

Trevisan has shown that constructions of pseudo-random generators from hard functions (the Nisan-Wigderson approach) also produce extractors. We show that constructions of pseudo-random generators from one-way permutations (the Blum-Micali-Yao approach) can be used for building extractors as well. Using this new technique we build extractors that do not use designs and polynomial-based error-correcting codes and that are very simple and efficient. For example, one extractor produces each output bit separately in $O(\log^2 n)$ time. These extractors work for weak sources with min entropy $\lambda n$, for arbitrary constant $\lambda > 0$, have seed length $O(\log^2 n)$, and their output length is $\approx n^{\lambda/3}$., Comment: 21 pages, an extended abstract will appear in Proc. ICALP 2005; small corrections, some comments and references added

Simon as extended by Brassard and H{\o}yer shows that there are tasks on which polynomial-time quantum machines are exponentially faster than each classical machine infinitely often. The present paper shows that there are tasks on which polynomial-time quantum machines are exponentially faster than each classical machine almost everywhere., Comment: 16 pages