1 citations · 1 across the 5 of their papers we have counts for
Showing 2024Show all
3 papers · 1 filter
cs.CC2024
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…
cs.CC2024
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…
cs.CC2024
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…