Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: (Almost) tight bounds for randomized and quantum Local Search on
  hypercubes and grids   The Local Search problem, which finds a local minimum of a black-box function
on a given graph, is of both practical and theoretical importance to many areas
in computer science and natural sciences. In this paper, we show that for the
Boolean hypercube $\B^n$, the randomized query complexity of Local Search is
$\Theta(2^{n/2}n^{1/2})$ and the quantum query complexity is
$\Theta(2^{n/3}n^{1/6})$. We also show that for the constant dimensional grid
$[N^{1/d}]^d$, the randomized query complexity is $\Theta(N^{1/2})$ for $d \geq
4$ and the quantum query complexity is $\Theta(N^{1/3})$ for $d \geq 6$. New
lower bounds for lower dimensional grids are also given. These improve the
previous results by Aaronson [STOC'04], and Santha and Szegedy [STOC'04].
Finally we show for $[N^{1/2}]^2$ a new upper bound of $O(N^{1/4}(\log\log
N)^{3/2})$ on the quantum query complexity, which implies that Local Search on
grids exhibits different properties at low dimensions.

0
The categories of this paper are: hep-ph
3
The categories of this paper are: physics
20
The categories of this paper are: acc-phys
30
The categories of this paper are: q-alg
34
The categories of this paper are: chem-ph
23
The categories of this paper are: solv-int
14
The categories of this paper are: math-ph
11
The categories of this paper are: hep-lat
25
The categories of this paper are: patt-sol
10
The categories of this paper are: q-bio
4
The categories of this paper are: cond-mat
35
The categories of this paper are: mtrl-th
32
The categories of this paper are: atom-ph
22
The categories of this paper are: chao-dyn
24
The categories of this paper are: dg-ga
12
The categories of this paper are: nucl-th