SIGMOD Santiago, Chile, 2024

PODS 2024: Tutorials

Tutorial 1: Approximation Algorithms on Matrices - with some Database Applications!

Speaker: David Woodruff (CMU)


In this talk I will cover dimensionality reduction techniques, or sketching, for solving optimization problems on large matrices. Classical polynomial time solutions to optimization problems involving matrices are often no longer efficient given the large size of matrices arising on big data sets. Instead, one seeks linear or sometimes even sublinear time solutions to such optimization problems. These often involve randomized algorithms and come at the price of a small approximation error. The idea behind sketching techniques is to reduce a large instance of a problem to a much smaller instance of the same problem in such a way that solving the small instance gives an approximate solution to the large instance. Oftentimes the smaller problem is now so small that one can directly apply a classical polynomial time algorithm to solve it directly. Thus, the emphasis is on how to perform the reduction itself to the small problem very quickly, i.e., in linear or sub-linear time. I will survey a wide range of technique for this, which often have the form of multiplying the input matrix by a random matrix, or have the form of sampling or recursive sampling.

Tutorial 2: Closing the Gap Between Theory and Practice in Query Optimization

Speaker: Thomas Neummann (TU Munich)



Follow our progress: FacebookTwitter