Cover Image

The Randomness Deficiency Function and the Shift Operator

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Epstein, Samuel
Format:	Preprint
Published:	2023
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

On Kolmogorov Structure Functions
by: Epstein, Samuel
Published: (2024)

On the Existence of Anomalies, The Reals Case
by: Epstein, Samuel
Published: (2023)

Game Derandomization
by: Epstein, Samuel
Published: (2024)

Some Implications of the Independence Postulate for Physics
by: Epstein, Samuel
Published: (2023)

On the Algorithmic Information Between Probabilities
by: Epstein, Samuel
Published: (2023)

Semi-Classical Subspaces, The No Synchronization Law, and More
by: Epstein, Samuel
Published: (2024)

Two Simple Proofs of Müller's Theorem
by: Epstein, Samuel
Published: (2024)

Two Quantum Paradigms, but Still No Signal
by: Epstein, Samuel
Published: (2024)

Hilbert Functions and Low-Degree Randomness Extractors
by: Golovnev, Alexander, et al.
Published: (2024)

Toward Better Depth Lower Bounds: Strong Composition of XOR and a Random Function
by: Chukhin, Nikolai, et al.
Published: (2024)

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

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

Recursive Jump Operators and Optimal Proof Systems
by: Egidy, Fabian
Published: (2026)

Aaronson-Ambainis Conjecture Is True For Random Restrictions
by: Bhattacharya, Sreejata Kishor
Published: (2024)

No Complete Problem for Constant-Cost Randomized Communication
by: Fang, Yuting, et al.
Published: (2024)

Strongly Refuting Random CSP without Literals
by: Chan, Siu On, et al.
Published: (2026)

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

Optimal Coding for Randomized Kolmogorov Complexity and Its Applications
by: Hirahara, Shuichi, et al.
Published: (2024)

Hardness of Random Reordered Encodings of Parity for Resolution and CDCL
by: Chew, Leroy, et al.
Published: (2024)

Limits of Sequential Local Algorithms on the Random $k$-XORSAT Problem
by: Yung, Kingsley
Published: (2024)

A Pseudorandom Generator for Functions of Low-Degree Polynomial Threshold Functions
by: Yao, Penghui, et al.
Published: (2025)

An approximation notion between P and FPTAS
by: Bismuth, Samuel, et al.
Published: (2026)

Random tensor isomorphism under orthogonal and unitary actions
by: Chizewer, Jeremy, et al.
Published: (2026)

Randomized Black-Box PIT for Small Depth +-Regular Non-commutative Circuits
by: Bharadwaj, G V Sumukha, et al.
Published: (2024)

Bounded-Depth Frege Lower Bounds for Random 3-CNFs via Deterministic Restrictions
by: Gryaznov, Svyatoslav, et al.
Published: (2024)

Lifting with Inner Functions of Polynomial Discrepancy
by: Manor, Yahel, et al.
Published: (2024)

Approximate Degree Composition for Recursive Functions
by: Chakraborty, Sourav, et al.
Published: (2024)

Boolean Functions with Minimal Spectral Sensitivity
by: Prūsis, Krišjānis, et al.
Published: (2024)

Special Coverings of Sets and Boolean Functions
by: Margaryan, Stepan
Published: (2024)

Periodicity of Transcendental Entire Functions Sharing Set with their Shifts
by: Roy, Soumon, et al.
Published: (2025)

Switching Graph Matrix Norm Bounds: from i.i.d. to Random Regular Graphs
by: Xu, Jeff
Published: (2024)

Lines in Every Direction with No ee-Random Points
by: Lutz, Neil, et al.
Published: (2025)

Separations between Combinatorial Measures for Transitive Functions
by: Chakraborty, Sourav, et al.
Published: (2021)

One-Way Functions and Polynomial Time Dimension
by: Nandakumar, Satyadev, et al.
Published: (2024)

One-Way Communication Complexity of Partial XOR Functions
by: Podolskii, Vladimir V., et al.
Published: (2023)

Low Sets and Closure Properties of Counting Function Classes
by: Ivanashev, Yaroslav
Published: (2025)

New Techniques for Constructing Rare-Case Hard Functions
by: Nareddy, Tejas, et al.
Published: (2024)

Second-Order Parameterizations for the Complexity Theory of Integrable Functions
by: Bacho, Aras, et al.
Published: (2025)

On Extremal Properties of k-CNF: Capturing Threshold Functions
by: Gurumukhani, Mohit, et al.
Published: (2024)

Local Correction of Linear Functions over the Boolean Cube
by: Amireddy, Prashanth, et al.
Published: (2024)