Speaker: |
Anamay Tengse |

Organiser: |
Eeshan Modak |

Date: |
Friday, 1 Jan 2021, 17:15 to 18:15 |

Venue: |

(Scan to add to calendar)

About two decades later, two groups: Grochow, Kumar, Saks and Saraf (2017), and Forbes, Shpilka and Volk (2018), independently proposed the framework of 'algebraically natural proofs' for algebraic circuits. They observed that most of the known lower bounds against algebraic circuit models fit in this framework, and showed that 'algebraically natural proofs' do not exist for VP (poly-sized algebraic circuits), under a (non-standard) derandomisation assumption. Forbes, Shpilka and Volk (2018) also provided some evidence that suggested that the derandomisation assumption might indeed be true.

This year, in joint works with Chatterjee, Kumar, Ramya and Saptharishi, we observed the following seemingly contradictory facts about algebraically natural proofs.

1. Algebraically natural proofs (kind of) *exist* for all "interesting" polynomials in VP and VNP (algebraic P and NP).

2. Algebraically natural proofs *do not exist* for VNP (algebraic NP), if permanent is exponentially hard.

In this talk, we will first understand the algebraically natural proofs framework, and then try to make sense of our recent findings.

Zoom link: https://zoom.us/j/98132227553?pwd=K2cyQllKVjExdUhlRm0vc0ZHcEt0Zz09