Image de couverture de livre

On Kolmogorov Structure Functions

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteur principal:	Epstein, Samuel
Format:	Preprint
Publié:	2024
Sujets:	Computational Complexity
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

The Randomness Deficiency Function and the Shift Operator
par: Epstein, Samuel
Publié: (2023)

Game Derandomization
par: Epstein, Samuel
Publié: (2024)

On the Existence of Anomalies, The Reals Case
par: Epstein, Samuel
Publié: (2023)

Semi-Classical Subspaces, The No Synchronization Law, and More
par: Epstein, Samuel
Publié: (2024)

Two Simple Proofs of Müller's Theorem
par: Epstein, Samuel
Publié: (2024)

Two Quantum Paradigms, but Still No Signal
par: Epstein, Samuel
Publié: (2024)

Some Implications of the Independence Postulate for Physics
par: Epstein, Samuel
Publié: (2023)

On the Algorithmic Information Between Probabilities
par: Epstein, Samuel
Publié: (2023)

Optimal Coding for Randomized Kolmogorov Complexity and Its Applications
par: Hirahara, Shuichi, et autres
Publié: (2024)

Space-bounded online Kolmogorov complexity is additive
par: Bauwens, Bruno, et autres
Publié: (2025)

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

Prime Successor Irreducibility: Turing Machine Complexity, Kolmogorov Complexity, and Weakness-Based Formulations
par: Goertzel, Ben, et autres
Publié: (2026)

A Pseudorandom Generator for Functions of Low-Degree Polynomial Threshold Functions
par: Yao, Penghui, et autres
Publié: (2025)

Key-agreement exists if and only if the "interactive vs non interactive Kolmogorov problem" is not in ioBPP: a short proof
par: Bauwens, Bruno, et autres
Publié: (2025)

An approximation notion between P and FPTAS
par: Bismuth, Samuel, et autres
Publié: (2026)

Lifting with Inner Functions of Polynomial Discrepancy
par: Manor, Yahel, et autres
Publié: (2024)

Approximate Degree Composition for Recursive Functions
par: Chakraborty, Sourav, et autres
Publié: (2024)

Boolean Functions with Minimal Spectral Sensitivity
par: Prūsis, Krišjānis, et autres
Publié: (2024)

Special Coverings of Sets and Boolean Functions
par: Margaryan, Stepan
Publié: (2024)

Hilbert Functions and Low-Degree Randomness Extractors
par: Golovnev, Alexander, et autres
Publié: (2024)

One-Way Functions and Polynomial Time Dimension
par: Nandakumar, Satyadev, et autres
Publié: (2024)

Separations between Combinatorial Measures for Transitive Functions
par: Chakraborty, Sourav, et autres
Publié: (2021)

Quantum Kolmogorov complexity and quantum correlations in deterministic-control quantum Turing machines
par: Lemus, Mariano, et autres
Publié: (2023)

New Techniques for Constructing Rare-Case Hard Functions
par: Nareddy, Tejas, et autres
Publié: (2024)

On Extremal Properties of k-CNF: Capturing Threshold Functions
par: Gurumukhani, Mohit, et autres
Publié: (2024)

Local Correction of Linear Functions over the Boolean Cube
par: Amireddy, Prashanth, et autres
Publié: (2024)

Low Sets and Closure Properties of Counting Function Classes
par: Ivanashev, Yaroslav
Publié: (2025)

Second-Order Parameterizations for the Complexity Theory of Integrable Functions
par: Bacho, Aras, et autres
Publié: (2025)

One-Way Communication Complexity of Partial XOR Functions
par: Podolskii, Vladimir V., et autres
Publié: (2023)

On the Complexity of Combinatorial Optimization on Fixed Structures
par: Megiddo, Nimrod
Publié: (2024)

Proof Systems Based on Structured Circuits
par: Micun, Matthäus, et autres
Publié: (2026)

Efficient approximation schemes for scheduling on a stochastic number of machines
par: Epstein, Leah, et autres
Publié: (2024)

Refuting the Direct Sum Conjecture for Total Functions in Deterministic Communication Complexity
par: Mackenzie, Simon, et autres
Publié: (2024)

Exact versus Approximate Representations of Boolean Functions in the De Morgan Basis
par: Chattopadhyay, Arkadev, et autres
Publié: (2025)

Spectral Norm, Economical Sieve, and Linear Invariance Testing of Boolean Functions
par: Datta, Swarnalipa, et autres
Publié: (2023)

Structure in Communication Complexity and Constant-Cost Complexity Classes
par: Hatami, Hamed, et autres
Publié: (2024)

Tight Lower Bounds for Block-Structured Integer Programs
par: Hunkenschröder, Christoph, et autres
Publié: (2024)

A Parameterized Study of Secluded Structures in Directed Graphs
par: Schmidt, Jonas, et autres
Publié: (2025)

Optimizing for aggressive-style strategies in Flesh and Blood is NP-hard
par: Romão, Leonardo Gasparini, et autres
Publié: (2025)

Toward Better Depth Lower Bounds: Strong Composition of XOR and a Random Function
par: Chukhin, Nikolai, et autres
Publié: (2024)