March 24, 2023

Theory Seminar: Zihan Tan

The theory seminar is back in Levine 307 this Friday 3/24 at 1PM, featuring Zihan Tan from Rutgers University. Title: A Subpolynomial Approximation Algorithm for Graph Crossing Number in Low-Degree Graphs Abstract: Graph Crossing Number is a fundamental and extensively studied problem with wide ranging applications. In this problem, the goal is to draw an input graph G in the plane so as to minimize the number of crossings between the images of its edges.

March 16, 2023

Theory Seminar: Kamesh Munagala

This week, to account for visit day, theory seminar will be on Thursday March 16 at noon (instead of Friday at 1PM). It will be held in the PCPSE (Perelman Center for Political Science and Economics), in the Dean’s forum on the second floor. We are excited to have Kamesh Munagala from Duke speaking. Please find the abstract and bio below. Abstract: We study the classical Bayesian auction setting with a twist: Between the revenue maximizing seller and the buyers lies an intermediary that is better informed about the buyer values.

March 10, 2023

Theory Seminar: Huan Li

Our speaker for this week’s theory seminar is Huan Li, a PhD student here at Penn. The talk will take place in Levine 307 on Friday 3/10 at 1pm. Title: On Weighted Graph Sparsification by Linear Sketching Abstract: A seminal work of [Ahn-Guha-McGregor, PODS'12] showed that one can compute a cut sparsifier of an unweighted undirected graph by taking a near-linear number of linear measurements on the graph. Subsequent works also studied computing other graph sparsifiers using linear sketching, and obtained near-linear upper bounds for spectral sparsifiers [Kapralov-Lee-Musco-Musco-Sidford, FOCS'14] and first non-trivial upper bounds for spanners [Filtser-Kapralov-Nouri, SODA'21].