Classifying Polynomials from a Computational Perspective by Manindra Agrawal скачать в хорошем качестве

Classifying Polynomials from a Computational Perspective by Manindra Agrawal

ICTS Colloquium Title : Classifying Polynomials from a Computational Perspective Speaker : Manindra Agrawal, Indian Institute of Technology, Kanpur Date : Monday, June 10, 2019 Time : 3:00 PM Venue : Emmy Noether Seminar Room, ICTS Campus, Bangalore Abstract : We consider the problem of classifying polynomials according to difficulty of computing them. We argue that this approach gives better classification of polynomials according to their properties compared with the usual ones like degree or sparsity. After giving the definition, we identify two classes of polynomials that give rise to the central question in algebraic complexity theory and introduce the Polynomial Identity Testing (PIT) problem which has come to play a key role in resolving this question. Finally, we summarize the progress made in the past two decades in solving the PIT. Detailed information about this seminar is also available at ICTS Seminars and Colloquia Table of Contents (powered by https://videoken.com) 0:00:00 INTRODUCTION 0:00:55 POLYNOMIALS FROM A COMPUTATIONAL PERSPECTIVE 0:01:49 OVERVIEW 0:02:59 POLYNOMIALS 0:03:15 EXAMPLE: CHEBYSHEV POLYNOMIALS 0:04:01 EXAMPLE: BESSEL POLYNOMIALS 0:04:21 EXAMPLE: EULER POLYNOMIALS 0:05:41 EXAMPLE: DETERMINANT POLYNOMIALS 0:06:21 EXAMPLE: PERMANENT POLYNOMIALS 0:07:38 OUTLINE 0:08:47 USING BASIC PARAMETERS 0:10:09 USING ALGEBRAIC GEOMETRY 0:12:37 USING ARITHMETIC COMPLEXITY 0:16:31 ARITHMETIC CIRCUITS 0:17:59 AN EXAMPLE 0:19:50 ARITHMETIC COMPLEXITY 0:20:37 CIRCUIT PARAMETERS 0:20:56 PROPERTIES OF ARITHMETIC CIRCUITS 0:23:39 WHY NO DIVISION OPERATION? 0:24:16 ARITHMETIC COMPLEXITY OF POLYNOMIAL FAMILIES 0:25:44 EXAMPLES 0:26:12 BOUNDS ON ARITHMETIC COMPLEXITY 0:27:16 CLASSIFYING ARITHMETIC COMPLEXITY OF POLYNOMIAL FAMILIES 0:29:37 CAPTURING LOW COMPLEXITY FAMILIES 0:29:52 EXAMPLES: POLYNOMIAL FAMILIES IN VP 0:30:08 CAPTURING INTERESTING FAMILIES 0:34:18 EXAMPLES: POLYNOMIAL FAMILIES IN VNP 0:35:00 EXAMPLES: UNIVARIATE POLYNOMIAL FAMILIES IN 0:35:08 PERMANENT FAMILY AND VNP 0:36:47 Is VP # VNP? 0:38:39 POLYNOMIAL IDENTITY TESTING 0:39:42 AN EXAMPLE 0:40:49 COMPLEXITY OF PIT 0:42:49 CONNECTION OF PIT WITH LOWER BOUNDS 0:43:46 BLACK-BOX ALGORITHM FOR PIT 0:46:46 DETERMINISTIC BLACK-BOX ALGORITHMS FOR PIT 0:48:34 DETERMINISTIC BLACK-BOX ALGORITHMS FOR 4-PIT 0:50:06 DETERMINISTIC BLACK-BOX ALGORITHMS SLIGHTLY BETTER THAN WORST POSSIBLE 0:54:20 Q&A