Prerona Chatterjee

Based on my Research Papers

Recent Progress in Algebraic Circuit Complexity

• Continuous Methods in Discrete Optimization and Complexity, Mysuru, India.
• Survey Talk that includes joint work with Mrinal Kumar, Deepanshu Kush, Shubhangi Saraf, Adrian She, Amir Shpilka and Ben Lee Volk.

Lower Bounds for some Algebraic Models of Computation

• CSE Department, IIT Bombay. [Slides]
• CSE Department, IIT Hyderabad. [Slides]
• IMSc, Chennai. [Slides]
• Mathematics Department, IIT Hyderabad. [Slides, Slides]
• CSE Department, IIT Madras. [Slides]
• Mathematics Department, IIT Madras. [Slides]
• NISER, Bhubaneswar. [Slides, Slides]
• Survey talk based on some of my works that prove Lower Bounds against different Algebraic Models of Computation.
• Includes joint work with Pavel Hrubesͮ, Mrinal Kumar, Deepanshu Kush, Shubhangi Saraf, Adrian She, Amir Shpilka and Ben Lee Volk.

Lower Bounds for Sums of Ordered Set-Multilinear ABPs

• Algebraic and Analytic Methods in Computational Complexity, Dagstuhl, Germany. [Slides]
• CSA Department Seminar, IISc Bangalore. [Slides]
• CSE Seminar, IIT Hyderabad. [Slides]
• Based on joint work with Deepanshu Kush, Shubhangi Saraf and Amir Shpilka

Monotone Classes Beyond VNP

• Workshop on Algebra and Computation.
• Based on joint work with Kshitij Gajjar and Anamay Tengse

Lower Bounds Against Non-Commutative Models of Algebraic Computation

• Proof Complexity and Meta-Mathematics, Simons Institute for the Theory of Computing, Berkeley.
• Survey Talk on Lower Bounds in the Non-Commutative Model of Algebraic Computation
• Includes joint work with Pavel Hrubesͮ.
• Video.

A Quadratic Lower Bound against Homogeneous Non-Commutative Circuits

• Algebraic and Analytic Methods in Computational Complexity, Dagstuhl, Germany. [Slides]
• WACT 2023, University of Warwick, UK. [Slides, Video]
• Seminar, CMI, India. [Slides]
• Based on joint work with Pavel Hrubesͮ.

Separating ABPs and some Structured Formulas in the Non-Commutative Setting

• Complexity Theory with a Human Face, 3rd Edition, Špindlerův Mlýn, Czechia.

Lower Bounds in Algebraic Circuit Complexity

• Theory Seminar @ IIITH, IIIT Hyderabad. [Slides]
• Math Seminar, IIT Guwahati. [Slides]
• Short survey on lower bounds in algebraic circuit complexity with focus on the quadratic lower bound against ABPs.
• Based on joint work with Mrinal Kumar, Adrian She and Ben Lee Volk.

Lower Bounds in Algebraic Circuit Complexity

• TCS Women Spotlight Event, STOC 2021.
• Survey talk based on three of my recent works.
• Video.

A Quadratic Lower Bound for Algebraic Branching Programs

• Theory CS Reading Group, IIT Bombay.
• Based on joint work with Mrinal Kumar, Adrian She and Ben Lee Volk.

Faithful Homomorphisms and PIT - A Short Survey

• Bootcamp on PIT, SIGTACS, IIT Kanpur.
• Based on joint work with Ramprasad Saptharishi.

Algebraic Independence Testing over Arbitrary Fields

• Student Rump Session, WIT, 2018, Harvard University.

Constructing Faithful Maps over Arbitrary Fields

• WACT, 2018, Université Paris Diderot.
• Based on joint work with Ramprasad Saptharishi.

Other Research Talks

Entropy in Algebraic Independence Testing

• JRfest, ICTS-TIFR Bengaluru, India.
• Based on an alternate view of statements in [GSS19].

An Almost Quadratic Lower Bound Against Formulas for a Constant-Degree Polynomial

• MMcomplexity, IIT Gandhinagar, India.
• Based on a generalisation of Kalorkoti's Lower Bound.

A Quadratic Lower Bound for Homogeneous ABPs

• Second Qualifier Presentation, TIFR, Mumbai.
• Based on the paper by Kumar.

Linear Matroid Intersection is in quasi-NC

• First Qualifier Presentation, TIFR, Mumbai.
• Based on the paper by Gurjar and Thierauf.

Unbalanced Random Matching Markets

• STCS Day, 2017, TIFR, Mumbai.
• Based on the paper by Ashlagi, Kanoria and Leshno.

Compactness Theorem for Propositional Logic: A Topological Proof

• Seminar Presentation, IIT Guwahati
• Based on the lecture notes by Minnes.