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)

  • Apr
    19

    CS Seminar: Hardware-Aware Efficient Primitives for Machine Learning (Dan Fu)

    Department of Computer Science (CS)

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

    EVENT DETAILS

    TIME Friday, April 19, 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)

  • Apr
    24

    CS Seminar: AI Powered Movement Analysis, Big Rehabilitation Data and a Path to Precision Rehabilitation (R. James Cotton)

    Department of Computer Science (CS)

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

    EVENT DETAILS

    TIME Wednesday, April 24, 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)

  • Apr
    25

    TGI Bagel Thursday

    Department of Computer Science (CS)

    9:00 AM 3514, Mudd Hall ( formerly Seeley G. Mudd Library)

    EVENT DETAILS

    TIME Thursday, April 25, 2024 at 9:00 AM - 11:00 AM

    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)

  • Apr
    29

    CS Seminar: Kaize Ding

    Department of Computer Science (CS)

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

    EVENT DETAILS

    TIME Monday, April 29, 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)

  • May
    1

    CS Seminar: Tong Zhang

    Department of Computer Science (CS)

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

    EVENT DETAILS

    TIME Wednesday, May 1, 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)

  • May
    3

    CS Seminar: Shafi Goldwasser

    Department of Computer Science (CS)

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

    EVENT DETAILS

    TIME Friday, May 3, 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)

  • May
    8

    Extending Care: A Conversation about Conservation and Futurity

    Block Museum of Art

    6:00 PM Block Museum of Art, Mary and Leigh

    EVENT DETAILSmore info

    TIME Wednesday, May 8, 2024 at 6:00 PM - 7:30 PM

    LOCATION Block Museum of Art, Mary and Leigh    map it

    ADD TO CALENDAR

    CONTACT Block Museum of Art    block-museum@northwestern.edu EMAIL

    CALENDAR Block Museum of Art

  • May
    30

    TGI Bagel Thursday

    Department of Computer Science (CS)

    9:00 AM 3514, Mudd Hall ( formerly Seeley G. Mudd Library)

    EVENT DETAILS

    TIME Thursday, May 30, 2024 at 9:00 AM - 11:00 AM

    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)

  • Jun
    10

    Northwestern Engineering PhD Hooding and Master's Degree Recognition Ceremony

    McCormick School of Engineering and Applied Science

    9:00 AM Welsh-Ryan Arena

    EVENT DETAILSmore info

    TIME Monday, June 10, 2024 at 9:00 AM - 11:00 AM

    LOCATION Welsh-Ryan Arena   

    ADD TO CALENDAR

    CONTACT Amy Pokrass    amy.pokrass@northwestern.edu EMAIL

    CALENDAR McCormick School of Engineering and Applied Science

  • Jun
    10

    Northwestern Engineering Undergraduate Convocation

    McCormick School of Engineering and Applied Science

    2:00 PM Welsh-Ryan Arena

    EVENT DETAILSmore info

    TIME Monday, June 10, 2024 at 2:00 PM - 4:00 PM

    LOCATION Welsh-Ryan Arena   

    ADD TO CALENDAR

    CONTACT Amy Pokrass    amy.pokrass@northwestern.edu EMAIL

    CALENDAR McCormick School of Engineering and Applied Science