Copertina

Polynomial-Time Almost Log-Space Tree Evaluation by Catalytic Pebbling

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Asadi, Vahid R., Cleve, Richard
Natura:	Preprint
Pubblicazione:	2026
Soggetti:	Computational Complexity Data Structures and Algorithms
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

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

Optimal Trickle-Down Theorems for Path Complexes via C-Lorentzian Polynomials with Applications to Sampling and Log-Concave Sequences
di: Leake, Jonathan, et al.
Pubblicazione: (2025)

Efficient Catalytic Graph Algorithms
di: Cook, James, et al.
Pubblicazione: (2025)

Bipartite Matching is in Catalytic Logspace
di: Agarwala, Aryan, et al.
Pubblicazione: (2025)

Almost-Optimal Upper and Lower Bounds for Clustering in Low Dimensional Euclidean Spaces
di: Cohen-Addad, Vincent, et al.
Pubblicazione: (2026)

Self-referential instances of the dominating set problem are irreducible
di: Zhou, Guangyan
Pubblicazione: (2026)

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

Solving Polynomial Equations Over Finite Fields
di: Dell, Holger, et al.
Pubblicazione: (2024)

The Quasi-Polynomial Low-Degree Conjecture is False
di: Buhai, Rares-Darius, et al.
Pubblicazione: (2025)

A Polynomial Space Lower Bound for Diameter Estimation in Dynamic Streams
di: Khanna, Sanjeev, et al.
Pubblicazione: (2025)

Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy
di: Assadi, Sepehr, et al.
Pubblicazione: (2024)

Polynomial-Time Pseudodeterministic Construction of Primes
di: Chen, Lijie, et al.
Pubblicazione: (2023)

Polynomial kernels for edge modification problems towards block and strictly chordal graphs
di: Dumas, Maël, et al.
Pubblicazione: (2022)

Turnstile Streaming Algorithms Might (Still) as Well Be Linear Sketches, for Polynomial-Length Streams
di: Jiang, Cheng, et al.
Pubblicazione: (2026)

On the Space Complexity of Online Convolution
di: Andersson, Joel Daniel, et al.
Pubblicazione: (2025)

The Structure of In-Place Space-Bounded Computation
di: Cook, James, et al.
Pubblicazione: (2025)

Improved Space Bounds for Subset Sum
di: Belova, Tatiana, et al.
Pubblicazione: (2024)

The Computational Complexity of Almost Stable Clustering with Penalties
di: Khodamoradi, Kamyar, et al.
Pubblicazione: (2025)

Gray Codes With Constant Delay and Constant Auxiliary Space
di: Amarilli, Antoine, et al.
Pubblicazione: (2026)

Near-Optimal Space Lower Bounds for Streaming CSPs
di: Fei, Yumou, et al.
Pubblicazione: (2026)

Linear Space Streaming Lower Bounds for Approximating CSPs
di: Chou, Chi-Ning, et al.
Pubblicazione: (2021)

A Space-space Trade-off for Directed st-Connectivity
di: Edenhofer, Roman
Pubblicazione: (2026)

Space Complexity Dichotomies for Subgraph Finding Problems in the Streaming Model
di: Shih, Yu-Sheng, et al.
Pubblicazione: (2026)

Tight Space Lower Bound for Pseudo-Deterministic Approximate Counting
di: Grossman, Ofer, et al.
Pubblicazione: (2023)

Encoding Co-Lex Orders of Finite-State Automata in Linear Space
di: Becker, Ruben, et al.
Pubblicazione: (2025)

A Strongly Polynomial-Time Algorithm for Weighted General Factors with Three Feasible Degrees
di: Shao, Shuai, et al.
Pubblicazione: (2023)

Sublinear-Time Approximation for Graph Frequency Vectors in Hyperfinite Graphs
di: Moroie, Gregory
Pubblicazione: (2025)

A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT
di: Buhrman, Harry, et al.
Pubblicazione: (2025)

Constant Time with Minimal Preprocessing, a Robust and Extensive Complexity Class
di: Grandjean, Étienne, et al.
Pubblicazione: (2025)

The Art of Staying Ahead of Deadlines: Improved Algorithms for the Minimum Tardy Processing Time
di: Stoian, Mihail
Pubblicazione: (2024)

Black-Box Identity Testing of Noncommutative Rational Formulas in Deterministic Quasipolynomial Time
di: Arvind, V., et al.
Pubblicazione: (2023)

Faster Exponential-Time Approximation Algorithms Using Approximate Monotone Local Search
di: Esmer, Barış Can, et al.
Pubblicazione: (2022)

Scalable Neighborhood Local Search for Single-Machine Scheduling with Family Setup Times
di: Balzereit, Kaja, et al.
Pubblicazione: (2024)

Trickle-down Theorems via C-Lorentzian Polynomials II: Pairwise Spectral Influence and Improved Dobrushin's Condition
di: Leake, Jonathan, et al.
Pubblicazione: (2025)

Revisiting Tree Canonization using polynomials
di: Arvind, V., et al.
Pubblicazione: (2024)

Polynomial-time sampling despite disorder chaos
di: Ma, Eric, et al.
Pubblicazione: (2025)

Polynomial-time tolerant testing stabilizer states
di: Arunachalam, Srinivasan, et al.
Pubblicazione: (2024)

Emit As You Go: Enumerating Edges of a Spanning Tree
di: Casel, Katrin, et al.
Pubblicazione: (2025)

Pseudo-Deterministic Construction of Irreducible Polynomials over Finite Fields
di: Rai, Shanthanu S
Pubblicazione: (2024)

Hardness and Tractability of T_{h+1}-Free Edge Deletion
di: Gaikwad, Ajinkya, et al.
Pubblicazione: (2026)