Adversary lower bound for the k-sum problem

Aleksandrs Belovs (U Latvia)�

Robert Špalek (Google)

Knapsack packing problem

​

For a fixed k,�is there a k-tuple among n numbers�that sums up to a prescribed number?

​

Measure number of queries, not time.

Orthogonal arrays

A subset T ⊂ [q]^k of size q^k-1 is called an orthogonal array iff for every index i and�every vector (x₁... x_i-1, x_i+1... x_k), there is�exactly one x_i such that x∈ T.

​

• k-tuples with a fixed sum form an orthogonal array
• general problem:�Is there S⊂[n] with |S|=k such that x_S∈ T_S ?

Known results

• Classically, ϴ(n) queries are sufficient and necessary for bounded-error algorithms.�
• Using quantum walks, one can solve this problem with only O(n^k/(k+1)) queries [Ambainis '03].
• By polynomial method, element distinctness needs Ω(n^2/3) queries [Aaronson & Shi '01].�Their lower bound applies to k-sum for k≥2.

Our result and technique

• We prove a matching Ω(n^k/(k+1)) bound�(when alphabet size q≥n^k).

​

We use general adversary method Adv^± [Høyer, Lee & Š '06]:

• Adv^± generalizes nonnegative-weight adversary method Adv⁺�[Ambainis'03, Barnum, Saks & Szegedy '03],
• Adv^± characterizes quantum query complexity [Reichardt '09].

Implication of our result

The O(n^k/(k+1)) quantum algorithm searches for a 1-certificate. It works for any function with 1-certificate complexity k.

Some functions can be computed faster.�k-distinctness needs just o(n^3/4) queries [B '12], because its 1-certificates have structure.

​

• For k-sum, searching for a 1-certificate�as a whole is the best one can do,�and the general algorithm is optimal.

Novelty of our technique

Adv^± is tight, but its bounds are expressed by solutions to exponentially large SDP (in #bits).

​

Adv^± bounds stronger than Adv⁺ were only known for functions on constant #bits, and they were found by numerical optimization.

​

• We show how to design the optimal adversary matrix for a large function.

Merits of our technique

The polynomial method-based Ω(n^2/3) bound doesn't compose and wasn't generalized since 2001.

• Adversary bounds compose by definition.
• After Belovs designed an Adv^± matrix reproving the Ω(n^2/3) bound for k=2, we easily generalized it for all k.
• Using our technique, an almost optimal�Ω^~(n^9/7) bound for triangle-sum was soon obtained by [B & Rosmanis '12].

Technical part

Adversary bound

• Γ is a real adversary matrix
• rows indexed by 1-inputs of f
• columns indexed by 0-inputs of f
• ‖.‖ is spectral norm, ○ is entrywise product
• Δ_i [x,y]=0 when x_i=y_i , and =1 otherwise
• Adv⁺ imposes entrywise constraint Γ≥0�

Q₂(f) = ϴ(Adv^±(f)) [HLŠ '06, Reichardt '09]

Adv⁺ versus Adv^±

• Γ⁺ is a probability distribution.�By putting all weight on hard-to-distinguish input pairs, one usually gets a decent bound, e.g. Ω(√n) for element distinctness.�
• Γ^± is a linear combination of orthogonal projectors. Projectors usually cannot be expressed using nonnegative coefficients.�It's harder to bound the spectral norms.

Adversary matrix for k-sum

1. Embed Γ into a larger matrix Γ^~
• allow indexing multiple rows by the same 1-input
• columns are indexed by all inputs, not just 0-inputs��
2. Split Γ^~ into slices G_S of size
• G_S has rows containing a k-sum at the positions S

Adversary matrix for k-sum

• Write���projector F_m corresponds to m loaded inputs�
• Bound ‖Γ^~‖ from both sides using simple combinatorics, thanks to its simple structure

Adversary matrix for k-sum

5. Instead of mapping exactly Γ^~ → Γ^~ ○ Δ₁ , change arbitrarily entries with x₁=y₁ , and apply ‖Γ^~₁ ○ Δ₁‖ ≤ 2‖Γ^~₁‖ thanks to γ₂(Δ₁)≤2.�
6. This Γ^~₁ has as simple structure as Γ^~,�hence we can bound ‖Γ^~₁‖ similarly.

Adversary matrix for k-sum

• Optimize {α_m} to maximize Adv^±.�max α₀ s.t.

Adversary matrix for k-sum

• Show that the bound for Γ^~ applies to Γ when the alphabet is large enough.�
• delete "illegal" columns corresponding to 1-inputs, and obtain a valid adversary matrix
• upper bounds on ‖Γ ○ Δ_i‖ still hold
• lower bound on ‖Γ‖ get constant-times worse�when alphabet size q≥n^k

Concluding remarks

Summary

1. First nontrivial lower bound using Adv^±
2. Easily applicable and generalizable
3. New tricks for analyzing adversary matrices
4. Search for a 1-certificate as a whole is optimal for some functions

Open problems

• Relax the alphabet size requirement
• Lower bound for k-collision
• Lower bound for k-distinctness
• Lower bound for graph collision