| Title | : | Power of Programs over Monoids : Towards the PLP Conjecture |
| Speaker | : | Janani Sundaresan (Rutgers University) |
| Details | : | Tue, Mar 2, 2021 4:00 PM, @ https://meet.google.com/moh-pbtq-wyg |
| Abstract | : | Programs over monoids can be viewed as a series of if-else statements or instructions which query the input indices and output an element over a monoid. Programs either accept or reject based on the final output. Monoids have been an effective tool in characterizing computational resources. For example, a language (equivalently every family of Boolean functions) can be computed by constant depth polynomial-size circuits if and only if it can be computed by a polynomial length program over an aperiodic monoid. In a more general setting, how does the algebraic structure of the monoid affect the computational power of programs over it? A monoid is called universal if for every language, there exists a program computing it over the monoid. A monoid is said to have the polynomial length property if any program over it can be reduced to polynomial length without changing the language accepted. The PLP conjecture is the following powerful dichotomy - any monoid is universal if and only if it does not have the polynomial length property. The conjecture has been confirmed for the case when the monoids are groups. It is still open for other kinds of monoids. A particularly appealing structure is that of aperiodic monoids. An important aperiodic monoid that captures the difficulty of the problem is a monoid called the BA2. We show the conjecture for the case of BA2 when the program has a polynomial sized witness for the zero set. This talk will present the development of a graph-theoretic representation that not only settles the above case but also can be a potential tool for the general form of the conjecture as well. We also extend known results about the computational power of the BA2 monoid while computing PARITY. This is joint work with Manasi Kulkarni and Jayalal Sarma. The work has been accepted for presentation at LATA 2021. |