sricharana67@univie.ac.at

Date: 10 April 2025
Time: 11:45 – 12:45
Location: Forschungslabor 3 (sofa room)

Speaker: Maximilian Vötsch
Title: The Power of Random Projections

Abstract:
Many of the optimization problems computer scientists care about can be formulated as a matrix problem of the form min_X ||AX – B|| or min_X,Y ||XY – B|| where constraints on the matrices X and Y encode our problem’s specific structure. In some cases these problems are easy and have analytic solutions, in other cases they are hard and solving the problem exactly involves trying all possible matrices.
What if there was a tool that lets us speed up solving such problems by reducing the search space for “free”? I will talk about one of the most fundamental Lemmas (according to some) in CS, the Johnson-Lindenstrauss lemma and more recent developments in JL-flavored methods, as well as as many applications as we can fit into 60 minutes to give you an idea when to use these techniques in your own research.

Date: 27 March 2025
Time: 11:45 – 12:45
Location: Forschungslabor 3 (sofa room)

Speaker: A. R. Sricharan
Title: How to Concentrate If You Must

Abstract:
Random events happen a lot, generating random variables in their wake. Chernoff’s bound says that you can be pretty sure that these random variables are very close to where you expect them to be. One does not think twice about when to apply a Chernoff bound, but one (yours truly) does indeed think multiple times and gets oneself mightily confused on how to go about doing this.

I tried a month ago to get to the bottom of this, and I have a few observations and many many more questions to share. It is related to, among other things,

1. Legendre transforms in physics,
2. Not wanting to solve integrals,
3. Strong convexity, and who would have guessed,
4. The Multiplicative Weights Update method.