Cover Image

The Impact of Partial Computations on the Red-Blue Pebble Game

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Papp, Pál András, Sobczyk, Aleksandros, Yzelman, A. N.
Format:	Preprint
Published:	2025
Subjects:	Distributed, Parallel, and Cluster Computing 68Q10, 68Q17 F.2.2; F.1.1
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Red-Blue Pebbling with Multiple Processors: Time, Communication and Memory Trade-offs
by: Böhnlein, Toni, et al.
Published: (2024)

Approaching I/O-optimality for Approximate Attention
by: Papp, Pál András, et al.
Published: (2026)

Gathering Semi-Synchronously Scheduled Two-State Robots
by: Otaka, Kohei, et al.
Published: (2024)

Replication in Graph Partitioning and Scheduling Problems
by: Papp, Pál András, et al.
Published: (2026)

DAG Scheduling in the BSP Model
by: Papp, Pál András, et al.
Published: (2023)

Explicit separations between randomized and deterministic Number-on-Forehead communication
by: Kelley, Zander, et al.
Published: (2023)

Multiprocessor Scheduling with Memory Constraints: Fundamental Properties and Finding Optimal Solutions
by: Papp, Pál András, et al.
Published: (2025)

I/O complexity and pebble games with partial computations
by: Sobczyk, Aleksandros
Published: (2024)

Stochastic well-structured transition systems
by: Aspnes, James
Published: (2025)

Smaller Depth-2 Linear Circuits for Disjointness Matrices
by: Ye, Lixi
Published: (2026)

Two-Robot Computational Landscape: A Complete Characterization of Model Power in Minimal Mobile Robot Systems
by: Kitamura, Naoki, et al.
Published: (2025)

Computing Inductive Invariants of Regular Abstraction Frameworks
by: Czerner, Philipp, et al.
Published: (2024)

$Δ$-Nets: Interaction-Based System for Optimal Parallel $λ$-Reduction
by: Salvadori, Daniel Augusto Rizzi
Published: (2025)

On Graph Grammars and Games
by: Vijayakumar, Jayakrishna, et al.
Published: (2024)

Safe Low Bandwidth SPV: A Formal Treatment of Simplified Payment Verification Protocols and Security Bounds
by: Wright, Craig S
Published: (2025)

Greedy Poisson Rejection Sampling
by: Flamich, Gergely
Published: (2023)

Constraint Satisfaction Problems over Finitely Bounded Homogeneous Structures: a Dichotomy between FO and L-hard
by: Dorochko, Leonid, et al.
Published: (2026)

Curved Boolean Logic: A Contextual Generalization of Propositional Logic with Algorithmic Consequences
by: von Liechtenstein, Maximilian R. P.
Published: (2025)

IECZ-III: Hardcore Condensation Lift with Size-Aware Invariants
by: Lela, Marko
Published: (2025)

Efficient Parallel Scheduling for Sparse Triangular Solvers
by: Böhnlein, Toni, et al.
Published: (2025)

Shifted Partial Derivative Polynomial Rank and Codimension
by: Edwards, Darren J.
Published: (2025)

Completeness classes in algebraic complexity theory
by: Bürgisser, Peter
Published: (2024)

Quantum Advantage in Computational Chemistry?
by: Gundlach, Hans, et al.
Published: (2025)

An MDL-Style Cost Functional KC, Distribution-Preserving Reductions ($A2^d$), and an $AC^0$+log Lower Bound for 3SAT via Balanced 3XOR
by: Lela, Marko
Published: (2025)

Polynomial Prenexing of QBFs with Non-Monotone Boolean Operators
by: Saffidine, Abdallah, et al.
Published: (2025)

Improved Bounds for Coin Flipping, Leader Election, and Random Selection
by: Chattopadhyay, Eshan, et al.
Published: (2025)

The Serial Scaling Hypothesis
by: Liu, Yuxi, et al.
Published: (2025)

Functional Lower Bounds in Algebraic Proofs: Symmetry, Lifting, and Barriers
by: Hakoniemi, Tuomas, et al.
Published: (2024)

NP-hardness of p-adic linear regression
by: Baker, Gregory D.
Published: (2026)

Mathematical Foundations for Peer-to-Peer Lattice Computation
by: Gorinevski, Danil
Published: (2026)

Data Scheduling Algorithm for Scalable and Efficient IoT Sensing in Cloud Computing
by: Mohammad, Noor Islam S.
Published: (2025)

Light Cone Consistency: Toward a Unified Theory of Consistency in Message-Passing Systems
by: Landers, Rob, et al.
Published: (2026)

Pure Data Spaces
by: Youssef, Saul
Published: (2025)

The Word Problem for Finitary Automaton Groups
by: Kotowsky, Maximilian, et al.
Published: (2023)

On Small-depth Frege Proofs for PHP
by: Håstad, Johan
Published: (2024)

How do humans succeed in tasks like proving Fermat's Theorem or predicting the Higgs boson?
by: Levin, Leonid A.
Published: (2022)

NP-Completeness Proofs of All or Nothing, Water Walk, and Remembered Length Using the T-Metacell Framework
by: Eua-anant, Pakapim, et al.
Published: (2025)

Ethic Duality: A Homological Framework for Primal-Dual Problems
by: Pasechnyuk-Vilensky, Dmitry, et al.
Published: (2025)

A Theory for Coloring Walks in a Digraph
by: Chaiken, Seth
Published: (2024)

The Complexity of Iterated Reversible Computation
by: Eppstein, David
Published: (2021)