Seminar Announcement
Date: Thursday, 16 January 2025
Time: 10:45 AM
Venue: Seminar Hall
Order-finding for Structured ABPs
Anamay Tengse
NISER Bhubaneswar.
16-01-25

---

Abstract

In 1979, Leslie Valiant showed that we can count the number of satisfying assignments of a 3CNF formula, by computing the permanent of a matrix that is polynomially larger than the formula. Here, the permanent is a polynomial that looks much like the determinant, except that all the coefficients are +1. In a different work from 1979, Valiant conjectured that despite this similarity with the determinant, any procedure that transforms a matrix A into another matrix B, such that Det(B) = Perm(A), would incur a super-polynomial blow-up. This conjecture, which is essentially implied by P-not-equals-NP, and is hence arguably easier, is regarded as the birth of algebraic complexity.

Algebraic Branching Programs (ABPs) are a computational model that capture the 'determinantal complexity' of a polynomial (how large a matrix B(x) needs to be so that det(B(x)) = f(x)). As a result, most questions about ABPs are hard to tackle, and people have therefore looked at more structured ABPs, like Read-once Oblivious ABPs (ROABPs).

In this talk, we will first familiarize ourselves with algebraic complexity in general, and ABPs and ROABPs, and then look at the complexity of what is called ``the order-finding problem'' for ROABPs.