Cover Image

Simulating Time With Square-Root Space

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Williams, R. Ryan
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Isomorphism Testing of Rooted Trees in Linear Time
by: Lindeberg, Anna
Published: (2024)

On the Bit Size of Sum-of-Squares Proofs for Symmetric Formulations
by: Bortolotti, Alex, et al.
Published: (2025)

Constructive Separations and Their Consequences
by: Chen, Lijie, et al.
Published: (2022)

Spectral Certificates and Sum-of-Squares Lower Bounds for Semirandom Hamiltonians
by: Kocurek, Nicholas
Published: (2025)

Multiquadratic Sum-of-Squares Lower Bounds Imply VNC$^1$ $\neq$ VNP
by: Rossman, Benjamin, et al.
Published: (2025)

On the Degree Automatability of Sum-of-Squares Proofs
by: Bortolotti, Alex, et al.
Published: (2025)

The Space-Time Cost of Purifying Quantum Computations
by: Zhandry, Mark
Published: (2024)

Polynomial-Time Almost Log-Space Tree Evaluation by Catalytic Pebbling
by: Asadi, Vahid R., et al.
Published: (2026)

Tight Quantum Time-Space Tradeoffs for Permutation Inversion
by: Akshima, et al.
Published: (2025)

Polynomial-Time Classical Simulation of Noisy IQP Circuits with Constant Depth
by: Rajakumar, Joel, et al.
Published: (2024)

Improved Bounds on the Space Complexity of Circuit Evaluation
by: Shalunov, Yakov
Published: (2025)

The Complexity of Logarithmic Space Bounded Counting Classes
by: Vijayaraghavan, T. C.
Published: (2025)

Low-soundness direct-product testers and PCPs from Kaufman--Oppenheim complexes
by: O'Donnell, Ryan, et al.
Published: (2025)

How Pinball Wizards Simulate a Turing Machine
by: Adejoh, Rosemary, et al.
Published: (2025)

Polynomial-Time Classical Simulation of Noisy Quantum Circuits with Naturally Fault-Tolerant Gates
by: Nelson, Jon, et al.
Published: (2024)

Subset Sum in Near-Linear Pseudopolynomial Time and Polynomial Space
by: Sajith, Thejas Radhika
Published: (2025)

Frontier Space-Time Algorithms Using Only Full Memory
by: Chmel, Petr, et al.
Published: (2026)

Parallel Play Saves Quantifiers
by: Carmosino, Marco, et al.
Published: (2024)

A Smoothed Analysis of the Space Complexity of Computing a Chaotic Sequence
by: Okada, Naoaki, et al.
Published: (2024)

The 2CNF Boolean Formula Satisfiability Problem and the Linear Space Hypothesis
by: Yamakami, Tomoyuki
Published: (2017)

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

The Root Theorem of Context Engineering
by: Schick, Borja Odriozola
Published: (2026)

Sum of Squares Circuits
by: Loconte, Lorenzo, et al.
Published: (2024)

Resolution Over Linear Equations: Combinatorial Games for Tree-like Size and Space
by: Gryaznov, Svyatoslav, et al.
Published: (2024)

The Probability Spaces of QuickSort
by: Nadareishvili, George, et al.
Published: (2025)

Topological Collapse: P = NP Implies #P = FP via Solution-Space Homology
by: Alasli, M.
Published: (2026)

Realizing Metric Spaces with Convex Obstacles
by: Kisfaludi-Bak, Sándor, et al.
Published: (2025)

BigO(Bench) -- Can LLMs Generate Code with Controlled Time and Space Complexity?
by: Chambon, Pierre, et al.
Published: (2025)

Time hierarchies for sublogarithmic-space quantum computation
by: Say, A. C. Cem
Published: (2025)

Trading Determinism for Time: The k-Reach Problem
by: Bhadra, Ronak, et al.
Published: (2024)

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

Polynomial-Time PIT from (Almost) Necessary Assumptions
by: Andrews, Robert, et al.
Published: (2025)

The PCP-like Theorem for Sub-linear Time Inapproximability
by: Ma, Hengzhao, et al.
Published: (2021)

Sublinear Time Algorithms for Abelian Group Isomorphism and Basis Construction
by: Bshouty, Nader H.
Published: (2025)

Exponential-Size Circuit Complexity is Comeager in Symmetric Exponential Time
by: Hitchcock, John M.
Published: (2026)

A Proposed Characterization of p-Simulation Between Theories
by: Monroe, Hunter
Published: (2025)

Toward a Characterization of Simulation Between Arithmetic Theories
by: Monroe, Hunter
Published: (2026)

Man, these New York Times games are hard! A computational perspective
by: Alberti, Alessandro Giovanni, et al.
Published: (2025)

A Critique of Quigley's "A Polynomial Time Algorithm for 3SAT"
by: DeJesse, Nicholas, et al.
Published: (2025)

Maximizing Phylogenetic Diversity under Time Pressure: Planning with Extinctions Ahead
by: Jones, Mark, et al.
Published: (2024)