| Title | : | Lower Bounds for some Algebraic Models of Computation |
| Speaker | : | Prerona Chatterjee (NISER Bhubaneswar) |
| Details | : | Tue, 27 Aug, 2024 3:00 PM @ Online |
| Abstract: | : | Algebraic circuits and formulas are two of the most natural models for computing polynomials, and proving superpolynomial lower bounds against these models are central questions in the field of complexity theory. A long line of works culminating in the recent breakthrough work of Limaye, Srinivasan and Tavenas proved the first super-polynomial lower bound against constant depth algebraic circuits and formulas. However, proving lower bounds in the general case continues to remain widely open. Another important model for computing polynomials is that of algebraic branching programs, whose power lies in between that of circuits and formulas. In this talk we will discuss the current state-of-the art for lower bounds against these models of computation in the general as well as some structured settings. I will then describe my recent work with Kush, Saraf and Shpilka (CCC 2024), in greater detail; and conclude with some future research directions that I am excited about, and also my teaching interests. About the Speaker: Dr. Prerona Chatterjee is currently a visiting faculty member at NISER Bhubaneswar. Before joining NISER, she did her PhD at TIFR Mumbai, and then spent two years as a postdoctoral researcher, first at the Czech Academy of Sciences and then at the Tel Aviv University, Israel. She works in the area of algebraic complexity theory. Google Meet Link : meet.google.com/hrx-dtmg-weq |
