Cover Image

On the Existence of Anomalies, The Reals Case

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

The Randomness Deficiency Function and the Shift Operator
by: Epstein, Samuel
Published: (2023)

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

On Kolmogorov Structure Functions
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)

On the Existence of Algebraic Natural Proofs
by: Chatterjee, Prerona, et al.
Published: (2020)

On the Existence of Seedless Condensers: Exploring the Terrain
by: Chattopadhyay, Eshan, et al.
Published: (2023)

Worst-Case and Average-Case Hardness of Hypercycle and Database Problems
by: Fu, Cheng-Hao, et al.
Published: (2025)

Experiments, Computability, and the Existence of Physical Functions
by: Castillo, Isaac Pérez
Published: (2026)

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

Existence and nonexistence of commutativity gadgets for entangled CSPs
by: Culf, Eric, et al.
Published: (2025)

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

Dual-Tape Perspective and Generator Independence: The Algebraic Foundation of Real Boolean Turing Machines
by: Zheng, Jingwen, et al.
Published: (2026)

Average-Case Hardness of Binary-Encoded Clique in Proof and Communication Complexity
by: de Rezende, Susanna F., et al.
Published: (2026)

Efficient approximation schemes for scheduling on a stochastic number of machines
by: Epstein, Leah, et al.
Published: (2024)

Average-Case Hardness of Parity Problems: Orthogonal Vectors, k-SUM and More
by: Dalirrooyfard, Mina, et al.
Published: (2025)

Optimizing for aggressive-style strategies in Flesh and Blood is NP-hard
by: Romão, Leonardo Gasparini, et al.
Published: (2025)

Representing Matroids over the Reals is $\exists \mathbb R$-complete
by: Kim, Eun Jung, et al.
Published: (2023)

Termination of Real Linear Loops
by: Neumann, Eike, et al.
Published: (2026)

How Real is Incomputability in Physics?
by: Trejo, José Manuel Agüero, et al.
Published: (2023)

The Existential Theory of the Reals with Summation Operators
by: Bläser, Markus, et al.
Published: (2024)

Realizing Graphs with Cut Constraints
by: Silva, Lucas de Oliveira, et al.
Published: (2025)

How Hard Is Continuous Clustering? Lower Bounds from the Existential Theory of the Reals
by: Majumdar, Angshul
Published: (2026)

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

Geometric and computational hardness of bilevel programming
by: Bolte, Jérôme, et al.
Published: (2024)

Real Stability and Log Concavity are coNP-Hard
by: Chin, Tracy
Published: (2024)

Physically-Motivated Guiding States for Local Hamiltonians
by: Waite, Gabriel, et al.
Published: (2025)

Local Enumeration: The Not-All-Equal Case
by: Gurumukhani, Mohit, et al.
Published: (2025)

Fundamental Problems on Bounded-Treewidth Graphs: The Real Source of Hardness
by: Esmer, Barış Can, et al.
Published: (2024)

Beyond Bits: An Introduction to Computation over the Reals
by: Miltzow, Tillmann
Published: (2026)

Asymmetric Number Partitioning with Splitting and Interval Targets
by: Bismuth, Samuel, et al.
Published: (2022)

From Amortized to Worst Case Delay in Enumeration Algorithms
by: Capelli, Florent, et al.
Published: (2021)

Online Orthogonal Vectors Revisited
by: Gajulapalli, Karthik, et al.
Published: (2026)

Correspondences in computational and dynamical complexity II: forcing complex reductions
by: Everett, Samuel
Published: (2026)

Devil's Games and $\text{Q}\mathbb{R}$: Continuous Games complete for the First-Order Theory of the Reals
by: Meijer, Lucas, et al.
Published: (2025)

Tensor Ranks and the Fine-Grained Complexity of Dynamic Programming
by: Alman, Josh, et al.
Published: (2023)

Baby PIH: Parameterized Inapproximability of Min CSP
by: Guruswami, Venkatesan, et al.
Published: (2023)