Pith. sign in

REVIEW 2 major objections 4 minor 25 references

Hardness Amplification of Optimization Problems

T0 review · 2 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Direct products lift weak hardness to 99% failure

desk verdict The direct product feasibility framework is a genuine contribution, but the End-of-a-Line lemma is false and the TFNP/Nash claims built on it collapse. read the letter →

arxiv 1908.10248 v1 pith:W6ECNLJA submitted 2019-08-27 cs.CC

Elazar Goldenberg , Karthik C. S. This is my paper · ORCID
classification cs.CC
keywords hardnessamplificationdirectproductaverage-caseoptimizationproblemsfine-grainedcomplexityTFNPMaxSATEndofaLine
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper claims that any optimization problem satisfying a single structural condition, direct product feasibility, can have its average-case hardness amplified. If every algorithm running in time $t$ fails to find an optimal solution on a $\frac{1}{\alpha(n)}$ fraction of instances from a samplable distribution, then a new samplable distribution exists on which every algorithm running in roughly $t/\mathrm{poly}(\alpha(n))$ time fails on at least 99 percent of instances. The condition asks for an efficient aggregator that stitches $k$ instances into one large instance and an efficient decoder that recovers an optimal solution for every coordinate from any optimal solution of the aggregate. If the theorem is right, weak average-case hardness becomes a transferable phenomenon across NP-hard problems, problems in P, and total search problems, rather than a phenomenon requiring bespoke algebraic reductions.

What carries the argument

The load-bearing object is direct product feasibility (Definition 3.3): an efficient pair $(\mathrm{Gen}, \mathrm{Dec})$ where $\mathrm{Gen}$ takes $k$ instances of size $d$ and outputs one instance of size $S(d,k)$, and $\mathrm{Dec}$ takes any feasible solution of the aggregate, an index $i$, and the original sub-instances, and outputs a feasible solution of the $i$-th instance, with optimality preserved whenever the input solution is optimal. The argument also relies on a direct product lemma, which bounds the fraction of coordinates on which planting a fixed input $x$ changes the success probability of a Boolean function on $k$-tuples away from its global average. The amplification algorithm embeds the given instance $x$ in a uniformly random coordinate, samples the other coordinates from $D$, runs the alleged strong solver on the aggregate, decodes the relevant coordinate, and repeats $c$ times; the lemma plus Markov's inequality shows this succeeds on a $1-\mathrm{fail}(d)$ fraction of inputs.

What would settle it

For End of a Line, take two simple directed lines and form their coordinate-wise product as described in Lemma 6.7. The vertex whose first coordinate is a non-zero endpoint and whose second coordinate is an internal vertex is an optimal solution of the aggregate, but decoding to the second coordinate returns an internal vertex that is not an optimal solution of the second line; a direct check of that example settles the TFNP application.

Watch

Extended reading notes

Core claim

The paper's central claim, Theorem 3.4, is that for any pair of optimization problems $\Pi, \Lambda$ that is $(S,T)$-direct product feasible, weak average-case hardness of $\Pi$ implies strong average-case hardness of $\Lambda$. Concretely, if $D$ is a samplable distribution over size-$d$ instances of $\Pi$ such that every randomized algorithm running in time $t(d)$ fails to find an optimal solution on at least $\mathrm{fail}(d)$ fraction of $D$, then setting $k = 64\cdot \mathrm{fail}(d)^{-6}$ and $c = \frac{200\ln(1/(1-p))}{p}$, and assuming $k\cdot s(d)+T(d,k)+v(d) \le \frac{t(d)}{2c}$, yields a samplable distribution $D'$ over instances of $\Lambda$ of size $S(d,k)$ such that every $\frac{t(d)}{2c}$-time algorithm fails on at least 99 percent of $D'$. The proof is a self-reduction: a hypothetical solver for $D'$ is used to solve $D$ by planting the input in a random coordinate of an aggregated instance and repeating the decode step, with a direct product lemma controlling the loss in success probability.

Load-bearing premise

The whole scheme hinges on the decoding property: an optimal solution of the stitched instance must always yield optimal solutions for every piece; if any stitching fails that, the amplification conclusion can fail.

Editorial extensions

If this is right

  • MaxSAT and disjoint-union NP-hard problems such as Vertex Cover and Dominating Set get amplified from $1/\mathrm{poly}(n)$ failure to 99 percent failure against polynomial-time algorithms.
  • Under randomized ETH, MaxSAT's subexponential-time hardness on a tiny fraction becomes 99 percent failure against super-polynomial-time algorithms.
  • For LCS and Edit Distance, a $1/n^{o(1)}$ failure rate against $n^{2-\varepsilon}$ algorithms becomes 99 percent failure against $n^{2-\varepsilon'}$ algorithms on instances of size $n^{1+o(1)}$.
  • Matrix multiplication admits the same amplification despite the absence of a known fast deterministic verifier, using randomized verification inside the reduction.
  • For total search problems, the paper derives analogous amplifications for Factoring, End of a Line, and hence approximate Nash equilibrium.

Reading between the lines

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

  • A useful next step is to characterize direct product feasibility itself: the paper shows it holds trivially for disjoint-union problems, requires careful scaling for Knapsack, needs a separator symbol for LCS and edit distance, and appears to fail for Fréchet distance; a systematic criterion would turn the theorem into a classification of which optimization problems can be made hard on average.
  • The End of a Line aggregation in Lemma 6.7 appears to violate the decoding requirement: in the coordinate-wise product of two simple lines, any vertex whose first coordinate is a non-zero endpoint is an optimal solution of the aggregate, but decoding it to the second coordinate can return an internal vertex that is not an optimal solution of that sub-instance. If this is correct, the TFNP and Nash
  • Because the amplification is self-referential, the same problem with only a different distribution, it offers a template for building fine-grained one-way functions from any directly-product-feasible problem that is mildly hard on average.
  • The 99 percent bound is not structural; the proof's parameter $c$ can be adjusted to push failure probability arbitrarily close to 1 at the cost of a larger running-time gap, so the constant is a convention rather than a barrier.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 4 minor

Summary. The paper introduces a notion called direct product feasibility (DPF) for optimization problems and proves a general hardness amplification theorem. For a DPF problem, if every t(n)-time algorithm fails on at least fail(d) fraction of instances sampled from an efficiently samplable distribution, then, under parameter conditions, there is another samplable distribution over larger instances on which every t(d)/(2c)-time algorithm fails on at least 99% of inputs. The proof uses a Feige-Kilian direct product lemma, which is stated and proved in the appendix. The theorem is then applied to several problems: MaxSAT and Knapsack in NP, LCS, Edit Distance, and Matrix Multiplication in P, and Factoring and End of a Line in TFNP, with a claimed consequence for approximate Nash equilibrium. The abstract and introduction advertise these TFNP and Nash applications as among the main results.

Significance. If the main conditional theorem is correct, it provides a clean and uniform route to hardness amplification for optimization problems, with an elementary proof that avoids the hard-core lemma used in prior NP hardness amplification. The applications to MaxSAT, Knapsack, LCS, Edit Distance, and Matrix Multiplication are concrete, and the Feige-Kilian direct product lemma is proved from first principles in the appendix, making the paper reasonably self-contained. However, the End of a Line application is based on a false direct product feasibility claim, so the TFNP and Nash equilibrium results are unsupported. Since those are prominently advertised in the abstract, the false lemma is load-bearing for a substantial portion of the paper's claimed contribution.

major comments (2)
  1. [Theorem 3.4 and its proof] The formal statement of Theorem 3.4 omits a necessary smallness condition on fail(d). In the correctness proof, the inequality 0.01 - k^{-1/6} >= 0.005 is used; substituting k = 64 * fail(d)^{-6} gives 0.01 - fail(d)/2 >= 0.005, which holds only if fail(d) <= 0.01. The theorem as stated allows arbitrary fail(d) in (0,1], so the formal statement is false as written. The corollaries use fail(d) = 1/d, 1/d^{o(1)}, or subexponentially small values, so the applications are not affected, but the main theorem must be corrected by adding fail(d) <= 0.01.
  2. [Lemma 6.7 and Corollaries 6.8, 6.10] Lemma 6.7 is false: the coordinatewise aggregation of End of a Line instances does not satisfy Definition 3.3. Under Definition 6.6, a vertex x is an optimal solution exactly when it is an unbalanced endpoint and x is not 0^n. Consider the simple line 0 -> 1 -> 2 defined by S(0)=1, S(1)=2, S(2)=2, P(1)=0, P(2)=1, P(0)=0; its unique optimal vertex is 2. In the product of two copies, the vertex x' = (0,2) satisfies P'(S'(x')) = (P(S(0)), P(S(2))) = (0,1), which is not equal to (0,2), so Delta(I',x') = 1 and x' is optimal for the aggregate. Decoding the first coordinate gives 0, which is not optimal for the first subinstance. Thus optimality of the aggregate is an existential OR over coordinates rather than a conjunction, and an optimal aggregate solution need not induce optimal solutions in every coordinate. Consequently Corollary 6.8, Corollary 6.10, and the claimed Nash equilibrium consequence are unsupported.
minor comments (4)
  1. [Lemma 6.7 statement] The statement of Lemma 6.7 says 'Factor is (S,T)-self direct product feasible' but the proof and surrounding text concern End of a Line; this should be corrected to EoL.
  2. [Definition 6.6] The condition in Definition 6.6, written as 'A(B(x)) != x != 0^n', is ambiguous; it should be parenthesized as '(A(B(x)) != x or B(A(x)) != x) and x != 0^n'.
  3. [Section 2.1, Step 2] In the proof sketch for Max Clique, Step 2 says 'Pick randomly i in [k]'; for the Feige-Kilian argument to apply, i should be chosen uniformly at random, and the text should say so explicitly.
  4. [Lemma 5.13 proof] The proof of Lemma 5.13 says that the i-th block of C' is 'indeed the optimal solution', but the text accidentally refers to 'optimal alignment'; this is a minor wording issue, since the intended object is an optimal product matrix.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the main reduction is self-contained and the direct product lemma is proved in the appendix.

full rationale

Theorem 3.4 is a conditional reduction: from a hardness assumption on a distribution D and a structural decoding hypothesis (Definition 3.3), it constructs a new distribution D' and proves hardness by contradiction. The only nontrivial external ingredient, the Feige–Kilian direct product lemma (Lemma 3.5), is stated explicitly and proved in Appendix A by elementary variance and Markov arguments; it is not imported from the authors' own prior work and it does not presuppose the target hardness. Each application (MaxSAT, Knapsack, LCS, Edit Distance, matrix multiplication, factoring) supplies an explicit Gen/Dec pair and proves the required optimality-decoding property, rather than fitting a parameter to the conclusion. No quantity that is 'predicted' is used to define the hypothesis, and no uniqueness theorem or ansatz is smuggled in through a self-citation. The skeptical notes about Lemma 6.7 and about the fail(d) threshold in Theorem 3.4 are correctness concerns, not circularity: even if those claims are wrong, the derivation does not reduce to its inputs by construction.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

The central theorem depends only on standard probability inequalities and the Feige-Kilian lemma, which is proved. The applications require the problems to satisfy the direct product feasibility condition; this holds for the listed problems except End of a Line. No free parameters or invented entities appear.

assumptions (3)
  • standard math Feige-Kilian direct product lemma (Lemma 3.5)
    Used as the core averaging tool in the proof of Theorem 3.4. The paper reproduces a proof in Appendix A, originally from [FK00] and [GO05].
  • domain assumption Existence of a deterministic optimality verifier V running in v(d) time
    Theorem 3.4 assumes V to check candidate solutions and certify optimality. For matrix multiplication this does not hold, so the authors modify the proof; this is acknowledged in Section 5.3.
  • ad hoc to paper Unstated smallness constraint on fail(d)
    The proof of Theorem 3.4 requires 0.01 - fail(d)/2 to be positive, i.e. fail(d) less than 0.02 (in practice fail(d) less than 0.01). The formal statement allows any fail(d) in (0,1], so the proof has a gap for larger fail(d). All applications use small fail(d), but the theorem as stated is not fully proved.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Hardness Amplification of Optimization Problems." pith.science (2026). https://pith.science/paper/W6ECNLJA

@misc{pith2026190810248,
  author       = {Pith},
  title        = {Pith review of: Hardness Amplification of Optimization Problems},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/W6ECNLJA}},
  note         = {Machine review of arXiv:1908.10248}
}
abstract

In this paper, we prove a general hardness amplification scheme for optimization problems based on the technique of direct products. We say that an optimization problem $\Pi$ is direct product feasible if it is possible to efficiently aggregate any $k$ instances of $\Pi$ and form one large instance of $\Pi$ such that given an optimal feasible solution to the larger instance, we can efficiently find optimal feasible solutions to all the $k$ smaller instances. Given a direct product feasible optimization problem $\Pi$, our hardness amplification theorem may be informally stated as follows: If there is a distribution $\mathcal{D}$ over instances of $\Pi$ of size $n$ such that every randomized algorithm running in time $t(n)$ fails to solve $\Pi$ on $\frac{1}{\alpha(n)}$ fraction of inputs sampled from $\mathcal{D}$, then, assuming some relationships on $\alpha(n)$ and $t(n)$, there is a distribution $\mathcal{D}'$ over instances of $\Pi$ of size $O(n\cdot \alpha(n))$ such that every randomized algorithm running in time $\frac{t(n)}{poly(\alpha(n))}$ fails to solve $\Pi$ on $\frac{99}{100}$ fraction of inputs sampled from $\mathcal{D}'$. As a consequence of the above theorem, we show hardness amplification of problems in various classes such as NP-hard problems like Max-Clique, Knapsack, and Max-SAT, problems in P such as Longest Common Subsequence, Edit Distance, Matrix Multiplication, and even problems in TFNP such as Factoring and computing Nash equilibrium.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

25 extracted references · 23 canonical work pages

  1. [7]

    Sivakumar

    [CPS99] Jin-yi Cai, Aduri Pavan, and D. Sivakumar. On the har dness of permanent. In STACS 99, 16th Annual Symposium on Theoretical Aspects of Comp uter Sci- ence, T rier, Germany, March 4-6, 1999, Proceedings, pages 90–99,

    work page 1999

  2. [8]

    Chan and Ryan Williams

    [CW16] Timothy M. Chan and Ryan Williams. Deterministic apsp , orthogonal vec- tors, and more: Quickly derandomizing razborov-smolensky. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, V A, USA, January 10-12, 2016, pages 1246–1255,

    work page 2016

  3. [10]

    Papadimitr iou

    [DP11] Constantinos Daskalakis and Christos H. Papadimitr iou. Continuous local search. In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, California, USA, January 23-25, 2011, pages 790–804,

    work page 2011

  4. [12]

    Relations between average case comple xity and approxima- tion complexity

    [Fei02] Uriel Feige. Relations between average case comple xity and approxima- tion complexity . In Proceedings on 34th Annual ACM Symposium on Theory of Computing, May 19-21, 2002, Montr´ eal, Qu´ ebec, Canada, pages 534–543,

    work page 2002

  5. [14]

    Levin, R amarathnam V enkatesan, and David Zuckerman

    [GIL+90] Oded Goldreich, Russell Impagliazzo, Leonid A. Levin, R amarathnam V enkatesan, and David Zuckerman. Security preserving ampl ification of hardness. In 31st Annual Symposium on Foundations of Computer Science, St. Louis, Missouri, USA, October 22-24, 1990, Volume I , pages 318–326,

    work page 1990

  6. [16]

    Hardness of continu ous local search: Query complexity and cryptographic lower bounds

    [HY17] Pavel Hub´ aˇ cek and Eylon Yogev . Hardness of continu ous local search: Query complexity and cryptographic lower bounds. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algori thms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19 , pages 1352–1371,

    work page 2017

  7. [23]

    List-decoding using the XOR lemma

    [Tre03] Luca Trevisan. List-decoding using the XOR lemma. I n 44th Symposium on Foundations of Computer Science (FOCS 2003), 11-14 October 200 3, Cambridge, MA, USA, Proceedings, pages 126–135,

    work page 2003

  8. [25]

    Theory and applications of tra pdoor functions (ex- tended abstract)

    [Yao82] Andrew Chi-Chih Yao. Theory and applications of tra pdoor functions (ex- tended abstract). In 23rd Annual Symposium on Foundations of Computer Sci- ence, Chicago, Illinois, USA, 3-5 November 1982 , pages 80–91,

    work page 1982

Show all 25 references
  1. [1988]

    On nondeterministic derandomi zation of freivalds’ algorithm: Consequences, avenues and algorithmic progres s

    [K ¨ un18] Marvin K ¨ unnemann. On nondeterministic derandomi zation of freivalds’ algorithm: Consequences, avenues and algorithmic progres s. In 26th An- nual European Symposium on Algorithms, ESA 2018, August 20- 22, 2018, Helsinki, Finland, pages 56:1–56:16,

    2018

  2. [1989]

    A birthday re petition theorem and complexity of approximating dense CSPs

    [MR16] Pasin Manurangsi and Prasad Raghavendra. A birthday re petition theorem and complexity of approximating dense CSPs. CoRR, abs/1607.02986,

    arXiv

  3. [1998]

    Settling the complexity of compu ting approximate two- player nash equilibria

    [Rub16] Aviad Rubinstein. Settling the complexity of compu ting approximate two- player nash equilibria. In IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency , New Brunswick, New Jersey, USA , pages 258–265,

    2016

  4. [1999]

    Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made

    [AHWW16] Amir Abboud, Thomas Dueholm Hansen, Virginia Vass ilevska Williams, and Ryan Williams. Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computi...

    2016

  5. [2001]

    [IW97] Russell Impagliazzo and Avi Wigderson

    Preliminary version in FOCS’98. [IW97] Russell Impagliazzo and Avi Wigderson. P = BPP if E requires exponential circuits: Derandomizing the XOR lemma. In Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, El Paso, T ex as, USA, May 4-6, 1997, page...

    1997

  6. [2002]

    Unique end of potential line

    [FGMS18] John Fearnley , Spencer Gordon, Ruta Mehta, and Rahul Savani. Unique end of potential line. CoRR, abs/1811.03841,

    arXiv

  7. [2003]

    On uniform amplification of hardness i n NP

    [Tre05] Luca Trevisan. On uniform amplification of hardness i n NP. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Balt imore, MD, USA, May 22-24, 2005 , pages 31–38,

    2005

  8. [2006]

    Papadimitriou, and A viad Rubinstein

    [BPR16] Yakov Babichenko, Christos H. Papadimitriou, and A viad Rubinstein. Can almost everybody be almost happy? In Proceedings of the 2016 ACM Con- ference on Innovations in Theoretical Computer Science, Cambri dge, MA, USA, January 14-16, 2016, pages 1–9,

    2016

  9. [2009]

    A duality between clause width and clause density for SAT

    [CIP06] Chris Calabro, Russell Impagliazzo, and Ramamohan Paturi. A duality between clause width and clause density for SAT. In 21st Annual IEEE Conference on Computational Complexity (CCC 2006), 16-20 Ju ly 2006, Prague, Czech Republic, pages 252–260,

    2006

  10. [2011]

    Direct product testing

    [DS14] Irit Dinur and David Steurer. Direct product testing . In IEEE 29th Conference on Computational Complexity, CCC 2014, Vancouver, BC, Canad a, June 11-13, 2014, pages 188–196,

    2014

  11. [2012]

    Hard-core distributions for somewhat hard problems

    [Imp95] Russell Impagliazzo. Hard-core distributions for somewhat hard problems. In 36th Annual Symposium on Foundations of Computer Science, Mil waukee, Wisconsin, USA, 23-25 October 1995 , pages 538–545,

    1995

  12. [2013]

    Why walking the dog takes time: Frech et distance has no strongly subquadratic algorithms unless SETH fails

    [Bri14] Karl Bringmann. Why walking the dog takes time: Frech et distance has no strongly subquadratic algorithms unless SETH fails. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Phil adelphia, P A, USA, October 18-21, 2014 , pages 661–670,

    2014

  13. [2014]

    Average-case fine-grained hardness

    [BRSV17] Marshall Ball, Alon Rosen, Manuel Sabin, and Prashan t Nalini Vasude- van. Average-case fine-grained hardness. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing , STOC 2017, pages 483– 496, New York, NY , USA,

    2017

  14. [2016]

    Locally testing di rect product in the low error range

    37 [DG08] Irit Dinur and Elazar Goldenberg. Locally testing di rect product in the low error range. In 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, October 25-28, 2008, Philadelphia, P A, USA , pages 613– 622,

    2008

  15. [2017]

    Rothblum

    38 [GR18] Oded Goldreich and Guy N. Rothblum. Counting t-cliqu es: Worst-case to average-case reductions and direct interactive proof syst ems. In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 201 8, Paris, France, October 7-9, 2018 , pages 77–88,

    2018

  16. [2018]

    [Lip89] Richard J. Lipton. New directions in testing. In Distributed Computing And Cryptography, Proceedings of a DIMACS Workshop, Princeton, New Jersey, USA, October 4-6, 1989, pages 191–202,

    1989

  17. [2019]

    Tight hardness results for LCS and other sequence similarity meas ures

    [ABW15] Amir Abboud, Arturs Backurs, and Virginia Vassilev ska Williams. Tight hardness results for LCS and other sequence similarity meas ures. In IEEE 56th Annual Symposium on Foundations of Computer Science, FOC S 2015, Berkeley, CA, USA, 17-20 October, 2015 , pages 59–78,

    2015

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.