Buchumschlag

Optimal Coding for Randomized Kolmogorov Complexity and Its Applications

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Hirahara, Shuichi, Lu, Zhenjian, Nanashima, Mikito
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Computational Complexity
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Communication Complexity is NP-hard
von: Hirahara, Shuichi, et al.
Veröffentlicht: (2025)

Optimal PSPACE-hardness of Approximating Set Cover Reconfiguration
von: Hirahara, Shuichi, et al.
Veröffentlicht: (2024)

Asymptotically Optimal Inapproximability of Maxmin $k$-Cut Reconfiguration
von: Hirahara, Shuichi, et al.
Veröffentlicht: (2024)

Asymptotically Optimal Inapproximability of E$k$-SAT Reconfiguration
von: Hirahara, Shuichi, et al.
Veröffentlicht: (2025)

Probabilistically Checkable Reconfiguration Proofs and Inapproximability of Reconfiguration Problems
von: Hirahara, Shuichi, et al.
Veröffentlicht: (2023)

Reachability of Independent Sets and Vertex Covers Under Extended Reconfiguration Rules
von: Hirahara, Shuichi, et al.
Veröffentlicht: (2025)

On Kolmogorov Structure Functions
von: Epstein, Samuel
Veröffentlicht: (2024)

Random Permutations in Computational Complexity
von: Hitchcock, John M., et al.
Veröffentlicht: (2025)

Prime Successor Irreducibility: Turing Machine Complexity, Kolmogorov Complexity, and Weakness-Based Formulations
von: Goertzel, Ben, et al.
Veröffentlicht: (2026)

Polynomial-Time Pseudodeterministic Construction of Primes
von: Chen, Lijie, et al.
Veröffentlicht: (2023)

Optimal Communication Complexity of Chained Index
von: Sundaresan, Janani
Veröffentlicht: (2024)

Random Reed-Solomon Codes are List Recoverable with Optimal List Size
von: Doron, Dean, et al.
Veröffentlicht: (2024)

Direct Product Theorems for Randomized Query Complexity
von: Ben-David, Shalev, et al.
Veröffentlicht: (2025)

Linear Planar 3-SAT and Its Applications in Planning
von: Desbois, Victorien, et al.
Veröffentlicht: (2025)

Computational Complexity of Envy-free and Exchange-stable Seat Arrangement Problems on Grid Graphs
von: Kawase, Sota, et al.
Veröffentlicht: (2024)

Optimal Proof Systems for Complex Sets are Hard to Find
von: Egidy, Fabian, et al.
Veröffentlicht: (2024)

The SPARSE-Relativization Framework and Applications to Optimal Proof Systems
von: Egidy, Fabian
Veröffentlicht: (2026)

CodeComplex: Dataset for Worst-Case Time Complexity Prediction
von: Baik, Seung-Yeop, et al.
Veröffentlicht: (2024)

Spiky Rank and Its Applications to Rigidity and Circuits
von: Hambardzumyan, Lianna, et al.
Veröffentlicht: (2026)

The Optimization of Random Tree Codes for Limited Computational Resources
von: Bacinoglu, B. Tan
Veröffentlicht: (2025)

Space-bounded online Kolmogorov complexity is additive
von: Bauwens, Bruno, et al.
Veröffentlicht: (2025)

Punctured Low-Bias Codes Behave Like Random Linear Codes
von: Guruswami, Venkatesan, et al.
Veröffentlicht: (2021)

Complexity of Planar Graph Orientation Consistency, Promise-Inference, and Uniqueness, with Applications to Minesweeper Variants
von: MIT Hardness Group, et al.
Veröffentlicht: (2024)

On the Incompressibility of Truth With Application to Circuit Complexity
von: Tonon, Luke
Veröffentlicht: (2025)

Time Series Correlations and Kolmogorov Complexity: A Hausdorff Dimension Perspective
von: Hamzi, Boumediene, et al.
Veröffentlicht: (2026)

Kolmogorov-Loveland betting strategies lose the Betting game on open sets
von: Petrović, Tomislav
Veröffentlicht: (2024)

Optimal Proximity Gap for Folded Reed--Solomon Codes via Subspace Designs
von: Jeronimo, Fernando Granha, et al.
Veröffentlicht: (2026)

Searching for Falsified Clause in Random (log n)-CNFs is Hard for Randomized Communication
von: Riazanov, Artur, et al.
Veröffentlicht: (2025)

PAC codes with Bounded-Complexity Sequential Decoding: Pareto Distribution and Code Design
von: Moradi, Mohsen, et al.
Veröffentlicht: (2024)

Structure in Communication Complexity and Constant-Cost Complexity Classes
von: Hatami, Hamed, et al.
Veröffentlicht: (2024)

Anti-Concentration for the Unitary Haar Measure and Applications to Random Quantum Circuits
von: Fefferman, Bill, et al.
Veröffentlicht: (2024)

From Proof Complexity to Circuit Complexity via Interactive Protocols
von: Arteche, Noel, et al.
Veröffentlicht: (2024)

Complex Boolean Turing Machines: An Algebraic Semantic Framework for Computational Complexity
von: Zheng, Bojin, et al.
Veröffentlicht: (2026)

Information-Based Complexity vs Computational Complexity in Phaseless Polynomial Interpolation
von: Przybyłek, Michał R., et al.
Veröffentlicht: (2026)

Identifying Codes Kernelization Limitations
von: Banik, Aritra, et al.
Veröffentlicht: (2025)

On Lattices, Learning with Errors, Random Linear Codes, and Cryptography
von: Regev, Oded
Veröffentlicht: (2024)

The Randomness Deficiency Function and the Shift Operator
von: Epstein, Samuel
Veröffentlicht: (2023)

Optimal Trickle-Down Theorems for Path Complexes via C-Lorentzian Polynomials with Applications to Sampling and Log-Concave Sequences
von: Leake, Jonathan, et al.
Veröffentlicht: (2025)

Query Complexity with Unknowns
von: Mande, Nikhil S., et al.
Veröffentlicht: (2024)

The Complexity of Tensor Rank
von: Schaefer, Marcus, et al.
Veröffentlicht: (2016)