New upper and lower bounds for randomized and quantum Local Search

Shengyu Zhang

REVIEW

New upper and lower bounds for randomized and quantum Local Search

Shengyu Zhang

Quantum Physics · Submitted 6 Mar 2006 · 23 references

Pith's verdict: Tight bounds for local search on the hypercube and grids are likely right but the block-threading proof in §4.2.2 needs a referee's hard look before the paper's claims are trusted.

T0 · AI review

How this review was made: An AI referee (deepseek-v4-flash) read the paper on August 28, 2026 and answered a fixed list of questions about it. T0 is the starting level every paper gets. The levels describe how deeply Pith has checked the paper, never the authors.

T0 AI review An AI read the paper and answered a fixed list of questions.
T1 Audit Automatic checks that the references and files the paper relies on exist and match.
T2 Compute The paper's code or calculations re-run with the same results.
T3 Formal statement The claims written out in a formal math language a computer can read.
T4 Proof Those claims proved, and the proof checked by computer.

How Pith checks papers →

· 2 major objections · 4 minor · Ask about this paper · The compiled record · Read the full review →

Challenge this review Comment (0) Read on arXiv ↗

Cite ▾

arXiv IDquant-ph/0603034 (version 1)

Pith IDQXVVRWSI, Pith's permanent record of this paper and its review

CitationShengyu Zhang. "New upper and lower bounds for randomized and quantum Local Search." arXiv:quant-ph/0603034 (2006). https://pith.science/paper/QXVVRWSI

Cite this reviewBibTeX for Pith's review of this paper

Claim paper

Why Pith says this

Highlight any text to comment on it.

Editor's note

read the letter

The paper deserves a serious referee. It closes the open query-complexity questions for randomized and quantum local search on the Boolean hypercube and on constant-dimensional grids, up to tight bounds for most dimensions. The core idea is new and reusable: decompose the graph as a product, run a random walk in one factor, and use a self-avoiding clock path in the other to turn passing probabilities into hitting probabilities. That genuinely improves on Aaronson's and Santha–Szegedy's lower bounds, and the upper bound for slowly expanding graphs is a nice complement, giving the improved quantum bound on the 2D grid. The author also honestly lists the remaining gaps and credits corrections to a previous version. Credit where it's due: this is a real contribution.

The soft spots, in proportion. The most delicate part is Section 4.2.2, the block-threading argument for grids. The proof asserts that the block-threaded walk can be thought of as a product walk on [α]^{d-1} × [L], and that hitting probabilities are unchanged except for reflections within blocks. This is plausible, and the accompanying figure helps. But the reduction from Local Search to the PathP problem, as formalized in Theorem 9's Claim 1, is not shown to work for vertices that lie on block-changing segments. The adversary weight scheme in Theorem 9 only assigns weights to vertices of the form x^w_{j+r} ⊗ z^c_{j+s,j} with (r,s) ∈ {(0,0),(1,0),(1,1)}; the intermediate vertices on a block-changing segment are not of that form. The text says the probability 'has nothing to do with the block-changing' and tells the reader to 'think of the graph as' the product, but it never spells out how membership queries on those intermediate vertices are handled with only a constant-factor overhead, nor how the weight scheme extends to them. This is load-bearing: the tight bounds for d ≥ 4 and d ≥ 6 rest on it. I don't think it's a fundamental flaw—the idea is sound and likely repairable—but a referee will need to demand a precise statement.

Minor point: the proof of Proposition 11 (the line walk bound) is sketched with a reflecting-rule argument that is somewhat compressed, though the high-level strategy is believable.

For whom: query-complexity researchers, especially those working on local search, total search problems, or adversary methods. If the block-threading gap gets written up carefully, this is a strong paper. As it stands, it is still worth serious peer review rather than desk rejection; the referee should focus on Section 4.2.2 and ask for a rigorous treatment of the block-changing segments.

Referee report

Major objections (2)

[§4.2.2, Eqs. (100)–(101)] The application of Theorem 9 to the block-threaded grid assumes that the graph can be treated as the product graph [α]^{d-1}×[L]. This is the load-bearing step for the tight bounds RLS([n]^d)=Ω(n^{d/2}) for d≥4 and QLS([n]^d)=Ω(n^{d/3}) for d≥6. In the construction described in the text, the block-changing segments are paths of positive length whose internal vertices are not of the form x^w_{j+r}⊗z^c_{j+s,j} used in Theorem 9's Claim 1 and in the weight scheme (Eqs. (27)–(28)). Contracting these segments to single clock edges produces a graph that is a minor or subdivision of the claimed product graph, not a subgraph of [n']^d in the sense required by Theorem 9. The assertion that the probability 'has nothing to do with the block-changing' addresses hitting probabilities, but it does not prove that every query on a vertex lying on a block-changing segment can be simulated by at most two membership queries, nor does it assign adversary weights to such variables. Without an explicit embedding of [α]^{d-1}×[L] as a subgraph, or a formal extension of Theorem 9 to the threaded path family, Eqs. (100)–(101) do not follow from the stated theorem.
[§4.2.3, Eqs. (104)–(105)] The claimed lower bound QLS([n]^2)=Ω(n^{2/5}) is presented as following 'the same track' as Theorem 9, but the random walk introduced there changes blocks after every step, so its paths are not instances of the product-walk/clock path family P used in Theorem 9. The proof does not verify that the function f_X in Eq. (104) has a unique local minimum at the end point, does not show how queries to vertices on block-changing segments are simulated with O(1) membership queries, and does not derive the analogue of the bound in Eqs. (34)–(35) for the claimed Θ(1) and Θ(1/n^{4/5}) passing probabilities. The d=2 entry of Theorem 3 is therefore not established by the written proof.

Minor objections (4)

[§4.2.3, first paragraph] The opening sentence says the new walk improves QLS([n]^2) from Ω(n^{1/3}) to Ω(n^{4/5}); the value derived in Eq. (105) is Ω(n^{2/5}), and n^{4/5} would contradict the upper bound O(√n) of Theorem 5. Please correct the exponent.
[§4.2.1, quantum bounds for d=5,4,3] The text concludes Ω(n^{5/2}), Ω(n^2), Ω(n^{3/2}) from the formula Ω(n^{d/2−1}); the formula gives Ω(n^{3/2}), Ω(n), Ω(n^{1/2}) for d=5,4,3. Please correct these intermediate values.
[§4.2.2, displayed formulas (100)–(101)] The superscripts appear to be missing in the displayed formulas: for example, 'n1+(1−r)(d−1)' should read n^{1+(1-r)(d-1)}. Please fix the typesetting.
[Proposition 11] The assertion that max_{i,j} p^{(t)}_{ij} decreases as t increases is used to obtain the O(1/n) bound for t>n^2; this monotonicity is not proved and should be justified or replaced by a direct tail argument.

How Pith checks papers → · Full audit of this paper →

The paper

The paper claims

Tight query bounds for Local Search on hypercubes and grids.

The reading

Local Search—finding a vertex whose value is no larger than any neighbor's—is a fundamental subroutine in combinatorial optimization, and its query complexity measures how expensive it is to carry out with only black-box access to the function. The paper pins down this cost for two central graph families. It proves that on the Boolean hypercube the randomized query complexity RLS is $\Theta($2^{{n/2}}$ $n^{{1/2}}$)$ and the quantum query complexity QLS is $\Theta($2^{{n/3}}$ $n^{{1/6}}$)$, and on constant-dimensional grids $\mathrm{RLS}([n]^d) = \Theta($n^{{d/2}}$)$ for $d \geq 4$ while $\mathrm{QLS}([n]^d) = \Theta($n^{{d/3}}$)$ for $d \geq 6$. These are tight bounds, replacing earlier results that had polynomial gaps. The upper-bound half also produces new algorithms for slowly expanding graphs; for the 2D grid it gives a quantum algorithm using $O(\sqrt{n} (\log\log n)^{1.5})$ queries, improving the previous $O($n^{{2/3}}$)$ bound and showing low-dimensional grids are genuinely easier.

What carries the argument

The key machinery is the product-graph clock: decompose a graph $G$ as $G_w \times G_c$, run a regular random walk in $G_w$, and pair each step with two forward steps along a fixed self-avoiding path in $G_c$. The $G_c$ part acts as a one-way clock, so each vertex of the combined path is associated with a unique time; this converts passing probabilities into hitting probabilities and makes the adversary weight analysis tractable. The lower-bound proof combines this construction with the quantum adversary method and the relational adversary method, choosing weights so that the clock's one-wayness does the work. The upper-bound algorithm instead uses slow expansion: it samples in exponentially shrinking balls around a best-so-far vertex, tests whether the boundary of the current ball has high function values, and then follows a decreasing path inside the final small ball, using quantum minimum-finding for the boundary tests.

Extended reading notes

Core claim

The paper's central claim is that Local Search on a graph containing a product graph $G_w \times G_c$ has query complexity controlled by a random walk in one factor timed by an irreversible 'clock' walk along a self-avoiding path in the other factor. This clock makes the troublesome 'passing probability' of earlier analyses become a much smaller 'hitting probability': a path can pass through a vertex only at one precise clock reading. Applying the resulting lower-bound theorem gives $\mathrm{RLS}(\{0,1\}^n) = \Theta($2^{{n/2}}$ $n^{{1/2}}$)$ and $\mathrm{QLS}(\{0,1\}^n) = \Theta($2^{{n/3}}$ $n^{{1/6}}$)$; on grids, $\mathrm{RLS}([n]^d) = \Theta($n^{{d/2}}$)$ for $d \geq 4$ and $\mathrm{QLS}([n]^d) = \Theta($n^{{d/3}}$)$ for $d \geq 6$, with improved lower bounds for the remaining small dimensions. The companion upper-bound theorem says that when the number of vertices within distance $k$ of any vertex grows like $O(k^\$\alpha$)$, Local Search can be solved with $O($d^{{\alpha-1}}$ \log\log d)$ randomized queries or $O($d^{{(\alpha-1)/2}}$ (\log\log d)^{1.5})$ quantum queries, where $d$ is the graph diameter; on $[n]^2$ this gives $\mathrm{QLS}([n]^2) = O(\sqrt{n} (\log\log n)^{1.5})$.

Load-bearing premise

The grid lower bounds assume that cutting a grid into blocks and threading them with disjoint block-changing segments produces exactly the same hitting probabilities as a product walk on $[\$\alpha$]^{d-1} \times [L]$, apart from reflections inside each block; if those segments introduce correlations or shorten the effective clock, the low-dimensional bounds do not follow.

Editorial extensions

If this is right

On the Boolean hypercube, the exact exponent is now known: no randomized algorithm can beat $\Theta(2^{n/2} n^{1/2})$ queries and no quantum algorithm can beat $\Theta(2^{n/3} n^{1/6})$, while matching algorithms exist.
On grids of dimension at least 4 (classically) or at least 6 (quantum), the generic random-sampling plus steepest-descent method is optimal up to constant factors.
On the 2D grid, quantum Local Search is now known to require at most $O(\sqrt{n} (\log\log n)^{1.5})$ queries, improving the previous $O(n^{2/3})$ bound; the $\Omega(n^{2/5})$ lower bound shows a genuine gap remains.
On graphs with polynomial volume growth, $c(k)=O(k^\alpha)$, Local Search admits diameter-based poly-logarithmic algorithms; on the line this yields $O(\log n \log\log n)$ randomized queries.
The paper's Section 6 lists the remaining gaps: for example, $\mathrm{QLS}([n]^2)$ is between $\Omega(n^{2/5})$ and $O(\sqrt{n})$, and $\mathrm{RLS}([n]^3)$ is between $\Omega(n^{3/2}/\sqrt{\log n})$ and $O(n^{3/2})$.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The same clock technique should transfer to other product-containing graphs—Hamming graphs, tori, or grids with unequal side lengths—by choosing a different random walk in the first factor; the paper's Theorem 9 is general, and only the applications are specialized.
The 2D gap between $\Omega(n^{2/5})$ and $O(\sqrt{n} (\log\log n)^{1.5})$ suggests the true quantum complexity may lie at an intermediate power of $n$; a more tailored random walk or a sharper upper bound using two-scale growth might close it.
The recursive shrinking-ball algorithm is phrased for any graph with slow volume growth, so it may also give improved bounds on trees, graphs of bounded genus, or other structured families, even though the paper only works out the grid and line cases.
If the lower bounds transfer to arbitrary graphs containing a product subgraph, then Local Search complexity would be governed by the best random walk in the largest product factor; this suggests a general principle connecting expansion, hitting times, and Local Search hardness.

Original abstract

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 combinatorial optimization, complexity theory and many other areas in theoretical computer science. In this paper, we study the problem in the randomized and quantum query models and give new lower and upper bound techniques in both models. The lower bound technique works for any graph that contains a product graph as a subgraph. Applying it to the Boolean hypercube {0,1}^n and the constant dimensional grids [n]^d, two particular product graphs that recently drew much attention, we get the following tight results: RLS({0,1}^n) = \Theta(2^{n/2}n^{1/2}), QLS({0,1}^n) = \Theta(2^{n/3}n^{1/6}), RLS([n]^d) = \Theta(n^{d/2}) for d \geq 4, QLS([n]^d) = \Theta(n^{d/3}) for d \geq 6. Here RLS(G) and QLS(G) are the randomized and quantum query complexities of Local Search on G, respectively. These improve the previous results by Aaronson [STOC'04], Ambainis (unpublished) and Santha and Szegedy [STOC'04]. Our new algorithms work well when the underlying graph expands slowly. As an application to [n]^2, a new quantum algorithm using O(\sqrt{n}(\log\log n)^{1.5}) queries is given. This improves the previous best known upper bound of O(n^{2/3}) (Aaronson, [STOC'04]), and implies that Local Search on grids exhibits different properties in low dimensions.

The compiled record

The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.

Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-09-23: 1 request, 7,187 input tokens.

What the abstract itself states, as probabilities: claims first 0.06 · states limitation 0.66 · human participants 0.01 · controlled comparison 0.08 · randomized assignment 0.03 · states quantitative result 0.99 · compares with prior results 0.98 · mentions code or data availability 0.02.

The abstract, sentence by sentence

arXiv listing abstract v1. Results and the main claim are underlined; show every role.

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 combinatorial optimization, complexity theory and many other areas in theoretical computer science. In this paper, we study the problem in the randomized and quantum query models and give new lower and upper bound techniques in both models. The lower bound technique works for any graph that contains a product graph as a subgraph. Applying it to the Boolean hypercube {0,1}^n and the constant dimensional grids [n]^d, two particular product graphs that recently drew much attention, we get the following tight results: RLS({0,1}^n) = \Theta(2^{n/2}n^{1/2}), QLS({0,1}^n) = \Theta(2^{n/3}n^{1/6}), RLS([n]^d) = \Theta(n^{d/2}) for d \geq 4, QLS([n]^d) = \Theta(n^{d/3}) for d \geq 6. Here RLS(G) and QLS(G) are the randomized and quantum query complexities of Local Search on G, respectively. These improve the previous results by Aaronson [STOC'04], Ambainis (unpublished) and Santha and Szegedy [STOC'04]. Our new algorithms work well when the underlying graph expands slowly. As an application to [n]^2, a new quantum algorithm using O(\sqrt{n}(\log\log n)^{1.5}) queries is given. This improves the previous best known upper bound of O(n^{2/3}) (Aaronson, [STOC'04]), and implies that Local Search on grids exhibits different properties in low dimensions.

background contribution method result interpretation main claim

What the classifier reports for each sentence. The number is the probability it gave the label.
#	sentence	role	the authors' own work	states the main conclusion	strength
s0	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 combinatorial optimization, complexity theory and many other areas in theoretical computer science.	background 1.00	0.04	0.02	asserted 1.00
s1	In this paper, we study the problem in the randomized and quantum query models and give new lower and upper bound techniques in both models.	contribution 1.00	0.94	0.13	asserted 1.00
s2	The lower bound technique works for any graph that contains a product graph as a subgraph.	method 0.85	0.84	0.06	asserted 1.00
s3	Applying it to the Boolean hypercube {0,1}^n and the constant dimensional grids [n]^d, two particular product graphs that recently drew much attention, we get the following tight results: RLS({0,1}^n) = \Theta(2^{n/2}n^{1/2}), QLS({0,1}^n) = \Theta(2^{n/3}n^{1/6}), RLS([n]^d) = \Theta(n^{d/2}) for d \geq 4, QLS([n]^d) = \Theta(n^{d/3}) for d \geq 6.	result 1.00	0.94	0.78	asserted 1.00
s4	Here RLS(G) and QLS(G) are the randomized and quantum query complexities of Local Search on G, respectively.	background 0.71	0.26	0.04	asserted 0.96
s5	These improve the previous results by Aaronson [STOC'04], Ambainis (unpublished) and Santha and Szegedy [STOC'04].	contribution 0.50	0.46	0.09	asserted 1.00
s6	Our new algorithms work well when the underlying graph expands slowly.	limitation 0.49	0.82	0.05	asserted 0.98
s7	As an application to [n]^2, a new quantum algorithm using O(\sqrt{n}(\log\log n)^{1.5}) queries is given.	result 0.67	0.95	0.06	asserted 1.00
s8	This improves the previous best known upper bound of O(n^{2/3}) (Aaronson, [STOC'04]), and implies that Local Search on grids exhibits different properties in low dimensions.	interpretation 0.66	0.86	0.11	asserted 1.00

What kind of paper the classifier reports this is: theoretical result 0.90 · evidence from proof or derivation 1.00.

What was examined, and what was not

sources read

arXiv listing abstract v1

not examined

full text
figures and tables
references and citing sentences
relations to other papers

levels run

P abstract

not run

S sections
T body sentences
C citations
R cross-paper relations

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. Every number in the measurements table is the authors', checked by code. Record as JSON

Figures

**Figure 1.** The proof of the reflecting rule. Now let us consider the barrier setting. Note that a path may try to cross the two barriers in some pattern, for example, try to cross the left barrier (i.e. point 1) for a times and then try to cross the right barrier (i.e. point n) for b times. Imagine that we now remove the two barriers, then the path will touch (from right) but not cross the point 1 − a and will touch (from left) but not cross the point n + b − a. To use the reflecting rule, we just need to further note the following simple fact: {paths touching but not crossing the point 1 − a}…

**Figure 2.** Illustration for changing a block in the 2-dimensi

**Figure 3.** y x t=1 t=2 t=3 t=4 t=2n −1 1/5 t=2n +1 1/5 t=2n 1/5 1/5 t=2n +2 each length: a random number from {1,2,...,n } 4/5

Figures reproduced from arXiv:quant-ph/0603034 by the authors.

References

Works cited (23)

[1]

K. Aardal, S. Hoesel, J.K. Lenstra, L. Stougie. A Decade of Comb inatorial Optimization. CWI Tracts 122, pp. 5-14, 1997

View on Pith 1997
[2]

S. Aaronson. Lower Bounds for Local Search by Quantum Argu ments. Proceedings of the thirty- sixth Annual ACM Symposium on Theory of Computing, pp. 465-474, 2004

View on Pith 2004
[3]

E. Aarts and J. Lenstra, John Wiley & Sons, Inc. New York, NY, U SA, 1997

View on Pith 1997
[4]

D. Aldous. Minimization Algorithms and Random Walk on the d-Cube. Annals of Probability, 11(2), pp. 403-413, 1983. 24

View on Pith 1983
[5]

I. Althofer and K. Koschnich. On the Deterministic Complexity of S earching Local Maxima. Discrete Applied Mathematics 43, pp. 111-113, 1993

View on Pith 1993
[6]

A. Ambainis. Polynomial Degree vs. Quantum Query Complexity. Pr oceedings of the 44th An- nual IEEE Symposium on Foundations of Computer Science, pp. 230 -239, 2003

View on Pith 2003
[7]

A. Ambainis. Quantum Lower Bounds by Quantum Arguments, Jou rnal of Computer and Sys- tem Sciences, 64, pp. 750-767, 2002

View on Pith 2002
[8]

H. Barnum, M. Saks, M. Szegedy. Quantum Query Complexity and Semideﬁnite Programming. Proceedings of the 18th Annual IEEE Conference on Computation al Complexity, pp. 179-193, 2003

View on Pith 2003
[9]

R. Beals, H. Buhrman, R. Cleve, M.Mosca, R. de Wolf. Quantum Low er Bounds by Polynomials. Journal of ACM, 48, pp. 778-797, 2001

View on Pith 2001
[10]

H. Buhrman and R. de Wolf. Complexity Measures and Decision Tre e Complexity: a survey. Theoretical Computer Science, Volume 288, Issue 1, pp. 21-43, 2 002

View on Pith
[11]

C. Durr and P. Hoyer. A Quantum Algorithm for Finding the Minimum , quant-ph/9607014, 1996

View on Pith Pith review arXiv 1996
[12]

L. Grover. A Fast Quantum Mechanical Algorithm for Database Search, Proceedings of the 28th Annual ACM Symposium on the Theory of Computing, pp. 212-2 19, 1996

View on Pith 1996
[13]

P. Hoyer and R. Spalek. Lower Bounds on Quantum Query Comple xity, Bulletin of the Euro- pean Association for Theoretical Computer Science 87, pp. 78-10 3, 2005

View on Pith 2005
[14]

D. Johnson, C. Papadimitriou, and M. Yannakakis. How Easy is Lo cal Search, Journal of Computer and System Sciences 37, pp. 429448, 1988

View on Pith 1988
[15]

S. Laplante and F. Magniez. Lower Bounds for Randomized and Q uantum Query Complexity Using Kolmogorov Arguments. Proceedings of the 19th Annual IEE E Conference on Computa- tional Complexity, pp. 294-304, 2004

View on Pith 2004
[16]

D. Llewellyn and C. Tovey. Dividing and Conquering the Square. Dis crete Applied Mathematics 43, pp. 131-153, 1993

View on Pith 1993
[17]

D. Llewellyn, C. Tovey, M. Trick. Local Optimization on Graphs. D iscrete Aplied Mathematics 23, pp. 157-178, 1989. Erratum: 46, pp. 93-94, 1993

View on Pith 1989
[18]

N. Megiddo and C. Papadimitriou. On Total Functions, Existence Theorems, and Computa- tional Complexity. Theoretical Computer Science 81, pp. 317324, 1991

View on Pith 1991
[19]

J. Orlin, A. Punnen, A. Schulz. Approximate Local Search in Com binatorial Optimization. SIAM Journal on Computing, 33(5), pp. 12011214, 2004

View on Pith 2004
[20]

M. Santha and M. Szegedy. Quantum and Classical Query Comple xities of Local Search Are Polynomially Related. Proceedings of the thirty-sixth annual ACM sy mposium on Theory of computing, pp. 494-501, 2004

View on Pith 2004
[21]

R. Spalek and M. Szegedy. All Quantum Adversary Methods Are Equivalent. Proceedings of 32nd International Colloquium on Automata, Languages and Progr amming, pp. 1299-1311, LNCS 3580, Lisboa, Portugal, 2005

View on Pith 2005
[22]

Y. Verhoeven, Enhanced Algorithms for Local Search. Infor mation Processing Letters 97, pp. 171176, 2006

View on Pith 2006
[23]

S. Zhang. On the Power of Ambainis Lower Bounds, Theoretical Computer Science, 339(2-3), pp. 241-256, 2005. 25

View on Pith 2005

How the literature uses it

Papers whose main result relates to this one's

How each label was checked · JSON

Found among the papers closest to this one by title and main claim. Pith's classifier compared each pair's main results and a second model family confirmed the relation; checked against two further families, shown conflicts agreed 118 times in 120 and shown same results 218 times in 239. The quoted sentence is the other paper's main claim.

States the same result 1 paper

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})$.

(Almost) tight bounds for randomized and quantum Local Search on hypercubes and grids · 0.98

Discussion

Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.

[1] [1]

K. Aardal, S. Hoesel, J.K. Lenstra, L. Stougie. A Decade of Comb inatorial Optimization. CWI Tracts 122, pp. 5-14, 1997

View on Pith 1997

[2] [2]

S. Aaronson. Lower Bounds for Local Search by Quantum Argu ments. Proceedings of the thirty- sixth Annual ACM Symposium on Theory of Computing, pp. 465-474, 2004

View on Pith 2004

[3] [3]

E. Aarts and J. Lenstra, John Wiley & Sons, Inc. New York, NY, U SA, 1997

View on Pith 1997

[4] [4]

D. Aldous. Minimization Algorithms and Random Walk on the d-Cube. Annals of Probability, 11(2), pp. 403-413, 1983. 24

View on Pith 1983

[5] [5]

I. Althofer and K. Koschnich. On the Deterministic Complexity of S earching Local Maxima. Discrete Applied Mathematics 43, pp. 111-113, 1993

View on Pith 1993

[6] [6]

A. Ambainis. Polynomial Degree vs. Quantum Query Complexity. Pr oceedings of the 44th An- nual IEEE Symposium on Foundations of Computer Science, pp. 230 -239, 2003

View on Pith 2003

[7] [7]

A. Ambainis. Quantum Lower Bounds by Quantum Arguments, Jou rnal of Computer and Sys- tem Sciences, 64, pp. 750-767, 2002

View on Pith 2002

[8] [8]

H. Barnum, M. Saks, M. Szegedy. Quantum Query Complexity and Semideﬁnite Programming. Proceedings of the 18th Annual IEEE Conference on Computation al Complexity, pp. 179-193, 2003

View on Pith 2003

[9] [9]

R. Beals, H. Buhrman, R. Cleve, M.Mosca, R. de Wolf. Quantum Low er Bounds by Polynomials. Journal of ACM, 48, pp. 778-797, 2001

View on Pith 2001

[10] [10]

H. Buhrman and R. de Wolf. Complexity Measures and Decision Tre e Complexity: a survey. Theoretical Computer Science, Volume 288, Issue 1, pp. 21-43, 2 002

View on Pith

[11] [11]

C. Durr and P. Hoyer. A Quantum Algorithm for Finding the Minimum , quant-ph/9607014, 1996

View on Pith Pith review arXiv 1996

[12] [12]

L. Grover. A Fast Quantum Mechanical Algorithm for Database Search, Proceedings of the 28th Annual ACM Symposium on the Theory of Computing, pp. 212-2 19, 1996

View on Pith 1996

[13] [13]

P. Hoyer and R. Spalek. Lower Bounds on Quantum Query Comple xity, Bulletin of the Euro- pean Association for Theoretical Computer Science 87, pp. 78-10 3, 2005

View on Pith 2005

[14] [14]

D. Johnson, C. Papadimitriou, and M. Yannakakis. How Easy is Lo cal Search, Journal of Computer and System Sciences 37, pp. 429448, 1988

View on Pith 1988

[15] [15]

S. Laplante and F. Magniez. Lower Bounds for Randomized and Q uantum Query Complexity Using Kolmogorov Arguments. Proceedings of the 19th Annual IEE E Conference on Computa- tional Complexity, pp. 294-304, 2004

View on Pith 2004

[16] [16]

D. Llewellyn and C. Tovey. Dividing and Conquering the Square. Dis crete Applied Mathematics 43, pp. 131-153, 1993

View on Pith 1993

[17] [17]

D. Llewellyn, C. Tovey, M. Trick. Local Optimization on Graphs. D iscrete Aplied Mathematics 23, pp. 157-178, 1989. Erratum: 46, pp. 93-94, 1993

View on Pith 1989

[18] [18]

N. Megiddo and C. Papadimitriou. On Total Functions, Existence Theorems, and Computa- tional Complexity. Theoretical Computer Science 81, pp. 317324, 1991

View on Pith 1991

[19] [19]

J. Orlin, A. Punnen, A. Schulz. Approximate Local Search in Com binatorial Optimization. SIAM Journal on Computing, 33(5), pp. 12011214, 2004

View on Pith 2004

[20] [20]

M. Santha and M. Szegedy. Quantum and Classical Query Comple xities of Local Search Are Polynomially Related. Proceedings of the thirty-sixth annual ACM sy mposium on Theory of computing, pp. 494-501, 2004

View on Pith 2004

[21] [21]

R. Spalek and M. Szegedy. All Quantum Adversary Methods Are Equivalent. Proceedings of 32nd International Colloquium on Automata, Languages and Progr amming, pp. 1299-1311, LNCS 3580, Lisboa, Portugal, 2005

View on Pith 2005

[22] [22]

Y. Verhoeven, Enhanced Algorithms for Local Search. Infor mation Processing Letters 97, pp. 171176, 2006

View on Pith 2006

[23] [23]

S. Zhang. On the Power of Ambainis Lower Bounds, Theoretical Computer Science, 339(2-3), pp. 241-256, 2005. 25

View on Pith 2005