Ενημερώνουμε ότι αύριο Πέμπτη 11/7, στο διάστημα 16:00 - 18:00, υπάρχουν δύο πολύ ενδιαφέρουσες ομιλίες στον Αρχιμήδη, από τον Δημήτρη Χρήστου (UT Austin), στο διάστημα 16:00 - 17:00, και τον Ηλία Ζαδίκ (Yale), στο διάστημα 17:00 - 18:00. Οι ομιλίες αφορούν σε πρόσφατα ερευνητικά αποτελέσματα σε αντικείμενα που σχετίζονται στενά με το αντικείμενο του μαθήματος και σας ενθαρρύνουμε να τις παρακολουθήσετε.
Ακολουθούν οι τίτλοι, σύντομες περιλήψεις και σύντομα βιογραφικά των ομιλητών, καθώς και MS-Teams link για να παρακολουθήσετε τις ομιλίες από απόσταση, όσοι δεν μπορείτε να έρθετε στον Αρχιμήδη.
=====================================================================
Title (Dimitris Christou, 16:00 - 17:00 ): A Multi-Dimensional Online Contention Resolution Scheme for Revenue Maximization
Abstract: We study multi-buyer multi-item sequential item pricing mechanisms for online revenue maximization with the goal of approximating a natural fractional relaxation – the ex ante optimal revenue. We assume that buyers’ values are subadditive but make no assumptions on the value distributions. While the optimal revenue, and therefore also the ex ante benchmark, is inapproximable by any simple mechanism in this context, previous work has shown that a weaker benchmark that optimizes over so-called “buy-many” mechanisms can be approximated. Approximations are known, in particular, for settings with either a single buyer or many unit-demand buyers. We extend these results to the much broader setting of many subadditive buyers. We show that the ex ante buy-many revenue can be approximated via sequential item pricings to within an $O(log^2 m)$ factor, where m is the number of items. We also show that a logarithmic dependence on m is necessary. Our approximation is achieved through the construction of a new multi-dimensional Online Contention Resolution Scheme (OCRS), that provides an online rounding of the optimal ex ante solution.
Bio: Dimitris Christou is a 3rd year Computer Science PhD student at UT Austin. He is fortunate to be advised by Prof. Shuchi Chawla. Prior to joining UT Austin, he received a Diploma in Electrical and Computer Engineering from the National Technical University of Athens, supervised by Prof. Dimitris Fotakis. During that time, he completed two research internships offered by the LIP6 Research Institute at Sorbonne University, France. His research interests lie in the intersection of Online Algorithms, Economics and Data-Driven algorithmic design. His previous work resolves open questions for online decision making, server problems, multistage optimisation and learning-augmented algorithms. His current work focuses on problems in the intersection of Online Decision Making and Economics, such as the Pandora’s Box problem and Online Revenue Maximization.
Meeting ID: 395 520 739 305
Passcode: tCsPus
=====================================================================
Title (Ilias Zadik, 17:00 - 18:00): Counting Stars is Constant-Degree Optimal For Detecting Any Planted Subgraph
Abstract: Over the last decade, multiple papers have studied the power of low-degree polynomials in detecting subgraphs in random graphs. Formally, all these papers study special cases of the following general hypothesis testing problem: let H=H_n be an arbitrary undirected graph on n vertices. Can a D-degree polynomial detect between a "null" Erdős-Rényi random graph G(n,p) and a "planted'" random graph which is the union of G(n,p) together with a random copy of H=H_n? The special cases include the case when H is a clique (the planted clique model), when H is a matching (the planted matching problem), and more.
We prove a new unifying positive result that for all H=H_n, as long as D=O(1), the optimal such D-degree polynomial is always given simply by the count stars in the input graph. This allows us to prove multiple old and new results in the literature of low-degree polynomials for this task.
Bio: Ilias Zadik ( https://iliaszadik.github.io ) is Assistant Professor of Statistics and Data Science at Yale University. His research mainly focuses on the mathematical theory of statistics and its many connections with other fields such as computer science, probability theory, and statistical physics. His primary area of interest is the study of "computational-statistical trade-offs", where the goal is to understand whether computational bottlenecks are unavoidable in modern statistical models or a limitation of currently used techniques. Prior to Yale, he held postdoctoral positions at MIT and NYU. He received his PhD from MIT in 2019.
Meeting ID: 345 129 612 964
Passcode: TBnfah
=====================================================================