A new characterization of VNP via colored determinant by Dr. Prasad Chaugule

Venue: Bharti501

Abstract: Understanding the algebraic complexity class VNP through alternative characterizations is a central theme in algebraic complexity theory, closely tied to the VP vs. VNP problem. While the permanent provides a canonical complete polynomial for VNP, identifying natural and combinatorial variants that lead to new structural insights remains an important challenge.In this talk, I will present a new characterization of VNP based on acombinatorial variant of the determinant, which we call the colored determinant. This polynomial is defined as a signed sum over properly colored cycle covers of a directed graph, where each cycle is required to be monochromatic. We show that the colored determinant is VNP-complete under p-projections over all fields, thereby adding a new non-monotone VNP-complete polynomial family distinct from the permanent and previously studied determinant variants.

Using this polynomial, we introduce a new computational model called the conditional stack branching program. Unlike standard stack branching programs, this model allows the stack operation on an edge to depend on the current top of the stack. We show that this added conditional power is sufficient to increase expressiveness: a single-stack conditional stack branching program already characterizes VNP. This sharply contrasts with prior results, where at least two stacks were required to capture VNP.

Speaker Bio: Dr. Prasad Chaugule is a Post Doctoral fellow in the Theory Group at Department of Computer Science and Engineering, IIT Delhi. His research lies in Arithmetic Circuit Complexity. He earned his Ph.D from IIT Bombay.