Image de couverture de livre

Optimal Coding for Randomized Kolmogorov Complexity and Its Applications

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Hirahara, Shuichi, Lu, Zhenjian, Nanashima, Mikito
Format:	Preprint
Publié:	2024
Sujets:	Computational Complexity
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

Communication Complexity is NP-hard
par: Hirahara, Shuichi, et autres
Publié: (2025)

Optimal PSPACE-hardness of Approximating Set Cover Reconfiguration
par: Hirahara, Shuichi, et autres
Publié: (2024)

Asymptotically Optimal Inapproximability of Maxmin $k$-Cut Reconfiguration
par: Hirahara, Shuichi, et autres
Publié: (2024)

Asymptotically Optimal Inapproximability of E$k$-SAT Reconfiguration
par: Hirahara, Shuichi, et autres
Publié: (2025)

Probabilistically Checkable Reconfiguration Proofs and Inapproximability of Reconfiguration Problems
par: Hirahara, Shuichi, et autres
Publié: (2023)

Reachability of Independent Sets and Vertex Covers Under Extended Reconfiguration Rules
par: Hirahara, Shuichi, et autres
Publié: (2025)

On Kolmogorov Structure Functions
par: Epstein, Samuel
Publié: (2024)

Random Permutations in Computational Complexity
par: Hitchcock, John M., et autres
Publié: (2025)

Prime Successor Irreducibility: Turing Machine Complexity, Kolmogorov Complexity, and Weakness-Based Formulations
par: Goertzel, Ben, et autres
Publié: (2026)

Polynomial-Time Pseudodeterministic Construction of Primes
par: Chen, Lijie, et autres
Publié: (2023)

Optimal Communication Complexity of Chained Index
par: Sundaresan, Janani
Publié: (2024)

Random Reed-Solomon Codes are List Recoverable with Optimal List Size
par: Doron, Dean, et autres
Publié: (2024)

Direct Product Theorems for Randomized Query Complexity
par: Ben-David, Shalev, et autres
Publié: (2025)

Linear Planar 3-SAT and Its Applications in Planning
par: Desbois, Victorien, et autres
Publié: (2025)

Computational Complexity of Envy-free and Exchange-stable Seat Arrangement Problems on Grid Graphs
par: Kawase, Sota, et autres
Publié: (2024)

Optimal Proof Systems for Complex Sets are Hard to Find
par: Egidy, Fabian, et autres
Publié: (2024)

The SPARSE-Relativization Framework and Applications to Optimal Proof Systems
par: Egidy, Fabian
Publié: (2026)

CodeComplex: Dataset for Worst-Case Time Complexity Prediction
par: Baik, Seung-Yeop, et autres
Publié: (2024)

Spiky Rank and Its Applications to Rigidity and Circuits
par: Hambardzumyan, Lianna, et autres
Publié: (2026)

The Optimization of Random Tree Codes for Limited Computational Resources
par: Bacinoglu, B. Tan
Publié: (2025)

Space-bounded online Kolmogorov complexity is additive
par: Bauwens, Bruno, et autres
Publié: (2025)

Punctured Low-Bias Codes Behave Like Random Linear Codes
par: Guruswami, Venkatesan, et autres
Publié: (2021)

Complexity of Planar Graph Orientation Consistency, Promise-Inference, and Uniqueness, with Applications to Minesweeper Variants
par: MIT Hardness Group, et autres
Publié: (2024)

On the Incompressibility of Truth With Application to Circuit Complexity
par: Tonon, Luke
Publié: (2025)

Time Series Correlations and Kolmogorov Complexity: A Hausdorff Dimension Perspective
par: Hamzi, Boumediene, et autres
Publié: (2026)

Kolmogorov-Loveland betting strategies lose the Betting game on open sets
par: Petrović, Tomislav
Publié: (2024)

Optimal Proximity Gap for Folded Reed--Solomon Codes via Subspace Designs
par: Jeronimo, Fernando Granha, et autres
Publié: (2026)

Searching for Falsified Clause in Random (log n)-CNFs is Hard for Randomized Communication
par: Riazanov, Artur, et autres
Publié: (2025)

PAC codes with Bounded-Complexity Sequential Decoding: Pareto Distribution and Code Design
par: Moradi, Mohsen, et autres
Publié: (2024)

Structure in Communication Complexity and Constant-Cost Complexity Classes
par: Hatami, Hamed, et autres
Publié: (2024)

Anti-Concentration for the Unitary Haar Measure and Applications to Random Quantum Circuits
par: Fefferman, Bill, et autres
Publié: (2024)

From Proof Complexity to Circuit Complexity via Interactive Protocols
par: Arteche, Noel, et autres
Publié: (2024)

Complex Boolean Turing Machines: An Algebraic Semantic Framework for Computational Complexity
par: Zheng, Bojin, et autres
Publié: (2026)

Information-Based Complexity vs Computational Complexity in Phaseless Polynomial Interpolation
par: Przybyłek, Michał R., et autres
Publié: (2026)

Identifying Codes Kernelization Limitations
par: Banik, Aritra, et autres
Publié: (2025)

On Lattices, Learning with Errors, Random Linear Codes, and Cryptography
par: Regev, Oded
Publié: (2024)

The Randomness Deficiency Function and the Shift Operator
par: Epstein, Samuel
Publié: (2023)

Optimal Trickle-Down Theorems for Path Complexes via C-Lorentzian Polynomials with Applications to Sampling and Log-Concave Sequences
par: Leake, Jonathan, et autres
Publié: (2025)

Query Complexity with Unknowns
par: Mande, Nikhil S., et autres
Publié: (2024)

The Complexity of Tensor Rank
par: Schaefer, Marcus, et autres
Publié: (2016)