Simina Brânzei
I'm an Assistant Professor of Computer Science at Purdue University. My research interests are in theory of computation, artificial intelligence, algorithmic game theory, learning, algorithms, computational complexity and their interface with dynamical systems and optimization. Example of topics I worked on include fair division, markets and auctions, games, learning dynamics, and local search processes. My research is supported by an NSF CAREER Award.
Before joining Purdue I was a postdoc at the Hebrew University of Jerusalem hosted by Noam Nisan and Michael Schapira, and a research fellow at the Simons Institute for the Theory of Computing. I completed my Ph.D. at Aarhus University in Denmark, where I was advised by Peter Bro Miltersen. My graduate research was supported in part by an IBM Ph.D. Fellowship and a Google Anita Borg Memorial Scholarship. During that time I also visited Carnegie Mellon University and Tsinghua University. My undergraduate and master's degrees are from the University of Waterloo, where I was advised by Kate Larson.
Activities
We are running a theory seminar (hybrid). Feel free to contact me if you would like to give a talk. There is also a reading group led by students.
I'm co-organizing the ACM EC 2024 Mentoring Workshop. I also co-organized the EC 2023 Mentoring Workshop, a Mini-Symposium on Games and Learning at CanaDAM 2023, a Workshop on Fair Division at FOCS 2022, and the 2019 Midwest Theory Day.
Teaching
CS 580: Algorithm Design, Analysis, and Implementation (Graduate), Fall 2019, Fall 2022.
CS 584: Theory of Computation and Computational Complexity (Graduate), Spring 2018, Spring 2019, Fall 2020.
CS 592: Algorithmic Game Theory (Graduate), Fall 2018, Spring 2020, Spring 2022.
CS 483: Introduction to the Theory of Computation (Undergraduate), Spring 2021, Spring 2024.
CS 381: Introduction to the Analysis of Algorithms (Undergraduate), Fall 2021, Spring 2023, Spring 2024.
Mentees
Current: Reed C. Phillips (Ph.D.)
Past: Nicholas J. Recker (Ph.D., Applied research mathematician at NSA) Nithish Kumar (Master's, Ph.D. student at Purdue)
Papers
Note: Authors are listed in alphabetical order.
Randomized Lower Bounds for Tarski Fixed Points in High Dimensions, Simina Brânzei, Reed Phillips, and Nicholas J. Recker. Preprint.
Spectral Lower Bounds for Local Search, Simina Brânzei and Nicholas J. Recker. Preprint.
Searching, Sorting, and Cake Cutting in Rounds, Simina Brânzei, Dimitris Paparas, and Nicholas J. Recker. Preprint.
Tit-for-Tat Strategies Drive Growth and Inequality in Production Economies, Simina Brânzei, Ruta Mehta, and Noam Nisan. In Proceedings of the Royal Society A: Mathematical, Physical, and Engineering Sciences, 2024.
One page abstract in NeurIPS 2018.
Dueling over Dessert, Mastering the Art of Repeated Cake Cutting, Simina Brânzei, MohammadTaghi Hajiaghayi, Reed Phillips, Suho Shin, and Kun Wang. In Proceedings of the 38th Conference on Neural Information Processing Systems (NeurIPS 2024). Here are the slides from WALE 2024 talk.
The Sharp Power Law of Local Search on Expanders, Simina Brânzei, Davin Choo, and Nicholas J. Recker. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2024).
Tit-for-Tat Dynamics and Market Volatility, Simina Brânzei. In Nonlinearity, vol. 37, issue 3, pp. 035006, IOP Publishing & London Mathematical Society, 2024.
Algorithms for Competitive Division of Chores, Simina Brânzei and Fedor Sandomirskiy. In Mathematics of Operations Research, vol. 49, issue 1, pp. 398-429, 2024.
Learning and Collusion in Multi-unit Auctions, Simina Brânzei, Mahsa Derakhshan, Negin Golrezaei, and Yanjun Han. In Proceedings of the 37th Conference on Neural Information Processing Systems (NeurIPS 2023).
Phase Transitions of Diversity in Stochastic Block Model Dynamics, Simina Brânzei, Nithish Kumar, and Gireeja Ranade. In Proceedings of the 59th Allerton Conference on Communication, Control, and Computing (Allerton 2023).
Walrasian Pricing in Multi-unit Auctions, Simina Brânzei, Aris Filos-Ratsikas, Peter Bro Miltersen, and Yulong Zeng. In Artificial Intelligence, 2023.
Preliminary version in Proceedings of the International Symposium on Mathematical Foundations of Computer Science (MFCS 2017).
The Query Complexity of Cake Cutting, Simina Brânzei and Noam Nisan. In Proceedings of the 36th Conference on Neural Information Processing Systems (NeurIPS 2022).
The Query Complexity of Local Search and Brouwer in Rounds, Simina Brânzei and Jiawei Li. In Proceedings of the 35th Annual Conference on Learning Theory (COLT 2022)
How to Charge Lightning: The Economics of Bitcoin Transaction Channels, Simina Brânzei, Erel Segal-Halevi, and Aviv Zohar. In Proceedings of the 58th Allerton Conference on Communication, Control, and Computing (Allerton 2022).
Nash Social Welfare Approximation for Strategic Agents, Simina Brânzei, Vasilis Gkatzelis, and Ruta Mehta. In Operations Research, 2022.
Preliminary version in Proceedings of the 18th ACM conference on Economics and Computation (ACM EC 2017). Here is a video of the talk.
Exchange Markets: Proportional Response Dynamics and Beyond, Simina Brânzei. In ACM SIGecom Exchanges 2021.
P4-free Partition and Cover Numbers, Alexander Block, Simina Brânzei, Hemanta K. Maji, Himanshi Mehta, Tamalika Mukherjee, and Hai H. Nguyen. In Proceedings of the Conference on Information-Theoretic Cryptography (ITC 2021)
Proportional Dynamics in Exchange Economies, Simina Brânzei, Nikhil Devanur, and Yuval Rabani. In Proceedings of the 21st ACM Conference on Economics and Computation (ACM EC 2021)
Multiplayer Bandit Learning, from Competition to Cooperation, Simina Brânzei and Yuval Peres. In Proceedings of the 34th Annual Conference on Learning Theory (COLT 2021)
Weighted Clustering: Towards Solving the User's Dilemma, Margareta Ackerman, Shai Ben-David, Simina Brânzei, and David Loker. In Pattern Recognition, 2021.
Preliminary version in Proceedings of the Twenty-Sixth Conference on Artificial Intelligence (AAAI 2012).
Communication Complexity of Cake Cutting, Simina Brânzei and Noam Nisan. In Proceedings of the 20th ACM Conference on Economics and Computation (ACM EC 2019).
Sharing Information with Competitors, Simina Brânzei, Claudio Orlandi, and Guang Yang. In Proceedings of the 12th International Symposium on Algorithmic Game Theory (SAGT 2019).
Online Learning with an Almost Perfect Expert, Simina Brânzei and Yuval Peres. In Proceedings of the National Academy of Sciences (PNAS 2019), Vol. 116, No. 13, pages 5949-5954. (arXiv)
Walrasian Dynamics in Multi-unit Markets, Simina Brânzei and Aris Filos-Ratsikas. In Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI 2019).
The Authorship Dilemma: Alphabetical or Contribution?, Margareta Ackerman and Simina Brânzei. In Journal of Autonomous Agents and Multiagent Systems, 2017. [see discussion on AGT blog]
Preliminary version as extended abstract in Proceedings of the Thirteenth International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2014).
Computation of Stackelberg Equilibria of Finite Sequential Games, Branislav Bosansky, Simina Brânzei, Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, and Troels Bjerre Sørensen. In ACM Transactions on Economics and Computation, 2017.
Preliminary version in Proceedings of the Eleventh Conference on Web and Internet Economics (WINE 2015).
An Algorithmic Framework for Strategic Fair Division, Simina Brânzei, Ioannis Caragiannis, David Kurokawa, and Ariel D. Procaccia. In Proceedings of the 30th AAAI Conference on Artificial Intelligence (AAAI 2016). Revise and resubmit in Games and Economic Behavior.
To Give or not to Give: Fair Division for Single Minded Valuations, Simina Brânzei, Yuezhou Lv, and Ruta Mehta. In Proceedings of the 25th International Joint Conference on Artificial Intelligence (IJCAI 2016) [presentation].
Verifiably Truthful Mechanisms, Simina Brânzei and Ariel D. Procaccia. In Proceedings of the Sixth Conference on Innovations in Theoretical Computer Science (ITCS 2015) [presentation].
A Dictatorship Theorem for Cake Cutting. Simina Brânzei and Peter Bro Miltersen. In Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence (IJCAI 2015) [presentation + poster].
The Adjusted Winner Procedure: Characterizations and Equilibria, Haris Aziz, Simina Brânzei, Aris Filos-Ratsikas, and Søren Frederiksen. In Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence (IJCAI 2015) [presentation + poster].
Computation of Stackelberg Equilibria of Finite Sequential Games, Branislav Bosansky, Simina Brânzei, Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, and Troels Bjerre Sørensen. In Proceedings of the Eleventh Conference on Web and Internet Economics (WINE 2015).
Characterization and Computation of Equilibria for Indivisible Goods, Simina Brânzei, Hadi Hosseini, and Peter Bro Miltersen. In Proceedings of the Eighth International Symposium on Algorithmic Game Theory (SAGT 2015).
A Note on Envy-Free Cake Cutting with Polynomial Valuations, Simina Brânzei. In Information Processing Letters, Vol. 115, No. 2, p. 93-95, 2015.
The Fisher Market Game: Equilibrium and Welfare, Simina Brânzei, Yiling Chen, Xiaotie Deng, Aris Filos-Ratsikas, Søren Frederiksen, and Jie Zhang. In Proceedings of the Twenty-Eighth Conference on Artificial Intelligence (AAAI 2014).
Simultaneous Cake Cutting, Eric Balkanski, Simina Brânzei, David Kurokawa, and Ariel D. Procaccia. In Proceedings of the Twenty-Eighth Conference on Artificial Intelligence (AAAI 2014).
Implementation and Computation of a Value for Generalized Characteristic Function Games, Tomasz Michalak, Piotr Szczepanski, Talal Rahwan, Agatha Chrobak, Simina Brânzei, Michael Wooldridge, Nicholas Jennings. In ACM Transactions on Economics and Computation, Vol. 2, No. 4, p 1-35, 2014.
Externalities in Cake Cutting, Simina Brânzei, Ariel D. Procaccia, and Jie Zhang. In Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence (IJCAI 2013) [presentation + poster].
How Bad is Selfish Voting?, Simina Brânzei, Ioannis Caragiannis, Jamie Morgenstern, and Ariel D. Procaccia. In Proceedings of the Twenty-Seventh Conference on Artificial Intelligence (AAAI 2013).
Equilibrium Analysis in Cake Cutting, Simina Brânzei and Peter Bro Miltersen. In Proceedings of the Twelfth International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2013) [presentation + poster]
Matchings with Externalities and Attitudes, Simina Brânzei, Tomasz Michalak, Talal Rahwan, Kate Larson, and Nicholas R. Jennings. In Proceedings of the Twelfth International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2013) [presentation + poster]
Social Distance Games, Simina Brânzei and Kate Larson. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence (IJCAI 2011). An extended abstract also appeared in the Proceedings of the Tenth International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2011).
Coalitional Affinity Games and the Stability Gap, Simina Brânzei and Kate Larson. In Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence (IJCAI 2009). An extended abstract also appeared in the Proceedings of the Eighth International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2009).
Technical Reports
Computational Fair Division, Simina Brânzei. Ph.D. thesis, Aarhus University, 2015.
Equilibria of Chinese Auctions, Simina Brânzei, Clara Forero, Kate Larson, and Peter Bro Miltersen, 2012.
Two Coalitional Models for Network Formation and Matching Games, Simina Brânzei. Master's thesis, University of Waterloo, 2011.
Local Anonymity: A Metric for Improving User Privacy in Tor, Simina Brânzei, Tariq Elahi, and Ian Goldberg. CACR Tech Report 2011-17, University of Waterloo, 2011.Misc
I grew up in Bacau, Romania and finished high school at Colegiul National Ferdinand I.If you ever visit Romania, I highly recommend the region of Maramures, the cities Brasov/Constanța/Iasi/Sibiu (the latter was designated a European Capital of Culture for the year 2007), the painted monasteries of Bucovina (which are part of the UNESCO World Heritage), the Carpathian Mountains, and the Black Sea.
I'm also a big fan of Romanian classical music (see The Lark and The Romanian Rhapsody by Enescu) and folk music (You can find some of Maria Tanase's songs here).
Contact
|
