Brown (Computer Science) Theory Seminar

Brown University

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:

For Speakers:


Spring 2025 Schedule


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
 

Previous Semesters

Fall 2024

Spring 2024

Fall 2023