Reconstructing Arithmetic Formulas: Insights by Neeraj Kayal at Algebraic Complexity Workshop 🧮
Join the discussion on reconstructing arithmetic formulas with Neeraj Kayal during the Algebraic Complexity Theory Workshop, organized by Prahladh Harsha, Ramprasad Saptharishi, and Srikanth Srinivasan on March 25, 2019.
International Centre for Theoretical Sciences
379 views • May 14, 2019
About this video
Discussion Meeting
Workshop on Algebraic Complexity Theory
ORGANIZERS: Prahladh Harsha, Ramprasad Saptharishi and Srikanth Srinivasan
DATE: 25 March 2019 to 29 March 2019
VENUE: Madhava Lecture Hall, ICTS Bangalore
Algebraic complexity aims at understanding the computational aspects of algebraic objects such as multivariate polynomials, tensors etc. The primary focus in this field has been the study of multivariate polynomials, and its hardness based on the number of addition/multiplication operations required to compute it (i.e. via `algebraic circuits'). This is a quest to answer the ``VP vs VNP'' question, an algebraic analogue of the classical ``P vs NP'' question and is a fundamental open problem in algebraic complexity.
These questions about multivariate polynomial broadly fall in one of the following categories:
Lower bounds: Can we find explicit polynomials that cannot be computed by small algebraic circuits?
Polynomial Identity Testing: Given an algebraic circuit C, can we test efficiently if the circuit C is computing the zero polynomial? (Or equivalently, can we test if two circuits C_1 and C_2 are computing the same polynomial?)
Reconstruction: Given blackbox access to a circuit C, can we query evaluations of this blackbox to reconstruct a small circuit for C?
These above problems, albeit very different at first glance, are intimately connected to each other. Over the last 7-8 years, there has been tremendous progress in understanding the above questions for natural subclasses of circuits, the deep relationships between these problems, and also some barrier results to give clarity on what types of techniques are promising approaches to the general problems. This five day workshop would have a series of about 25-30 lectures by various researchers in the field comprising of some of the recent advances in the field and also some tutorials aimed at giving students a gentle introduction to the area.
CONTACT US: wact2019@icts.res.in
PROGRAM LINK: https://www.icts.res.in/discussion-meeting/wact2019
Workshop on Algebraic Complexity Theory
ORGANIZERS: Prahladh Harsha, Ramprasad Saptharishi and Srikanth Srinivasan
DATE: 25 March 2019 to 29 March 2019
VENUE: Madhava Lecture Hall, ICTS Bangalore
Algebraic complexity aims at understanding the computational aspects of algebraic objects such as multivariate polynomials, tensors etc. The primary focus in this field has been the study of multivariate polynomials, and its hardness based on the number of addition/multiplication operations required to compute it (i.e. via `algebraic circuits'). This is a quest to answer the ``VP vs VNP'' question, an algebraic analogue of the classical ``P vs NP'' question and is a fundamental open problem in algebraic complexity.
These questions about multivariate polynomial broadly fall in one of the following categories:
Lower bounds: Can we find explicit polynomials that cannot be computed by small algebraic circuits?
Polynomial Identity Testing: Given an algebraic circuit C, can we test efficiently if the circuit C is computing the zero polynomial? (Or equivalently, can we test if two circuits C_1 and C_2 are computing the same polynomial?)
Reconstruction: Given blackbox access to a circuit C, can we query evaluations of this blackbox to reconstruct a small circuit for C?
These above problems, albeit very different at first glance, are intimately connected to each other. Over the last 7-8 years, there has been tremendous progress in understanding the above questions for natural subclasses of circuits, the deep relationships between these problems, and also some barrier results to give clarity on what types of techniques are promising approaches to the general problems. This five day workshop would have a series of about 25-30 lectures by various researchers in the field comprising of some of the recent advances in the field and also some tutorials aimed at giving students a gentle introduction to the area.
CONTACT US: wact2019@icts.res.in
PROGRAM LINK: https://www.icts.res.in/discussion-meeting/wact2019
Video Information
Views
379
Likes
4
Duration
01:02:46
Published
May 14, 2019