Simina Brânzei


I'm an Assistant Professor of Computer Science at Purdue University. Before coming here I spent two years at the Hebrew University of Jerusalem hosted by Noam Nisan and Michael Schapira, as well as a semester at the Simons Institute for the Theory of Computing at the University of California Berkeley.

I completed my Ph.D. advised by Peter Bro Miltersen at Aarhus University in Denmark. My 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 the Institute for Interdisciplinary Information Sciences at Tsinghua University. Before grad school I was an intern at Legg Mason Canada, IBM, and Google.

I'm interested in theoretical computer science and artificial intelligence, in particular algorithmic game theory and theoretical aspects of learning.

Activities

We are running an online theory seminar. Feel free to contact me if you would like to give a talk. There is also a reading group led by students, which meets every Thursday at 4:00 PM EST.

In Spring 2019 I co-organized with Elena Grigorescu the 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.

CS 381: Introduction to the Analysis of Algorithms (Undergraduate), Fall 2021.

Papers


Note: The papers are in alphabetical author order.

Algorithms for Competitive Division of Chores, Simina Brânzei and Fedor Sandomirskiy. Minor revision in Mathematics of Operations Research.

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)

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).

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)

Nash Social Welfare Approximation for Strategic Agents, Simina Brânzei, Vasilis Gkatzelis, and Ruta Mehta. In Operations Research, 2022.
(improves EC '17 version; arXiv here)

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, 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 (short version in AAAI '12).

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).

Universal Growth in Production Economies, Simina Brânzei, Ruta Mehta, and Noam Nisan. In Proceedings of the 32nd Conference on Neural Information Processing Systems (NeurIPS 2018).

Nash Social Welfare Approximation for Strategic Agents, Simina Brânzei, Vasilis Gkatzelis, and Ruta Mehta. In Proceedings of the 18th ACM conference on Economics and Computation (ACM EC 2017). Here is a video of the talk.

Walrasian Pricing in Multi-unit Auctions, Simina Brânzei, Aris Filos-Ratsikas, Peter Bro Miltersen, and Yulong Zeng. In Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017).

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]
(abstract in 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.
(invited, extended abstract in 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).

The Authorship Dilemma: Alphabetical or Contribution?, Margareta Ackerman and Simina Brânzei. In Proceedings of the Thirteenth International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2014) (extended abstract). [AGT blog]

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]

Weighted Clustering, Margareta Ackerman, Shai Ben-David, Simina Brânzei, and David Loker. In Proceedings of the Twenty-Sixth Conference on Artificial Intelligence (AAAI 2012).

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).

Preprints

Searching, Sorting, and Cake Cutting in Rounds, Simina Brânzei, Dimitris Paparas, and Nicholas Recker. Preprint.

Consensus with Bounded Space and Minimal Communication, Simina Brânzei and Yuval Peres. Preprint.

Tit-for-Tat Dynamics and Market Volatility, Simina Brânzei. Preprint.

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.

Education

Aarhus University, Denmark
Ph.D. in Computer Science, Sep 2011 - Feb 2015

University of Waterloo, Canada
Master of Mathematics in Computer Science, May 2010 - Aug 2011

University of Waterloo, Canada
Bachelor of Computer Science, 2004 - 2009

Academic Positions

Hebrew University of Jerusalem, Israel
Postdoctoral Fellow, Jan 2016 - Dec 2017. Host: Noam Nisan and Michael Schapira.

University of California Berkeley, USA
Research Fellow, Simons Institute for the Theory of Computing, Aug - Dec 2015. Mentor: Vince Conitzer

Aarhus University, Denmark
Researcher, Mar - Jul 2015. Host: Peter Bro Miltersen

Tsinghua University, China
Visiting Scholar, Aug 2013 - Oct 2013, Institute for Interdisciplinary Information Sciences

Carnegie Mellon University, USA
Visiting Scholar, Sep 2012 - Jun 2013. Host: Ariel D. Procaccia

Internships

University of Waterloo, Canada
Undergraduate Research Assistant, Jan - Apr 2010, May - Aug 2008. Mentor: Kate Larson.

Google, New York, USA
Software Engineering Intern, May - Aug 2009

IBM, Toronto, Canada
Software Engineering Intern, Sep - Dec 2006, May - Aug 2007, Jan - Apr 2008
Reserch and development in compiler optimization.

IBM, Toronto, Canada
Software Engineering Intern, Jan - Apr 2006, Markham, Canada

Legg Mason Canada, Waterloo, Canada
Quantitative Analyst Intern, May - Aug 2005, Waterloo, Canada

Misc

I grew up in Bacau, Romania and finished high school at Colegiul National Ferdinand I. I used to write math olympiads while there.

If you ever visit Romania, I highly recommend the region of Maramures, the cities of Brasov, Iasi, and Sibiu (which was designated a European Capital of Culture for the year 2007), and the painted monasteries of Bucovina, which are part of the UNESCO World Heritage. And of the course the beautiful 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).

An interview in the Romanian newspaper Adevarul can be found here.

Contact

E-mail: simina@purdue.edu

Address: 1205 Lawson Building, 305 N University St, West Lafayette, IN 47907, USA

Images from my work.

A few drawings (more details).