BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Computer Science and Engineering - ECPv6.13.0//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-ORIGINAL-URL:https://homecse.iitd.ac.in
X-WR-CALDESC:Events for Computer Science and Engineering
REFRESH-INTERVAL;VALUE=DURATION:PT1H
X-Robots-Tag:noindex
X-PUBLISHED-TTL:PT1H
BEGIN:VTIMEZONE
TZID:Asia/Kolkata
BEGIN:STANDARD
TZOFFSETFROM:+0530
TZOFFSETTO:+0530
TZNAME:IST
DTSTART:20260101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Kolkata:20260204T120000
DTEND;TZID=Asia/Kolkata:20260204T130000
DTSTAMP:20261010T144915
CREATED:20260201T193547Z
LAST-MODIFIED:20260201T193547Z
UID:2413-1770206400-1770210000@homecse.iitd.ac.in
SUMMARY:A new characterization of VNP via colored determinant by Dr. Prasad Chaugule
DESCRIPTION:Venue: Bharti501 \nAbstract: 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. \nUsing 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. \n  \nSpeaker 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.
URL:https://homecse.iitd.ac.in/event/a-new-characterization-of-vnp-via-colored-determinant-by-dr-prasad-chaugule/
LOCATION:Bharti 501\, IIT Campus\, Hauz Khas\, New Delhi
END:VEVENT
END:VCALENDAR