max planck institut

informatik

informatik

<< Previous Entry | Next Entry >> | New Event Entry | Edit this Entry | Login to DB (to update, delete) |

Title: | A Quadratic Size-Hierarchy Theorem for Small-Depth Multilinear Formulas |
---|---|

Speaker: | Suryajith Chillara |

coming from: | IIT Bombay |

Speakers Bio: | |

Event Type: | AG1 Mittagsseminar (own work) |

Visibility: | D1, MMCI We use this to send out email in the morning. |

Level: | AG Audience |

Language: | English |

Date: | Thursday, 18 October 2018 |
---|---|

Time: | 13:00 |

Duration: | 45 Minutes |

Location: | Saarbrücken |

Building: | E1 4 |

Room: | 024 |

It is a fundamental problem in the study of computational complexity to understand if access to more resources would mean strictly more computational power. In classical complexity, we have seen such examples in terms of Time Hierarchy and Space Hierarchy theorems. Here, time and space are the resources. It is natural to ask such a question in the setting of algebraic complexity setting. Here, access to more resources translates to allowing the model to perform more number of operations which in turn is allowing the "algebraic formulas" to have larger size.
Arithmetic formulas are directed trees where the leaves are labelled by variables and elements of the field, and internal vertices are labelled by + or x. Every internal vertex computes a polynomial by operating on its inputs. It is easy to see that they are a natural model of computation of polynomials, syntactically (symbolically). The size of the arithmetic formulas refers to the number of + and x operations needed to compute the polynomial. |

Name(s): | Nitin Saurabh |
---|

Video Broadcast: | No | To Location: |
---|

Note: | |
---|---|

Attachments, File(s): |

Created: | Nitin Saurabh, 10/17/2018 01:36 PM |

Last modified: | Uwe Brahm/MPII/DE, 10/18/2018 07:01 AM |

- Nitin Saurabh, 10/17/2018 01:36 PM -- Created document.