BEGIN:VCALENDAR
PRODID:-//planitpurple.northwestern.edu//iCalendar Event//EN
VERSION:2.0
CALSCALE:GREGORIAN
METHOD:PUBLISH
CLASS:PUBLIC
BEGIN:VTIMEZONE
TZID:America/Chicago
TZURL:http://tzurl.org/zoneinfo-outlook/America/Chicago
X-LIC-LOCATION:America/Chicago
BEGIN:DAYLIGHT
TZOFFSETFROM:-0600
TZOFFSETTO:-0500
TZNAME:CDT
DTSTART:19700308T020000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=2SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:-0500
TZOFFSETTO:-0600
TZNAME:CST
DTSTART:19701101T020000
RRULE:FREQ=YEARLY;BYMONTH=11;BYDAY=1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
SEQUENCE:0
DTSTART;TZID=America/Chicago:20260729T100000
DTEND;TZID=America/Chicago:20260729T120000
DTSTAMP:20260730T004708Z
SUMMARY:Phawin Prongpaophan Prospectus July 29: Structural and Algorithmic Properties of Combinatorial Optimization Problems on Random Graphs
UID:643565@northwestern.edu
TZID:America/Chicago
DESCRIPTION: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. 
LOCATION:Mudd Hall ( formerly Seeley G. Mudd Library)\, 3501\, 2233 Tech Drive\, Evanston\, IL 60208
TRANSP:OPAQUE
URL:https://planitpurple.northwestern.edu/event/643565
CREATED:20260722T050000Z
STATUS:CONFIRMED
LAST-MODIFIED:20260722T050000Z
PRIORITY:0
BEGIN:VALARM
TRIGGER:-PT10M
ACTION:DISPLAY
DESCRIPTION:Reminder
END:VALARM
END:VEVENT
END:VCALENDAR