:: Library Catalog

Imagen de Portada

Guardado en:

Detalles Bibliográficos
Autores principales:	Hirahara, Shuichi, Lu, Zhenjian, Nanashima, Mikito
Formato:	Preprint
Publicado:	2024
Materias:	Computational Complexity
Acceso en línea:	https://arxiv.org/abs/2409.12744
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

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

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

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

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

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

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

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

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

On Kolmogorov Structure Functions
por: Epstein, Samuel
Publicado: (2024)

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

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

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

Optimal Communication Complexity of Chained Index
por: Sundaresan, Janani
Publicado: (2024)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

The Randomized Query Complexity of Finding a Tarski Fixed Point on the Boolean Hypercube
por: Brânzei, Simina, et al.
Publicado: (2024)

Adjusted Kolmogorov Complexity of Binary Words with Empirical Entropy Normalization
por: Vidakovic, Brani
Publicado: (2025)

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

Quantum Advantages in (n,d)->1 Random Access Codes
por: Ambainis, Andris, et al.
Publicado: (2015)

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

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

Cosystolic Expansion of Sheaves on Posets with Applications to Good 2-Query Locally Testable Codes and Lifted Codes
por: First, Uriya A., et al.
Publicado: (2024)

BigO(Bench) -- Can LLMs Generate Code with Controlled Time and Space Complexity?
por: Chambon, Pierre, et al.
Publicado: (2025)

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