I/O complexity and pebble games with partial computations

DOI10.1016/J.IPL.2026.106637MaRDI QIDQ7296158zbMATH OpenFDO

Authors Aleksandros Sobczyk

Publication date 14 July 2026

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.IPL.2026.106637

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• 8/7-approximation algorithm for (1,2)-TSP
• Code Generation for a One-Register Machine
• Complete Register Allocation Problems
• Extending the Hong-Kung model to memory hierarchies
• Fine-grained I/O complexity via reductions: new lower bounds, faster algorithms, and a time hierarchy
• scientific article; zbMATH DE number 1953444 (Why is no real title available?)
• scientific article; zbMATH DE number 2107836 (Why is no real title available?)
• scientific article; zbMATH DE number 5937963 (Why is no real title available?)
• Inapproximability of the standard pebble game and hard to pebble graphs
• New approximation algorithms for \((1,2)\)-TSP
• Numerical linear algebra and optimization
• Numerical methods for large eigenvalue problems
• Optimal Code Generation for Expression Trees
• Optimal sparse matrix dense vector multiplication in the I/O-model
• Optimization of Straight Line Programs
• Randomized Algorithms for Matrices and Data
• The I/O Complexity of Sparse Matrix Dense Matrix Multiplication
• The input/output complexity of sparse matrix multiplication
• The Pebbling Problem is Complete in Polynomial Space
• The Traveling Salesman Problem with Distances One and Two
• Time-space trade-offs in a pebble game

This page was built for publication: I/O complexity and pebble games with partial computations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7296158)