Tata Institute of Fundamental Research
Two-and-a-half proofs of "the duality trick"
STCS Student Seminar
Speaker:
Anamay Tengse
Organiser:
Shubhada Agrawal
Date:
Friday, 9 Apr 2021, 17:15 to 18:15
Venue:
(Scan to add to calendar)
Abstract:
The fact that the polynomial (x1+...+xn)^d can be written as a poly(n,d)-sum of products of univariates is a consequence of what is popularly known as 'the duality trick' in the algebraic complexity circles. The actual identity is much more general, and in particular, applies to any linear form raised to an arbitrary power. Saxena (2008) famously used this duality to derive identity testing algorithms for polynomials that are poly(n,d)-sums of powers of linear forms. This model (AKA sum-power-sum) coincides with the well-studied notion of Waring rank in mathematics.
In this talk, we will see two proofs of the duality trick due to Saxena and Shpilka respectively. Both these proofs use fairly elementary ideas about polynomials. We shall then see a different proof of correctness of Saxena's construction that uses mildly non-elementary algebraic geometry.
Zoom link: https://zoom.us/j/98132227553?pwd=K2cyQllKVjExdUhlRm0vc0ZHcEt0Zz09
| Speaker: | Anamay Tengse |
| Organiser: | Shubhada Agrawal |
| Date: | Friday, 9 Apr 2021, 17:15 to 18:15 |
| Venue: |
(Scan to add to calendar)
Abstract:
The fact that the polynomial (x1+...+xn)^d can be written as a poly(n,d)-sum of products of univariates is a consequence of what is popularly known as 'the duality trick' in the algebraic complexity circles. The actual identity is much more general, and in particular, applies to any linear form raised to an arbitrary power. Saxena (2008) famously used this duality to derive identity testing algorithms for polynomials that are poly(n,d)-sums of powers of linear forms. This model (AKA sum-power-sum) coincides with the well-studied notion of Waring rank in mathematics.
In this talk, we will see two proofs of the duality trick due to Saxena and Shpilka respectively. Both these proofs use fairly elementary ideas about polynomials. We shall then see a different proof of correctness of Saxena's construction that uses mildly non-elementary algebraic geometry.
Zoom link: https://zoom.us/j/98132227553?pwd=K2cyQllKVjExdUhlRm0vc0ZHcEt0Zz09
In this talk, we will see two proofs of the duality trick due to Saxena and Shpilka respectively. Both these proofs use fairly elementary ideas about polynomials. We shall then see a different proof of correctness of Saxena's construction that uses mildly non-elementary algebraic geometry.
Zoom link: https://zoom.us/j/98132227553?pwd=K2cyQllKVjExdUhlRm0vc0ZHcEt0Zz09