No. |
Title |
Author |
Year |
---|

1 |
Optimal Coding Theorems in Time-Bounded Kolmogorov Complexity |
Lu, Zhenjian et al. |
2022 |

2 |
Probabilistic Kolmogorov Complexity with Applications to Average-Case Complexity |
Goldberg, Halley et al. |
2022 |

3 |
An Efficient Coding Theorem via Probabilistic Representations and Its Applications |
Lu, Zhenjian et al. |
2021 |

4 |
Majority vs. Approximate Linear Sum and Average-Case Complexity Below NCĀ¹ |
Chen, Lijie et al. |
2021 |

5 |
Algorithms and Lower Bounds for De Morgan Formulas of Low-Communication Leaf Gates |
Kabanets, Valentine et al. |
2020 |

6 |
Beyond Natural Proofs: Hardness Magnification and Locality |
Chen, Lijie et al. |
2020 |

7 |
NP-Hardness of Circuit Minimization for Multi-Output Functions |
Ilango, Rahul et al. |
2020 |

8 |
NP-hardness of Minimum Circuit Size Problem for OR-AND-MOD Circuits |
Hirahara, Shuichi et al. |
2018 |

9 |
Conspiracies Between Learning Algorithms, Circuit Lower Bounds, and Pseudorandomness |
Oliveira, Igor C. Carboni et al. |
2017 |

10 |
Learning Circuits with few Negations |
Blais, Eric et al. |
2015 |