Derandomization and distinguishing complexity

Eric Allender, Michal Koucký, Sambuddha Roy, Detlef Ronneburger

Research output: Contribution to journalConference articlepeer-review

12 Scopus citations


We continue an investigation of resource-bounded Kolmogorov complexity and de randomization techniques begun in [2, 3]. We introduce nondeterministic time-bounded Kolmogorov complexity measures (KNt and KNT) and examine the properties of these measures using constructions of hitting set generators for nondeterministic circuits. We observe that KNt bears many similarities to the nondeterministic distinguishing complexity C N D of [8]. This motivates the definition of a new notion of time-bounded distinguishing complexity KDt, as an intermediate notion with connections to the class FewEXP. The set of KDt-random strings is complete for EXP under P/poly reductions. Most of the notions of resource-bounded Kolmogorov complexity discussed here and in the earlier papers have close connections to circuit size (on different types of circuits). We extend this framework to define notions of Kolmogorov complexity KB and KF that are related to branching program size and formula size, respectively. The sets of KB- and KF-random strings lie in coNP; we show that oracle access to these sets enables one to factor Blum integers. We obtain related intractability results for approximating minimum formula size, branching program size, and circuit size. The NEXP ⊆ NC1 and NEXP ⊆ L/poly questions are shown to be equivalent to conditions about the KF and KB complexity of sets in P.

Original languageEnglish (US)
Pages (from-to)209-220
Number of pages12
JournalProceedings of the Annual IEEE Conference on Computational Complexity
StatePublished - 2003
Event18th Annual IEEE Conference on Computational Complexity - Aarhus, Denmark
Duration: Jul 7 2003Jul 10 2003

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Computational Mathematics


Dive into the research topics of 'Derandomization and distinguishing complexity'. Together they form a unique fingerprint.

Cite this