Buchumschlag

Adjusted Kolmogorov Complexity of Binary Words with Empirical Entropy Normalization

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
1. Verfasser:	Vidakovic, Brani
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Computation Computational Complexity Information Theory 68Q30, 60G09 F.2.3
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Quantum Sabotage Complexity
von: Cornelissen, Arjan, et al.
Veröffentlicht: (2024)

CLIQUE as an AND of Polynomial-Sized Monotone Constant-Depth Circuits
von: Bodnar, Levente
Veröffentlicht: (2024)

Formula Size-Depth Tradeoffs for Iterated Sub-Permutation Matrix Multiplication
von: Rossman, Benjamin
Veröffentlicht: (2024)

Quantum Time-Space Tradeoffs for Matrix Problems
von: Beame, Paul, et al.
Veröffentlicht: (2024)

Tight Bounds on the Spooky Pebble Game: Recycling Qubits with Measurements
von: Kornerup, Niels, et al.
Veröffentlicht: (2021)

IECZ-III: Hardcore Condensation Lift with Size-Aware Invariants
von: Lela, Marko
Veröffentlicht: (2025)

An SoS Entropy Dichotomy via Windowed Hypercontractivity
von: Lela, Marko
Veröffentlicht: (2025)

An MDL-Style Cost Functional KC, Distribution-Preserving Reductions ($A2^d$), and an $AC^0$+log Lower Bound for 3SAT via Balanced 3XOR
von: Lela, Marko
Veröffentlicht: (2025)

Near-Optimal Bootstrapping of Hitting Sets for Algebraic Models
von: Kumar, Mrinal, et al.
Veröffentlicht: (2018)

Separation of PSPACE and EXP
von: Czerwinski, Reiner
Veröffentlicht: (2021)

On the Complexity of Identifying Groups without Abelian Normal Subgroups: Parallel, First Order, and GI-Hardness
von: Grochow, Joshua A., et al.
Veröffentlicht: (2025)

Polynomial Prenexing of QBFs with Non-Monotone Boolean Operators
von: Saffidine, Abdallah, et al.
Veröffentlicht: (2025)

The Word Problem for Products of Symmetric Groups
von: Simon, Hans U.
Veröffentlicht: (2025)

The Extremum Stack is a Minimal Sufficient Statistic for Rate-Independent Functionals: A Kolmogorov Complexity Characterisation
von: Frydrych, Piotr
Veröffentlicht: (2026)

Curved Boolean Logic: A Contextual Generalization of Propositional Logic with Algorithmic Consequences
von: von Liechtenstein, Maximilian R. P.
Veröffentlicht: (2025)

Weighted Automata and Logics Meet Computational Complexity
von: Kostolányi, Peter
Veröffentlicht: (2023)

NP-hardness of p-adic linear regression
von: Baker, Gregory D.
Veröffentlicht: (2026)

Minimalistic System Modelling: Behaviours, Interfaces, and Local Reasoning
von: Galmiche, Didier, et al.
Veröffentlicht: (2024)

Leakage-Resilient Hardness Equivalence to Logspace Derandomization
von: Shalunov, Yakov
Veröffentlicht: (2023)

NP-hard problems are not in BQP
von: Czerwinski, Reiner
Veröffentlicht: (2023)

Explicit separations between randomized and deterministic Number-on-Forehead communication
von: Kelley, Zander, et al.
Veröffentlicht: (2023)

The Computational Complexity of Variational Inequalities and Applications in Game Theory
von: Kapron, Bruce M., et al.
Veröffentlicht: (2024)

Counting Martingales for Measure and Dimension in Complexity Classes
von: Hitchcock, John M., et al.
Veröffentlicht: (2025)

The Polynomial Hierarchy does not collapse
von: Czerwinski, Reiner
Veröffentlicht: (2024)

How Does Machine Learning Manage Complexity?
von: Fortnow, Lance
Veröffentlicht: (2026)

Which graph motif parameters count?
von: Bläser, Markus, et al.
Veröffentlicht: (2025)

The Optimizer Quotient and the Certification Trilemma
von: Simas, Tristan
Veröffentlicht: (2026)

The Quantum Query Complexity of Finding a Tarski Fixed Point on the 2D Grid
von: Phillips, Reed
Veröffentlicht: (2026)

Conserved active information
von: Chen, Yanchen, et al.
Veröffentlicht: (2025)

On Channel Simulation with Causal Rejection Samplers
von: Goc, Daniel, et al.
Veröffentlicht: (2024)

Computational Complexity of Determining the Assembly Index
von: Masierak, Piotr
Veröffentlicht: (2026)

Logarithmic Weisfeiler--Leman and Treewidth
von: Levet, Michael, et al.
Veröffentlicht: (2023)

Canonizing Graphs of Bounded Rank-Width in Parallel via Weisfeiler--Leman
von: Levet, Michael, et al.
Veröffentlicht: (2023)

Unifying lower bounds for algebraic machines, semantically
von: Seiller, Thomas, et al.
Veröffentlicht: (2018)

On systematic construction of correct logic programs
von: Drabent, Włodzimierz
Veröffentlicht: (2025)

On the MST-ratio: Theoretical Bounds and Complexity of Finding the Maximum
von: Ameli, Afrouz Jabal, et al.
Veröffentlicht: (2024)

Computational Complexity of Physical Counting
von: Simas, Tristan
Veröffentlicht: (2026)

DAG Scheduling in the BSP Model
von: Papp, Pál András, et al.
Veröffentlicht: (2023)

E-variables and tests of randomness for distribution classes
von: Potapov, Georgii, et al.
Veröffentlicht: (2026)

Dichotomy for orderings?
von: Kun, Gábor, et al.
Veröffentlicht: (2025)