1.
Fast
online matching in lossless expanders,
with Bruno Bauwens
2.
Universal
codes in the shared randomness model with general distortion capabilities, with Bruno Bauwens
3.
Secret
key agreement from correlated data, with no prior information, STACS 2020,
Montpellier.
4.
Universal
almost optimal compression and Slepian-Wolf coding in
probabilistic polynomial time, with Bruno Bauwens.
5.
An operational
characterization of mutual information in algorithmic information theory,
with Andrei Romashchenko, Journal of
ACM, 66(5), pp. 38:1-38:42, 2019 (conference version in ICALP 2018, Prague, July 9-13, 2018.)
6.
Distributed
compression through the lens of algorithmic information theory: a primer,
chapter in Mathematics Almost Everywhere: In Memory of Solomon Marcus, World
Scientific, 2018.
7.
Kolmogorov
complexity version of Slepian-Wolf coding, STOC
2017, Montreal, June 19-23, 2017
8.
List
approximation for increasing Kolmogorov complexity, STACS 2017,
Hannover, Germany, March 8-11, 2017
9.
A brief on short
descriptions, with Jason Teutsch, SIGACT News, March 2016.
10. On approximate decidability of minimal
programs, with J. Teutsch, TOCT 2015.
11. On optimal language compression for sets
in PSPACE/poly, with N. Vinodchandran, Theory Comput Syst, 2015.
12. Linear list-approximation for short
programs (or the power of a few random bits), with B. Bauwens,
CCC 2014,
In
short: It
is possible to construct in randomized poly time a list of linear size
containing a close to shortest description for any given
string. This cannot be done by any deterministic algorithm regardless of
running time.
13. Short lists with
short programs in short time, with B. Bauwens, A.
Makhlin, N. Vereshchagin, CCC 2013. [slides]
In short: It is possible to
construct in poly time a list containing a close to shortest description for any given
string.
14. On efficient
constructions of short lists containing mostly Ramsey graphs, TAMC 2013.
In
short: Under
a hardness assumption, it is shown that one can construct in poly time a list of polylog size containing optimal ramsey graphs.
15. Short lists
with short programs in short time -
a short proof, CiE 2014.
In
short: A
short exposition of some results from [Bauwens, Mahklin,
Vereshchagin, Zimand](the poly-time upper bound) and [Teutsch]
16. Symmetry of
information: a closer look, WTCS 2012, Auckland, Feb. 2012
In
short: Establishes
van Lambalgen-type
theorems for finite strings and randomness notions for plain complexity and
prefix-free complexity. Simplifies
the proof from the CCC’2011 paper.
17. Non-uniform
Kolmogorov extractors
In
short: This
is the part of the ``Symmetry of information and nonuniform randomness extraction via Kolmogorov
extractors” paper (CCC’2011) containing the results on nonuniform Kolmogorov extractors. It corrects one
of the results in the CCC’2011 paper.
18. Symmetry of
information and bounds on nonuniform randomness
extraction via Kolmogorov extractors, CCC 2011, San Jose, june 8-10, 2011. [slides]
In
short: Using Kolmogorov extractors, we show that for random strings x
and y, x is random conditioned by y iff y is
random conditioned by x. We also prove bounds on the quantity of advice
information that is needed to extract from a single source, an output with
randomness rate 1.
19. Combinatorial
characterizations of extractors and Kolmogorov extractors, CCR 2011, Cape
Town, Jan-Feb 2011. [slides]
In
short: Almost extractors and Kolmogorov extractors admit similar
characterizations in terms of a combinatorial object, called balanced table.
Part of the survey paper on Kolmogorov extractors.
20. Possibilities
and impossibilities in Kolmogorov complexity extraction. SIGACT News, Dec.
2010.
In
short: Survey paper on Kolmogorov extractors.
21. Impossibility
of independence amplification in Kolmogorov complexity theory, MFCS 2010,
Brno, Aug 2010. [slides]
In
short: From
two strings that have dependency \alpha, one cannot extract a string with randomness
deficiency less than \alpha. On the positive side, from two strings that have
dependency \alpha, one can extract with optimal parameters a string that has
randomness deficiency \alpha, even conditioned by any one of the input strings.
It follows that there is no effective procedure that reduces the dependency of
two strings.
22. Counting
dependent and independent strings, MFCS 2010, Brno, Aug 2010. [slides]
In
short: The
paper gives tight 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.
23. On generating
independent random strings, [slides], CiE 2009,
Heidelberg, July 2009. (This version corrects a small
error in Theorem 3)
In
short: From
two strings that are partially random (in the Kolmogorov complexity sense) and
independent it is possible to effectively construct polynomially many strings that are random and
pairwise independent. If the two initial strings have constant randomness rate,
one can construct in polynomial time a string that is random.
24. Extracting the
Kolmogorov complexity of strings and sequences from sources with limited
independence, [slides], STACS 2009, Freiburg, Feb. 2009.
In
short: I
showed here that there is a computable
transformation that takes as input two independent sequences and produces a
sequence with higher Kolmogorov complexity. This paper shows that this is possible
even if the two input sequences have a constant fraction of dependency. Also,
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.
25. Algorithmically
Independent Sequences, [slides], with Cristian Calude, DLT 2008, Kyoto, Sept. 2008.
In
short: We
put forward two notions of independence for infinite sequences. Some
impossibility results are obtained. For example, there is no uniform way to
obtain from a sequence with positive constructive Hausdorff dimension two sequences that are
independent.
26. Two sources are better
than one for increasing the Kolmogorov complexity of infinite sequences, [slides],
BEST PAPER AWARD, CSR 2008, Moscow, June 2008.
In
short: It
is known that there is no uniform effective transformation that takes one
infinite sequence with positive randomness rate (a.k.a Hausdorff dimension) and produces another
sequence with higher randomness rate. By contrast, we show that if we allow the
input to consist of two independent sequences, such a transformation exists.
27. Exposure-resilient extractors and the derandomization of probabilistic sublinear-time algorithms. [full version
-draft, Jan 14, 2008]. Computational Complexity, vol 17 (2008), pp. 220–253, DOI 10.1007/s00037-008-0243-3, special issue with selected
papers from CCC’2007.
In short: The full version is a merge of the CCC’2006 and CCC’2007 conference
papers. Some parameters are better than in the conference versions. [Slides
-talk Univ. of Bucharest, Feb. 2009]
28. On derandomizing probabilistic sublinear-time algorithms. [Proceedings version] [Slides] – Proc. 22nd Computational Complexity Conference
2007.
In
short: There
exists a positive constant \alpha < 1 such that for any function T(n) \leq n^{\alpha}
and for any problem L \in 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) \log T(n))} fraction of inputs of length n.
29. Exposure-resilient
extractors - Proc. 21st Computational Complexity Conference
2006.
In
short: 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. The paper contains the construction of such an extractor.
30. Simple extractors via
constructions of cryptographic pseudo-random generators (pdf), slides - BEST PAPER AWARD, ICALP’2005,
Lisbon.
In
short: Trevisan has
shown that constructions of pseudo-random generators from hard functions (the
Nisan-Wigderson approach)
also produce extractors. It is shown that constructions of pseudo-random
generators from one-way permutations (the Blum-Micali-Yao
approach) can be used for building extractors as well. The new extractors are
very simple and efficient (one of them works in polylog time).
31. A list-decodable code
with local encoding and local decoding, Proceedings SNPD’ 2005, Towson.
In
short: A
list-decodable code is constructed that allows encoding and list decoding in polylog time. The size of the list obtained at
decoding is exponential but not trivial and matches some known lower bounds.
32. The complexity of
finding top-Toda-equivalence-class members, with Lane Hemaspaandra, Mitsu Ogihara, and
Mohammed Zaki.
Shorter version in Proceedings LATIN’2004. Full version in Theory of Computing Systems,
vol. 39, no. 5 (Sept. 2006), pp. 669--684.
In
short: We identify
two computable properties of P-selective sets. Finding “the most likely: string
at each length can be done in FP^{\Sigma^2_p} and P-selective sets are not
bi-immune to the class of weakly-rankable sets.
33. Almost everywhere
superiority for quantum polynomial-time languages, with Edith Hemaspaandra and Lane Hemaspaandra.
In
short: It is shown
that there are languages (i.e., predicates) that can be computed, using
black-box access, by a polynomial-time quantum algorithm and for which every
classical machine needs exponential-time on almost every input.
34. Almost everywhere
superiority for quantum polynomial time, with Edith Hemaspaandra and Lane Hemaspaandra, Information and Computation,
vol. 175(2), 171-181, 2002.
In
short: It
is shown that there are functions that can be computed, using black-box access,
by a polynomial-time quantum algorithm and for which every classical machine
needs exponential-time on almost every input.
35. Probabilistically checkable
proofs the easy way, TCS’2002, Montreal, August 25-29, 2002.
In
short: Presents a much easier version of the PCP Theorem, but also
weaker, in which the prover is given a solution to an NP problem
and is polynomially bounded. It is employed to show that a
polynomial prover can send only polylog bits to convince a verifier that a
Boolean formula is satisfiable.
36. Extractors for the real
world with Kundi Xue, Journal of Universal Computer
Science, vol 6(1), 212-225, 2000.
In
short: An
extractor is presented that though theoretically weak is very good for values
of parameters of interest in practical applications. It is also shown that
checking whether a graph is an extractor is NP-complete.
37. Weighted NP Optimization
Problems: Logical Definability and Approximation Properties , in SIAM J. on Computing, 28(1),
1999, 36-56.
In
short: It
discusses how syntactical descriptions based on logic of arbitrary NP
optimization problems affect their approximation properties. Before this paper,
only the case of polynomially bounded
NP optimization problems has been studied.
38. Sampling under
adverse conditions ,
Workshop on Parallel Algorithms (WOPA'99), part of FCRC Atlanta, May, 1999.
· Less Recent Papers (some
have their abstract below):
Abstracts:
Marius Zimand,
A High-Low Kolmogorov
Complexity Law Equivalent To The 0-1 Law,
Information Processing Letters, 57(2)(1996), pp. 59-64.
Keywords:
Kolmogorov complexity, logical definability, probability asymptotics
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.
Lane A. Hemaspaandra, Ajit Ramachandran, and Marius Zimand,
Worlds to Die For ,
Sigact News
26(4)(1995), pp. 5-15; also TR 597, Computer Science Dept., U. Rochester,
November 1995.
Keywords:
computational complexity theory; complete sets; polynomial hierarchy;
pseudorandom generators; relativization; time hierarchiees.
We survey the background and challenges of
a number of open problems in the theory of relativization. Among the topics covered are pseudorandom
generators, time hierarchies, the potential collapse of the polynomial
hierarchy, and the existence of complete sets.
Lane Hemaspaandra, K. Rajasethupathy,
P. Sethupathy,
and Marius Zimand,
Power balance and congressional
apportionment algorithms
TR637, Computer Science Dept., U. Rochester, Sept. 1996
Keywords: power
indices, simulated annealing, dynamic programming
We measure the performance, in the task of
apportioning the Congress of the United States, of an algorithm combining a
simulated-annealing-driven search with an exact-computation dynamic programming
evaluation of the apportionments visited in the search. We compare this with
the actual algorithm used in the United States to apportion Congress, and with
a number of other algorithms that have been proposed. We conclude that on every
set of census data in this country's history, the simulated-annealing
apportionment provably yields far fairer apportionments than those of any of
the other algorithm considered, including the algorithm currently used for
Congressional apportionment.
Marius Zimand,
How to Privatize
Random Bits,
TR 616, Computer Science Dept., U. Rochester, April 1996.
Keywords: one-way
functions; pseudo-random generator; hard function; P/poly; EXP;
resource-bounded measure.
The paper investigates the extent to which
a public source of random bits can be used to obtain private random bits that
can be safely used in cryptographic protocols. We consider two cases: (a) the
case in which the part privatizing random bits is computationally more powerful
than the adversary, and (b) the case in which the part privatizing random bits
has a small number of private random bits. The first case corresponds to
randomized hard functions and the second variant corresponds to randomized
pseudo-random generators. We show the existence of strong randomized hard
functions and pseudo-random generators. As a side effect, it is shown that
relative to a random oracle $\p/poly$ is not measurable in $EXP$ in the
resource-bounded theoretical sense and a very strong separation between sublinear time and $AC^0$ is obtained.
Lane A. Hemaspaandra, Mohammed J. Zaki and Marius Zimand,
Polynomial-Time Semi-Rankable Sets,
TR 584, Computer Science Dept., U. Rochester, May 1995, revised February 1996.
Keywords:
semi-feasible sets; P-selectivity; ranking; closure properties; NNT.
We study the polynomial-time semi-rankable sets
(P-sr), the ranking analog of the P-selective sets.
We prove that P-sr is
a strict subset of the P-selective sets, and indeed that the two classes differ
with respect to closure under complementation, closure under union with P sets,
and closure under join with P sets. We also show that though P-sr falls
between the P-rankable and the weakly-P-rankable sets in its inclusiveness, it equals
neither of these classes.
Marius Zimand,
On the Size of Classes with Weak
Membership Properties,
Theoretical Computer Science (to appear); preliminary version in Proceedings
ICCI'95; also TR 557, Computer Science Dept., U. Rochester, December 1994.
Keywords:
resource-bounded measure; P-selective sets; P-multiselective sets; cheatable sets; easily countable
sets; easily approximable sets; near-testable sets; nearly
near-testable sets; P-bi-immune sets.
It is shown that the following classes
have measure 0 in E: the class of P-selective sets, the class of P-multiselective sets,
the class of cheatable sets, the class of easily countable sets, the class of
easily approximable sets, the class of near-testable sets,
the class of nearly near-testable sets, the class of sets that are not
P-bi-immune. These are corollaries of a more general result stating that the
class of sets that are p-isomorphic to P-quasi-approximable sets has measure 0 in E. By
considering the recent approach of Allender and
Strauss for measuring in subexponential classes,
we obtain similar results with respect to P for classes having weak logarithmic
time membership properties.
Marius Zimand,
Large Sets in AC$^0$: A Kolmogorov
Complexity Related Property and Some Applications,
Final version in Information Processing Letters, 62(30):165-170, 1997; also TR
556, Computer Science Dept., U. Rochester, December 1994.
Keywords: AC$^0$;
Kolmogorov complexity; strong separation.
If $A$ is a set in AC$^0$ such that for
some $q > 0$ and infinitely many $n$, $|A^n| >
2^{n - \log^q n}$,
then $A$ contains more than quasipolynomially many
strings with polynomial-time bounded length-conditioned Kolmogorov complexity
below $n^{\epsilon}$, for arbitrary $\epsilon > 0$, at each length $n$ where
$A$ satisfies the above density condition. As a consequence, we exhibit a set
in NP that is bi-immune to sets in AC$^0$ that satisfy the above density
condition.
Marius Zimand,
Martin-L\"{o}f Tests Can Help
Too ,
TR 541, Computer Science Dept., U. Rochester, November 1994.
Keywords:
Kolmogorov complexity; Martin-L\"{o}f test;
logical definability; probabilistic computation; probability asymptotics.
We argue that Martin-L\"{o}f tests provide useful techniques in proofs involving
Kolmogorov complexity. Our examples cover more areas: (1) logical definability;
we prove an analogue of the 0-1 Law for various logics in terms of structures
with high Kolmogorov complexity; (2) probabilistic computation; we display a
relation between the Kolmogorov complexity of the random strings on which a
probabilistic algorithm errs and the probability error of the algorithm as well
as a trade-off relation between the error probability, the length of the random
bits, the number of provers, and
the length of the provers' answers in one-round multiprover interactive proof systems for NP; and
(3) convergence rates of probability asymptotics; we find a general lower bound on the
convergence rate of such probabilities in terms of Kolmogorov complexity and
provide a concrete example for the probability that a random graph with $n$
vertices is connected.
Cristian Calude and Marius Zimand,
Effective Category and Measure
in Abstract Complexity Theory,,
Theoretical Computer Science, 154(2)(1996), pp. 307-327.
Keywords:
complexity measure; operator speed-up theorem; operator gap theorem;
compression theorem; effective Baire classification;
effective measure.
Strong variants of the Operator Speed-up
Theorem, Operator Gap Theorem and Compression Theorem are obtained using an
effective version of Baire Category
Theorem. It is also shown that all complexity classes of recursive predicates
have effective measure zero in the space of recursive predicates and, on the
other hand, the class of predicates with almost everywhere complexity above an
arbitrary recursive threshold has recursive measure one in the class of
recursive predicates.
Marius Zimand,
Weighted NP Optimization
Problems: Logical Definability and Approximation Properties , SIAM J. on Computing, vol.
28(1), 36-56, 1999; first version in Proc. 10th Structure in Complexity Theory
1995, pages 12-28; also TR 516, Computer Science Dept., U. Rochester, June
1994.
Keywords:
optimization problems; approximation algorithms; complexity classes;
interactive proof systems.
An optimization problem $A$ is defined by:
(1) a set ${\cal I}_A$
of input instances; we assume that this set can be recognized in polynomial
time, (2) for each $I \in {\cal I}_A$, a set ${\cal F}_A(I)$ of feasible solutions
associated to each input instance; we assume that each element in ${\cal F}_A(I)$
has size polynomially bounded in the size of $I$, and (3) an
objective function $f_A$ which maps each feasible
solution to a real number; we assume that this function is computable in
polynomial time. Problem $A$ is an NP optimization problem if the associated
decision problem ($\mbox{e.g.}$, given $I \in {\cal I}_A$ and a real value $k$, does there exists $J \in {\cal F}_A(I)$
with $f_A(J) \geq k$ ?) is in NP. 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, we
observe that, by attaching weights to tuples over the domain of the input, all
${NP}$ optimization problems admit a logical characterization. We show 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 and this is the
best possible result. We further analyze the weighted analogue of all
syntactically defined classes of optimization problems that are known to have
good approximation properties: $MAX~NP, MAX~SNP, MAX~SNP(\pi),
MIN~F^+\Pi_1$ and $MIN~F^+\Pi_2(1)$. All these classes continue to have the
same approximation properties in the case of positive weights. Using reductions
from multiprover interactive systems, we show that if $
NP \not \subseteq DTIME[2^{\log^{O(1)} n}]$, the approximation properties of
the above classes devaluate considerably when negative weights are also allowed
(with the exception of $MIN~F^+\Pi_1$, where only a weaker deterioration could
be proven). It follows that the general weighted versions of MAX 2SAT, SET
COVER, PRIORITY ORDERING (given a finite set $X$ and real-valued weights $w(\cdot, \cdot)$ to all pairs of
distinct elements in $X$ find the maximum over all permutations $\pi$ of $X$ of
$\sum_{\{(x,y)~:~ x,y \in X,
\pi(x) < \pi(y)\}} w(x,y)$) and of some other
closely related natural problems are not approximable in quasipolynomial time within a factor of $2^{\log^\mu
n}$ for some $\mu > 0$ (depending on the problem), unless $NP \subseteq DTIME[2^{\log^{O(1)}
n}]$.
· Lane
A. Hemaspaandra and Marius Zimand,
Strong Self-Reducibility
Precludes Strong Immunity,
Mathematical Systems Theory vol 29(5)(1996),
pp. 535-548; also TR 480 revised, Computer Science Dept., U. Rochester,
December 1993; revised May 1994.
Keywords:
structural complexity theory; balanced immunity; bi-immunity; generic oracles;
probability one separations.
We prove that NT is P bi-immune relative
to a generic oracle. Such a result is unobtainable for balanced immunity, as we
prove that NT is {\em not\/} P balanced immune. However, we
prove that NP and $\oplus$P are both P balanced immune relative to
a random oracle. We also investigate the structure of ambiguity-bounded
classes.
Marius Zimand,
The Complexity of the Optimal
Spanning Hypertree Problem,
TR 471, Computer Science Dept., U. Rochester, September 1993.
Keywords: hypergraphs; spanning hypertrees;
NP-completeness; approximation algorithms.
The notion of h-hypertree was defined in [Tomescu 1986] in order to improve the Bonferroni inequalities. We prove that the
problem of finding the optimal spanning h-hypertree of a complete hypergraph is NP complete, for $h \geq 3$.
Moreover, no polynomial time approximate algorithm even with poor approximation
ratio seems to exist for this problem. The existence of such an algorithm for
the minimum version achieving an approximation ratio of poly(n) implies P = NP,
and, for the maximum version, the existence of a quasipolynomial algorithm achieving the ratio
$2^{log^{\in}n}$ implies $NP \subseteq DTIME[n^{log^{O(1)}n}]$.
Marius Zimand,
On the Topological Size of
p-m-Complete Degrees,
Theoretical Computer Science 147(2)(1995), pp. 137-147; also TR 459, Computer
Science Dept., U. Rochester, May 1993.
Keywords:
p-m-degree; Baire category; p-isomorphism problem;
collapsing and noncollapsing degree.
A class of sets $C$ is nowhere dense if
for every open set one can find via a witness function an open subset which is
contained in the complement of $C$. The class $C$ is meagre (or of Baire first category) if it is a countable
union of nowhere dense sets, and is of Baire second
category if it is not meagre. All
polynomial many-one degrees are shown to be of second Baire category when witness functions are
allowed to run in $2^{\log^hn}$
time, for any $h$. Any improvement of this result for the complete p-m-degrees
of RE, EXP or NP implies P $\not=$ NP. The topological size of p-creative for P
sets and of polinomially paddable sets is also investigated.
Back to
Marius Zimand's Home
Page