Computer Science Speaking Skills Talk

  • Remote Access - Zoom
  • Virtual Presentation
  • TIMOTHY CHU
  • Ph.D. Student
  • Computer Science Department
  • Carnegie Mellon University
Speaking Skills

Algorithms and Hardness on Geometric Graphs

For a class of dense graphs generated from geometric points in d dimensions, we show almost-input-time algorithms and fine-grained hardness results for tasks ranging from matrix-vector multiplication, spectral sparsifier construction, and Laplacian system solving.

As a consequence of our work, we show fast algorithms to perform maximum flow, sparse cut, and effective resistance computation quickly on such graphs.

Presented in Partial Fulfillment of the CSD Speaking Skills Requirement.

Zoom Participation. See announcement.

For More Information, Please Contact: 
Keywords: