News & Events
Department Events & Announcements

Events

  • Jul
    29

    Phawin Prongpaophan Prospectus July 29: Structural and Algorithmic Properties of Combinatorial Optimization Problems on Random Graphs

    Department of Computer Science (CS)

    10:00 AM 3501, Mudd Hall ( formerly Seeley G. Mudd Library)

    EVENT DETAILS

    Graphs are mathematical objects that model many complex systems and have become a central element of algorithm design. However, traditional worst-case analysis often yields pessimistic complexity bounds that ignore the typical structure of real-world instances. This thesis studies average-case analysis for various algorithms solving combinatorial optimization problems on graphs. It also investigates the combinatorial structures underlying these problems. These insights lead to a better understanding of the limitations of existing algorithms and provide guidance for developing new algorithmic techniques.

    Specifically, my research includes the following problems:

    Community Detection on Stochastic Block Models (SBM). Consider a graph in which each vertex belongs to a hidden community, and the probability of an edge between any pair of vertices depends solely on the community assignments of the two vertices. The goal is to recover the community partition from the observed graph. We show that a semidefinite programming (SDP) relaxation designed for exact recovery in symmetric SBMs cannot be directly extended to asymmetric SBMs, and we provide geometric intuition explaining this limitation.

    Sum of Leaf Weights in the Minimum Spanning Tree. Let G be a complete graph in which each edge weight is sampled independently from the Uniform(0,1) distribution, and let T be the minimum spanning tree of G. Define a leaf edge as an edge of T that is incident to a leaf of T. We establish tight bounds on the expected sum of the weights of all leaf edges, together with the concentration around it. These results substantially improve the state-of-the-art bounds for several variants of the minimum spanning tree problem, including the probabilistic minimum spanning tree (PMST).

    Probabilistic Minimum Spanning Tree (PMST). Given a graph in which each vertex is present independently with probability p, the goal is to find an a priori spanning tree T that minimizes the expected total length after deleting edges while preserving connectivity among the vertices that remain present. We establish new upper and lower bounds on the expected length of the optimal a priori spanning tree.

    more less

    TIME Wednesday, July 29, 2026 at 10:00 AM - 12:00 PM

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

    ADD TO CALENDAR

    CONTACT Jensen Smith    jensen.smith@northwestern.edu EMAIL

    CALENDAR Department of Computer Science (CS)

  • Jul
    24

    Mehmet Kerem Aydin Final Defense July 24: Nonideal Image Formation As Information: Physics-Guided Spectral and Thermal Computational Imaging

    Department of Computer Science (CS)

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

    EVENT DETAILS

    TIME Friday, July 24, 2026 at 9:30 AM - 11:30 AM

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

    ADD TO CALENDAR

    CONTACT Jensen Smith    jensen.smith@northwestern.edu EMAIL

    CALENDAR Department of Computer Science (CS)

  • Jul
    24

    Patrick O'Reilly Final Defense July 24: Token Fixes: From Reactive to Proactive Algorithmic Interventions for Responsible Audio AI

    Department of Computer Science (CS)

    12:00 PM 1-122 (HCI+D Center), Frances Searle Building

    EVENT DETAILS

    TIME Friday, July 24, 2026 at 12:00 PM - 2:00 PM

    LOCATION 1-122 (HCI+D Center), Frances Searle Building    map it

    ADD TO CALENDAR

    CONTACT Jensen Smith    jensen.smith@northwestern.edu EMAIL

    CALENDAR Department of Computer Science (CS)

  • Jul
    29

    Tommy McMichen Final Defense July 29: Preserving Data Collections in the Compiler

    Department of Computer Science (CS)

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

    EVENT DETAILS

    TIME Wednesday, July 29, 2026 at 2:00 PM - 4:00 PM

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

    ADD TO CALENDAR

    CONTACT Jensen Smith    jensen.smith@northwestern.edu EMAIL

    CALENDAR Department of Computer Science (CS)

  • Aug
    20

    Nathaniel Hejduk Qualifying Exam Presentation August 20: Navigating Mixed-Typed Migration with Profilers

    Department of Computer Science (CS)

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

    EVENT DETAILS

    TIME Thursday, August 20, 2026 at 1:00 PM - 4:00 PM

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

    ADD TO CALENDAR

    CONTACT Jensen Smith    jensen.smith@northwestern.edu EMAIL

    CALENDAR Department of Computer Science (CS)

  • Sep
    24

    Bagel Thursday + Discussion

    Department of Computer Science (CS)

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

    EVENT DETAILS

    TIME Thursday, September 24, 2026 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)

  • Sep
    28

    CS Seminar

    Department of Computer Science (CS)

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

    EVENT DETAILS

    TIME Monday, September 28, 2026 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
    5

    CS Seminar: Formal Relational Equivalence for SQL, GenAI, and Beyond (Brian Suchy)

    Department of Computer Science (CS)

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

    EVENT DETAILS

    TIME Monday, October 5, 2026 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
    29

    Bagel Thursday + Discussion

    Department of Computer Science (CS)

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

    EVENT DETAILS

    TIME Thursday, October 29, 2026 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)

  • Nov
    19

    Bagel Thursday + Discussion

    Department of Computer Science (CS)

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

    EVENT DETAILS

    TIME Thursday, November 19, 2026 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)