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)

• Aug

  14

  Undergraduate Quantum Summer School

  McCormick School of Engineering and Applied Science

  All Day Ford Motor Company Engineering Design Center

  EVENT DETAILSmore info

  Innovation in Quantum Pedagogy, Application, and its Relation to Culture (IQ-PARC), funded by the Department of Defense — National Defense Education Program, is extending an invitation to underrepresented students nationwide (including military-connected students) to participate in a summer school focused on quantum technologies, to be held at Northwestern University. Join us for presentations by faculty and industry partners introducing quantum technologies, cutting-edge research areas, and related job opportunities particularly in the areas of national security.

  This effort aims to foster an inclusive environment that encourages participation from all corners of the academic community. Successful applicants will receive up to $1,000 USD to cover travel and lodging expenses in Evanston, IL.

  Priority application deadline: May 15, 2024.

  Decisions will be sent by June 15, 2024.

  Register Now

  more less

  TIME Wednesday, August 14, 2024

  LOCATION Ford Motor Company Engineering Design Center    map it

  ADD TO CALENDAR

  CONTACT Dongyang Li    lidongyang@northwestern.edu EMAIL

  CALENDAR McCormick School of Engineering and Applied Science

• Aug

  15

  Undergraduate Quantum Summer School

  McCormick School of Engineering and Applied Science

  All Day Ford Motor Company Engineering Design Center

  EVENT DETAILSmore info

  Innovation in Quantum Pedagogy, Application, and its Relation to Culture (IQ-PARC), funded by the Department of Defense — National Defense Education Program, is extending an invitation to underrepresented students nationwide (including military-connected students) to participate in a summer school focused on quantum technologies, to be held at Northwestern University. Join us for presentations by faculty and industry partners introducing quantum technologies, cutting-edge research areas, and related job opportunities particularly in the areas of national security.

  This effort aims to foster an inclusive environment that encourages participation from all corners of the academic community. Successful applicants will receive up to $1,000 USD to cover travel and lodging expenses in Evanston, IL.

  Priority application deadline: May 15, 2024.

  Decisions will be sent by June 15, 2024.

  Register Now

  more less

  TIME Thursday, August 15, 2024

  LOCATION Ford Motor Company Engineering Design Center    map it

  ADD TO CALENDAR

  CONTACT Dongyang Li    lidongyang@northwestern.edu EMAIL

  CALENDAR McCormick School of Engineering and Applied Science

• Sep

  16

  Computer Science Incoming MS Placement Exam

  Department of Computer Science (CS)

  All Day

  EVENT DETAILS

  *Applicable to new MS students. Does not apply to BSMS and BAMS students.

  more less

  TIME Monday, September 16, 2024

  ADD TO CALENDAR

  CONTACT MS Student Help    ms-help@cs.northwestern.edu EMAIL

  CALENDAR Department of Computer Science (CS)

• Sep

  16

  Computer Science PhD Orientation

  Department of Computer Science (CS)

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

  EVENT DETAILS

  New Ph.D. students and CS-affiliated faculty, all CS-affiliated Ph.D. students are welcome to attend the Fall 2024 Ph.D. orientation. This full day orientation various panels to orient PhD affiliates with the department and get answers to questions about PhD life.

  more less

  TIME Monday, September 16, 2024 at 8:00 AM - 5:00 PM

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

  ADD TO CALENDAR

  CONTACT PhD Student Help    phd-student-help@cs.northwestern.edu EMAIL

  CALENDAR Department of Computer Science (CS)

• Sep

  24

  Fall 2024 Classes Begin (No Northwestern Monday in Fall)

  University Academic Calendar

  All Day

  EVENT DETAILS

  Fall 2024 Classes Begin (No Northwestern Monday in Fall)

  more less

  TIME Tuesday, September 24, 2024

  ADD TO CALENDAR

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

  CALENDAR University Academic Calendar

• Sep

  25

  CS Seminar

  Department of Computer Science (CS)

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

  EVENT DETAILS

  TBA

  more less

  TIME Wednesday, September 25, 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)

• Sep

  30

  Last day to add a class or change a section for Fall (Last day for tuition adjustment related to enrollment changes (to or from full-time). No reductions are made to bills for dropped or swapped classes after this date)

  University Academic Calendar

  All Day

  EVENT DETAILS

  Last day to add a class or change a section for Fall (Last day for tuition adjustment related to enrollment changes (to or from full-time). No reductions are made to bills for dropped or swapped classes after this date)

  more less

  TIME Monday, September 30, 2024

  ADD TO CALENDAR

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

  CALENDAR University Academic Calendar

• Sep

  30

  CS Seminar

  Department of Computer Science (CS)

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

  EVENT DETAILS

  TBA

  more less

  TIME Monday, September 30, 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)

• Oct

  2

  CS Seminar

  Department of Computer Science (CS)

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

  EVENT DETAILS

  TBA

  more less

  TIME Wednesday, October 2, 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)

• Oct

  7

  CS Seminar

  Department of Computer Science (CS)

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

  EVENT DETAILS

  TBA

  more less

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