Buchumschlag

Term Coding and Dispersion: A Perfect-vs-Rate Complexity Dichotomy for Information Flow

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
1. Verfasser:	Riis, Søren
Format:	Preprint
Veröffentlicht:	2026
Schlagworte:	Information Theory 94A15, 68Q17, 05C57 E.4; F.1.3; G.2.2
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Term Coding for Extremal Combinatorics: Dispersion and Complexity Dichotomies
von: Riis, Søren
Veröffentlicht: (2025)

Term Coding: An Entropic Framework for Extremal Combinatorics and the Guessing--Number Sandwich Theorem
von: Riis, Søren
Veröffentlicht: (2026)

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

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

ETH-Tight Complexity of Optimal Morse Matching on Bounded-Treewidth Complexes
von: Philip, Geevarghese, et al.
Veröffentlicht: (2026)

Nearly Tight Lower Bounds for Relaxed Locally Decodable Codes via Robust Daisies
von: Goldberg, Guy, et al.
Veröffentlicht: (2025)

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

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

#P is Sandwiched by One and Two #2DNF Calls: Is Subtraction Stronger Than We Thought?
von: Bannach, Max, et al.
Veröffentlicht: (2025)

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

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

Approximate Distributed Coded Computing: Polynomial Codes and Randomized Sketching
von: Charalambides, Neophytos, et al.
Veröffentlicht: (2026)

Graph polynomials: some questions on the edge
von: Farr, Graham, et al.
Veröffentlicht: (2024)

On the Complexity of Minimum Riesz s-Energy Subset Selection in Euclidean and Ultrametric Spaces
von: Emmerich, Michael T. M., et al.
Veröffentlicht: (2026)

Computing shortest closed curves on non-orientable surfaces
von: Bulavka, Denys, et al.
Veröffentlicht: (2024)

Human Supervision as an Information Bottleneck: A Unified Theory of Error Floors in Human-Guided Learning
von: Dominguez, Alejandro Rodriguez
Veröffentlicht: (2026)

On (In)approximability of MaxMin Independent Set Reconfiguration
von: Hoang, Hung P., et al.
Veröffentlicht: (2026)

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)

Greedy Poisson Rejection Sampling
von: Flamich, Gergely
Veröffentlicht: (2023)

On the width of complicated JSJ decompositions
von: Huszár, Kristóf, et al.
Veröffentlicht: (2023)

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

Minor Embedding in Broken Chimera and Pegasus Graphs is NP-complete
von: Lobe, Elisabeth, et al.
Veröffentlicht: (2021)

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

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

The Gallai Vertex Problem is $Θ_2^p$-Complete
von: Nikabadi, Amir, et al.
Veröffentlicht: (2026)

On the twin-width of smooth manifolds
von: Bonnet, Édouard, et al.
Veröffentlicht: (2024)

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)

ARRIVAL: Recursive Framework & $\ell_1$-Contraction
von: Haslebacher, Sebastian
Veröffentlicht: (2025)

Drift and selection in LLM text ecosystems
von: Riis, Søren
Veröffentlicht: (2026)

Generalisations of Matrix Partitions : Complexity and Obstructions
von: Barsukov, Alexey, et al.
Veröffentlicht: (2021)

The Quasi-probability Method and Applications for Trace Reconstruction
von: Rubinstein, Ittai
Veröffentlicht: (2024)

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

Shifted Partial Derivative Polynomial Rank and Codimension
von: Edwards, Darren J.
Veröffentlicht: (2025)

Recognizing Penny and Marble Graphs is Hard for Existential Theory of the Reals
von: Lubiw, Anna, et al.
Veröffentlicht: (2025)

Functional Lower Bounds in Algebraic Proofs: Symmetry, Lifting, and Barriers
von: Hakoniemi, Tuomas, et al.
Veröffentlicht: (2024)

Folding One Polyhedral Metric Graph into Another
von: Chung, Lily, et al.
Veröffentlicht: (2024)

Complexities of Well-Quasi-Ordered Substructural Logics
von: Galatos, Nikolaos, et al.
Veröffentlicht: (2025)

PoSME: Proof of Sequential Memory Execution via Latency-Bound Pointer Chasing with Causal Hash Binding
von: Condrey, David L.
Veröffentlicht: (2026)

Mastering NIM and Impartial Games with Weak Neural Networks: An AlphaZero-inspired Multi-Frame Approach
von: Riis, Søren
Veröffentlicht: (2024)

XiSort: Deterministic Sorting via IEEE-754 Total Ordering and Entropy Minimization
von: Alpay, Faruk
Veröffentlicht: (2025)