Tata Institute of Fundamental Research
Constructing Faithful Maps
STCS Student Seminar
Speaker:
Prerona Chatterjee
Organiser:
Varun Narayanan
Date:
Friday, 14 Sep 2018, 17:15 to 18:15
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
Abstract: Suppose we are given a set of $k$ polynomials, $f_1, \ldots, f_k \in \mathbb{F}[x_1, \ldots, x_n]$. They are said to be algebraically dependent if there is a non-zero polynomial $A$ over $\mathbb{F}$ in $k$ variables such that $A(f_1, \ldots, f_k) = 0$. Otherwise, they are said to be algebraically independent.
Just like a set of $k$ linearly independent vectors in $\mathbb{R}^n$ actually resides in a $k$-dimensional subspace, a set of $k$ algebraically independent polynomials intuitively has the same "freedom" as only $k$ independent variables. A faithful map formalises this.
Suppose $\{f_1, \ldots, f_k\} \subseteq \mathbb{F}[x_1, \ldots, x_n]$ is a set of algebraically independent polynomials. A map $\phi : \{x_i\} \mapsto \mathbb{F}[y_1, \ldots, y_k]$ is said to be faithful if the set of polynomials $\{f_i(\phi(x_1), \ldots, \phi(x_n))\}_{i \in [k]} \subseteq \mathbb{F}[y_1, \ldots, y_k]$ is algebraically independent.
In this talk, we will construct faithful maps when the underlying field is $\mathbb{Q}$, $\mathbb{R}$ or $\mathbb{C}$ for example. Apart from being an interesting question in its own right, construction of faithful maps also has applications in algebraic circuit complexity.
| Speaker: | Prerona Chatterjee |
| Organiser: | Varun Narayanan |
| Date: | Friday, 14 Sep 2018, 17:15 to 18:15 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
Abstract: Suppose we are given a set of $k$ polynomials, $f_1, \ldots, f_k \in \mathbb{F}[x_1, \ldots, x_n]$. They are said to be algebraically dependent if there is a non-zero polynomial $A$ over $\mathbb{F}$ in $k$ variables such that $A(f_1, \ldots, f_k) = 0$. Otherwise, they are said to be algebraically independent.
Just like a set of $k$ linearly independent vectors in $\mathbb{R}^n$ actually resides in a $k$-dimensional subspace, a set of $k$ algebraically independent polynomials intuitively has the same "freedom" as only $k$ independent variables. A faithful map formalises this.
Suppose $\{f_1, \ldots, f_k\} \subseteq \mathbb{F}[x_1, \ldots, x_n]$ is a set of algebraically independent polynomials. A map $\phi : \{x_i\} \mapsto \mathbb{F}[y_1, \ldots, y_k]$ is said to be faithful if the set of polynomials $\{f_i(\phi(x_1), \ldots, \phi(x_n))\}_{i \in [k]} \subseteq \mathbb{F}[y_1, \ldots, y_k]$ is algebraically independent.
In this talk, we will construct faithful maps when the underlying field is $\mathbb{Q}$, $\mathbb{R}$ or $\mathbb{C}$ for example. Apart from being an interesting question in its own right, construction of faithful maps also has applications in algebraic circuit complexity.
Just like a set of $k$ linearly independent vectors in $\mathbb{R}^n$ actually resides in a $k$-dimensional subspace, a set of $k$ algebraically independent polynomials intuitively has the same "freedom" as only $k$ independent variables. A faithful map formalises this.
Suppose $\{f_1, \ldots, f_k\} \subseteq \mathbb{F}[x_1, \ldots, x_n]$ is a set of algebraically independent polynomials. A map $\phi : \{x_i\} \mapsto \mathbb{F}[y_1, \ldots, y_k]$ is said to be faithful if the set of polynomials $\{f_i(\phi(x_1), \ldots, \phi(x_n))\}_{i \in [k]} \subseteq \mathbb{F}[y_1, \ldots, y_k]$ is algebraically independent.
In this talk, we will construct faithful maps when the underlying field is $\mathbb{Q}$, $\mathbb{R}$ or $\mathbb{C}$ for example. Apart from being an interesting question in its own right, construction of faithful maps also has applications in algebraic circuit complexity.