10 citations · 51 across the 27 of their papers we have counts for
4 papers · 1 filter
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…