News & Events
Department Events & Announcements

Events

  • Feb
    12

    CS Seminar: Recent Advances in Strongly Polynomial Algorithms for Linear Programming (Bento Natura)

    Department of Computer Science (CS)

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

    EVENT DETAILS

    Monday / CS Seminar
    February 12th / 12:00 PM
    In Person / Mudd 3514

    Speaker
    Bento Natura, Georgia Tech

    Talk Title
    Recent Advances in Strongly Polynomial Algorithms for Linear Programming

    Abstract
    Whereas ellipsoid methods and interior point methods provide polynomial-time linear programming algorithms, the running time bounds depend on bit-complexity or condition measures that can be unbounded in the problem dimension. This is in contrast with the simplex method that always admits an exponential bound.

    An important unresolved question in operations research, theoretical computer science, and related fields, concerns the existence of a strongly polynomial algorithm for linear programming. Such an algorithm's running time would solely depend on the problem's dimension and the number of constraints, independent of any additional condition numbers. This question, first articulated by Megiddo in the 1980s, has gained prominence as Smale's 9th problem.

    In the first part of our talk, we introduce a new polynomial-time path-following interior point method where the number of iterations admits a combinatorial upper bound that is exponential in the number of constraints. More precisely, the iteration count of our algorithm is at most a small polynomial factor times the segment count of any piecewise linear trajectory within a wide neighborhood of the central path. Notably, it parallels the iteration count of any path-following interior point method, with an adjustment for this polynomial factor.

    In the second part of our talk, we give a strongly polynomial algorithm for minimum cost generalized flow, and hence all linear programs with at most two nonzero entries per row, or at most two nonzero entries per column. This provides a next milestone towards answering Smale’s 9th problem.

    Biography
    Bento Natura is a Ronald J. and Carol T. Beerman/ARC Postdoctoral Fellow in ISyE at Georgia Tech. He obtained his PhD in the Department of Mathematics at the London School of Economics, where he was supervised by László Végh. His doctoral thesis earned him the departmental Dissertation Prize and placed as a runner-up for the PhD Prize awarded by the OR Society of the United Kingdom. Prior to his PhD, Bento earned Bachelor's and Master's degrees in Mathematics from the University of Bonn, under the supervision of Stephan Held and Jens Vygen. Bento's current research interests are centered on algorithms, optimization, and game theory.

    Research Interests/Area
    Algorithms and Optimization

    more less

    TIME Monday, February 12, 2024 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)

  • Feb
    22

    Optimisation, dimension reduction, representation theory, reproducibility by Dmitrii Pasechnik (Oxford)

    Department of Computer Science (CS)

    9:00 AM

    EVENT DETAILS

    TIME Thursday, February 22, 2024 at 9:00 AM - 10:00 AM

    ADD TO CALENDAR

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

    CALENDAR Department of Computer Science (CS)

  • Feb
    26

    CS Seminar: Accessible Foundation Models: Systems, Algorithms, and Science (Tim Dettmers)

    Department of Computer Science (CS)

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

    EVENT DETAILS

    TIME Monday, February 26, 2024 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)

  • Feb
    28

    CS Seminar: Paths to AI Accountability (Sarah Cen)

    Department of Computer Science (CS)

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

    EVENT DETAILS

    TIME Wednesday, February 28, 2024 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)

  • Mar
    4

    CS Seminar: Understanding Language Models through Discovery and by Design (John Hewitt)

    Department of Computer Science (CS)

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

    EVENT DETAILS

    TIME Monday, March 4, 2024 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)

  • Mar
    8

    PhD Prospective Student Visit Day

    Department of Computer Science (CS)

    8:00 AM Mudd Hall ( formerly Seeley G. Mudd Library)

    EVENT DETAILS

    TIME Friday, March 8, 2024 at 8:00 AM - 6:00 PM

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

    ADD TO CALENDAR

    CONTACT Madeleine Lantin    m-agaton@northwestern.edu EMAIL

    CALENDAR Department of Computer Science (CS)

  • Mar
    9

    Winter Classes End

    University Academic Calendar

    All Day

    EVENT DETAILS

    TIME Saturday, March 9, 2024

    ADD TO CALENDAR

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

    CALENDAR University Academic Calendar

  • Mar
    16

    Spring Break Begins

    University Academic Calendar

    All Day

    EVENT DETAILS

    TIME Saturday, March 16, 2024

    ADD TO CALENDAR

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

    CALENDAR University Academic Calendar

  • Mar
    22

    Winter Degrees Conferred

    University Academic Calendar

    All Day

    EVENT DETAILS

    TIME Friday, March 22, 2024

    ADD TO CALENDAR

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

    CALENDAR University Academic Calendar

  • Mar
    25

    Spring Break Ends

    University Academic Calendar

    All Day

    EVENT DETAILS

    TIME Monday, March 25, 2024

    ADD TO CALENDAR

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

    CALENDAR University Academic Calendar