10 citations · 51 across the 27 of their papers we have counts for
38 papers
Accelerating Scientific Research with Gemini: Case Studies and Common Techniques
David P. Woodruff, Vincent Cohen-Addad, Lalit Jain +33
Recent advances in large language models (LLMs) have opened new avenues for accelerating scientific research. While models are increasingly capable of assisting with routine tasks,…
Dueling over Multiple Pieces of Dessert
Simina Brânzei, Reed Phillips
We study the dynamics of repeated fair division between two players, Alice and Bob, where Alice partitions a cake into two subsets and Bob chooses his preferred one over rounds…
The Query Complexity of Local Search in Rounds on General Graphs
Simina Brânzei, Ioannis Panageas, Dimitris Paparas
We analyze the query complexity of finding a local minimum in rounds on general graphs. More precisely, given a graph and oracle access to an unknown function $f :…
Computing Envy-Free up to Any Good (EFX) Allocations via Local Search
Simina Brânzei
We present a simple local search algorithm for computing EFX (envy-free up to any good) allocations of indivisible goods among agents with additive valuations. EFX is a com…
Tarski Lower Bounds from Multi-Dimensional Herringbones
Simina Brânzei, Reed Phillips, Nicholas Recker
Tarski's theorem states that every monotone function from a complete lattice to itself has a fixed point. We analyze the query complexity of finding such a fixed point on the -d…
A note on quantum lower bounds for local search via congestion and expansion
Simina Brânzei, Nicholas J. Recker
We consider the quantum query complexity of local search as a function of graph geometry. Given a graph with vertices and black box access to a function $f : V \to…
The Randomized Query Complexity of Finding a Tarski Fixed Point on the Boolean Hypercube
Simina Brânzei, Reed Phillips, Nicholas Recker
The Knaster-Tarski theorem, also known as Tarski's theorem, guarantees that every monotone function defined on a complete lattice has a fixed point. We analyze the query complexity…
Spectral Lower Bounds for Local Search
Simina Brânzei, Nicholas J. Recker
Local search is a powerful heuristic in optimization and computer science, the complexity of which has been studied in the white box and black box models. In the black box model, w…
Dueling Over Dessert, Mastering the Art of Repeated Cake Cutting
Simina Brânzei, MohammadTaghi Hajiaghayi, Reed Phillips +2
We consider the setting of repeated fair division between two players, denoted Alice and Bob, with private valuations over a cake. In each round, a new cake arrives, which is ident…
Phase Transitions of Diversity in Stochastic Block Model Dynamics
Simina Brânzei, Nithish Kumar, Gireeja Ranade
This paper proposes a stochastic block model with dynamics where the population grows using preferential attachment. Nodes with higher weighted degree are more likely to recruit ne…
Learning and Collusion in Multi-unit Auctions
Simina Brânzei, Mahsa Derakhshan, Negin Golrezaei +1
We consider repeated multi-unit auctions with uniform pricing, which are widely used in practice for allocating goods such as carbon licenses. In each round, identical units of…
The Sharp Power Law of Local Search on Expanders
Simina Brânzei, Davin Choo, Nicholas Recker
Local search is a powerful heuristic in optimization and computer science, the complexity of which was studied in the white box and black box models. In the black box model, we are…
The Query Complexity of Local Search and Brouwer in Rounds
Simina Brânzei, Jiawei Li
We consider the query complexity of finding a local minimum of a function defined on a graph. This abstract problem is fundamental to many optimization tasks, such as finding a loc…
Consensus with Bounded Space and Minimal Communication
Simina Branzei, Yuval Peres
Population protocols are a fundamental model in distributed computing, where many nodes with bounded memory and computational power have random pairwise interactions over time. Thi…
Searching, Sorting, and Cake Cutting in Rounds
Simina Brânzei, Dimitris Paparas, Nicholas Recker
We study searching and sorting in rounds motivated by a fair division question: given a cake cutting problem with players, compute a fair allocation in at most rounds of in…
Tit-for-Tat Dynamics and Market Volatility
Simina Brânzei
We consider tit-for-tat dynamics in production markets, where there is a set of players connected via a weighted graph. Each player can produce an eponymous good using its…
Multiplayer Bandit Learning, from Competition to Cooperation
Simina Brânzei, Yuval Peres
The stochastic multi-armed bandit model captures the tradeoff between exploration and exploitation. We study the effects of competition and cooperation on this tradeoff. Suppose th…
Proportional Dynamics in Exchange Economies
Simina Brânzei, Nikhil R. Devanur, Yuval Rabani
We study the Proportional Response dynamic in exchange economies, where each player starts with some amount of money and a good. Every day, the players bring one unit of their good…
Algorithms for Competitive Division of Chores
Simina Brânzei, Fedor Sandomirskiy
We study the problem of allocating divisible bads (chores) among multiple agents with additive utilities when monetary transfers are not allowed. The competitive rule is known for…
Sharing Information with Competitors
Simina Brânzei, Claudio Orlandi, Guang Yang
We study the mechanism design problem in the setting where agents are rewarded using information only. This problem is motivated by the increasing interest in secure multiparty com…
Online Learning with an Almost Perfect Expert
Simina Brânzei, Yuval Peres
We study the multiclass online learning problem where a forecaster makes a sequence of predictions using the advice of experts. Our main contribution is to analyze the regime w…
Universal Growth in Production Economies
Simina Brânzei, Ruta Mehta, Noam Nisan
We consider a simple variant of the von Neumann model of an expanding economy, in which multiple producers make goods according to their production function. The players trade thei…
How to Charge Lightning: The Economics of Bitcoin Transaction Channels
Simina Brânzei, Erel Segal-Halevi, Aviv Zohar
Off-chain transaction channels represent one of the leading techniques to scale the transaction throughput in cryptocurrencies. However, the economic effect of transaction channels…
Walrasian Dynamics in Multi-unit Markets
Simina Brânzei, Aris Filos-Ratsikas
In a multi-unit market, a seller brings multiple units of a good and tries to sell them to a set of buyers that have monetary endowments. While a Walrasian equilibrium does not alw…