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