The Brown Theory Seminar is a weekly seminar organized by the theory group in the Department of Computer Science at Brown University. The seminar invites external speakers to present their research on a wide range of topics in theoretical computer science.
Time and Location: All talks are held on Wednesdays noon-1pm in CIT 241 unless otherwise noted.
Stay Updated:
Subscribe to the theory mailing list to receive announcements about upcoming talks.
Here is a Google Calendar link with the seminar schedule.
Recordings of past talks are available on our YouTube channel.
For Speakers:
If you are interested in giving a talk, please contact Yu Cheng (organizer for Spring 2025).
Relevant information for invited speakers.
Date | Speaker | Title | Abstract | Recording |
---|---|---|---|---|
Feb 12 (Wed) | Stefano Leonardi | The Role of Transparency in Repeated First-Price Auctions with Unknown Valuations | We study the problem of regret minimization for a single bidder in a sequence of first-price auctions where the bidder discovers the item’s value only if the auction is won. Our main contribution is a complete characterization, up to logarithmic factors, of the minimax regret in terms of the auction’s transparency, which controls the amount of information on competing bids disclosed by the auctioneer at the end of each auction. Our results hold under different assumptions (stochastic, adversarial, and their smoothed variants) on the environment generating the bidder’s valuations and competing bids. These minimax rates reveal how the interplay between transparency and the nature of the environment affects how fast one can learn to bid optimally in first-price auctions. |
|
Feb 14 (Fri) | Euiwoong Lee | Theory and Applications of Complete Min-CSPs: A Case Study in Correlation Clustering | We will discuss recent algorithmic results on fundamental problems in data science and clustering, including Correlation Clustering, Low-Rank Approximation, and Metric Distance Violation. A unifying theme will be their connections to Minimum Constraint Satisfaction Problems (CSPs) in complete instances. Starting from the rich theory of dense Max CSPs with several algorithmic tools (e.g., convex hierarchy, random sampling, regularity lemma), we show how this theory can be augmented to handle minimization objectives in applied domains. These efforts also inspired a systematic study on Min-CSPs in complete instances. |
|
Feb 19 (Wed) | Haifeng Xu | Rethinking Online Content Ecosystems in the Era of Generative AIs | Online contents not only are important to our life but also underlie the recent success of generative AIs (GenAIs) technology. In turn, GenAI is also revolutionizing the way contents are now created, which is much less costly, possibly even more creative, though depending on availability of human-created contents to sustainably refine GenAI’s model training. Such human-AI mutual dependence is fundamentally transforming existing content ecosystems. If not addressed properly, it may distort human creators’ incentives and even drive humans out of the ecosystem. In this talk, I will present our recent works on understanding such human-vs-GenAI competition through the lens of computational economics, and how to design creator reward mechanisms to incentivize desirable distribution of human content creation. Our designed mechanism not only has nice theoretical properties, but also achieved success during live tests with ~10 millions of users on a leading industrial content platform. |
|
Feb 26 (Wed) | Kishen Gowda | TBA | TBA |
|
Mar 5 (Wed) | Yibin Yang | TBA | TBA |
|
Mar 12 (Wed) | Gabriele Farina | TBA | TBA |
|
Mar 19 (Wed) | Jiapeng Zhang | TBA | TBA |
|
Mar 26 (Wed) | No seminar (Spring Break) | |||
Apr 2 (Wed) | No seminar | |||
Apr 9 (Wed) | Chris Kapulkin | TBA | TBA |
|
Apr 16 (Wed) | Yiping Ma | TBA | TBA |
|
Apr 23 (Wed) | Rico Zenklusen | TBA | TBA |