Tata Institute of Fundamental Research
Algebraic Natural Proofs: the plot thickens
STCS Student Seminar
Speaker:
Anamay Tengse
Organiser:
Eeshan Modak
Date:
Friday, 1 Jan 2021, 17:15 to 18:15
Venue:
(Scan to add to calendar)
Abstract:
In the late 1990s, a paper by Razborov and Rudich pointed out a barrier towards proving boolean circuit lower bounds. They observed that almost all of the then known lower bounds could be proved using a specific template: the 'natural proofs framework'. They further showed that any 'natural proof' for P/poly (poly-sized boolean circuits) would contradict the existence of One-Way-Functions: a crucial primitive in modern day cryptography. Thus, their paper essentially ruled out "natural" techniques for proving strong boolean circuit lower bounds.
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
| Speaker: | Anamay Tengse |
| Organiser: | Eeshan Modak |
| Date: | Friday, 1 Jan 2021, 17:15 to 18:15 |
| Venue: |
(Scan to add to calendar)
Abstract:
In the late 1990s, a paper by Razborov and Rudich pointed out a barrier towards proving boolean circuit lower bounds. They observed that almost all of the then known lower bounds could be proved using a specific template: the 'natural proofs framework'. They further showed that any 'natural proof' for P/poly (poly-sized boolean circuits) would contradict the existence of One-Way-Functions: a crucial primitive in modern day cryptography. Thus, their paper essentially ruled out "natural" techniques for proving strong boolean circuit lower bounds.
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
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