Seminars

View all Seminars  |  Download ICal for this event

Learning Read-Once Determinants via the Principal Minor Assignment Problem

Series: M.Tech (Research) Colloquium

Speaker: Abhiram Aravind, M.Tech (Research), Dept. of CSA, IISc

Date/Time: May 19 11:00:00

Location: CSA Lecture Hall (Room No. 112, Ground Floor)

Faculty Advisor: Prof. Chandan Saha

Abstract:
A symbolic determinant under rank-one restriction is a polynomial of the form det(C + A_0 x_0 + ... + A_{n-1} x_{n-1}) where C, A_0, ..., A_{n-1} are square matrices over some field F and A_0, A_1, ..., A_{n-1} are rank-one. We ask the following problem: given black-box access to the polynomial det(C + A_0 x_0 + ... + A_{n-1} x_{n-1}), find square matrices D, B_0, B_1, ..., B_{n-1} with B_0, ..., B_{n-1} being rank-one such that det(C + A_0 x_0 + ... + A_{n-1} x_{n-1}) = det(D + B_0 x_0 + ... + B_{n-1} x_{n-1}). Since this polynomial family is known to be equivalent to read-once determinants (RODs), we call this problem Learning RODs. A read-once determinant is a determinant whose entries are either field constants or variables, with each variable appearing at most once.

For learning RODs, we give a randomised polynomial time algorithm by connecting it to another well-known problem in linear algebra: the Principal Minor Assignment Problem (PMAP). In PMAP, we are asked to construct a matrix with a given list of principal minors. We show that learning RODs is randomised polynomial time equivalent to a black-box variant of PMAP: given black-box access to det(A + X) where A is a square matrix over F and X is a diagonal matrix with variable entries, find a matrix B such that det(A+X) = det(B+X). We then solve this black-box PMAP in randomised polynomial time by reducing it to PMAP for a special class of matrices that satisfy what we call property R. The randomised polynomial time equivalence between learning RODs and black-box PMAP as well as the reduction from black-box PMAP to PMAP of matrices that satisfy property R can be derandomised in quasi-polynomial time.