All reports by Author Marius Zimand:

__
TR22-056
| 18th April 2022
__

Zhenjian Lu, Igor Carboni Oliveira, Marius Zimand#### Optimal Coding Theorems in Time-Bounded Kolmogorov Complexity

__
TR18-043
| 22nd February 2018
__

Andrei Romashchenko, Marius Zimand#### An operational characterization of mutual information in algorithmic information theory

Revisions: 2

__
TR15-017
| 20th January 2015
__

Bruno Bauwens, Marius Zimand#### Linear list-approximation for short programs (or the power of a few random bits)

__
TR13-007
| 8th January 2013
__

Bruno Bauwens, Anton Makhlin, Nikolay Vereshchagin, Marius Zimand#### Short lists with short programs in short time

Revisions: 1

__
TR11-069
| 18th April 2011
__

Marius Zimand#### On the optimal compression of sets in PSPACE

__
TR05-071
| 29th June 2005
__

Marius Zimand#### Simple extractors via constructions of cryptographic pseudo-random generators

__
TR01-027
| 23rd March 2001
__

Marius Zimand#### Probabilistically Checkable Proofs The Easy Way

Zhenjian Lu, Igor Carboni Oliveira, Marius Zimand

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 ... more >>>

Andrei Romashchenko, Marius Zimand

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 ...
more >>>

Bruno Bauwens, Marius Zimand

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$. ... more >>>

Bruno Bauwens, Anton Makhlin, Nikolay Vereshchagin, Marius Zimand

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 ... more >>>

Marius Zimand

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 ... more >>>

Marius Zimand

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 ...
more >>>

Marius Zimand

We present a weaker variant of the PCP Theorem that admits a

significantly easier proof. In this

variant the prover only has $n^t$ time to compute each

bit of his answer, for an arbitray but fixed constant

$t$, in contrast to

being all powerful. We show that

3SAT ...
more >>>