Copertina

Optimal Coding for Randomized Kolmogorov Complexity and Its Applications

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Hirahara, Shuichi, Lu, Zhenjian, Nanashima, Mikito
Natura:	Preprint
Pubblicazione:	2024
Soggetti:	Computational Complexity
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Communication Complexity is NP-hard
di: Hirahara, Shuichi, et al.
Pubblicazione: (2025)

Optimal PSPACE-hardness of Approximating Set Cover Reconfiguration
di: Hirahara, Shuichi, et al.
Pubblicazione: (2024)

Asymptotically Optimal Inapproximability of Maxmin $k$-Cut Reconfiguration
di: Hirahara, Shuichi, et al.
Pubblicazione: (2024)

Asymptotically Optimal Inapproximability of E$k$-SAT Reconfiguration
di: Hirahara, Shuichi, et al.
Pubblicazione: (2025)

Probabilistically Checkable Reconfiguration Proofs and Inapproximability of Reconfiguration Problems
di: Hirahara, Shuichi, et al.
Pubblicazione: (2023)

Reachability of Independent Sets and Vertex Covers Under Extended Reconfiguration Rules
di: Hirahara, Shuichi, et al.
Pubblicazione: (2025)

On Kolmogorov Structure Functions
di: Epstein, Samuel
Pubblicazione: (2024)

Random Permutations in Computational Complexity
di: Hitchcock, John M., et al.
Pubblicazione: (2025)

Prime Successor Irreducibility: Turing Machine Complexity, Kolmogorov Complexity, and Weakness-Based Formulations
di: Goertzel, Ben, et al.
Pubblicazione: (2026)

Polynomial-Time Pseudodeterministic Construction of Primes
di: Chen, Lijie, et al.
Pubblicazione: (2023)

Optimal Communication Complexity of Chained Index
di: Sundaresan, Janani
Pubblicazione: (2024)

Random Reed-Solomon Codes are List Recoverable with Optimal List Size
di: Doron, Dean, et al.
Pubblicazione: (2024)

Direct Product Theorems for Randomized Query Complexity
di: Ben-David, Shalev, et al.
Pubblicazione: (2025)

Linear Planar 3-SAT and Its Applications in Planning
di: Desbois, Victorien, et al.
Pubblicazione: (2025)

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

Optimal Proof Systems for Complex Sets are Hard to Find
di: Egidy, Fabian, et al.
Pubblicazione: (2024)

The SPARSE-Relativization Framework and Applications to Optimal Proof Systems
di: Egidy, Fabian
Pubblicazione: (2026)

CodeComplex: Dataset for Worst-Case Time Complexity Prediction
di: Baik, Seung-Yeop, et al.
Pubblicazione: (2024)

Spiky Rank and Its Applications to Rigidity and Circuits
di: Hambardzumyan, Lianna, et al.
Pubblicazione: (2026)

The Optimization of Random Tree Codes for Limited Computational Resources
di: Bacinoglu, B. Tan
Pubblicazione: (2025)

Space-bounded online Kolmogorov complexity is additive
di: Bauwens, Bruno, et al.
Pubblicazione: (2025)

Punctured Low-Bias Codes Behave Like Random Linear Codes
di: Guruswami, Venkatesan, et al.
Pubblicazione: (2021)

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

On the Incompressibility of Truth With Application to Circuit Complexity
di: Tonon, Luke
Pubblicazione: (2025)

Time Series Correlations and Kolmogorov Complexity: A Hausdorff Dimension Perspective
di: Hamzi, Boumediene, et al.
Pubblicazione: (2026)

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

Optimal Proximity Gap for Folded Reed--Solomon Codes via Subspace Designs
di: Jeronimo, Fernando Granha, et al.
Pubblicazione: (2026)

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

PAC codes with Bounded-Complexity Sequential Decoding: Pareto Distribution and Code Design
di: Moradi, Mohsen, et al.
Pubblicazione: (2024)

Structure in Communication Complexity and Constant-Cost Complexity Classes
di: Hatami, Hamed, et al.
Pubblicazione: (2024)

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

From Proof Complexity to Circuit Complexity via Interactive Protocols
di: Arteche, Noel, et al.
Pubblicazione: (2024)

Complex Boolean Turing Machines: An Algebraic Semantic Framework for Computational Complexity
di: Zheng, Bojin, et al.
Pubblicazione: (2026)

Information-Based Complexity vs Computational Complexity in Phaseless Polynomial Interpolation
di: Przybyłek, Michał R., et al.
Pubblicazione: (2026)

Identifying Codes Kernelization Limitations
di: Banik, Aritra, et al.
Pubblicazione: (2025)

On Lattices, Learning with Errors, Random Linear Codes, and Cryptography
di: Regev, Oded
Pubblicazione: (2024)

The Randomness Deficiency Function and the Shift Operator
di: Epstein, Samuel
Pubblicazione: (2023)

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

Query Complexity with Unknowns
di: Mande, Nikhil S., et al.
Pubblicazione: (2024)

The Complexity of Tensor Rank
di: Schaefer, Marcus, et al.
Pubblicazione: (2016)