| Title | : | New Measures of Space over Real and Complex Numbers, Parameterised Counting in Log-Space and Roots of Independence Polynomial |
| Speaker | : | Om Prakash (IITM) |
| Details | : | Wed, 31 May, 2023 10:00 AM @ Google Meet |
| Abstract: | : | In 1989, Blum, Shub, and Smale introduced a real analogue of the Turing Machine, also called the Blum-Shub-Smale (BSS) model, as a formal model for the study of numerical computations. n this work, we look at various possibilities for notions of space for the BSS model of real computation. We focus on the succinctness of representations of rational func- tions /polynomials based on arithmetic circuits. We establish limitations of using various notions such as circuit size and unit-space along with a simultaneous time bound as notions os space in the BSS model. In the second part of the thesis, we develop the notions for parameterized counting complexity in the log-space bounded setting. We introduce a new framework for parameterised counting in logspace, inspired by the parameterised space bounded models developed by Elberfeld, Stockhusen, and Tantau (IPEC 2013, Algo- rithmica 2015). In the spirit of the operators paraW and paraβ by Stockhusen and Tantau, we introduce variants based on tail-nondeterminism, paraW[1], and paraβ-tail. Then, we consider counting versions of all four operators applied to logspace and obtain several natural complete problems for the resulting classes: counting paths in digraphs, counting first-order models for formulas, and counting graph homomorphisms. FInally, we study the inependence polynomial of a graph(i.e a polynomial in which coefficient of x^i represents the number of independent sets of size i in G). Roots of the independence polynomial has received wide attention in the literature. We focus on the gap between the second smallest root and the smallest root of the independence polynomial. We prove that the coefficients of the inverse power series of the independence poly- nomial form a strictly monotone sequence, and using this result, we prove that when ordered with respect to modulus, there is a gap in between the roots of the indepen- dence polynomial. Further, we study the relationship between combinatorial parame- ters of graph conductance, density, and the gap between the second smallest root and the smallest root of the independence polynomial of various graph classes: Path, Cycle, and Complete Bipartite Graph. Web Conference Link :https://meet.google.com/rrh-fjjc-vxq |
