Description

Speaker: Dr. Mrinal Kumar, Simons Institute for the Theory of Computing,

Berkeley, USA.

Time: 11 am, Friday, 11th January.

Venue: Ramanujan Hall.

Title : Some closure results for polynomial factorization and applications

Abstract : In a sequence of seminal results in the 80's, Kaltofen showed

that if an n-variate polynomial of degree poly(n) can be computed by an

arithmetic circuit of size poly(n), then each of its factors can also be

computed an arithmetic circuit of size poly(n). In other words,

the complexity class VP (the algebraic analog of P) of polynomials, is

closed under taking factors.

A fundamental question in this line of research, which has largely

remained open is to understand if other natural classes of

multivariate polynomials, for instance, arithmetic formulas, algebraic

branching programs, constant depth arithmetic circuits or the

complexity class VNP (the algebraic analog of NP) of polynomials, are

closed under taking factors. In addition to being fundamental

questions on their own, such 'closure results' for polynomial

factorization play a crucial role in the understanding of hardness

randomness tradeoffs for algebraic computation.

I will talk about the following two results, whose study was motivated

by these questions.

1. The class VNP is closed under taking factors. This proves a

conjecture of B{\"u}rgisser.

2. All factors of degree at most poly(log n) of polynomials with

constant depth circuits of size

poly(n) have constant (a slightly larger constant) depth arithmetic

circuits of size poly(n).

This partially answers a question of Shpilka and Yehudayoff and has

applications to hardness-randomness tradeoffs for constant depth

arithmetic circuits. Based on joint work with Chi-Ning Chou and Noam

Solomon.

Berkeley, USA.

Time: 11 am, Friday, 11th January.

Venue: Ramanujan Hall.

Title : Some closure results for polynomial factorization and applications

Abstract : In a sequence of seminal results in the 80's, Kaltofen showed

that if an n-variate polynomial of degree poly(n) can be computed by an

arithmetic circuit of size poly(n), then each of its factors can also be

computed an arithmetic circuit of size poly(n). In other words,

the complexity class VP (the algebraic analog of P) of polynomials, is

closed under taking factors.

A fundamental question in this line of research, which has largely

remained open is to understand if other natural classes of

multivariate polynomials, for instance, arithmetic formulas, algebraic

branching programs, constant depth arithmetic circuits or the

complexity class VNP (the algebraic analog of NP) of polynomials, are

closed under taking factors. In addition to being fundamental

questions on their own, such 'closure results' for polynomial

factorization play a crucial role in the understanding of hardness

randomness tradeoffs for algebraic computation.

I will talk about the following two results, whose study was motivated

by these questions.

1. The class VNP is closed under taking factors. This proves a

conjecture of B{\"u}rgisser.

2. All factors of degree at most poly(log n) of polynomials with

constant depth circuits of size

poly(n) have constant (a slightly larger constant) depth arithmetic

circuits of size poly(n).

This partially answers a question of Shpilka and Yehudayoff and has

applications to hardness-randomness tradeoffs for constant depth

arithmetic circuits. Based on joint work with Chi-Ning Chou and Noam

Solomon.

Description

Ramanujan Hall, Department of Mathematics

Date

Fri, January 11, 2019

Start Time

11:00am IST

Priority

5-Medium

Access

Public

Created by

DEFAULT ADMINISTRATOR

Updated

Tue, January 8, 2019 7:58pm IST