Zobrazeno 1 - 10
of 67
pro vyhledávání: '"Brânzei, Simina"'
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 of finding such a fixed point on the $k$-dimensional grid of side len
Externí odkaz:
http://arxiv.org/abs/2409.03751
Autor:
Branzei, Simina
This thesis comprises of two separate game theoretic models that fall under the general umbrella of network formation games. The first is a coalitional model of interaction in social networks that is based on the idea of social distance, in which pla
Externí odkaz:
http://hdl.handle.net/10012/6112
Autor:
Brânzei, Simina, Recker, Nicholas J.
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, we are given a graph $G = (V,E)$ and oracle access to a function $f : V
Externí odkaz:
http://arxiv.org/abs/2403.06248
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 identical to the ones in previous rounds. Alice cuts the cake at a point of
Externí odkaz:
http://arxiv.org/abs/2402.08547
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 new nodes, and nodes always recruit nodes from their own community. This
Externí odkaz:
http://arxiv.org/abs/2307.13713
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, $K$ identical units of a good are sold to a group of buyers that have valuations with dimini
Externí odkaz:
http://arxiv.org/abs/2305.17402
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 given a graph $G = (V,E)$ and oracle access to a function $f : V \to
Externí odkaz:
http://arxiv.org/abs/2305.08269
Autor:
Brânzei, Simina, Li, Jiawei
We consider the query complexity of finding a local minimum of a function defined on a graph, where at most $k$ rounds of interaction with the oracle are allowed. Rounds model parallel settings, where each query takes resources to complete and is exe
Externí odkaz:
http://arxiv.org/abs/2101.00061
Autor:
Branzei, Simina, Peres, Yuval
Population protocols are a fundamental model in distributed computing, where many nodes with bounded memory and computational power have random pairwise interactions over time. This model has been studied in a rich body of literature aiming to unders
Externí odkaz:
http://arxiv.org/abs/2101.00025
We study searching and sorting in rounds motivated by a fair division question: given a cake cutting problem with $n$ players, compute a fair allocation in at most $k$ rounds of interaction with the players. Rounds interpolate between the simultaneou
Externí odkaz:
http://arxiv.org/abs/2012.00738