Search Mailing List Archives
[theory-seminar] Theory Lunch 09/30: Jay Mardia
junyaoz at stanford.edu
Mon Sep 27 10:14:47 PDT 2021
This week's theory lunch will take place Thursday at noon in the Engineering Quad. We'll start with some socializing, followed by a whiteboard talk at 12:30pm.
Jay will tell us about: Space complexity and the planted clique problem
Abstract: The planted clique problem is well-studied in the context of observing, explaining, and predicting interesting computational phenomena associated with statistical problems. These phenomena were discovered and studied using the definition "computational efficiency = polynomial time algorithm".
We ask whether the known stat-comp phenomena are robust to changing our notion of computational efficiency. That is, are they fundamental to the statistical problem or do they change based on our computational lens?
We study this question using space efficiency as our notion of efficient computation. Our work gives evidence that the known phenomena are indeed robust to this change in computational lens.
This week we ordered food from Bytes Cafe (Thanks, Megan!).
The menu is as follows (both are vegetarian):
Greek salad (with pepper, cucumber, tomato, Kalamata olives and feta cheese),
Caesar salad (Oven roasted garlic croutons and parmesan cheese).
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the theory-seminar