AG 1, AG 2, AG 3, INET, AG 4, AG 5, D6, SWS, RG1, MMCI   Info

AG Audience

English

30 Minutes

The main goal of algebraic complexity theory is to show explicit polynomials whose computation requires algebraic circuits of superpolynomial size. It was a longstanding open problem to prove superpolynomial lower bounds against algebraic circuits of even depth 3, whereas constant-depth boolean circuit lower bounds were long known. In a recent breakthrough result of Limaye, Srinivasan, Tavenas, the first-ever superpolynomial lower bounds were shown against constant-depth algebraic circuits. We improve this lower bound by using a refinement of their techniques. We also show that our lower bound cannot be improved significantly using these same techniques.

This is joint work with C.S. Bhargav and Nitin Saxena.

Jennifer Gerling

+49 681 9325 1801

--email hidden

Zoom

passcode not visible

logged in users only