Pith. sign in

REVIEW 8 minor 161 references

On the Approximability of Parameterized Minimum Monotone Satisfying Assignment

T0 review · 0 major / 8 minor · reviewed 2026-07-10 · glm-5.2

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

Pith's one-line read Level 3 of MMSA stays close to Set Cover in FPT regime

desk verdict Clean FPT approximation for k-MMSA_3 plus a gap-preserving reduction to k-MMSA_2; MMSA_4 lower bounds sharpened via better parameters for Marx's reduction. read the letter →

arxiv 2607.06852 v1 pith:BOFSZWW3 submitted 2026-07-07 cs.CC

Venkatesan Guruswami , Bingkai Lin , Xuandi Ren , Xin Zheng This is my paper · ORCID
classification cs.CC
keywords mmsainapproximabilityparameterizedapproximabilityapproximationassignmentgivehierarchy
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 studies a hierarchy of optimization problems called Minimum Monotone Satisfying Assignment (MMSA), defined by how many times a Boolean circuit alternates between AND and OR gates. The second level is equivalent to Set Cover, where parameterized inapproximability is relatively mild (polylogarithmic in n). The fourth level is known to be much harder, admitting polynomial-factor inapproximability. The third level, sitting between these two, had remained unexplored in the parameterized setting. This paper shows that the third level is surprisingly close to the second: there is a fixed-parameter tractable algorithm achieving an O(2^k log n)-approximation, nearly matching the O(log n) greedy ratio for Set Cover. The key mechanism is a greedy covering argument that exploits the fact that any weight-k solution has at most 2^k distinct subsets, so enumerating candidate bottom-level conjunctions guarantees a constant fraction of progress per step. Complementing this, the paper gives a gap-preserving reduction from the third level to the second level, meaning that any strong inapproximability for the third level would automatically yield new lower bounds for Set Cover itself. The paper also sharpens known hardness for the fourth level by revisiting an earlier gap-creating reduction with better-chosen parameters, showing n^{o(1)} inapproximability under W[2]≠FPT and n^{O(1/k)} inapproximability in n^{o(k)} time under ETH. Together these results locate where the complexity jump occurs in the MMSA hierarchy: between the third and fourth levels, not between the second and third.

What carries the argument

The approximation algorithm uses a greedy covering strategy on the top-level AND clauses of the MMSA_3 circuit. After pruning bottom conjunctions to size at most k (justified because a weight-k assignment cannot satisfy any larger conjunction), the algorithm repeatedly selects the bottom conjunction covering the most currently uncovered clauses. The analysis bounds progress via a counting argument: a weight-k solution's support has at most 2^k distinct subsets, so some subset must serve as a witness for at least a 1/2^k fraction of uncovered clauses. The gap-preserving reduction from MMSA_3 to MMSA_2 contracts each distinct bottom conjunction into a single Boolean variable, mapping a weight-

What would settle it

A weight-k satisfying assignment of the original circuit that relies on a bottom conjunction of size greater than k being true—but this is impossible by definition, since setting more than k variables to 1 exceeds the weight budget. The pruning is therefore safe for the promise version of the problem.

Watch

Extended reading notes

Core claim

The central discovery is that parameterized MMSA at depth 3 admits an O(2^k log n)-approximation in FPT time, placing it in the same qualitative regime as Set Cover (depth 2) rather than depth 4. The approximation works by a greedy set-cover-style argument: since any weight-k satisfying assignment has at most 2^k distinct subsets of its support, and each bottom conjunction in the circuit has size at most k, one can always find a conjunction that covers at least a 1/2^k fraction of currently uncovered top-level clauses, yielding termination in O(2^k log n) steps. The paper also provides a reduction in the reverse direction—from gap MMSA_3 to gap MMSA_2—establishing that depth-3 hardness would

Load-bearing premise

The pruning step (Lemma 2.4) removes every bottom conjunction of size greater than k from the MMSA_3 circuit, justified by the observation that no weight-k assignment can satisfy such a conjunction. This is sound for the gap problem where the yes-case promises a solution of weight at most k, but it means the reduction and algorithm are tailored to the parameterized promise setting and do not directly apply to the unparameterized optimization version.

Editorial extensions

If this is right

  • A polylogarithmic or even constant-factor FPT inapproximability for MMSA_3 under W[1]≠FPT would imply the same for k-SetCover, resolving a major open problem.
  • An ω(2^k) FPT inapproximability for MMSA_3 under W[2]≠FPT would yield superconstant FPT inapproximability for Set Cover, another long-standing open question.
  • The separation between MMSA_3 (approximable within O(2^k log n)) and MMSA_4 (inapproximable within n^{o(1)}) clarifies that the complexity jump in the MMSA hierarchy occurs specifically between depths 3 and 4 in the parameterized regime.
  • The improved ETH-based lower bound for MMSA_4 (n^{O(1/k)} in n^{o(k)} time) strengthens the known connection between MMSA_4 and k-MinLabel, suggesting depth-4 MMSA as the canonical hard problem for polynomial-factor parameterized inapproximability.

Reading between the lines

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

  • The reduction from MMSA_3 to MMSA_2 suggests a possible research program: construct MMSA_3 gap instances directly (e.g., via PCP or label-cover techniques adapted to the parameterized setting) and then transfer the resulting hardness down to Set Cover, bypassing the barriers that have stalled direct approaches.
  • The 2^k factor in the approximation ratio may not be tight; if one could improve it to poly(k) or even polylog(k), the reduction would imply correspondingly stronger consequences for Set Cover, potentially matching known lower bounds.
  • The fact that MMSA_3 and MMSA_2 are close in approximability but MMSA_4 is far suggests that the alternation from depth 3 to depth 4 introduces a qualitative change in the combinatorial structure—possibly related to the transition from set-cover-type to label-cover-type constraints.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

0 major / 8 minor

Summary. This paper studies the parameterized approximability of the Minimum Monotone Satisfying Assignment (MMSA) hierarchy, focusing on the third level, k-MMSA_3, which sits between k-SetCover (k-MMSA_2) and k-MinLabel (captured by k-MMSA_4). The authors make three main contributions: (1) a deterministic FPT-time O(2^k log n)-approximation algorithm for k-MMSA_3 (Theorem 3.1), showing that in the parameterized regime the third level remains close to the second; (2) an FPT-time gap-preserving reduction from (k,h)-gap k-MMSA_3 to (2k, h/k)-gap k-MMSA_2 (Theorem 4.1), establishing that stronger inapproximability for k-MMSA_3 would imply new hardness for k-SetCover; (3) improved inapproximability for k-MMSA_4 by revisiting Marx's reduction with better parameters, yielding no n^{o(1)}-factor FPT approximation under W[2]≠FPT (Corollary 5.7) and no n^{O(1/k)}-factor approximation in n^{o(k)} time under ETH (Corollary 5.6). The proofs are clean, self-contained, and build on standard tools (perfect hash families, greedy covering, padding arguments).

Significance. The paper addresses a well-motivated gap in the parameterized complexity of the MMSA hierarchy. The O(2^k log n)-approximation for k-MMSA_3 is a concrete algorithmic result showing the third level is not dramatically harder than k-SetCover in the FPT regime, contrasting with the polynomial-time setting where MMSA_3 is known to be much harder. The gap-preserving reduction from k-MMSA_3 to k-MMSA_2 is conceptually valuable: it explains why k-MMSA_3 has not yielded independent inapproximability and provides a potential route to resolving open problems for k-SetCover. The improved k-MMSA_4 inapproximability, obtained by a careful reparameterization of Marx's existing reduction, cleanly separates the third and fourth levels. The results are falsifiable in the standard sense of complexity-theoretic conditional lower bounds, and the algorithmic upper bound is constructive and implementable in principle. The paper ships no machine-checked proofs or code, but the proofs are short enough to be verified by hand.

minor comments (8)
  1. §1, paragraph 2: The footnote 1 notes that [DS04] studied monotone formulae rather than circuits, and that the distinction matters only in the unbounded-depth setting. It would help the reader to clarify in the main text (not just the footnote) that all results in this paper concern the circuit variant, since the W[P]/W[SAT] discussion later in the same paragraph refers to the unbounded-depth setting.
  2. §1, paragraph 5: The phrase 'total-FPT-inapproximability' is defined in footnote 4 as ruling out FPT-time f(k)-approximation for every computable f. This terminology is slightly non-standard; consider citing or aligning with the terminology used in [Mar13] or [FKLM20] for consistency.
  3. §2.2, Definition 2.3: The circuit form uses w_{i_1,...,i_t} as an index in [n], but the notation is introduced without explicitly stating that multiple tuples (i_1,...,i_t) can map to the same index (i.e., the same variable can appear in multiple bottom gates). This is implicit but worth stating for clarity.
  4. §3, proof of Theorem 3.1: The algorithm enumerates at most n^2 candidate sets N_{a,b} per iteration. It would be useful to state the total running time explicitly as O(2^k · log n · poly(n)), or more precisely O(2^k · log n · n^2 · poly(n)), to make the FPT claim fully transparent.
  5. §4, proof of Theorem 4.1: The reduction outputs a k-MMSA_2 instance on at most n^2 variables. Corollary 4.2 then states the contrapositive in terms of t(√n, log k). The substitution n → n^2 and k → 2k is correct, but the step from t(n^2, 2k) · 2^k to t(√n, log k)/k in the denominator could benefit from one line of algebraic explanation, as the direction of the implication is easy to get backwards.
  6. §5.2, Theorem 5.4: The reduction constructs C' by adding two outer layers. The statement says 'the same n variables,' but the perfect hash family introduces indices i ∈ [m] and T ∈ (Σ choose k) that index the outer conjunction and disjunction. It would be clearer to state that the new circuit is on the same set of input variables but has additional gates indexed by [m] × (Σ choose k).
  7. Table 1: The entry for k-MMSA_4 'n^{1/poly(k)}' under ETH with 'n^{o(k)}' runtime is listed with reference [KLM19, KN21], while the improved 'n^{O(1/k)}' result from Corollary 5.6 is listed separately. Consider merging these into a single row or adding a note that the latter supersedes the former, to avoid the impression that both are the best known.
  8. References: The arXiv identifier in the header (2607.06852) suggests a 2026 submission, but several references (e.g., [LRSW23], [CMV23]) are from 2023. This is not an error per se, but the authors should verify that no more recent results have appeared that would affect the discussion of k-SetCover inapproximability in §1.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity found; all main results are derived from first principles with standard combinatorial tools and externally verifiable complexity assumptions.

full rationale

The paper presents three main results: (1) an FPT-time O(2^k log n)-approximation for k-MMSA_3 (Theorem 3.1), (2) a gap-preserving reduction from k-MMSA_3 to k-MMSA_2 (Theorem 4.1), and (3) improved inapproximability for k-MMSA_4 (Corollaries 5.6, 5.7). Each is derived from first principles. The algorithm in Theorem 3.1 uses a clean greedy covering argument with a correct averaging bound over the at most 2^k subsets of a weight-k satisfying assignment. The reduction in Theorem 4.1 contracts bottom conjunctions into MMSA_2 variables; its completeness (at most 2^k true conjunctions) and soundness (decoded weight <= k * |A| <= h) are verified by direct combinatorial argument. Lemma 2.4's pruning step is sound: if OPT(C) <= k, no conjunction of size > k can be satisfied by a weight-k assignment, so removing them preserves all relevant solutions. The MMSA_4 results follow from reparameterizing Marx's reduction [Mar13] with perfect hash families of size h = n^{Theta(1/k)} from Lemma 2.2, an independent construction from [AYZ95]. The hardness results rely on standard complexity assumptions (W[1]!=FPT, W[2]!=FPT, ETH) and cite prior work appropriately. No result is defined in terms of its own conclusion, no parameter is fitted and renamed as prediction, and no self-citation chain is load-bearing in a circular way. The paper is self-contained against external benchmarks.

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

The paper introduces no new free parameters or invented entities. It relies on standard complexity assumptions and known combinatorial constructions.

assumptions (4)
  • domain assumption W[1] != FPT
    Standard complexity assumption used for FPT inapproximability of k-MMSA_4 (Corollary 5.7).
  • domain assumption W[2] != FPT
    Standard complexity assumption used for total-FPT inapproximability of k-MMSA_4 (Corollary 5.7).
  • domain assumption ETH (Exponential Time Hypothesis)
    Standard complexity assumption used for n^{o(k)}-time inapproximability of k-MMSA_4 (Corollary 5.6).
  • standard math Existence of efficient perfect hash families (Lemma 2.2)
    Cited from [AYZ95], used in the reduction for k-MMSA_4 in Theorem 5.4.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On the Approximability of Parameterized Minimum Monotone Satisfying Assignment." pith.science (2026). https://pith.science/paper/BOFSZWW3

@misc{pith2026260706852,
  author       = {Pith},
  title        = {Pith review of: On the Approximability of Parameterized Minimum Monotone Satisfying Assignment},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/BOFSZWW3}},
  note         = {Machine review of arXiv:2607.06852}
}
abstract

The parameterized Minimum Monotone Satisfying Assignment ($k$-MMSA) problem asks whether a monotone Boolean circuit admits a satisfying assignment of Hamming weight at most $k$. The MMSA hierarchy is defined by allowing a bounded number of alternations between AND and OR gates in the circuit. While the polynomial-time approximability of the MMSA hierarchy has been studied extensively, much less is known in the parameterized setting. In particular, $k$-MMSA$_2$ is the well-known $k$-SetCover problem, whose parameterized inapproximability lies in the $\text{polylog}(n)$ regime. In contrast, $k$-MMSA$_4$ captures $k$-MinLabel, for which known lower bounds give $\text{poly}(n)$ inapproximability. Sandwiched by $k$-MMSA$_2$ and $k$-MMSA$_4$, the inapproximability of $k$-MMSA$_3$ remained comparatively unexplored. In this paper, we give an FPT-time $O(2^k \log n)$-approximation algorithm for $k$-MMSA$_3$, suggesting that in the fixed-parameter regime, the third level of MMSA remains surprisingly close to the second level. Complementing this algorithm, we also give an FPT-time gap-preserving reduction from $k$-MMSA$_3$ to $k$-MMSA$_2$. Thus, stronger inapproximability for $k$-MMSA$_3$ would imply new hardness for $k$-MMSA$_2$, potentially offering a route around the current barriers for the latter problem. Revisiting Marx's reduction from $k$-MMSA$_t$ to gap $k$-MMSA$_{t+2}$, we also show that $k$-MMSA$_4$ admits no $n^{o(1)}$-factor FPT approximation unless W[2]=FPT, and no $n^{O(1/k)}$-factor approximation running in $n^{o(k)}$ time under ETH. These results separate the parameterized approximability behavior of the third and fourth levels and clarify where stronger inapproximability enters the $k$-MMSA hierarchy.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

161 extracted references · 161 canonical work pages

  1. [2]

    Approximation, Randomization, and Combinatorial Optimization

    Chlamt\'. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023) , pages =. 2023 , volume =

    work page 2023

  2. [1]

    Kanj and Ge Xia , title =

    Jianer Chen and Xiuzhen Huang and Iyad A. Kanj and Ge Xia , title =. Journal of Computer and System Sciences , volume =. 2006 , doi =

    work page 2006

  3. [3]

    Approximation Algorithms for NP-Hard Problems , editor =

    Sanjeev Arora and Carsten Lund , title =. Approximation Algorithms for NP-Hard Problems , editor =

    work page

  4. [4]

    2021 , eprint =

    Xuandi Ren , title =. 2021 , eprint =

    work page 2021

  5. [5]

    Parameterized Complexity Theory , series =

    Flum, J. Parameterized Complexity Theory , series =. 2006 , doi =

    work page 2006

  6. [6]

    Goldwasser and Rajeev Motwani , editor =

    Michael H. Goldwasser and Rajeev Motwani , editor =. Intractability of Assembly Sequencing: Unit Disks in the Plane , booktitle =. 1997 , url =. doi:10.1007/3-540-63307-3\_70 , timestamp =

    work page doi:10.1007/3-540-63307-3 1997

  7. [7]

    Buss and Shlomo Moran and Toniann Pitassi , title =

    Michael Alekhnovich and Samuel R. Buss and Shlomo Moran and Toniann Pitassi , title =. J. Symb. Log. , volume =. 2001 , url =. doi:10.2307/2694916 , timestamp =

    work page doi:10.2307/2694916 2001

  8. [8]

    40th Annual Symposium on Foundations of Computer Science,

    Christopher Umans , title =. 40th Annual Symposium on Foundations of Computer Science,. 1999 , url =. doi:10.1109/SFFCS.1999.814619 , timestamp =

    work page doi:10.1109/sffcs.1999.814619 1999

Show all 161 references
  1. [9]

    Irit Dinur and Shmuel Safra , title =. Inf. Process. Lett. , volume =. 2004 , url =. doi:10.1016/J.IPL.2003.11.007 , timestamp =

    2004 doi

  2. [10]

    Noga Alon and Raphael Yuster and Uri Zwick , title =. J. 1995 , url =. doi:10.1145/210332.210337 , timestamp =

    1995 doi

  3. [11]

    and Koml\'

    Fredman, Michael L. and Koml\'. On the Size of Separating Systems and Families of Perfect Hash Functions , journal =. 1984 , doi =

    1984

  4. [12]

    Completely inapproximable monotone and antimonotone parameterized problems , journal =

    D. Completely inapproximable monotone and antimonotone parameterized problems , journal =. 2013 , url =. doi:10.1016/J.JCSS.2012.09.001 , timestamp =

    2013 doi

  5. [13]

    Fixed-Parameter and Approximation Algorithms:

    Rajesh Hemant Chitnis and MohammadTaghi Hajiaghayi and Guy Kortsarz , editor =. Fixed-Parameter and Approximation Algorithms:. Parameterized and Exact Computation - 8th International Symposium,. 2013 , url =. doi:10.1007/978-3-319-03898-8\_11 , timestamp =

    2013 doi

  6. [14]

    36th Annual Symposium on Foundations of Computer Science, Milwaukee, Wisconsin, USA, 23-25 October 1995 , pages =

    Mihir Bellare and Oded Goldreich and Madhu Sudan , title =. 36th Annual Symposium on Foundations of Computer Science, Milwaukee, Wisconsin, USA, 23-25 October 1995 , pages =. 1995 , url =. doi:10.1109/SFCS.1995.492573 , timestamp =

    1995 doi

  7. [15]

    2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS) , pages=

    Exponentially-hard gap-csp and local PRG via local hardcore functions , author=. 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS) , pages=. 2017 , organization=

    2017

  8. [16]

    Mihir Bellare and Oded Goldreich and Madhu Sudan , title =

  9. [17]

    SIAM Journal on Computing , volume=

    An isomorphism between subexponential and parameterized complexity theory , author=. SIAM Journal on Computing , volume=. 2007 , publisher=

    2007

  10. [18]

    Reed, I. S. and Solomon, G. , title =. Journal of the Society for Industrial and Applied Mathematics , volume =. 1960 , doi =

    1960

  11. [19]

    2000 , isbn =

    Katz, Jonathan and Trevisan, Luca , title =. 2000 , isbn =. doi:10.1145/335305.335315 , booktitle =

    2000 doi

  12. [20]

    30th Annual Symposium on Foundations of Computer Science , pages=

    Dispersers, deterministic amplification, and weak random sources , author=. 30th Annual Symposium on Foundations of Computer Science , pages=. 1989 , organization=

    1989

  13. [21]

    Parameterized Intractability of Even Set and Shortest Vector Problem , journal =

    Arnab Bhattacharyya and. Parameterized Intractability of Even Set and Shortest Vector Problem , journal =. 2021 , url =. doi:10.1145/3444942 , timestamp =

    2021 doi

  14. [22]

    Draft available at http://www

    Essential Coding Theory , author=. Draft available at http://www. cse. buffalo. edu/atri/courses/coding-theory/book , year=

  15. [23]

    Proceedings of the 55th Annual ACM Symposium on Theory of Computing , pages=

    Parameterized Inapproximability of the Minimum Distance Problem over All Fields and the Shortest Vector Problem in All _p Norms , author=. Proceedings of the 55th Annual ACM Symposium on Theory of Computing , pages=

  16. [24]

    http://staff.ustc.edu.cn/ jiema/ExtrGT2016/March\ author=

  17. [25]

    Downey and Michael R

    Rodney G. Downey and Michael R. Fellows , title =. 1995 , url =. doi:10.1137/S0097539792228228 , timestamp =

    1995 doi

  18. [26]

    and Pieterse, Astrid , title =

    Jansen, Bart M. and Pieterse, Astrid , title =. 2017 , issue_date =. doi:10.1007/s00453-016-0189-9 , journal =

    2017 doi

  19. [27]

    2021 , url =

    On Hardness of Approximation of Parameterized Set Cover and Label Cover: Threshold Graphs from Error Correcting Codes , booktitle =. 2021 , url =. doi:10.1137/1.9781611976496.24 , timestamp =

    2021 doi

  20. [28]

    A Simple Gap-Producing Reduction for the Parameterized Set Cover Problem , booktitle =

    Bingkai Lin , editor =. A Simple Gap-Producing Reduction for the Parameterized Set Cover Problem , booktitle =. 2019 , url =

    2019

  21. [29]

    2019 , url =

    On the Parameterized Complexity of Approximating Dominating Set , journal =. 2019 , url =

    2019

  22. [30]

    2019 , url =

    Yijia Chen and Bingkai Lin , title =. 2019 , url =

    2019

  23. [31]

    Journal of Computer and System Sciences , volume=

    On the Complexity of k-SAT , author=. Journal of Computer and System Sciences , volume=

  24. [32]

    Zarankiewicz , author=

    On a problem of K. Zarankiewicz , author=. Colloquium Mathematicum , year=

  25. [33]

    Journal of Computer and System Sciences , volume=

    Which problems have strongly exponential complexity? , author=. Journal of Computer and System Sciences , volume=. 2001 , publisher=

    2001

  26. [34]

    Tovey , journal=

    C. Tovey , journal=. A simplified. 1984 , volume=

    1984

  27. [35]

    Can You Beat Treewidth? , year =

    Marx, D. Can You Beat Treewidth? , year =. Theory of Computing , volume =. doi:10.4086/toc.2010.v006a005 , publisher =

    2010 doi

  28. [36]

    Optimal Parameterized Algorithms for Planar Facility Location Problems Using Voronoi Diagrams , year =

    Marx, D\'. Optimal Parameterized Algorithms for Planar Facility Location Problems Using Voronoi Diagrams , year =. ACM Trans. Algorithms , month =. doi:10.1145/3483425 , abstract =

    doi

  29. [37]

    Algorithmica , volume=

    Parameterized inapproximability of independent set in H-free graphs , author=. Algorithmica , volume=. 2023 , publisher=

    2023

  30. [38]

    Electron

    Mildly exponential reduction from gap 3SAT to polynomial-gap label-cover , author=. Electron. Colloquium Comput. Complex. , year=

  31. [39]

    44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) , pages =

    Pasin Manurangsi and Prasad Raghavendra , title =. 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) , pages =. 2017 , volume =. doi:10.4230/LIPIcs.ICALP.2017.78 , annote =

    2017 doi

  32. [40]

    Irit Dinur , title =. J. 2007 , url =. doi:10.1145/1236457.1236459 , timestamp =

    2007 doi

  33. [41]

    Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-

    Arnab Bhattacharyya and Suprovat Ghoshal and. Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-. Electron. Colloquium Comput. Complex. , volume =. 2018 , url =

    2018

  34. [42]

    From Gap-

    Parinya Chalermsook and Marek Cygan and Guy Kortsarz and Bundit Laekhanukit and Pasin Manurangsi and Danupon Nanongkai and Luca Trevisan , editor =. From Gap-. 58th. 2017 , url =. doi:10.1109/FOCS.2017.74 , timestamp =

    2017 doi

  35. [43]

    SIAM Journal on Computing , volume=

    Ruling out PTAS for graph min-bisection, dense k-subgraph, and bipartite clique , author=. SIAM Journal on Computing , volume=. 2006 , publisher=

    2006

  36. [44]

    Dinur, Irit , journal=. The

  37. [45]

    Kanj and Ge Xia , title =

    Jianer Chen and Xiuzhen Huang and Iyad A. Kanj and Ge Xia , title =. J. Comput. Syst. Sci. , volume =. 2006 , url =. doi:10.1016/j.jcss.2006.04.007 , timestamp =

    2006 doi

  38. [46]

    A probabilistic remark on algebraic program testing , author=. Inf. Process. Lett. , volume=

  39. [47]

    International symposium on symbolic and algebraic manipulation , pages=

    Probabilistic algorithms for sparse polynomials , author=. International symposium on symbolic and algebraic manipulation , pages=. 1979 , organization=

    1979

  40. [48]

    Guruswami, Venkatesan and Ren, Xuandi and Sandeep, Sai , journal=. Baby

  41. [49]

    Journal of the ACM (JACM) , volume=

    Fast probabilistic algorithms for verification of polynomial identities , author=. Journal of the ACM (JACM) , volume=. 1980 , publisher=

    1980

  42. [50]

    Decodability of group homomorphisms beyond the

    Dinur, Irit and Grigorescu, Elena and Kopparty, Swastik and Sudan, Madhu , booktitle=. Decodability of group homomorphisms beyond the

  43. [51]

    Parikshit Gopalan and Venkatesan Guruswami and Prasad Raghavendra , title =

  44. [52]

    Proceedings of the forty-first annual ACM symposium on Theory of computing , pages=

    List decoding tensor products and interleaved codes , author=. Proceedings of the forty-first annual ACM symposium on Theory of computing , pages=

  45. [53]

    Exact Weight Subgraphs and the k-Sum Conjecture

    Abboud, Amir and Lewi, Kevin. Exact Weight Subgraphs and the k-Sum Conjecture. Automata, Languages, and Programming. 2013

    2013

  46. [54]

    Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-

    Bhattacharyya, Arnab and Ghoshal, Suprovat and Karthik, CS and Manurangsi, Pasin , booktitle=. Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-. 2018 , organization=

    2018

  47. [55]

    The Complexity of Satisfiability of Small Depth Circuits

    Calabro, Chris and Impagliazzo, Russell and Paturi, Ramamohan. The Complexity of Satisfiability of Small Depth Circuits. Parameterized and Exact Computation. 2009

    2009

  48. [56]

    Improved Hardness of Approximating k-Clique under

    Lin, Bingkai and Ren, Xuandi and Sun, Yican and Wang, Xiuhan , journal=. Improved Hardness of Approximating k-Clique under

  49. [57]

    49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) , year=

    On Lower Bounds of Approximating Parameterized k-Clique , author=. 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) , year=

    2022

  50. [58]

    Constant approximating k -clique is W[1]-hard , booktitle =

    Bingkai Lin , editor =. Constant approximating k -clique is W[1]-hard , booktitle =. 2021 , url =

    2021

  51. [59]

    Sanjeev Arora and Shmuel Safra , title =. J. 1998 , url =. doi:10.1145/273865.273901 , timestamp =

    1998 doi

  52. [60]

    Lecture Notes on Linearity (Group Homomorphism) Testing , author=

  53. [61]

    46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) , year=

    A Simple Gap-Producing Reduction for the Parameterized Set Cover Problem , author=. 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) , year=

    2019

  54. [62]

    2014 , publisher=

    Analysis of boolean functions , author=. 2014 , publisher=

    2014

  55. [63]

    Ben-Sasson, Eli and Goldreich, Oded and Harsha, Prahladh and Sudan, Madhu and Vadhan, Salil , booktitle=. Robust

  56. [64]

    Assignment testers: Towards a combinatorial proof of the

    Dinur, Irit and Reingold, Omer , journal=. Assignment testers: Towards a combinatorial proof of the. 2006 , publisher=

    2006

  57. [65]

    Graph-Theoretic Concepts in Computer Science: 29th International Workshop, WG 2003

    Blow-ups, win/win’s, and crown rules: Some new directions in FPT , author=. Graph-Theoretic Concepts in Computer Science: 29th International Workshop, WG 2003. Elspeet, The Netherlands, June 19-21, 2003. Revised Papers 29 , pages=. 2003 , organization=

    2003

  58. [66]

    2004 , publisher=

    The probabilistic method , author=. 2004 , publisher=

    2004

  59. [67]

    Proceedings of the fortieth annual ACM symposium on Theory of computing , pages=

    On the constant-depth complexity of k-clique , author=. Proceedings of the fortieth annual ACM symposium on Theory of computing , pages=. 2008 , organization=

    2008

  60. [68]

    Clique is hard to approximate within n^

    Hastad, Johan , booktitle=. Clique is hard to approximate within n^. 1996 , organization=

    1996

  61. [69]

    SIAM Journal on Computing , volume=

    Introduction to Special Section on Probabilistic Proof Systems , author=. SIAM Journal on Computing , volume=. 1998 , publisher=

    1998

  62. [70]

    Proceedings of the twenty-sixth annual ACM symposium on Theory of computing , pages=

    Improved non-approximability results , author=. Proceedings of the twenty-sixth annual ACM symposium on Theory of computing , pages=

  63. [71]

    SIAM Journal on Computing , volume=

    Two-Prover Protocols---Low Error at Affordable Rates , author=. SIAM Journal on Computing , volume=. 2000 , publisher=

    2000

  64. [72]

    Proceedings of the thirty-eighth annual ACM symposium on Theory of computing , pages=

    Linear degree extractors and the inapproximability of max clique and chromatic number , author=. Proceedings of the thirty-eighth annual ACM symposium on Theory of computing , pages=

  65. [73]

    Proceedings of the twenty-fifth annual ACM symposium on Theory of computing , pages=

    Efficient probabilistically checkable proofs and applications to approximations , author=. Proceedings of the twenty-fifth annual ACM symposium on Theory of computing , pages=

  66. [74]

    Journal of the ACM (JACM) , volume=

    Interactive proofs and the hardness of approximating cliques , author=. Journal of the ACM (JACM) , volume=. 1996 , publisher=

    1996

  67. [75]

    Frontiers in Algorithmics - 13th International Workshop,

    Wenxing Lai , title =. Frontiers in Algorithmics - 13th International Workshop,

  68. [76]

    A talk given by Neeraj Kayal at the Simons Institute for the Theory of Computing, Berkeley, CA [Accessed: 2017/20/7] , pages=

    Solvability of systems of polynomial equations over finite fields , author=. A talk given by Neeraj Kayal at the Simons Institute for the Theory of Computing, Berkeley, CA [Accessed: 2017/20/7] , pages=

    2017

  69. [77]

    Bingkai Lin , title =. J

  70. [78]

    Fomin and Danny Hermelin and Magnus Wahlstr

    Marek Cygan and Fedor V. Fomin and Danny Hermelin and Magnus Wahlstr. Randomization in Parameterized Complexity (Dagstuhl Seminar 17041) , journal =

  71. [79]

    2015 , publisher=

    Parameterized algorithms , author=. 2015 , publisher=

    2015

  72. [80]

    Theoretical Computer Science , volume=

    On the complexity of fixed parameter clique and dominating set , author=. Theoretical Computer Science , volume=. 2004 , publisher=

    2004

  73. [81]

    CoRR, abs/1311.3054 , year=

    On the parameterized complexity of k-SUM , author=. CoRR, abs/1311.3054 , year=

    arXiv

  74. [82]

    European Symposium on Algorithms , pages=

    Losing weight by gaining edges , author=. European Symposium on Algorithms , pages=. 2014 , organization=

    2014

  75. [83]

    R. M. Karp , title =. Proceedings of a symposium on the Complexity of Computer Computations, held March 20-22, 1972, at the

    1972

  76. [84]

    Sanjeev Arora and Carsten Lund and Rajeev Motwani and Madhu Sudan and Mario Szegedy , title =. J. 1998 , url =. doi:10.1145/278298.278306 , timestamp =

    1998 doi

  77. [85]

    S. K. Stein , title =. Journal of Combinatorial Theory, Series

  78. [86]

    D. S. Johnson , title =. Journal of Computer and System Sciences , volume =

  79. [87]

    P. Slav\'. A Tight Analysis of the Greedy Algorithm for Set Cover , journal =

  80. [88]

    Journal of Computer and System Sciences , volume=

    Self-testing/correcting with applications to numerical problems , author=. Journal of Computer and System Sciences , volume=. 1993 , publisher=

    1993

  81. [89]

    Fixed-parameter tractability and completeness

    Downey, Rodney G and Fellows, Michael R , journal=. Fixed-parameter tractability and completeness. 1995 , publisher=

    1995

  82. [90]

    Raz and S

    R. Raz and S. Safra , title =. Proceedings of the 29th Annual

  83. [91]

    2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS) , year=

    A Proof of CSP Dichotomy Conjecture , author=. 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS) , year=

    2017

  84. [92]

    Cai, Jin-Yi and Chen, Xi , title =. J. ACM , month =. 2017 , issue_date =. doi:10.1145/2822891 , abstract =

    2017 doi

  85. [93]

    Eli Ben. Robust. 2006 , url =. doi:10.1137/S0097539705446810 , timestamp =

    2006 doi

  86. [94]

    L. Lov\'. On the ratio of optimal integral and fractional covers , journal =

  87. [95]

    V. Chv\'. A greedy heuristic for the set-covering problem , journal =

  88. [96]

    Dahstuhl Seminar , number=

    Data reductions and problem kernels , author=. Dahstuhl Seminar , number=

  89. [97]

    arXiv preprint arXiv:1607.02986 , year=

    A birthday repetition theorem and complexity of approximating dense CSPs , author=. arXiv preprint arXiv:1607.02986 , year=

    arXiv

  90. [98]

    Dinur and D

    I. Dinur and D. Steurer , title =. Symposium on Theory of Computing,

  91. [99]

    Lund and M

    C. Lund and M. Yannakakis , title =. Journal of the

  92. [100]

    47th International Colloquium on Automata, Languages, and Programming (ICALP 2020) , year=

    Parameterized Inapproximability for Steiner Orientation by Gap Amplification , author=. 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020) , year=

    2020

  93. [101]

    Journal of the ACM (JACM) , volume=

    The parameterized complexity of the k -biclique problem , author=. Journal of the ACM (JACM) , volume=. 2018 , publisher=

    2018

  94. [102]

    2013 , publisher=

    Fundamentals of parameterized complexity , author=. 2013 , publisher=

    2013

  95. [103]

    International Symposium on Algorithms and Computation , year=

    On the Parameterized Intractability of Determinant Maximization , author=. International Symposium on Algorithms and Computation , year=

  96. [104]

    Revisiting Alphabet Reduction in

    Guruswami, Venkatesan and Opr. Revisiting Alphabet Reduction in. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020) , pages =. 2020 , volume =. doi:10.4230/LIPIcs.APPROX/RANDOM.2020.34 , annote =

    2020 doi

  97. [105]

    ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network , booktitle =

    Irit Dinur and Pasin Manurangsi , editor =. ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network , booktitle =. 2018 , url =. doi:10.4230/LIPICS.ITCS.2018.36 , timestamp =

    2018 doi

  98. [106]

    ACM Trans

    Chitnis, Rajesh and Feldmann, Andreas Emil and Manurangsi, Pasin , title =. ACM Trans. Algorithms , month =. 2021 , issue_date =. doi:10.1145/3447584 , abstract =

    2021 doi

  99. [107]

    Downey, Rodney G and Fellows, Michael R , title =

  100. [108]

    Springer

    Flum, J. Parameterized Complexity Theory , publisher = "Springer", year =

  101. [109]

    International Workshop on Parameterized and Exact Computation , pages=

    On parameterized approximability , author=. International Workshop on Parameterized and Exact Computation , pages=. 2006 , organization=

    2006

  102. [110]

    The Computer Journal , volume=

    Parameterized complexity and approximation algorithms , author=. The Computer Journal , volume=. 2008 , publisher=

    2008

  103. [111]

    Journal of the ACM (JACM) , volume=

    A threshold of n for approximating set cover , author=. Journal of the ACM (JACM) , volume=. 1998 , publisher=

    1998

  104. [112]

    A Note on Max k-Vertex Cover: Faster

    Pasin Manurangsi , editor =. A Note on Max k-Vertex Cover: Faster. 2nd Symposium on Simplicity in Algorithms,. 2019 , url =. doi:10.4230/OASIcs.SOSA.2019.15 , timestamp =

    2019 doi

  105. [113]

    Vincent Cohen. Tight. 46th International Colloquium on Automata, Languages, and Programming,. 2019 , url =. doi:10.4230/LIPIcs.ICALP.2019.42 , timestamp =

    2019 doi

  106. [114]

    A Constant-Factor Approximation Algorithm for the k -Median Problem , journal =

    Moses Charikar and Sudipto Guha and. A Constant-Factor Approximation Algorithm for the k -Median Problem , journal =. 2002 , url =. doi:10.1006/jcss.2002.1882 , timestamp =

    2002 doi

  107. [115]

    Better Guarantees for k-Means and

    Sara Ahmadian and Ashkan Norouzi. Better Guarantees for k-Means and. 2020 , url =. doi:10.1137/18M1171321 , timestamp =

    2020 doi

  108. [116]

    Mount and Nathan S

    Tapas Kanungo and David M. Mount and Nathan S. Netanyahu and Christine D. Piatko and Ruth Silverman and Angela Y. Wu , title =. Comput. Geom. , volume =. 2004 , url =. doi:10.1016/j.comgeo.2004.03.003 , timestamp =

    2004 doi

  109. [117]

    Pensyl and Bartosz Rybicki and Aravind Srinivasan and Khoa Trinh , title =

    Jaroslaw Byrka and Thomas W. Pensyl and Bartosz Rybicki and Aravind Srinivasan and Khoa Trinh , title =. 2017 , url =. doi:10.1145/2981561 , timestamp =

    2017 doi

  110. [118]

    2016 , url =

    Shi Li and Ola Svensson , title =. 2016 , url =. doi:10.1137/130938645 , timestamp =

    2016 doi

  111. [119]

    Fixed-Parameter Approximation Schemes for Weighted Flowtime , booktitle =

    Andreas Wiese , editor =. Fixed-Parameter Approximation Schemes for Weighted Flowtime , booktitle =. 2018 , url =. doi:10.4230/LIPIcs.APPROX-RANDOM.2018.28 , timestamp =

    2018 doi

  112. [120]

    Piotr Skowron and Piotr Faliszewski , title =. J. Artif. Intell. Res. , volume =. 2017 , url =. doi:10.1613/jair.5628 , timestamp =

    2017 doi

  113. [121]

    Euiwoong Lee , title =. Math. Program. , volume =. 2019 , url =. doi:10.1007/s10107-018-1255-7 , timestamp =

    2019 doi

  114. [122]

    Parameterized Complexity and Approximation Algorithms , journal =

    D. Parameterized Complexity and Approximation Algorithms , journal =. 2008 , url =. doi:10.1093/comjnl/bxm048 , timestamp =

    2008 doi

  115. [123]

    Demaine and Mohammad Taghi Hajiaghayi and Ken

    Erik D. Demaine and Mohammad Taghi Hajiaghayi and Ken. Algorithmic Graph Minor Theory: Decomposition, Approximation, and Coloring , booktitle =. 2005 , url =. doi:10.1109/SFCS.2005.14 , timestamp =

    2005 doi

  116. [124]

    Constant Approximating Parameterized

    Bingkai Lin and Xuandi Ren and Yican Sun and Xiuhan Wang , editor =. Constant Approximating Parameterized. Proceedings of the 2023. 2023 , url =. doi:10.1137/1.9781611977554.ch126 , timestamp =

    2023 doi

  117. [125]

    On Lower Bounds of Approximating Parameterized k-Clique , booktitle =

    Bingkai Lin and Xuandi Ren and Yican Sun and Xiuhan Wang , editor =. On Lower Bounds of Approximating Parameterized k-Clique , booktitle =. 2022 , url =. doi:10.4230/LIPIcs.ICALP.2022.90 , timestamp =

    2022 doi

  118. [126]

    CoRR , volume =

    Yijia Chen and Yi Feng and Bundit Laekhanukit and Yanlin Liu , title =. CoRR , volume =. 2023 , url =. doi:10.48550/arXiv.2304.07516 , eprinttype =. 2304.07516 , timestamp =

    2023 doi arXiv

  119. [127]

    2022 , url =

    Almost Polynomial Factor Inapproximability for Parameterized k-Clique , booktitle =. 2022 , url =. doi:10.4230/LIPIcs.CCC.2022.6 , timestamp =

    2022 doi

  120. [128]

    Chitnis and M

    R. Chitnis and M. T. Hajiaghayi and G. Kortsarz , title =. Parameterized and Exact Computation - 8th International Symposium,

  121. [129]

    Applications of Random Algebraic Constructions to Hardness of Approximation , booktitle =

    Boris Bukh and. Applications of Random Algebraic Constructions to Hardness of Approximation , booktitle =. 2021 , url =. doi:10.1109/FOCS52979.2021.00032 , timestamp =

    2021 doi

  122. [130]

    M. T. Hajiaghayi and R. Khandekar and G. Kortsarz , title =. CoRR , volume =

  123. [131]

    37th Computational Complexity Conference (CCC 2022) , volume=

    Almost polynomial factor inapproximability for parameterized k-clique , author=. 37th Computational Complexity Conference (CCC 2022) , volume=

    2022

  124. [132]

    Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science , pages=

    On hardness of approximating the parameterized clique problem , author=. Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science , pages=

    2016

  125. [133]

    Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms , pages=

    Parameterized complexity and approximability of directed odd cycle transversal , author=. Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms , pages=. 2020 , organization=

    2020

  126. [134]

    The Hardness of Approximate Optima in Lattices, Codes, and Systems of Linear Equations , journal =

    Sanjeev Arora and L. The Hardness of Approximate Optima in Lattices, Codes, and Systems of Linear Equations , journal =. 1997 , url =. doi:10.1006/JCSS.1997.1472 , timestamp =

    1997 doi

  127. [135]

    Algorithms , volume=

    A survey on approximation in parameterized complexity: Hardness and algorithms , author=. Algorithms , volume=. 2020 , publisher=

    2020

  128. [136]

    Parameterized Approximation Schemes for Clustering with General Norm Objectives , journal =

    Fateme Abbasi and Sandip Banerjee and Jaroslaw Byrka and Parinya Chalermsook and Ameet Gadekar and Kamyar Khodamoradi and D. Parameterized Approximation Schemes for Clustering with General Norm Objectives , journal =

  129. [137]

    Journal of the ACM , year=

    Pliability and Approximating Max-CSPs , author=. Journal of the ACM , year=

  130. [138]

    2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS) , pages=

    Faster exact and approximate algorithms for k-cut , author=. 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS) , pages=. 2018 , organization=

    2018

  131. [139]

    A Parameterized Approximation Scheme for Min k -Cut , booktitle =

    Daniel Lokshtanov and Saket Saurabh and Vaishali Surianarayanan , editor =. A Parameterized Approximation Scheme for Min k -Cut , booktitle =

  132. [140]

    Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms , pages=

    An FPT algorithm beating 2-approximation for k-cut , author=. Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms , pages=. 2018 , organization=

    2018

  133. [141]

    A nearly 5/3-approximation

    Kawarabayashi, Ken-ichi and Lin, Bingkai , booktitle=. A nearly 5/3-approximation. 2020 , organization=

    2020

  134. [142]

    Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms , pages=

    Tight running time lower bounds for strong inapproximability of maximum k -coverage, unique set cover and related problems (via t -wise agreement testing theorem) , author=. Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms , pages=. 2020 , organization=

    2020

  135. [143]

    Algorithmica , volume=

    On subexponential and FPT-time inapproximability , author=. Algorithmica , volume=. 2015 , publisher=

    2015

  136. [144]

    Analyzing Boolean functions on the biased hypercube via higher-dimensional agreement tests: [Extended abstract] , booktitle =

    Irit Dinur and Yuval Filmus and Prahladh Harsha , editor =. Analyzing Boolean functions on the biased hypercube via higher-dimensional agreement tests: [Extended abstract] , booktitle =. 2019 , url =. doi:10.1137/1.9781611975482.128 , timestamp =

    2019 doi

  137. [145]

    Moshkovitz , title =

    D. Moshkovitz , title =. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 15th International Workshop,

  138. [146]

    Efficient approximation of MIN SET COVER by ``low-complexity" exponential algorithms , author=

  139. [147]

    Information Processing Letters , volume=

    Exponential-time approximation of weighted set cover , author=. Information Processing Letters , volume=. 2009 , publisher=

    2009

  140. [148]

    On the possibility of faster

    P. On the possibility of faster. Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms , pages=. 2010 , organization=

    2010

  141. [149]

    33rd International Symposium on Algorithms and Computation (ISAAC 2022) , year=

    On the Parameterized Intractability of Determinant Maximization , author=. 33rd International Symposium on Algorithms and Computation (ISAAC 2022) , year=

    2022

  142. [150]

    Parameterized Inapproximability of the Minimum Distance Problem over all Fields and the Shortest Vector Problem in all _p Norms , booktitle =

    Huck Bennett and Mahdi Cheraghchi and Venkatesan Guruswami and Jo. Parameterized Inapproximability of the Minimum Distance Problem over all Fields and the Shortest Vector Problem in all _p Norms , booktitle =. 2023 , url =. doi:10.1145/3564246.3585214 , timestamp =

    2023 doi

  143. [151]

    Distributed

    Abboud, Amir and Rubinstein, Aviad and Williams, Ryan , booktitle=. Distributed. 2017 , organization=

    2017

  144. [152]

    ACM Transactions on Algorithms (TALG) , volume=

    Algorithmic construction of sets for k-restrictions , author=. ACM Transactions on Algorithms (TALG) , volume=. 2006 , publisher=

    2006

  145. [153]

    2011 , pages = "148-151", chapter = 10, publisher=

    Extremal combinatorics: with applications in computer science , author=. 2011 , pages = "148-151", chapter = 10, publisher=

    2011

  146. [154]

    Vadhan and Avi Wigderson , title =

    Omer Reingold and Salil P. Vadhan and Avi Wigderson , title =. 41st Annual Symposium on Foundations of Computer Science,. 2000 , url =

    2000

  147. [155]

    Deterministic Simulation in

    Mikl. Deterministic Simulation in. Proceedings of the 19th Annual. 1987 , url =

    1987

  148. [156]

    1996 , url =

    Ronitt Rubinfeld and Madhu Sudan , title =. 1996 , url =

    1996

  149. [157]

    Computational Complexity , volume=

    Derandomized graph products , author=. Computational Complexity , volume=. 1995 , publisher=

    1995

  150. [158]

    2009 , url =

    Sanjeev Arora and Boaz Barak , title =. 2009 , url =

    2009

  151. [159]

    Daniel Lokshtanov and M. S. Ramanujan and Saket Saurabh and Meirav Zehavi , editor =. Parameterized Complexity and Approximability of Directed Odd Cycle Transversal , booktitle =

  152. [160]

    On a Vizing-like Conjecture for Direct Product Graphs , year =

    Klav. On a Vizing-like Conjecture for Direct Product Graphs , year =. doi:10.1016/0012-365X(96)00032-5 , journal =

    doi

  153. [161]

    Anderson, I. , year=. Béla Bollobás, Extremal Graph Theory (Academic Press, 1978), 488 pp., £19·50. , volume=. Proceedings of the Edinburgh Mathematical Society , publisher=. doi:10.1017/S0013091500003709 , number=

    1978 doi

Pith tools

Reviewed July 10, 2026 · model on record in the stance chip above.