Seminar • Algorithms and Complexity — Factoring Polynomials Given as Arithmetic Branching Programs

Thursday, July 2, 2020 — 11:00 AM EDT

Please note: This seminar will be given online.

Amit Sinhababu
Aalen University, Germany

A basic problem in computational algebra is polynomial factoring: Given a polynomial, compute all its irreducible factors. In a classic result, Kaltofen proved that if a polynomial P(x_1,...,x_n) of degree d is given as an arithmetic circuit of size s, then all its factors can be computed by arithmetic circuits of size poly(s,d). In other words, the algebraic complexity class VP is closed under factors. This result has applications in algebraic complexity, for example in derandomization of polynomial identity testing using explicit hard polynomials (lower bounds).

A natural direction to extend Kaltofen’s result is to prove analogous factor size bounds in more restricted / more general models than arithmetic circuits. Kaltofen’s proofs do not extend to the restricted models, as reusing previous computations is costly for these models. Recent works in this area focused on models like constant depth circuits, arithmetic formulas, arithmetic branching programs.

In a beautiful work, Oliveira (CCC 2015) proved that factors of a low-depth circuit/formula can be computed by small low-depth circuits/formulas, if we assume that the individual degree of the given polynomial is bounded by constant. In a follow-up work, Dutta, Saxena and Sinhababu (DSS, STOC 18) showed poly (s^log d) factor size upper bound for arithmetic formulas and branching programs.

In this work, we show poly (s,d) factor size upper bound for the model of arithmetic branching programs (ABP). Whereas the works of Oliveira and DSS used different versions of Newton iteration, we use the classic technique of Hensel lifting. Although Newton iteration and Hensel lifting are related techniques, the latter gives better bound for ABPs. We also use that the determinant of a symbolic matrix can be computed by a small ABP. In this talk, we give a brief survey of the earlier works and present the main ideas of our proof.

Joint work with Thomas Thierauf, to appear in CCC 20.

To join this seminar on Zoom, please go to https://zoom.us/j/98020744915
Meeting ID: 980 2074 4915

Location
Online seminar
200 University Avenue West

Waterloo, ON N2L 3G1

July 2020

S M T W T F S
28
29
30
1
3
4
5
7
10
11
12
13
14
15
16
17
18
19
20
21
24
25
26
27
28
29
30
31
1
1. 2020 (133)
1. August (2)
2. July (11)
3. June (19)
4. May (17)
5. April (20)
6. March (17)
7. February (25)
8. January (22)
2. 2019 (255)
1. December (21)
2. November (25)
3. October (16)
4. September (20)
5. August (18)
6. July (12)
7. June (23)
8. May (23)
9. April (32)
10. March (25)
11. February (16)
12. January (24)
3. 2018 (220)
4. 2017 (36)
5. 2016 (21)
6. 2015 (36)
7. 2014 (33)
8. 2013 (23)
9. 2012 (4)
10. 2011 (1)
11. 2010 (1)
12. 2009 (1)
13. 2008 (1)