arxiv: 2605.10778 · v1 · submitted 2026-05-11 · 💻 cs.CC

Recognition: no theorem link

When Does Sparsity Help for k-Independent Set in Hypergraphs and Other Boolean CSPs?

Timo Fritsch , Marvin K\"unnemann , Mirza Redzic , Julian Stie{\ss}

Authors on Pith no claims yet

Pith reviewed 2026-05-12 04:37 UTC · model grok-4.3

classification 💻 cs.CC

keywords k-independent sethypergraphsBoolean CSPsparsitytime complexitymatrix multiplicationconditional lower boundsphase transition

0 comments

The pith

Sparsity affects k-independent set in hypergraphs only below the Turán threshold, where a new algorithm becomes conditionally optimal under clique hypotheses.

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

The paper examines how the number of hyperedges m affects the time to find a size-k independent set in an n-node hypergraph. Turán's theorem makes the problem trivial for m = O(n^{2-ε}), but when m grows as Θ(n^γ) for γ ≥ 2 the authors give an algorithm running in O(min{n^{ω k /3} + m^{k/3}, n^k}) time for k divisible by 3. This running time is shown to be essentially the best possible assuming the k-clique and 3-uniform hyperclique hypotheses. The analysis extends to Boolean CSPs with binary constraints, yielding a full classification of sparsity effects, a tight bound for the NAND-plus-implication family, and several families that display a sharp phase transition from trivial to near-brute-force complexity.

Core claim

Above the Turán threshold m = Θ(n^γ) for γ ≥ 2, k-independent set admits an algorithm with running time O(min{n^{ω k /3} + m^{k/3}, n^k}) (k divisible by 3) that is essentially conditionally optimal under the k-clique and 3-uniform hyperclique hypotheses. For Boolean CSPs the influence of sparsity is classified for all binary constraint families, including a conditionally tight algorithm for NAND and implication constraints with time Θ(m^{ω k /6 ± c}) and a large class of families that exhibit a sharp phase transition at a density γ_F: trivial below the threshold and Θ(n^{k ± c}) above it. Combinations of constraints can require strictly higher time than either constraint alone.

What carries the argument

A sparsity-sensitive grouping algorithm that partitions variables into triples and applies fast matrix multiplication to detect consistent partial assignments in the regime m = Θ(n^γ) for γ ≥ 2.

Load-bearing premise

The optimality claims rest on the k-clique hypothesis and the 3-uniform hyperclique hypothesis.

What would settle it

An algorithm that detects k-cliques in time o(n^{ω k /3}) or solves 3-uniform hyperclique in time o(m^{k/3}) would show that the given hypergraph algorithm is not conditionally optimal.

read the original abstract

Consider the fundamental task of finding independent sets of (constant) size $k$ in a given $n$-node hypergraph. How is the time complexity affected by the sparsity of the input, i.e., the number of hyperedges $m$? Tur\'{a}n's theorem implies that the problem is trivial if $m=O(n^{2-\epsilon})$ for some $\epsilon> 0$. Above that threshold (i.e., if $m=\Theta(n^\gamma)$ for some $\gamma \ge 2$), we give a perhaps surprising algorithm with running time $O\left(\min\left\{n^{\frac{\omega}{3}k} + m^{k/3}, n^k\right\}\right)$ (for $k$ divisible by 3), which is essentially conditionally optimal for all $\gamma\ge 2$, assuming the $k$-clique and 3-uniform hyperclique hypotheses (here, $\omega<2.372$ denotes the matrix multiplication exponent). In fact, we obtain a more detailed time complexity, sensitive to the arity distribution of the hyperedges. To study such phenomena in more generality, we study the time complexity of finding solutions of (constant) size $k$ in sparse instances of Boolean constraint satisfaction problems, where $n$ and $m$ denote the number of variables and constraints. Our results include an essentially full classification of the influence of sparsity for Boolean constraint families of binary arity. Of particular technical interest is a conditionally tight algorithm for the family consisting of the binary NAND and Implication constraints, with a running time of $\Theta(m^{\omega k/6 \pm c})$. Further, we identify a large class of constraint families $F$ that exhibits a sharp phase transition: there is a threshold $\gamma_F$ such that the problem is trivial for $m=O(n^{\gamma_F-\epsilon})$, but requires essentially brute-force running time $\Theta(n^{k\pm c})$ for $m=\Omega(n^{\gamma_F})$, assuming the 3-uniform hyperclique hypothesis. Notably, in many cases the combination of constraints display higher time complexity than either constraint alone.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper maps sparsity effects for k-hypergraph independent set and binary Boolean CSPs, giving a new algorithm that beats brute force above the Turán threshold and a full classification of when density forces near-brute-force time.

read the letter

The core result is an algorithm for k-independent set in hypergraphs that runs in O(min{n^{ωk/3} + m^{k/3}, n^k}) time when k is divisible by 3 and m is at least quadratic in n. This is presented as conditionally optimal under the k-clique and 3-uniform hyperclique hypotheses, and the paper extends the same style of analysis to a complete classification of sparsity thresholds for every binary-arity Boolean constraint family. The NAND-plus-implication case gets its own tight bound of Θ(m^{ωk/6 ± c}). Combinations of constraints can require more time than either one alone, which is a useful negative observation. The handling of arity distributions in the hypergraph algorithm is the part that feels genuinely new; it lets the running time switch between n-based and m-based matrix multiplication depending on how the edges are sized. That produces a clean phase transition: below the Turán threshold the problem is trivial, and above it the new bound holds for all γ ≥ 2. The classification for binary CSPs is exhaustive within that arity limit and rests on the same hypotheses for the hardness direction. The soft spots are the usual ones for this style of work. All optimality claims are conditional, so the lower-bound side collapses if the clique hypotheses fail. The ±c terms hide some lower-order factors whose exact size is not visible in the abstract. The results stop at binary arity, leaving higher-arity CSPs open. Nothing in the stated claims looks internally inconsistent or circular. This is for researchers who already follow fine-grained complexity results on hypergraphs and sparse CSPs. A reader comfortable with matrix-multiplication reductions will find the extensions straightforward to follow. The algorithmic construction and the case analysis are concrete enough that the paper deserves a serious referee even if the proofs need polishing on the error terms.

Referee Report

0 major / 3 minor

Summary. The paper examines the effect of input sparsity on the complexity of finding constant-sized independent sets in hypergraphs and solutions to Boolean CSPs. Above the Turán threshold, it presents an algorithm for k-hypergraph independent set with running time O(min{n^{(ω k)/3} + m^{k/3}, n^k}) for k divisible by 3, which is conditionally optimal assuming the k-clique and 3-uniform hyperclique hypotheses. It provides an essentially complete classification of sparsity effects for binary-arity Boolean CSP families, including sharp phase transitions for certain constraint sets and cases where constraint combinations increase the time complexity.

Significance. If correct, the results are significant for fine-grained complexity theory. They show that sparsity enables faster algorithms via matrix multiplication even in dense regimes, with the running time depending on the distribution of hyperedge arities. The identification of phase transitions and the higher complexity of combined constraints are insightful. The work includes explicit algorithms and conditional lower bounds under standard hypotheses, strengthening the classification.

minor comments (3)

The abstract uses '± c' in the running time Θ(m^{ω k/6 ± c}) for the NAND/Implication family; this constant should be defined explicitly (e.g., its dependence on k or a concrete bound) in the statement of the result.
The phrase 'essentially conditionally optimal' in the abstract and main claims should be sharpened by explicitly matching the achieved exponents to those in the k-clique and 3-uniform hyperclique lower bounds.
Citations to the original statements of the k-clique hypothesis and 3-uniform hyperclique hypothesis should be added when these are first invoked.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive review and recommendation of minor revision. The referee's summary accurately captures our main results on the effect of sparsity for k-independent set in hypergraphs and the classification for binary Boolean CSPs.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper presents explicit algorithmic constructions for k-independent set and Boolean CSPs that rely on matrix-multiplication techniques applied to auxiliary graphs or hypergraphs whose sizes are bounded by functions of the input parameters n and m (or m^{1/3} in the 3-uniform case). These constructions are independent of the target running-time bounds. The matching conditional lower bounds are derived from standard external fine-grained hypotheses (k-clique hypothesis and 3-uniform hyperclique hypothesis) that are invoked but not proven inside the paper. The phase-transition analysis for binary-arity CSP families proceeds by exhaustive case distinction on arity distributions and constraint combinations, with hardness sides explicitly citing the external hypotheses rather than any internal self-definition, fitted parameter, or self-citation chain. No step reduces a claimed result to an input by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claims rest on Turán's theorem (standard) and two standard fine-grained hardness hypotheses; no free parameters or new entities are introduced.

axioms (2)

domain assumption k-clique hypothesis
Invoked to establish conditional optimality of the upper bound for γ≥2.
domain assumption 3-uniform hyperclique hypothesis
Used for the phase-transition lower bounds and the NAND+Implication tight bound.

pith-pipeline@v0.9.0 · 5718 in / 1356 out tokens · 43185 ms · 2026-05-12T04:37:51.431540+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

62 extracted references · 62 canonical work pages

[1]

New bounds for matrix multiplication: from alpha to omega,

Virginia. New Bounds for Matrix Multiplication: from Alpha to Omega , booktitle =. 2024 , url =. doi:10.1137/1.9781611977912.134 , timestamp =

work page doi:10.1137/1.9781611977912.134 2024
[2]

Parameterized complexity of constraint satisfaction problems , journal =

D. Parameterized complexity of constraint satisfaction problems , journal =. 2005 , url =. doi:10.1007/s00037-005-0195-9 , timestamp =

work page doi:10.1007/s00037-005-0195-9 2005
[3]

Finding Small Satisfying Assignments Faster Than Brute Force:

Marvin K. Finding Small Satisfying Assignments Faster Than Brute Force:. 35th Computational Complexity Conference,. 2020 , url =. doi:10.4230/LIPIcs.CCC.2020.27 , timestamp =

work page doi:10.4230/lipics.ccc.2020.27 2020
[4]

Schaefer , editor =

Thomas J. Schaefer , editor =. The Complexity of Satisfiability Problems , booktitle =. 1978 , url =. doi:10.1145/800133.804350 , timestamp =

work page doi:10.1145/800133.804350 1978
[5]

On Generating All Solutions of Generalized Satisfiability Problems , journal =

Nadia Creignou and Jean. On Generating All Solutions of Generalized Satisfiability Problems , journal =. 1997 , url =. doi:10.1051/ita/1997310604991 , timestamp =

work page doi:10.1051/ita/1997310604991 1997
[6]

Solving Linear Equations Parameterized by Hamming Weight , journal =

Vikraman Arvind and Johannes K. Solving Linear Equations Parameterized by Hamming Weight , journal =. 2016 , url =. doi:10.1007/s00453-015-0098-3 , timestamp =

work page doi:10.1007/s00453-015-0098-3 2016
[7]

Strang, Gilbert , biburl =

work page
[8]

The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory , journal =

Feder, Tom\'. The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory , journal =. 1998 , doi =

work page 1998
[9]

Bulatov , editor =

Andrei A. Bulatov , editor =. A Dichotomy Theorem for Nonuniform CSPs , booktitle =. 2017 , url =. doi:10.1109/FOCS.2017.37 , timestamp =

work page doi:10.1109/focs.2017.37 2017
[10]

A Proof of

Dmitriy Zhuk , editor =. A Proof of. 58th. 2017 , url =. doi:10.1109/FOCS.2017.38 , timestamp =

work page doi:10.1109/focs.2017.38 2017
[11]

The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 22201) , journal =

Martin Grohe and Venkatesan Guruswami and D. The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 22201) , journal =. 2022 , url =. doi:10.4230/DAGREP.12.5.112 , timestamp =

work page doi:10.4230/dagrep.12.5.112 2022
[12]

Nadia Creignou and Miki Hermann , title =. Inf. Comput. , volume =. 1996 , url =. doi:10.1006/INCO.1996.0016 , timestamp =

work page doi:10.1006/inco.1996.0016 1996
[13]

Bulatov , title =

Andrei A. Bulatov , title =. 43rd Symposium on Foundations of Computer Science. 2002 , url =. doi:10.1109/SFCS.2002.1181990 , timestamp =

work page doi:10.1109/sfcs.2002.1181990 2002
[14]

and Laaser, William T

Jones, Neil D. and Laaser, William T. , title =. Proceedings of the Sixth Annual ACM Symposium on Theory of Computing , pages =. 1974 , isbn =. doi:10.1145/800119.803883 , abstract =

work page doi:10.1145/800119.803883 1974
[15]

On the complexity of the subgraph problem , url =

Jaroslav Nešetřil and Svatopluk Poljak , journal =. On the complexity of the subgraph problem , url =

work page
[16]

Optimal Implementation of Watched Literals and More General Techniques , author=. J. Artif. Intell. Res. , year=

work page
[17]

Brailsford and Chris N

Sally C. Brailsford and Chris N. Potts and Barbara M. Smith , keywords =. Constraint satisfaction problems: Algorithms and applications , journal =. 1999 , issn =. doi:https://doi.org/10.1016/S0377-2217(98)00364-6 , url =

work page doi:10.1016/s0377-2217(98)00364-6 1999
[18]

45(1):5–32, 2001

Cheng. Applying constraint satisfaction techniques to job shop scheduling , journal =. 1997 , url =. doi:10.1023/A\ timestamp =

work page doi:10.1023/a 1997
[19]

Mackworth , title =

Alan K. Mackworth , title =. Artif. Intell. , volume =. 1992 , url =. doi:10.1016/0004-3702(92)90003-G , timestamp =

work page doi:10.1016/0004-3702(92)90003-g 1992
[20]

Lars Jaffke and Bart M. P. Jansen , editor =. Fine-Grained Parameterized Complexity Analysis of Graph Coloring Problems , booktitle =. 2017 , url =. doi:10.1007/978-3-319-57586-5\_29 , timestamp =

work page doi:10.1007/978-3-319-57586-5 2017
[21]

Fine-Grained Complexity of Analyzing Compressed Data: Quantifying Improvements over Decompress-and-Solve , booktitle =

Amir Abboud and Arturs Backurs and Karl Bringmann and Marvin K. Fine-Grained Complexity of Analyzing Compressed Data: Quantifying Improvements over Decompress-and-Solve , booktitle =. 2017 , url =. doi:10.1109/FOCS.2017.26 , timestamp =

work page doi:10.1109/focs.2017.26 2017
[22]

36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019) , pages =

Bringmann, Karl , title =. 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019) , pages =. 2019 , volume =. doi:10.4230/LIPIcs.STACS.2019.4 , annote =

work page doi:10.4230/lipics.stacs.2019.4 2019
[23]

Multivariate Fine-Grained Complexity of Longest Common Subsequence , booktitle =

Karl Bringmann and Marvin K. Multivariate Fine-Grained Complexity of Longest Common Subsequence , booktitle =. 2018 , url =. doi:10.1137/1.9781611975031.79 , timestamp =

work page doi:10.1137/1.9781611975031.79 2018
[24]

Cygan, F

Marek Cygan and Fedor V. Fomin and Lukasz Kowalik and Daniel Lokshtanov and D. Parameterized Algorithms , publisher =. 2015 , url =. doi:10.1007/978-3-319-21275-3 , isbn =

work page doi:10.1007/978-3-319-21275-3 2015
[25]

A Refined Laser Method and Faster Matrix Multiplication , booktitle =

Josh Alman and Virginia Vassilevska Williams , editor =. A Refined Laser Method and Faster Matrix Multiplication , booktitle =. 2021 , url =. doi:10.1137/1.9781611976465.32 , timestamp =

work page doi:10.1137/1.9781611976465.32 2021
[26]

CoRR , volume =

Ran Duan and Hongxun Wu and Renfei Zhou , title =. CoRR , volume =. 2022 , url =. doi:10.48550/ARXIV.2210.10173 , eprinttype =. 2210.10173 , timestamp =

work page doi:10.48550/arxiv.2210.10173 2022
[27]

2015 , url =

Mathias Weller and Annie Chateau and Rodolphe Giroudeau , title =. 2015 , url =. doi:10.1186/1471-2105-16-S14-S2 , timestamp =

work page doi:10.1186/1471-2105-16-s14-s2 2015
[28]

Williamson , editor =

Sanjeev Khanna and Madhu Sudan and David P. Williamson , editor =. A Complete Classification of the Approximability of Maximization Problems Derived from Boolean Constraint Satisfaction , booktitle =. 1997 , url =. doi:10.1145/258533.258538 , timestamp =

work page doi:10.1145/258533.258538 1997
[29]

Introduction to the theory of complexity and approximation algorithms

Jansen, Thomas. Introduction to the theory of complexity and approximation algorithms. Lectures on Proof Verification and Approximation Algorithms. 1998. doi:10.1007/BFb0053011

work page doi:10.1007/bfb0053011 1998
[30]

The implicit graph conjecture is false

Marvin K. A tight (non-combinatorial) conditional lower bound for Klee's Measure Problem in 3D , booktitle =. 2022 , url =. doi:10.1109/FOCS54457.2022.00059 , timestamp =

work page doi:10.1109/focs54457.2022.00059 2022
[31]

Towards Optimal Output-Sensitive Clique Listing or: Listing Cliques from Smaller Cliques , booktitle =

Mina Dalirrooyfard and Surya Mathialagan and Virginia. Towards Optimal Output-Sensitive Clique Listing or: Listing Cliques from Smaller Cliques , booktitle =. 2024 , url =. doi:10.1145/3618260.3649663 , timestamp =

work page doi:10.1145/3618260.3649663 2024
[32]

Tight Hardness for Shortest Cycles and Paths in Sparse Graphs , booktitle =

Andrea Lincoln and Virginia. Tight Hardness for Shortest Cycles and Paths in Sparse Graphs , booktitle =. 2018 , url =. doi:10.1137/1.9781611975031.80 , timestamp =

work page doi:10.1137/1.9781611975031.80 2018
[33]

Faster Combinatorial k-Clique Algorithms , booktitle =

Amir Abboud and Nick Fischer and Yarin Shechter , editor =. Faster Combinatorial k-Clique Algorithms , booktitle =. 2024 , url =. doi:10.1007/978-3-031-55598-5\_13 , timestamp =

work page doi:10.1007/978-3-031-55598-5 2024
[34]

On an extremal problem in graph theory. Mat. Fiz. Lapok 48 436--452 , author=. 1941 , publisher=

work page 1941
[35]

Surveys in combinatorics , volume=

Hypergraph turan problems , author=. Surveys in combinatorics , volume=. 2011 , publisher=

work page 2011
[36]

2015 IEEE 56th Annual Symposium on Foundations of Computer Science , pages=

Quadratic conditional lower bounds for string problems and dynamic time warping , author=. 2015 IEEE 56th Annual Symposium on Foundations of Computer Science , pages=. 2015 , organization=

work page 2015
[37]

Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=

The effect of sparsity on k-dominating set and related first-order graph properties , author=. Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2024 , organization=

work page 2024
[38]

19th International Symposium on Parameterized and Exact Computation (IPEC 2024) , pages=

Fine-Grained Complexity of Multiple Domination and Dominating Patterns in Sparse Graphs , author=. 19th International Symposium on Parameterized and Exact Computation (IPEC 2024) , pages=. 2024 , organization=

work page 2024
[39]

Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs , booktitle =

Amir Abboud and Virginia. Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs , booktitle =. 2016 , url =. doi:10.1137/1.9781611974331.CH28 , timestamp =

work page doi:10.1137/1.9781611974331.ch28 2016
[40]

32 Anupam Gupta, Ravishankar Krishnaswamy, Amit Kumar, and Debmalya Panigrahi

Liam Roditty and Virginia. Fast approximation algorithms for the diameter and radius of sparse graphs , booktitle =. 2013 , url =. doi:10.1145/2488608.2488673 , timestamp =

work page doi:10.1145/2488608.2488673 2013
[41]

If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser , journal =

Amir Abboud and Arturs Backurs and Virginia. If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser , journal =. 2018 , url =. doi:10.1137/16M1061771 , timestamp =

work page doi:10.1137/16m1061771 2018
[42]

Linear Time Algorithms for Knapsack Problems with Bounded Weights , journal =

David Pisinger , keywords =. Linear Time Algorithms for Knapsack Problems with Bounded Weights , journal =. 1999 , issn =. doi:https://doi.org/10.1006/jagm.1999.1034 , url =

work page doi:10.1006/jagm.1999.1034 1999
[43]

Ryan Williams , advisor =

R. Ryan Williams , advisor =. Algorithms and resource requirements for fundamental problems , year =

work page
[44]

27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016) , pages =

Chang, Yi-Jun , title =. 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016) , pages =. 2016 , volume =. doi:10.4230/LIPIcs.CPM.2016.13 , annote =

work page doi:10.4230/lipics.cpm.2016.13 2016
[45]

Combinatorial Designs Meet Hypercliques: Higher Lower Bounds for Klee's Measure Problem and Related Problems in Dimensions d

Egor Gorbachev and Marvin K. Combinatorial Designs Meet Hypercliques: Higher Lower Bounds for Klee's Measure Problem and Related Problems in Dimensions d. 39th International Symposium on Computational Geometry, SoCG 2023, June 12-15, 2023, Dallas, Texas,. 2023 , url =. doi:10.4230/LIPICS.SOCG.2023.36 , timestamp =

work page doi:10.4230/lipics.socg.2023.36 2023
[46]

The implicit graph conjecture is false

Mina Dalirrooyfard and Virginia. Induced Cycles and Paths Are Harder Than You Think , booktitle =. 2022 , url =. doi:10.1109/FOCS54457.2022.00057 , timestamp =

work page doi:10.1109/focs54457.2022.00057 2022
[47]

The implicit graph conjecture is false

Mina Dalirrooyfard and Ce Jin and Virginia. Approximation Algorithms and Hardness for n-Pairs Shortest Paths and All-Nodes Shortest Cycles , booktitle =. 2022 , url =. doi:10.1109/FOCS54457.2022.00034 , timestamp =

work page doi:10.1109/focs54457.2022.00034 2022
[48]

Listing, Verifying and Counting Lowest Common Ancestors in DAGs: Algorithms and Fine-Grained Lower Bounds , booktitle =

Surya Mathialagan and Virginia. Listing, Verifying and Counting Lowest Common Ancestors in DAGs: Algorithms and Fine-Grained Lower Bounds , booktitle =. 2022 , url =. doi:10.4230/LIPICS.ICALP.2022.94 , timestamp =

work page doi:10.4230/lipics.icalp.2022.94 2022
[49]

More consequences of falsifying

Amir Abboud and Karl Bringmann and Holger Dell and Jesper Nederlof , editor =. More consequences of falsifying. Proceedings of the 50th Annual. 2018 , url =. doi:10.1145/3188745.3188938 , timestamp =

work page doi:10.1145/3188745.3188938 2018
[50]

Worst-Case and Average-Case Hardness of Hypercycle and Database Problems , booktitle =

Cheng. Worst-Case and Average-Case Hardness of Hypercycle and Database Problems , booktitle =. 2025 , url =. doi:10.4230/LIPICS.ICALP.2025.81 , timestamp =

work page doi:10.4230/lipics.icalp.2025.81 2025
[51]

The Role of Regularity in (Hyper-)Clique Detection and Implications for Optimizing Boolean CSPs , booktitle =

Nick Fischer and Marvin K. The Role of Regularity in (Hyper-)Clique Detection and Implications for Optimizing Boolean CSPs , booktitle =. 2025 , url =. doi:10.4230/LIPICS.ICALP.2025.78 , timestamp =

work page doi:10.4230/lipics.icalp.2025.78 2025
[52]

25 [CHY23] Timothy M

Timothy M. Chan and Qizheng He and Yuancheng Yu , editor =. On the Fine-Grained Complexity of Small-Size Geometric Set Cover and Discrete k-Center for Small k , booktitle =. 2023 , url =. doi:10.4230/LIPICS.ICALP.2023.34 , timestamp =

work page doi:10.4230/lipics.icalp.2023.34 2023
[53]

A Fine-Grained Analogue of Schaefer's Theorem in

Karl Bringmann and Nick Fischer and Marvin K. A Fine-Grained Analogue of Schaefer's Theorem in. 34th Computational Complexity Conference,. 2019 , url =. doi:10.4230/LIPICS.CCC.2019.31 , timestamp =

work page doi:10.4230/lipics.ccc.2019.31 2019
[54]

Current Algorithms for Detecting Subgraphs of Bounded Treewidth Are Probably Optimal , booktitle =

Karl Bringmann and Jasper Slusallek , editor =. Current Algorithms for Detecting Subgraphs of Bounded Treewidth Are Probably Optimal , booktitle =. 2021 , url =. doi:10.4230/LIPICS.ICALP.2021.40 , timestamp =

work page doi:10.4230/lipics.icalp.2021.40 2021
[55]

Bulatov , title =

Andrei A. Bulatov , title =. J. 2013 , url =. doi:10.1145/2528400 , timestamp =

work page doi:10.1145/2528400 2013
[56]

Bulatov and D

Andrei A. Bulatov and D. Constraint Satisfaction Parameterized by Solution Size , journal =. 2014 , url =. doi:10.1137/120882160 , timestamp =

work page doi:10.1137/120882160 2014
[57]

Monochromatic Triangles, Triangle Listing and

Virginia. Monochromatic Triangles, Triangle Listing and. 61st. 2020 , url =. doi:10.1109/FOCS46700.2020.00078 , timestamp =

work page doi:10.1109/focs46700.2020.00078 2020
[58]

Towards polynomial lower bounds for dynamic problems , booktitle =

Mihai P. Towards polynomial lower bounds for dynamic problems , booktitle =. 2010 , url =. doi:10.1145/1806689.1806772 , timestamp =

work page doi:10.1145/1806689.1806772 2010
[59]

Fine-grained complexity for sparse graphs , booktitle =

Udit Agarwal and Vijaya Ramachandran , editor =. Fine-grained complexity for sparse graphs , booktitle =. 2018 , url =. doi:10.1145/3188745.3188888 , timestamp =

work page doi:10.1145/3188745.3188888 2018
[60]

Proceedings of the International Congress of Mathematicians (ICM 2018) , chapter =

József Balogh and Robert Morris and Wojciech Samotij , title =. Proceedings of the International Congress of Mathematicians (ICM 2018) , chapter =. 2018 , pages =. doi:10.1142/9789813272880_0172 , URL =

work page doi:10.1142/9789813272880_0172 2018
[61]

Algorithmic Applications of Hypergraph and Partition Containers , booktitle =

Or Zamir , editor =. Algorithmic Applications of Hypergraph and Partition Containers , booktitle =. 2023 , url =. doi:10.1145/3564246.3585163 , timestamp =

work page doi:10.1145/3564246.3585163 2023
[62]

Finding Four-Node Subgraphs in Triangle Time , booktitle =

Virginia. Finding Four-Node Subgraphs in Triangle Time , booktitle =. 2015 , url =. doi:10.1137/1.9781611973730.111 , timestamp =

work page doi:10.1137/1.9781611973730.111 2015