"Real Computation and Complexity Theory"
Date23rd Mar 2021
Time11:00 AM
Venue meet.google.com/nak-dtbd-nic
PAST EVENT
Details
Defining a notion of space in the real/complex model of computation introduced by Blum, Shub and Smale (BSS) is a challenging task. Though there were some attempts at defining a feasible notion of space over real/complex numbers, none of the measures seem to capture the notion of space in a satisfactory manner. De Naurois [CiE, 2006] introduced the notion of weak space as a possible measure of space for capturing small space computations. Joglekar et. al. [FCT, 2017] exhibited limitations of the model over complex numbers. It is important to explore various possibilities of defining space for computations over real/complex numbers to understand the difficulty of the problem. We study the feasibility of defining notions of space based on: 1) The unit cost model with a simultaneous time bound; 2) Size of an arithmetic circuit as a measure of space. We compare the space bounded complexity classes that can be defined based on these measures with the existing complexity classes. Finally, we introduce the computational model of algebraic branching programs with select nodes and explore the relationship of the model with space bounded complexity classes based on circuit parameters.
Speakers
Mr. Om Prakash, (CS16D017)
कंप्यूटर विज्ञान और इंजीनियरिंगComputer Science & Engg.