In a lossless compression system with target lengths, a compressor 𝒞 maps an integer m and a binary string x to an m -bit code p , and if m is sufficiently large, a decompressor 𝒟 reconstructs x from p . We call a pair ( m,x ) achievable for (𝒞,𝒟) if this reconstruction is successful. We introduce the notion of an optimal compressor 𝒞 opt by the following universality property: For any compressor-decompressor pair (𝒞,𝒟), there exists a decompressor 𝒟 ′ such that if (m,x) is achievable for (𝒞,𝒟), then ( m + Δ , x ) is achievable for (𝒞 opt , 𝒟 ′ ), where Δ 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 (𝒞,𝒟), no matter how slow 𝒞 is, or even if 𝒞 is non-computable, 𝒞 opt is a fixed compressor that in polynomial time produces codes almost as short as those of 𝒞. 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.

The classical coding theorem in Kolmogorov complexity states that if an $n$-bit string $x$ is sampled with probability $δ$ by an algorithm with prefix-free domain then K$(x) \leq \log(1/δ) + 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 $δ$ then rKt$(x) = O(\log(1/δ)) + 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/δ))$ bound instead of the information-theoretic optimal $\log(1/δ)$. 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 $δ$, 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/δ) +$ 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.

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.

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 ℓ > 2, the longest shared secret that can be established from a tuple of strings ( x 1 , …, x ℓ ) by ℓ 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.

Alice and Bob are given two correlated n-bit strings x1 and, respectively, x2, 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 compress their strings to almost minimal description length 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 polylogarithmic terms). More precisely, there exist probabilistic algorithms E1, E2, and D, with E1 and E2 running in polynomial time, having the following behavior: if n1, n2 are two integers satisfying n1 + n2 ≥ C(x1,x2), n1 ≥ C(x1 | x2), n2 ≥ C(x2 | x1), then for i ∈ {1,2}, Ei on input xi and ni outputs a string of length ni + O(log3 n) such that D on input E1(x1), E2(x2) reconstructs (x1,x2) with high probability (where C(x) denotes the plain Kolmogorov complexity of x, and C(x | 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 x1 and x2 are realizations of two discrete random variables representing n independent draws from a joint distribution. 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 prior information about the sources that are compressed.

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(log2n)-short programs. These results beat the lower bounds shown by Bauwens et al. [1] 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(log2n) 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 derive quantitative results regarding sets of n-bit strings that have different dependency or independency properties. Let C(x) be the Kolmogorov complexity of the string x. A string y has α dependency with a string x if C(y) − C(y | x) ≥ α. A set of strings {x 1 , . . . , x t } is pairwise α-independent if for all i ≠ j, C(x i ) − C(x i | x j ) < α. A tuple of strings (x 1 , . . . , x t ) is mutually α-independent if C(x π(1) . . . x π(t) ) > C(x 1 )+. . .+C(x t ) − α, for every permutation π of [t]. We show that: • For every n-bit string x with complexity C(x) ≥ α + 7 log n, the set of n-bit strings that have α dependency with x has size at least (1/poly(n))2 n−α . In case α is computable from n and C(x) ≥ α + 12 log n, the size of the same set is at least (1/C)2 n−α − poly(n)2 α , for some positive constant C. • There exists a set of n-bit strings A of size poly(n)2 α such that any n-bit string has α-dependency with some string in A. • If the set of n-bit strings {x 1 , . . . , x t } is pairwise α-independent, then t ≤ poly(n)2 α . This bound is tight within a poly(n) factor, because, for every n, there exists a set of n-bit strings {x 1 , . . . , x t } that is pairwise α-dependent with t = (1/poly(n)) · 2 α (for all α ≥ 5 log n). • If the tuple of n-bit strings (x 1 , . . . , x t ) is mutually α-independent, then t ≤ poly(n)2 α (for all α ≥ 7 log n + 6).

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 universal 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 exist computable functions that map every x to a list of size O(|x|2) containing a O(1)-short program for x and this is essentially optimal because we prove that such a list must have size Ω(|x|2). Finally we show that for some machines, computable lists containing a shortest program must have length Ω(2|x|).

We study whether randomness can be extracted from two strings that are only partially random and only partially independent, where randomness is taken in the sense of Kolmogorov complexity and the dependency of strings x and y is given by dep(x, y) = C(x) + C(y) − C(xy) (C(x) denotes the Kolmogorov complexity of x). The general setting is that the input of the extraction procedure consists of two strings x and y of length n, each having Kolmogorov complexity at least s(n) and dependency at most α(n). It is shown that there exists a computable function that, from two such strings x and y, extracts ≈2s(n) random bits that have Kolmogorov complexity ≈ 2s(n) − α(n) (so the output is α(n) close to being random). It is also shown that (a) it is possible to extract ≈s(n)/2 bits that are α(n) close to being random even conditioned by any one of x or y, and (b) it is possible to construct polynomially many strings of length ≈s(n)/3 that are pairwise α(n) close to being random and also α(n) close to random conditioned by any one of x and y. A polynomial-time extraction procedure exists for the case when x and y have linear Kolmogorov complexity (i.e. C(x) ≥ δn and C(y) ≥ δn, for a constant δ > 0). However, the output is only poly(α(n) + log n) close to random.

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: · 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; · 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, ω(1) amount of advice is. The proofs use Kolmogorov extractors as the main technical device.

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.

There exists a positive constant alphaT(n) lesnalphaand for any problemLisin BPTIME(T(n)), there exists a deterministic algorithm running in poly(T(n)) time which decides L, except for at most a 2-Omega(T(n)logT(n))fraction of inputs of lengthn.

An exposure-resilient extractor is an efficient procedure that, from a random variable with imperfect min-entropy, produces randomness that passes all statistical tests including those that have bounded access to the random variable, with adaptive queries that can depend on the string being tested. More precisely, EXT : {0, 1}ntimes {0, 1}drarr {0, 1}mis a (k, epsi)-exposure resilient extractor resistant to q queries if, when the min-entropy of x is at least k and y is random, EXT(x, y) looks epsi-random to all statistical tests modeled by oracle circuits of unbounded complexity that can query q bits of x. We construct, for any deltadelta, k = n - nOmega(1), epsi = n-Omega(1), m = nOmega(1)and d = O(log n)

Guruswamy and Indyk (2004) have shown that there exists an error-correcting code for which list-decoding from a (1-/spl epsi/) fraction of errors can be done in linear time. We present a binary code for which list-decoding from a (1/2-/spl epsi/) fraction of errors can be done in polylog time. The size of the list of candidates for the correct codeword is exponential but non-trivial and moreover is tight with respect to some known lower bounds. More precisely, for arbitrary constants /spl epsi/>0 and /spl lambda/>0 we present a code E : {0, 1}/sup n/ /spl rarr/ {0, 1}/sup n~/ such that n/sup ~/ = n/sup O(log(1//spl epsi/))/ and every ball in {0, 1}/sup n~/ of radius ( 1/2 -/spl epsi/)n/sup ~/ (in the Hamming-distance sense) contains at most 2/sup /spl lambda/n/ strings. Furthermore, the code E has encoding and list-decoding algorithms that produce each bit of their output in time polylog (n).

To better prepare our graduates to face the challenges in computer and information security, in Fall 2002, Towson University launched an undergraduate track in computer security for the computer science majors. This paper describes the motivation behind this track and discusses its structure and requirements.

Extending a well-known property of NP optimization problems in which the value of the optimum is guaranteed to be polynomially bounded in the length of the input, it is observed that, by attaching weights to tuples over the domain of the input, all NP optimization problems admit a logical characterization. It is shown that any NP optimization problem can be stated as a problem in which the constraint conditions can be expressed by a $\Pi_2$ first-order formula. The paper analyzes the weighted analogue of all syntactically defined classes of optimization problems that are known to have good approximation properties in the nonweighted case. Dramatic changes occur when negative weights are allowed.

It is shown that the 0–1 Law for recursive logics on finite structures admits an equivalent formulation in terms of Kolmogorov complexity. The new formulation opens the possibility of using the Kolmogorov complexity apparatus to easily derive various properties for finite structures satisfying a given properties. Examples that illustrate this point are provided.

All polynomial many-one degrees are shown to be of second Baire category in the superset topology when witness functions are allowed to run in 2loghn time, for any h. Any improvement of this result for the complete p-m-degrees of RE, EXP or NP implies P ≠ NP or the nonisomorphism of the NP-complete sets.

In the classical Cantor topology or in the superset topology, NP and, consequently, classes included in NP are meagre. However, in a natural combination of the two topologies, we prove that NP — P, if not empty, is a second category class, while NP-complete sets form a first category class. These results are extended to different levels in the polynomial hierarchy and to the low and high hierarchies. P-immune sets in NP, NP-simple sets, P-bi-immune sets and NP-effectively simple sets are all second category (if not empty). It is shown that if C is any of the above second category classes, then for all B∈NP there exists an A∈C such that A is arbitrarily close to B infinitely often.