News & Events
Department Events & Announcements

Events

  • Jan
    22

    CS Seminar: Arithmetic circuits: lower bounds, learning and applications (Ankit Garg)

    Department of Computer Science (CS)

    12:00 PM 3514, Mudd Hall ( formerly Seeley G. Mudd Library)

    EVENT DETAILS

    Wednesday / CS Seminar
    January 22nd / 12:00 PM
    Hybrid / Mudd 3514

    Speaker
    Ankit Garg, Microsoft Research India

    Talk Title
    Arithmetic circuits: lower bounds, learning and applications

    Abstract
    Arithmetic circuits are a natural model for computing polynomials via the basic operations of addition and multiplication. One of the fundamental open problems in this area is of proving lower bounds, i.e. finding an explicit polynomial that cannot be computed by polynomial sized arithmetic circuits (aka the VP vs VNP problem). While the question of proving lower bounds for general arithmetic circuits is still open, there has been remarkable progress in proving lower bounds for restricted classes of arithmetic circuits. Another important problem in this area is that of learning arithmetic circuits: given a polynomial (via query or black box access), output a small arithmetic circuit computing it (if one exists). This problem is hard in the worst case. I will present a meta framework for learning arithmetic circuits in the non-degenerate case using lower bound methods. We instantiate and implement this meta framework for various classes of arithmetic circuits. Then I will talk about extending the algorithms to the noisy setting as well as surprising and remarkable applications to classical problems in machine learning such as subspace clustering and mixtures of Gaussians. This is based on joint works with Pritam Chandra, Neeraj Kayal, Kunal Mittal, Chandan Saha and Tanmay Sinha.

    Biography
    Ankit Garg is a Senior Researcher at Microsoft Research India since July 2018. Prior to this, he was a Postdoctoral Researcher at Microsoft Research New England from 2016 - 2018. He completed his PhD in 2016 from Princeton University under the supervision of Prof Mark Braverman. His research has spanned several areas of theoretical computer science such as communication complexity, arithmetic complexity, optimization, mixture models and optimization. Several of his research papers have been published in top conferences in computer science such as STOC, FOCS, CCC, NeuRIPS and QIP, and recognized by Simons award for graduate students in theoretical computer science and a Siebel scholarship.

    Research/Interest Areas
    Theoretical Computer Science, Algorithms, Computational Complexity Theory

    ---
    Zoom: https://northwestern.zoom.us/j/92525649422?pwd=N6DlLBx6RRAtrar8vk27te6cjmzqXP.1
    Panopto: https://northwestern.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=4d9fd60c-89e5-48f6-bbdb-b261015638de
    DEI Minute: tinyurl.com/cspac-dei-minute

    more

    TIME Wednesday, January 22, 2025 at 12:00 PM - 1:00 PM

    LOCATION 3514, Mudd Hall ( formerly Seeley G. Mudd Library)    map it

    ADD TO CALENDAR

    CONTACT Wynante R Charles    wynante.charles@northwestern.edu EMAIL

    CALENDAR Department of Computer Science (CS)

  • Aug
    20

    Alumni Education Webinar: McCormick School of Engineering's Strategic Vision

    McCormick School of Engineering and Applied Science

    12:00 PM

    EVENT DETAILS

    TIME Wednesday, August 20, 2025 at 12:00 PM - 1:00 PM

    ADD TO CALENDAR

    CONTACT Andi Joppie    andi.joppie@northwestern.edu EMAIL

    CALENDAR McCormick School of Engineering and Applied Science

  • Sep
    8

    Welcome & Breakfast for New McCormick PhD Students

    McCormick School of Engineering and Applied Science

    9:00 AM LR2 & Tech East Plaza, Technological Institute

    EVENT DETAILS

    TIME Monday, September 8, 2025 at 9:00 AM - 10:00 AM

    LOCATION LR2 & Tech East Plaza, Technological Institute    map it

    ADD TO CALENDAR

    CONTACT Andi Joppie    andi.joppie@northwestern.edu EMAIL

    CALENDAR McCormick School of Engineering and Applied Science

  • Sep
    12

    New Undergraduate Fall 2025 Registration

    University Academic Calendar

    All Day

    EVENT DETAILS

    TIME Friday, September 12, 2025

    ADD TO CALENDAR

    CONTACT Office of the Registrar    nu-registrar@northwestern.edu EMAIL

    CALENDAR University Academic Calendar

  • Sep
    15

    Welcome & Luncheon for New Full-time Graduate Students

    McCormick School of Engineering and Applied Science

    11:00 AM Ryan Auditorium & Tech East Plaza, Technological Institute

    EVENT DETAILS

    TIME Monday, September 15, 2025 at 11:00 AM - 12:30 PM

    LOCATION Ryan Auditorium & Tech East Plaza, Technological Institute    map it

    ADD TO CALENDAR

    CONTACT Andi Joppie    andi.joppie@northwestern.edu EMAIL

    CALENDAR McCormick School of Engineering and Applied Science

  • Sep
    16

    Fall Classes Begin. Change of Registration (Drop/Add) Late registration for returning students begins

    University Academic Calendar

    All Day

    EVENT DETAILS

    TIME Tuesday, September 16, 2025

    ADD TO CALENDAR

    CONTACT Office of the Registrar    nu-registrar@northwestern.edu EMAIL

    CALENDAR University Academic Calendar

  • Sep
    25

    Bagel Thursday

    Department of Computer Science (CS)

    9:00 AM

    EVENT DETAILS

    TIME Thursday, September 25, 2025 at 9:00 AM - 11:00 AM

    ADD TO CALENDAR

    CONTACT Wynante R Charles    wynante.charles@northwestern.edu EMAIL

    CALENDAR Department of Computer Science (CS)