Papers available on-line

 Recent Papers:

  1. Algorithmically Independent Sequences, with Cristian Calude

      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.

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

  1. Exposure-resilient extractors and the derandomization of probabilistic sublinear-time algorithms. [full version -draft,  Jan 14, 2008]. To appear in Computational Complexity, 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.

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

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

  1. Simple extractors via constructions of cryptographic pseudo-random generators (pdf), slides  - Best Paper Award ICALP’2005.

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

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

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

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

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

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

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

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

  1. Sampling under adverse conditions , Workshop on Parallel Algorithms (WOPA'99), part of FCRC Atlanta, May, 1999.

In short: It is shown how to sample so that even an adversary that has access to sample points but whose computational power is polynomially bounded cannot find a Boolean function for which the sample points are bad. A (somewhat) different construction is presented in Probabilistically checkable proofs the easy way.

 

Less Recent Papers (some have their abstract below):

  1. Sharing random bits with no process coordination, in Proc. 12th. IPPS, Orlando, 1998.
  2. Relative to a random oracle, P/poly is not measurable in EXP, Information Processing Letters, 1999.
  3. Efficient Privatization of Random Bits, Workshop "Randomized Algorithms", satellite of MFCS'98, Brno, 1998.
  4. A High-Low Kolmogorov Complexity Law Equivalent To The 0-1 Law, Information Processing Letters, (57)(2), 1996, 59-64.
  5. Power balance and congressional apportionment algorithms, with L. Hemaspaandra, K. Rajasethupathy, P. Sethupaty, in Journal of Experimental Algorithms, vol. 3(#1), 1998.
  6. Worlds to Die For , with L. Hemaspaandra and A. Ramachandran, in Sigact News, 26(4), 1995, 5-15.
  7. Polynomial-Time Semi-Rankable Sets, with L. Hemaspaandra and M. Zaki, in Journal of Computing and Information, 2(1), 1996, 50-67.
  8. On the Size of Classes with Weak Membership Properties, Theoretical Computer Science.
  9. Large Sets in AC$^0$: A Kolmogorov Complexity Related Property and Some Applications, Information Processing Letters 62(3), 165-170, 1997.
  10. Martin-L\"{o}f Tests Can Help Too , Technical Report 541, Dept. of Computer Science, Univ. of Rochester, 1994.
  11. Effective Category and Measure in Abstract Complexity Theory, with Cristian Calude, in Theoretical Computer Science, 154(2), 1996.
  12. Strong Sell-Reducibility Precludes Strong Immunity, with Lane Hemaspaandra, in Mathematical Systems Theory 29(5), 1996, 539-548.
  13. The Complexity of the Optimal Spanning Hypertree Problem, Technical Report 471, Dept. of Computer Science, Univ. of Rochester, 1993.
  14. On the Topological Size of p-m-Complete Degrees, Theoretical Computer Science 147(2), 1996, 307-327.

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

Last Modified 2/5/2007

mzimandATtowsonDOTedu