8 Search Results for "Goldberg, Halley"

Document
DOI: 10.4230/LIPIcs.ITCS.2026.97
One-Way Functions and Boundary Hardness of Randomized Time-Bounded Kolmogorov Complexity

Authors: Yanyi Liu and Rafael Pass

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
We revisit the question of whether worst-case hardness of the time-bounded Kolmogorov complexity problem, MINK^{poly} - that is, determining whether a string is "structured" (i.e., K^t(x) < n-1) or "random" (i.e., K^{poly(t)} ≥ n-1) - suffices to imply the existence of one-way functions (OWF). Liu-Pass (CRYPTO'25) recently showed that worst-case hardness of a boundary version of MINK^{poly} - where, roughly speaking, the goal is to decide whether given an instance x, (a) x is K^poly-random (i.e., K^{poly(t)}(x) ≥ n-1), or just close to K^poly-random (i.e., K^{t}(x) < n-1 but K^{poly(t)} > n - log n) - characterizes OWF, but with either of the following caveats (1) considering a non-standard notion of probabilistic K^t, as opposed to the standard notion of K^t, or (2) assuming somewhat strong, and non-standard, derandomization assumptions. In this paper, we present an alternative method for establishing their result which enables significantly weakening the caveats. First, we show that boundary hardness of the more standard randomized K^t problem suffices (where randomized K^t(x) is defined just like K^t(x) except that the program generating the string x may be randomized). As a consequence of this result, we can provide a characterization also in terms of just "plain" K^t under the most standard derandomization assumption (used to derandomize just BPP into P) - namely E ̸ ⊆ ioSIZE[2^{o(n)}]. Our proof relies on language compression schemes of Goldberg-Sipser (STOC'85); using the same technique, we also present the the first worst-case to average-case reduction for the exact MINK^{poly} problem (under the same standard derandomization assumption), improving upon Hirahara’s celebrated results (STOC'18, STOC'21) that only applied to a gap version of the MINK^{poly} problem, referred to as GapMINK^{poly}, where the goal is to decide whether K^t(x) ≤ n-O(log n)) or K^{poly(t)}(x) ≥ n-1 and under the same derandomization assumption.
Cite as

Yanyi Liu and Rafael Pass. One-Way Functions and Boundary Hardness of Randomized Time-Bounded Kolmogorov Complexity. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 97:1-97:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{liu_et_al:LIPIcs.ITCS.2026.97,
  author =	{Liu, Yanyi and Pass, Rafael},
  title =	{{One-Way Functions and Boundary Hardness of Randomized Time-Bounded Kolmogorov Complexity}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{97:1--97:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.97},
  URN =		{urn:nbn:de:0030-drops-253849},
  doi =		{10.4230/LIPIcs.ITCS.2026.97},
  annote =	{Keywords: One-way functions, Time-Bounded Kolmogorov Complexity, Worst-case to Average-case Reductions}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.20
Samplability Makes Learning Easier

Authors: Guy Blanc, Caleb Koch, Jane Lange, Carmen Strassle, and Li-Yang Tan

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
The standard definition of PAC learning (Valiant 1984) requires learners to succeed under all distributions - even ones that are intractable to sample from. This stands in contrast to samplable PAC learning (Blum, Furst, Kearns, and Lipton 1993), where learners only have to succeed under samplable distributions. We study this distinction and show that samplable PAC substantially expands the power of efficient learners. We first construct a concept class that requires exponential sample complexity in standard PAC but is learnable with polynomial sample complexity in samplable PAC. We then lift this statistical separation to the computational setting and obtain a separation relative to a random oracle. Our proofs center around a new complexity primitive, explicit evasive sets, that we introduce and study. These are sets for which membership is easy to determine but are extremely hard to sample from. Our results extend to the online setting to similarly show that its landscape changes when the adversary is assumed to be efficient instead of computationally unbounded.
Cite as

Guy Blanc, Caleb Koch, Jane Lange, Carmen Strassle, and Li-Yang Tan. Samplability Makes Learning Easier. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 20:1-20:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{blanc_et_al:LIPIcs.ITCS.2026.20,
  author =	{Blanc, Guy and Koch, Caleb and Lange, Jane and Strassle, Carmen and Tan, Li-Yang},
  title =	{{Samplability Makes Learning Easier}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{20:1--20:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.20},
  URN =		{urn:nbn:de:0030-drops-253071},
  doi =		{10.4230/LIPIcs.ITCS.2026.20},
  annote =	{Keywords: PAC learning, Samplable distributions}
}
Document
DOI: 10.4230/LIPIcs.CCC.2025.34
Witness Encryption and NP-Hardness of Learning

Authors: Halley Goldberg and Valentine Kabanets

Published in: LIPIcs, Volume 339, 40th Computational Complexity Conference (CCC 2025)

Abstract
We study connections between two fundamental questions from computer science theory. (1) Is witness encryption possible for NP [Sanjam Garg et al., 2013]? That is, given an instance x of an NP-complete language L, can one encrypt a secret message with security contingent on the ability to provide a witness for x ∈ L? (2) Is computational learning (in the sense of [Leslie G. Valiant, 1984; Michael J. Kearns et al., 1994]) hard for NP? That is, is there a polynomial-time reduction from instances of L to instances of learning? Our main contribution is that certain formulations of NP-hardness of learning characterize the existence of witness encryption for NP. More specifically, we show: - witness encryption for a language L ∈ NP is equivalent to a half-Levin reduction from L to the Computational Gap Learning problem (denoted CGL [Benny Applebaum et al., 2008]), where a half-Levin reduction is the same as a Levin reduction but only required to preserve witnesses in one direction, and CGL formalizes agnostic learning as a decision problem. We show versions of the statement above for witness encryption secure against non-uniform and uniform adversaries. We also show that witness encryption for NP with ciphertexts of logarithmic length, along with a circuit lower bound for E, are together equivalent to NP-hardness of a generalized promise version of MCSP. We complement the above with a number of unconditional NP-hardness results for agnostic PAC learning. Extending a result of [Shuichi Hirahara, 2022] to the standard setting of boolean circuits, we show NP-hardness of "semi-proper" learning. Namely: - for some polynomial s, it is NP-hard to agnostically learn circuits of size s(n) by circuits of size s(n)⋅ n^{1/(log log n)^O(1)}. Looking beyond the computational model of standard boolean circuits enables us to prove NP-hardness of improper learning (ie. without a restriction on the size of hypothesis returned by the learner). We obtain such results for: - learning circuits with oracle access to a given randomly sampled string, and - learning RAM programs. In particular, we show that a variant of MINLT [Ker-I Ko, 1991] for RAM programs is NP-hard with parameters corresponding to the setting of improper learning. We view these results as partial progress toward the ultimate goal of showing NP-hardness of learning boolean circuits in an improper setting. Lastly, we give some consequences of NP-hardness of learning for private- and public-key cryptography. Improving a main result of [Benny Applebaum et al., 2008], we show that if improper agnostic PAC learning is NP-hard under a randomized non-adaptive reduction (with some restrictions), then NP ⊈ BPP implies the existence of i.o. one-way functions. In contrast, if CGL is NP-hard under a half-Levin reduction, then NP ⊈ BPP implies the existence of i.o. public-key encryption.
Cite as

Halley Goldberg and Valentine Kabanets. Witness Encryption and NP-Hardness of Learning. In 40th Computational Complexity Conference (CCC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 339, pp. 34:1-34:43, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{goldberg_et_al:LIPIcs.CCC.2025.34,
  author =	{Goldberg, Halley and Kabanets, Valentine},
  title =	{{Witness Encryption and NP-Hardness of Learning}},
  booktitle =	{40th Computational Complexity Conference (CCC 2025)},
  pages =	{34:1--34:43},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-379-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{339},
  editor =	{Srinivasan, Srikanth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2025.34},
  URN =		{urn:nbn:de:0030-drops-237281},
  doi =		{10.4230/LIPIcs.CCC.2025.34},
  annote =	{Keywords: agnostic PAC learning, witness encryption, NP-hardness}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2024.51
Consequences of Randomized Reductions from SAT to Time-Bounded Kolmogorov Complexity

Authors: Halley Goldberg and Valentine Kabanets

Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)

Abstract
A central open question within meta-complexity is that of NP-hardness of problems such as MCSP and MK^{t}P. Despite a large body of work giving consequences of and barriers for NP-hardness of these problems under (restricted) deterministic reductions, very little is known in the setting of randomized reductions. In this work, we give consequences of randomized NP-hardness reductions for both approximating and exactly computing time-bounded and time-unbounded Kolmogorov complexity. In the setting of approximate K^{poly} complexity, our results are as follows. 1) Under a derandomization assumption, for any constant δ > 0, if approximating K^t complexity within n^{δ} additive error is hard for SAT under an honest randomized non-adaptive Turing reduction running in time polynomially less than t, then NP = coNP. 2) Under the same assumptions, the worst-case hardness of NP is equivalent to the existence of one-way functions. Item 1 above may be compared with a recent work of Saks and Santhanam [Michael E. Saks and Rahul Santhanam, 2022], which makes the same assumptions except with ω(log n) additive error, obtaining the conclusion NE = coNE. In the setting of exact K^{poly} complexity, where the barriers of Item 1 and [Michael E. Saks and Rahul Santhanam, 2022] do not apply, we show: 3) If computing K^t complexity is hard for SAT under reductions as in Item 1, then the average-case hardness of NP is equivalent to the existence of one-way functions. That is, "Pessiland" is excluded. Finally, we give consequences of NP-hardness of exact time-unbounded Kolmogorov complexity under randomized reductions. 4) If computing Kolmogorov complexity is hard for SAT under a randomized many-one reduction running in time t_R and with failure probability at most 1/(t_R)^16, then coNP is contained in non-interactive statistical zero-knowledge; thus NP ⊆ coAM. Also, the worst-case hardness of NP is equivalent to the existence of one-way functions. We further exploit the connection to NISZK along with a previous work of Allender et al. [Eric Allender et al., 2023] to show that hardness of K complexity under randomized many-one reductions is highly robust with respect to failure probability, approximation error, output length, and threshold parameter.
Cite as

Halley Goldberg and Valentine Kabanets. Consequences of Randomized Reductions from SAT to Time-Bounded Kolmogorov Complexity. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 51:1-51:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{goldberg_et_al:LIPIcs.APPROX/RANDOM.2024.51,
  author =	{Goldberg, Halley and Kabanets, Valentine},
  title =	{{Consequences of Randomized Reductions from SAT to Time-Bounded Kolmogorov Complexity}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)},
  pages =	{51:1--51:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-348-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{317},
  editor =	{Kumar, Amit and Ron-Zewi, Noga},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.51},
  URN =		{urn:nbn:de:0030-drops-210444},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2024.51},
  annote =	{Keywords: Meta-complexity, Randomized reductions, NP-hardness, Worst-case complexity, Time-bounded Kolmogorov complexity}
}
Document
DOI: 10.4230/LIPIcs.CCC.2023.12
Improved Learning from Kolmogorov Complexity

Authors: Halley Goldberg and Valentine Kabanets

Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)

Abstract
Carmosino, Impagliazzo, Kabanets, and Kolokolova (CCC, 2016) showed that the existence of natural properties in the sense of Razborov and Rudich (JCSS, 1997) implies PAC learning algorithms in the sense of Valiant (Comm. ACM, 1984), for boolean functions in P/poly, under the uniform distribution and with membership queries. It is still an open problem to get from natural properties learning algorithms that do not rely on membership queries but rather use randomly drawn labeled examples. Natural properties may be understood as an average-case version of MCSP, the problem of deciding the minimum size of a circuit computing a given truth-table. Problems related to MCSP include those concerning time-bounded Kolmogorov complexity. MKTP, for example, asks for the KT-complexity of a given string. KT-complexity is a relaxation of circuit size, as it does away with the requirement that a short description of a string be interpreted as a boolean circuit. In this work, under assumptions of MKTP and the related problem MK^tP being easy on average, we get learning algorithms for boolean functions in P/poly that - work over any distribution D samplable by a family of polynomial-size circuits (given explicitly in the case of MKTP), - only use randomly drawn labeled examples from D, and - are agnostic (do not require the target function to belong to the hypothesis class). Our results build upon the recent work of Hirahara and Nanashima (FOCS, 2021) who showed similar learning consequences but under a stronger assumption that NP is easy on average.
Cite as

Halley Goldberg and Valentine Kabanets. Improved Learning from Kolmogorov Complexity. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 12:1-12:29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{goldberg_et_al:LIPIcs.CCC.2023.12,
  author =	{Goldberg, Halley and Kabanets, Valentine},
  title =	{{Improved Learning from Kolmogorov Complexity}},
  booktitle =	{38th Computational Complexity Conference (CCC 2023)},
  pages =	{12:1--12:29},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-282-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{264},
  editor =	{Ta-Shma, Amnon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.12},
  URN =		{urn:nbn:de:0030-drops-182825},
  doi =		{10.4230/LIPIcs.CCC.2023.12},
  annote =	{Keywords: learning, Kolmogorov complexity, meta-complexity, average-case complexity}
}
Document
DOI: 10.4230/LIPIcs.CCC.2023.35
An Algorithmic Approach to Uniform Lower Bounds

Authors: Rahul Santhanam

Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)

Abstract
We propose a new family of circuit-based sampling tasks, such that non-trivial algorithmic solutions to certain tasks from this family imply frontier uniform lower bounds such as "NP is not in uniform ACC⁰" and "NP does not have uniform polynomial-size depth-two threshold circuits". Indeed, the most general versions of our sampling tasks have implications for central open problems such as NP vs P and PSPACE vs P. We argue the soundness of our approach by showing that the non-trivial algorithmic solutions we require do follow from standard cryptographic assumptions. In addition, we give evidence that a version of our approach for uniform circuits is necessary in order to separate NP from P or PSPACE from P. We give an algorithmic characterization for the PSPACE vs P question: PSPACE ≠ P iff either E has sub-exponential time non-uniform algorithms infinitely often or there are non-trivial space-efficient solutions to our sampling tasks for uniform Boolean circuits. We show how to use our framework to capture uniform versions of known non-uniform lower bounds, as well as classical uniform lower bounds such as the space hierarchy theorem and Allender’s uniform lower bound for the Permanent. We also apply our framework to prove new lower bounds: NP does not have polynomial-size uniform AC⁰ circuits with a bottom layer of MOD 6 gates, nor does it have polynomial-size uniform AC⁰ circuits with a bottom layer of threshold gates. Our proofs exploit recently defined probabilistic time-bounded variants of Kolmogorov complexity [Zhenjian Lu et al., 2022; Halley Goldberg et al., 2022; Halley Goldberg et al., 2022].
Cite as

Rahul Santhanam. An Algorithmic Approach to Uniform Lower Bounds. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 35:1-35:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{santhanam:LIPIcs.CCC.2023.35,
  author =	{Santhanam, Rahul},
  title =	{{An Algorithmic Approach to Uniform Lower Bounds}},
  booktitle =	{38th Computational Complexity Conference (CCC 2023)},
  pages =	{35:1--35:26},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-282-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{264},
  editor =	{Ta-Shma, Amnon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.35},
  URN =		{urn:nbn:de:0030-drops-183053},
  doi =		{10.4230/LIPIcs.CCC.2023.35},
  annote =	{Keywords: Probabilistic Kolmogorov complexity, sampling algorithms, uniform lower bounds}
}
Document
DOI: 10.4230/LIPIcs.CCC.2022.16
Probabilistic Kolmogorov Complexity with Applications to Average-Case Complexity

Authors: Halley Goldberg, Valentine Kabanets, Zhenjian Lu, and Igor C. Oliveira

Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)

Abstract
Understanding the relationship between the worst-case and average-case complexities of NP and of other subclasses of PH is a long-standing problem in complexity theory. Over the last few years, much progress has been achieved in this front through the investigation of meta-complexity: the complexity of problems that refer to the complexity of the input string x (e.g., given a string x, estimate its time-bounded Kolmogorov complexity). In particular, [Shuichi Hirahara, 2021] employed techniques from meta-complexity to show that if DistNP ⊆ AvgP then UP ⊆ DTIME[2^{O(n/log n)}]. While this and related results [Shuichi Hirahara and Mikito Nanashima, 2021; Lijie Chen et al., 2022] offer exciting progress after a long gap, they do not survive in the setting of randomized computations: roughly speaking, "randomness" is the opposite of "structure", and upper bounding the amount of structure (time-bounded Kolmogorov complexity) of different objects is crucial in recent applications of meta-complexity. This limitation is significant, since randomized computations are ubiquitous in algorithm design and give rise to a more robust theory of average-case complexity [Russell Impagliazzo and Leonid A. Levin, 1990]. In this work, we develop a probabilistic theory of meta-complexity, by incorporating randomness into the notion of complexity of a string x. This is achieved through a new probabilistic variant of time-bounded Kolmogorov complexity that we call pK^t complexity. Informally, pK^t(x) measures the complexity of x when shared randomness is available to all parties involved in a computation. By porting key results from meta-complexity to the probabilistic domain of pK^t complexity and its variants, we are able to establish new connections between worst-case and average-case complexity in the important setting of probabilistic computations: - If DistNP ⊆ AvgBPP, then UP ⊆ RTIME[2^O(n/log n)]. - If DistΣ^P_2 ⊆ AvgBPP, then AM ⊆ BPTIME[2^O(n/log n)]. - In the fine-grained setting [Lijie Chen et al., 2022], we get UTIME[2^O(√{nlog n})] ⊆ RTIME[2^O(√{nlog n})] and AMTIME[2^O(√{nlog n})] ⊆ BPTIME[2^O(√{nlog n})] from stronger average-case assumptions. - If DistPH ⊆ AvgBPP, then PH ⊆ BPTIME[2^O(n/log n)]. Specifically, for any 𝓁 ≥ 0, if DistΣ_{𝓁+2}^P ⊆ AvgBPP then Σ_𝓁^{P} ⊆ BPTIME[2^O(n/log n)]. - Strengthening a result from [Shuichi Hirahara and Mikito Nanashima, 2021], we show that if DistNP ⊆ AvgBPP then polynomial size Boolean circuits can be agnostically PAC learned under any unknown 𝖯/poly-samplable distribution in polynomial time. In some cases, our framework allows us to significantly simplify existing proofs, or to extend results to the more challenging probabilistic setting with little to no extra effort.
Cite as

Halley Goldberg, Valentine Kabanets, Zhenjian Lu, and Igor C. Oliveira. Probabilistic Kolmogorov Complexity with Applications to Average-Case Complexity. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 16:1-16:60, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{goldberg_et_al:LIPIcs.CCC.2022.16,
  author =	{Goldberg, Halley and Kabanets, Valentine and Lu, Zhenjian and Oliveira, Igor C.},
  title =	{{Probabilistic Kolmogorov Complexity with Applications to Average-Case Complexity}},
  booktitle =	{37th Computational Complexity Conference (CCC 2022)},
  pages =	{16:1--16:60},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-241-9},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{234},
  editor =	{Lovett, Shachar},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.16},
  URN =		{urn:nbn:de:0030-drops-165785},
  doi =		{10.4230/LIPIcs.CCC.2022.16},
  annote =	{Keywords: average-case complexity, Kolmogorov complexity, meta-complexity, worst-case to average-case reductions, learning}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2022.92
Optimal Coding Theorems in Time-Bounded Kolmogorov Complexity

Authors: Zhenjian Lu, Igor C. Oliveira, and Marius Zimand

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Abstract
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 𝖪(x) ≤ log(1/δ) + O(1). In a recent work, Lu and Oliveira [Zhenjian Lu and Igor C. Oliveira, 2021] 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/δ). Motivated by this discrepancy, we investigate optimal coding theorems in the time-bounded setting. Our main contributions can be summarised as follows. • Efficient coding theorem for rKt with a factor of 2. Addressing a question from [Zhenjian Lu and Igor C. Oliveira, 2021], we show that if x can be efficiently sampled with probability at least δ then rKt(x) ≤ (2 + o(1)) ⋅ log(1/δ) + O(log n). 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 ≥ 0.99, a probabilistic representation of x that certifies this rKt complexity bound. • Optimality under a cryptographic assumption. Under a hypothesis about the security of cryptographic pseudorandom generators, we show that no efficient coding theorem can achieve a bound of the form rKt(x) ≤ (2 - o(1)) ⋅ 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. • Optimal coding theorem for pK^t and unconditional Antunes-Fortnow. We consider pK^t complexity [Halley Goldberg et al., 2022], 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 [Luis Filipe Coelho Antunes and Lance Fortnow, 2009] which characterizes the worst-case running times of languages that are in average polynomial-time over all 𝖯-samplable distributions.
Cite as

Zhenjian Lu, Igor C. Oliveira, and Marius Zimand. Optimal Coding Theorems in Time-Bounded Kolmogorov Complexity. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 92:1-92:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{lu_et_al:LIPIcs.ICALP.2022.92,
  author =	{Lu, Zhenjian and Oliveira, Igor C. and Zimand, Marius},
  title =	{{Optimal Coding Theorems in Time-Bounded Kolmogorov Complexity}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{92:1--92:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.92},
  URN =		{urn:nbn:de:0030-drops-164331},
  doi =		{10.4230/LIPIcs.ICALP.2022.92},
  annote =	{Keywords: computational complexity, randomized algorithms, Kolmogorov complexity}
}
  • Refine by Type
  • 8 Document/PDF
  • 3 Document/HTML

  • Refine by Publication Year
  • 2 2026
  • 1 2025
  • 1 2024
  • 2 2023
  • 2 2022

  • Refine by Author
  • 4 Goldberg, Halley
  • 4 Kabanets, Valentine
  • 2 Lu, Zhenjian
  • 2 Oliveira, Igor C.
  • 1 Blanc, Guy
  • Show More...

  • Refine by Series/Journal
  • 8 LIPIcs

  • Refine by Classification
  • 5 Theory of computation → Computational complexity and cryptography
  • 1 Theory of computation
  • 1 Theory of computation → Circuit complexity
  • 1 Theory of computation → Complexity classes
  • 1 Theory of computation → Machine learning theory

  • Refine by Keyword
  • 3 Kolmogorov complexity
  • 2 NP-hardness
  • 2 average-case complexity
  • 2 learning
  • 2 meta-complexity
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact