Date: December 1, 2025
Time: 3:45-5 p.m.
Location: Computing and Information Science Building, Room 450 or via Zoom
Speaker: Surendra Ghentiyala, Cornell University
Title: The structure of in-place space-bounded computation
Abstract: Reusing space is an idea which has proven incredibly fruitful in the study of space-bounded computation. We introduce and investigate a model of computation which captures a new notion of reusing space: in-place computation, which formalizes the idea of reusing the space typically reserved for the input to a computation. More formally, a function f is computable in-place if there exists a program which, given that the input tape initially reads x, always transforms the input tape so that upon termination it contains f(x). We define new complexity classes corresponding to in-place computation and relate them to more standard notions of reusing space, such as catalytic space.
With these definitions in place, we prove results highlighting both the power and limitations of in-place computation.
1. We show that in-place computation is likely incomparable with standard space-bounded complexity classes.
2. We show algorithms which perform many classic linear algebra operations in-place (e.g. matrix multiplication, matrix inversion, etc.)
Based on joint work with James Cook, Ian Mertz, Edward Pyne, and Nathan S. Sheffield.
Bio: Surendra Ghentiyala is a Ph.D. student in computer science at Cornell University advised by Noah Stephens-Davidowitz. His research interests are complexity theory and cryptography. Most recently, his research has focused on TFNP, a class of problems which are not believed to be NP-hard but are also unlikely to admit polynomial time algorithms.