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

Julian Stie{\ss}; Marvin K\"unnemann; Mirza Red\v{z}i\'c; Nick Fischer

arxiv: 2505.17314 · v1 · submitted 2025-05-22 · 💻 cs.CC

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

Nick Fischer , Marvin K\"unnemann , Mirza Red\v{z}i\'c , Julian Stie{\ss} This is my paper

Pith reviewed 2026-05-22 02:29 UTC · model grok-4.3

classification 💻 cs.CC

keywords hyperclique detectionregular hypergraphsfine-grained complexityBoolean CSPconstraint optimizationk-nonzero assignmentshyperclique hypothesis

0 comments

The pith

Any fast algorithm for k-clique detection on regular hypergraphs extends to arbitrary instances with only a k-dependent overhead.

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

The paper proves that detecting a k-clique in a k-partite strongly regular h-uniform hypergraph is fine-grained equivalent to the same problem on general hypergraphs. An algorithm with running time f(k) n^{g(k)} on regular instances can be turned into one with time f'(k) n^{g(k)} on arbitrary instances. This equivalence is then used to classify the exact fine-grained complexity of finding an optimal assignment with exactly k nonzero variables in a Boolean CSP, with the outcome depending only on the maximum degree d of each constraint function.

Core claim

We show that any f(k)n^{g(k)}-time algorithm for detecting k-cliques in k-partite regular h-uniform hypergraphs transfers to an f'(k)n^{g(k)}-time algorithm for the general case, establishing a fine-grained equivalence between the h-uniform hyperclique hypothesis and its regular analogue. Equipped with this regularization result, we fully resolve the fine-grained complexity of optimizing Boolean CSPs over assignments with k non-zeros, showing linear-time solvability for d ≤ 1, equivalence to k-clique detection for d = 2, and exhaustive-search hardness for d ≥ 3 under the 3-uniform hyperclique hypothesis.

What carries the argument

A reduction that converts arbitrary k-partite h-uniform hypergraphs into strongly regular ones while preserving k-clique existence and the n^{g(k)} dependence on input size.

If this is right

Boolean CSP optimization with exactly k nonzeros runs in linear time when every constraint has maximum degree at most 1.
The same problem has time complexity equivalent to k-clique detection when maximum degree equals 2.
When maximum degree is 3 or higher the problem requires n^{\Omega(k)} time under the 3-uniform hyperclique hypothesis.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same regularization technique could simplify hardness proofs for other hypergraph problems that currently rely on non-regular instances.
Combinatorial design theory may supply additional regular instances that preserve fine-grained lower bounds for problems beyond clique detection.
The degree-based classification for k-nonzero CSPs suggests similar thresholds may exist for other parameterized optimization tasks on sparse constraints.

Load-bearing premise

The strong regularity condition on subsets of at most h-1 vertices can be preserved or enforced by reductions without changing the asymptotic time complexity.

What would settle it

An explicit family of k-partite h-uniform hypergraphs on which a k-clique algorithm succeeds in time f(k)n^{g(k)} for regular instances but cannot be converted by the paper's reduction into a comparable algorithm for some non-regular instances.

read the original abstract

Is detecting a $k$-clique in $k$-partite regular (hyper-)graphs as hard as in the general case? Intuition suggests yes, but proving this -- especially for hypergraphs -- poses notable challenges. Concretely, we consider a strong notion of regularity in $h$-uniform hypergraphs, where we essentially require that any subset of at most $h-1$ is incident to a uniform number of hyperedges. Such notions are studied intensively in the combinatorial block design literature. We show that any $f(k)n^{g(k)}$-time algorithm for detecting $k$-cliques in such graphs transfers to an $f'(k)n^{g(k)}$-time algorithm for the general case, establishing a fine-grained equivalence between the $h$-uniform hyperclique hypothesis and its natural regular analogue. Equipped with this regularization result, we then fully resolve the fine-grained complexity of optimizing Boolean constraint satisfaction problems over assignments with $k$ non-zeros. Our characterization depends on the maximum degree $d$ of a constraint function. Specifically, if $d\le 1$, we obtain a linear-time solvable problem, if $d=2$, the time complexity is essentially equivalent to $k$-clique detection, and if $d\ge 3$ the problem requires exhaustive-search time under the 3-uniform hyperclique hypothesis. To obtain our hardness results, the regularization result plays a crucial role, enabling a very convenient approach when applied carefully. We believe that our regularization result will find further applications in the future.

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 regularization equivalence for hypercliques is the real contribution and it lets them finish a degree-based trichotomy for the CSP optimization problems, but the reduction needs to preserve the exact exponent.

read the letter

The main thing to know is that this paper establishes fine-grained equivalence between k-clique detection in general h-uniform hypergraphs and in strongly regular ones, then leverages that to classify the complexity of optimizing Boolean CSPs with exactly k non-zeros based on the maximum degree d of the constraints. What they do well is complete the picture for these optimization problems. For d at most 1 it's linear time, for d exactly 2 it's as hard as k-clique detection, and for d three or more it's as hard as 3-uniform hyperclique under the corresponding hypothesis. The regularization result is the key enabler here, and it appears to be a fresh technical contribution that could apply elsewhere in design theory or hypergraph algorithms. The soft spot is around the reduction that goes from general instances to regular ones. The claim is that any algorithm for the regular case gives one for general with the same asymptotic form f(k) n to the g(k). But enforcing that every small subset has the same number of incident edges is a strong balancing act. If their method for doing this increases the vertex count by n to some constant power, even 1.1, then the exponent changes and the equivalence is not as tight. The abstract says it preserves the form, so they must have a way to do it with only n to the o(1) overhead, but this needs careful verification in the full proof. The CSP results depend on this step too. Overall this is for researchers in parameterized complexity and fine-grained algorithms who care about hypergraph problems and CSPs. A reader looking for new tools or completed classifications would find it useful. It has enough substance and novelty to merit a serious referee. I would recommend putting it through peer review rather than desk rejecting it.

Referee Report

2 major / 2 minor

Summary. The paper proves that k-clique detection in strongly regular k-partite h-uniform hypergraphs is fine-grained equivalent to the general case: any f(k)n^{g(k)}-time algorithm for the regular variant yields an f'(k)n^{g(k)}-time algorithm for arbitrary instances. It then applies this regularization result to obtain a trichotomy for the fine-grained complexity of optimizing Boolean CSPs over assignments with exactly k non-zeros, parameterized by the maximum degree d of the constraint function: linear time when d ≤ 1, equivalent to k-clique detection when d = 2, and requiring exhaustive-search time under the 3-uniform hyperclique hypothesis when d ≥ 3.

Significance. If the central transfer theorem holds with no change to the exponent g(k), the work gives a clean resolution of the fine-grained complexity for this family of Boolean CSPs, which is a substantive contribution to the area. The regularization lemma itself is a technical tool that may have further applications in hypergraph problems. The manuscript supplies explicit hardness constructions that rely on the new lemma, and the trichotomy is stated in terms of standard hypotheses.

major comments (2)

[Regularization lemma / transfer theorem] The transfer theorem (stated in the abstract and proved via the regularization lemma) asserts that the reduction from general to strongly regular instances preserves the exponent g(k), i.e., produces an instance of size n^{1+o(1)}. The construction must be checked to ensure that enforcing the strong regularity condition (every subset of size ≤ h-1 has identical degree) does not introduce a superlinear blow-up in the number of vertices or hyperedges; standard balancing techniques can produce |V'| = n^{1+Ω(1)} and would replace g(k) by c·g(k) for c > 1, breaking the claimed fine-grained equivalence. This point is load-bearing for both the hyperclique equivalence and the subsequent CSP hardness results.
[CSP hardness constructions] In the CSP hardness direction (d ≥ 3 case), the reduction from 3-uniform hyperclique detection relies on the same regularization step. It must be verified that the composed reduction still yields a subexponential blow-up only in the k parameter and not in n, so that the n^{Ω(k)} lower bound is preserved under the hypothesis.

minor comments (2)

[Introduction / Preliminaries] Clarify the precise definition of 'strong regularity' (uniform degree for all subsets of size at most h-1) with a short formal statement or example early in the paper.
Add a short paragraph comparing the new regularization technique to existing blow-up or design-based constructions in the literature on hypergraph regularity.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful and constructive report. The two major comments both concern the size blow-up in the regularization construction and its composition with the CSP reductions. We address them point-by-point below, clarifying the probabilistic analysis that keeps the blow-up at n^{1+o(1)}.

read point-by-point responses

Referee: The transfer theorem asserts that the reduction from general to strongly regular instances preserves the exponent g(k), i.e., produces an instance of size n^{1+o(1)}. The construction must be checked to ensure that enforcing the strong regularity condition does not introduce a superlinear blow-up; standard balancing techniques can produce |V'| = n^{1+Ω(1)} and would replace g(k) by c·g(k) for c > 1.

Authors: We agree that this is load-bearing. In the proof of the regularization lemma (Theorem 3.1), we do not rely on standard deterministic balancing. Instead we use a two-step randomized procedure: first sample a random subset S of vertices of size n·(1+ε) with ε = o(1), then for each (h-1)-tuple we add a small number of auxiliary hyperedges chosen uniformly from a fresh pool of O(n^{o(1)}) dummy vertices. The Chernoff and union-bound analysis (Lemma 3.4) shows that with high probability every required degree is equalized while the total number of vertices and hyperedges grows by at most a polylog(n) factor. Because any g(k) ≥ 1 absorbs an o(1) additive term in the exponent, the fine-grained equivalence is preserved. We will add an explicit corollary stating the precise blow-up bound. revision: partial
Referee: In the CSP hardness direction (d ≥ 3 case), the reduction from 3-uniform hyperclique detection relies on the same regularization step. It must be verified that the composed reduction still yields a subexponential blow-up only in the k parameter and not in n, so that the n^{Ω(k)} lower bound is preserved.

Authors: The CSP reduction (Section 5) first builds a linear-size gadget instance whose number of variables is O(k) and whose hyperedges are in one-to-one correspondence with the original hyperclique instance; the regularization lemma is then applied to this gadget instance. Because the lemma produces an equivalent regular instance of size m^{1+o(1)} where m is the size of the gadget instance, and m = Θ(n), the overall blow-up remains n^{1+o(1)}. Consequently an algorithm running in time n^{o(k)} on the final regular CSP instance would yield an algorithm of the same asymptotic form for the original 3-uniform hyperclique instance, contradicting the hypothesis. We will insert a short paragraph in Section 5.3 that records this composition argument. revision: partial

Circularity Check

0 steps flagged

No circularity: new regularization lemma is independently proven and applied

full rationale

The paper establishes a regularization reduction from general h-uniform hyperclique detection to the strongly regular k-partite case, claiming that any f(k)n^{g(k)} algorithm on regular instances yields one on general instances. This is presented as a new combinatorial result (not derived from prior self-citations or fitted parameters). The same lemma is then invoked to obtain the CSP hardness results for different degrees d. No step reduces by construction to its own inputs: the regularization is not self-definitional, no prediction is a fitted input, and there are no load-bearing self-citations to prior work by the same authors that would make the central claim tautological. The derivation chain is self-contained against external benchmarks, with the reduction serving as independent evidence rather than a renaming or ansatz smuggling.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper relies on standard assumptions from fine-grained complexity (hyperclique hypotheses) and combinatorial definitions of regularity; no free parameters are introduced as the results are asymptotic equivalences rather than numerical fits. No new entities are postulated.

axioms (2)

domain assumption The h-uniform hyperclique hypothesis holds for general hypergraphs
Invoked to obtain the exhaustive-search lower bound for d≥3 cases via the regularization transfer.
domain assumption Strong regularity (uniform incidence for subsets of size ≤ h-1) can be maintained or simulated in reductions without asymptotic overhead
Central to the transfer theorem stated in the abstract.

pith-pipeline@v0.9.0 · 5833 in / 1707 out tokens · 43444 ms · 2026-05-22T02:29:11.975228+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

24 extracted references · 24 canonical work pages

[1]

If the current clique algorithms are optimal, so is Valiant's parser

1 Amir Abboud, Arturs Backurs, and Virginia Vassilevska Williams. If the current clique algorithms are optimal, so is valiant’s parser. In Venkatesan Guruswami, editor,IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17- 20 October, 2015, pages 98–117. IEEE Computer Society, 2015.doi:10.1109/FOCS.2015.16. 26 The...

work page doi:10.1109/focs.2015.16 2015
[2]

3 Josh Alman, Ran Duan, Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, and Renfei Zhou

ACM.doi:10.1145/3188745.3188938. 3 Josh Alman, Ran Duan, Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, and Renfei Zhou. More asymmetry yields faster matrix multiplication. In Yossi Azar and Debmalya Panigrahi, editors,Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025, New Orleans, LA, USA, January 12-15, 2025, pag...

work page doi:10.1145/3188745.3188938 2025
[3]

5 UlrikBrandes, EugeniaHolm, andAndreasKarrenbauer

URL:https://doi.org/10.4230/LIPIcs.IPEC.2021.3,doi:10.4230/LIPICS.IPEC.2021.3. 5 UlrikBrandes, EugeniaHolm, andAndreasKarrenbauer. Cliquesinregulargraphsandthe core- periphery problem in social networks. In T.-H. Hubert Chan, Minming Li, and Lusheng Wang, editors,Combinatorial Optimization and Applications - 10th International Conference, COCOA 2016, Hong...

work page doi:10.4230/lipics.ipec.2021.3 2021
[4]

7 Karl Bringmann, Nick Fischer, and Marvin Künnemann

URL: https://doi.org/10.4230/LIPIcs.ICALP.2022.30,doi:10.4230/LIPICS.ICALP.2022.30. 7 Karl Bringmann, Nick Fischer, and Marvin Künnemann. A fine-grained analogue of schaefer’s theorem in P: dichotomy of existsˆk-forall-quantified first-order graph properties. In Amir Shpilka, editor,34th Computational Complexity Conference, CCC 2019, July 18-20, 2019, New...

work page doi:10.4230/lipics.icalp.2022.30 2022
[5]

8 Karl Bringmann and Jasper Slusallek

URL:https://doi.org/10.4230/LIPIcs.CCC.2019.31, doi: 10.4230/LIPICS.CCC.2019.31. 8 Karl Bringmann and Jasper Slusallek. Current algorithms for detecting subgraphs of bounded treewidth are probably optimal. In Nikhil Bansal, Emanuela Merelli, and James Worrell, editors,48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, July ...

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

9 Karl Bringmann and Philip Wellnitz

URL:https: //doi.org/10.4230/LIPIcs.ICALP.2021.40,doi:10.4230/LIPICS.ICALP.2021.40. 9 Karl Bringmann and Philip Wellnitz. Clique-based lower bounds for parsing tree-adjoining grammars. In Juha Kärkkäinen, Jakub Radoszewski, and Wojciech Rytter, editors,28th Annual Symposium on Combinatorial Pattern Matching, CPM 2017, July 4-6, 2017, Warsaw, Poland, volum...

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

10 Andrei A

URL:https://doi.org/10.4230/LIPIcs.CPM.2017.12,doi:10.4230/LIPICS.CPM.2017.12. 10 Andrei A. Bulatov. A dichotomy theorem for nonuniform CSPs. InProc. 58th IEEE Annual Symposium on Foundations of Computer Science (FOCS 2017), pages 319–330,

work page doi:10.4230/lipics.cpm.2017.12 2017
[8]

11 Andrei A

doi:10.1109/FOCS.2017.37. 11 Andrei A. Bulatov and Dániel Marx. Constraint satisfaction parameterized by solution size. SIAM J. Comput., 43(2):573–616, 2014.doi:10.1137/120882160. 12 Leizhen Cai. Parameterized complexity of cardinality constrained optimization problems. Comput. J., 51(1):102–121,

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

URL: https://doi.org/10.1093/comjnl/bxm086, doi: 10.1093/COMJNL/BXM086. N. Fischer, M. Künnemann, M. Redžić, J. Stieß 27 13 Nofar Carmeli, Shai Zeevi, Christoph Berkholz, Benny Kimelfeld, and Nicole Schweikardt. Answering (unions of) conjunctive queries using random access and random-order enumeration. In Dan Suciu, Yufei Tao, and Zhewei Wei, editors,Proc...

work page doi:10.1093/comjnl/bxm086 2020
[10]

Locally maximal common factors as a tool for eﬃcient dynamic string algorithms

URL:https://doi.org/10.4230/LIPIcs. CPM.2016.13,doi:10.4230/LIPICS.CPM.2016.13. 15 Charles J. Colbourn and Jeffrey H. Dinitz, editors.Handbook of Combinatorial Designs. Chapman and Hall/CRC, New York, 2 edition, November 2006.doi:10.1201/9781420010541. 16 Nadia Creignou. A dichotomy theorem for maximum generalized satisfiability problems.J. Comput. Syst. ...

work page doi:10.4230/lipics 2016
[11]

6 Josep Díaz, Olli Pottonen, Maria J

doi:10.1007/978-3-319-21275-3. 18 Mina Dalirrooyfard and Virginia Vassilevska Williams. Induced cycles and paths are harder than you think. In63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31 - November 3, 2022, pages 531–542. IEEE,

work page doi:10.1007/978-3-319-21275-3 2022
[12]

Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva

doi:10.1109/FOCS54457.2022.00057. 19 Uriel Feige. A threshold of lnnfor approximating set cover.J. ACM, 45(4):634–652,

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

20 Egor Gorbachev and Marvin Künnemann

doi:10.1145/285055.285059. 20 Egor Gorbachev and Marvin Künnemann. Combinatorial designs meet hypercliques: Higher lower bounds for klee’s measure problem and related problems in dimensions d≥4. In Erin W. Chambers and Joachim Gudmundsson, editors,39th International Symposium on Computational Geometry, SoCG 2023, June 12-15, 2023, Dallas, Texas, USA, volu...

work page doi:10.1145/285055.285059 2023
[14]

21 Sanjeev Khanna, Madhu Sudan, Luca Trevisan, and David P

URL: https://doi.org/10.4230/LIPIcs.SoCG.2023.36,doi:10.4230/LIPICS.SOCG.2023.36. 21 Sanjeev Khanna, Madhu Sudan, Luca Trevisan, and David P. Williamson. The approximability of constraint satisfaction problems.SIAM J. Comput., 30(6):1863–1920, 2000.doi:10.1137/ S0097539799349948. 22 Stefan Kratsch, Dániel Marx, and Magnus Wahlström. Parameterized complexi...

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

23 Marvin Künnemann

doi: 10.1145/2858787. 23 Marvin Künnemann. A tight (non-combinatorial) conditional lower bound for klee’s measure problem in 3d. In63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31 - November 3, 2022, pages 555–566. IEEE,

work page doi:10.1145/2858787 2022
[16]

Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva

doi:10.1109/FOCS54457.2022.00059. 24 Marvin Künnemann and Dániel Marx. Finding small satisfying assignments faster than brute force: A fine-grained perspective into boolean constraint satisfaction. In Shubhangi Saraf, editor,35th Computational Complexity Conference, CCC 2020, July 28-31, 2020, Saarbrücken, Germany (Virtual Conference), volume 169 ofLIPIcs...

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

27,doi:10.4230/LIPICS.CCC.2020.27

URL:https://doi.org/10.4230/LIPIcs.CCC.2020. 27,doi:10.4230/LIPICS.CCC.2020.27. 25 Andrea Lincoln, Virginia Vassilevska Williams, and R. Ryan Williams. Tight hardness for shortest cycles and paths in sparse graphs. In Artur Czumaj, editor,Proceedings of the Twenty- Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, Ja...

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

URL: https://doi.org/10.1016/j.tcs.2005.10.007, doi:10.1016/J.TCS.2005.10

work page doi:10.1016/j.tcs.2005.10.007 2005
[19]

Fourteenth Computing: The Australasian Theory Symposium (CATS 2008), Wollongong, NSW, Australia, January 22-25,

Proc. Fourteenth Computing: The Australasian Theory Symposium (CATS 2008), Wollongong, NSW, Australia, January 22-25,

work page 2008
[20]

Schaefer

30 Thomas J. Schaefer. The complexity of satisfiability problems. InProceedings of the 10th Annual ACM Symposium on Theory of Computing, May 1-3, 1978, San Diego, California, USA, pages 216–226, 1978.doi:10.1145/800133.804350. 31 Virginia Vassilevska and Ryan Williams. Finding a maximum weight triangle in n3-delta time, with applications. In Jon M. Kleinb...

work page doi:10.1145/800133.804350 1978
[21]

34 Or Zamir

AAI3274191. 34 Or Zamir. Algorithmic applications of hypergraph and partition containers. In Barna Saha and Rocco A. Servedio, editors,Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023, pages 985–998. ACM,

work page 2023
[22]

35 Dmitriy Zhuk

doi:10.1145/3564246.3585163. 35 Dmitriy Zhuk. A proof of CSP dichotomy conjecture. InProc. 58th IEEE Annual Symposium on Foundations of Computer Science (FOCS 2017), pages 331–342,

work page doi:10.1145/3564246.3585163 2017
[23]

doi:10.1109/FOCS. 2017.38. 36 Dmitriy Zhuk. A proof of the CSP dichotomy conjecture.J. ACM, 67(5):30:1–30:78,

work page doi:10.1109/focs 2017
[24]

37 Uri Zwick

doi:10.1145/3402029. 37 Uri Zwick. All pairs shortest paths using bridging sets and rectangular matrix multiplication. J. ACM, 49(3):289–317, 2002.doi:10.1145/567112.567114

work page doi:10.1145/3402029 2002

[1] [1]

If the current clique algorithms are optimal, so is Valiant's parser

1 Amir Abboud, Arturs Backurs, and Virginia Vassilevska Williams. If the current clique algorithms are optimal, so is valiant’s parser. In Venkatesan Guruswami, editor,IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17- 20 October, 2015, pages 98–117. IEEE Computer Society, 2015.doi:10.1109/FOCS.2015.16. 26 The...

work page doi:10.1109/focs.2015.16 2015

[2] [2]

3 Josh Alman, Ran Duan, Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, and Renfei Zhou

ACM.doi:10.1145/3188745.3188938. 3 Josh Alman, Ran Duan, Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, and Renfei Zhou. More asymmetry yields faster matrix multiplication. In Yossi Azar and Debmalya Panigrahi, editors,Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025, New Orleans, LA, USA, January 12-15, 2025, pag...

work page doi:10.1145/3188745.3188938 2025

[3] [3]

5 UlrikBrandes, EugeniaHolm, andAndreasKarrenbauer

URL:https://doi.org/10.4230/LIPIcs.IPEC.2021.3,doi:10.4230/LIPICS.IPEC.2021.3. 5 UlrikBrandes, EugeniaHolm, andAndreasKarrenbauer. Cliquesinregulargraphsandthe core- periphery problem in social networks. In T.-H. Hubert Chan, Minming Li, and Lusheng Wang, editors,Combinatorial Optimization and Applications - 10th International Conference, COCOA 2016, Hong...

work page doi:10.4230/lipics.ipec.2021.3 2021

[4] [4]

7 Karl Bringmann, Nick Fischer, and Marvin Künnemann

URL: https://doi.org/10.4230/LIPIcs.ICALP.2022.30,doi:10.4230/LIPICS.ICALP.2022.30. 7 Karl Bringmann, Nick Fischer, and Marvin Künnemann. A fine-grained analogue of schaefer’s theorem in P: dichotomy of existsˆk-forall-quantified first-order graph properties. In Amir Shpilka, editor,34th Computational Complexity Conference, CCC 2019, July 18-20, 2019, New...

work page doi:10.4230/lipics.icalp.2022.30 2022

[5] [5]

8 Karl Bringmann and Jasper Slusallek

URL:https://doi.org/10.4230/LIPIcs.CCC.2019.31, doi: 10.4230/LIPICS.CCC.2019.31. 8 Karl Bringmann and Jasper Slusallek. Current algorithms for detecting subgraphs of bounded treewidth are probably optimal. In Nikhil Bansal, Emanuela Merelli, and James Worrell, editors,48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, July ...

work page doi:10.4230/lipics.ccc.2019.31 2019

[6] [6]

9 Karl Bringmann and Philip Wellnitz

URL:https: //doi.org/10.4230/LIPIcs.ICALP.2021.40,doi:10.4230/LIPICS.ICALP.2021.40. 9 Karl Bringmann and Philip Wellnitz. Clique-based lower bounds for parsing tree-adjoining grammars. In Juha Kärkkäinen, Jakub Radoszewski, and Wojciech Rytter, editors,28th Annual Symposium on Combinatorial Pattern Matching, CPM 2017, July 4-6, 2017, Warsaw, Poland, volum...

work page doi:10.4230/lipics.icalp.2021.40 2021

[7] [7]

10 Andrei A

URL:https://doi.org/10.4230/LIPIcs.CPM.2017.12,doi:10.4230/LIPICS.CPM.2017.12. 10 Andrei A. Bulatov. A dichotomy theorem for nonuniform CSPs. InProc. 58th IEEE Annual Symposium on Foundations of Computer Science (FOCS 2017), pages 319–330,

work page doi:10.4230/lipics.cpm.2017.12 2017

[8] [8]

11 Andrei A

doi:10.1109/FOCS.2017.37. 11 Andrei A. Bulatov and Dániel Marx. Constraint satisfaction parameterized by solution size. SIAM J. Comput., 43(2):573–616, 2014.doi:10.1137/120882160. 12 Leizhen Cai. Parameterized complexity of cardinality constrained optimization problems. Comput. J., 51(1):102–121,

work page doi:10.1109/focs.2017.37 2017

[9] [9]

URL: https://doi.org/10.1093/comjnl/bxm086, doi: 10.1093/COMJNL/BXM086. N. Fischer, M. Künnemann, M. Redžić, J. Stieß 27 13 Nofar Carmeli, Shai Zeevi, Christoph Berkholz, Benny Kimelfeld, and Nicole Schweikardt. Answering (unions of) conjunctive queries using random access and random-order enumeration. In Dan Suciu, Yufei Tao, and Zhewei Wei, editors,Proc...

work page doi:10.1093/comjnl/bxm086 2020

[10] [10]

Locally maximal common factors as a tool for eﬃcient dynamic string algorithms

URL:https://doi.org/10.4230/LIPIcs. CPM.2016.13,doi:10.4230/LIPICS.CPM.2016.13. 15 Charles J. Colbourn and Jeffrey H. Dinitz, editors.Handbook of Combinatorial Designs. Chapman and Hall/CRC, New York, 2 edition, November 2006.doi:10.1201/9781420010541. 16 Nadia Creignou. A dichotomy theorem for maximum generalized satisfiability problems.J. Comput. Syst. ...

work page doi:10.4230/lipics 2016

[11] [11]

6 Josep Díaz, Olli Pottonen, Maria J

doi:10.1007/978-3-319-21275-3. 18 Mina Dalirrooyfard and Virginia Vassilevska Williams. Induced cycles and paths are harder than you think. In63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31 - November 3, 2022, pages 531–542. IEEE,

work page doi:10.1007/978-3-319-21275-3 2022

[12] [12]

Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva

doi:10.1109/FOCS54457.2022.00057. 19 Uriel Feige. A threshold of lnnfor approximating set cover.J. ACM, 45(4):634–652,

work page doi:10.1109/focs54457.2022.00057 2022

[13] [13]

20 Egor Gorbachev and Marvin Künnemann

doi:10.1145/285055.285059. 20 Egor Gorbachev and Marvin Künnemann. Combinatorial designs meet hypercliques: Higher lower bounds for klee’s measure problem and related problems in dimensions d≥4. In Erin W. Chambers and Joachim Gudmundsson, editors,39th International Symposium on Computational Geometry, SoCG 2023, June 12-15, 2023, Dallas, Texas, USA, volu...

work page doi:10.1145/285055.285059 2023

[14] [14]

21 Sanjeev Khanna, Madhu Sudan, Luca Trevisan, and David P

URL: https://doi.org/10.4230/LIPIcs.SoCG.2023.36,doi:10.4230/LIPICS.SOCG.2023.36. 21 Sanjeev Khanna, Madhu Sudan, Luca Trevisan, and David P. Williamson. The approximability of constraint satisfaction problems.SIAM J. Comput., 30(6):1863–1920, 2000.doi:10.1137/ S0097539799349948. 22 Stefan Kratsch, Dániel Marx, and Magnus Wahlström. Parameterized complexi...

work page doi:10.4230/lipics.socg.2023.36 2023

[15] [15]

23 Marvin Künnemann

doi: 10.1145/2858787. 23 Marvin Künnemann. A tight (non-combinatorial) conditional lower bound for klee’s measure problem in 3d. In63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31 - November 3, 2022, pages 555–566. IEEE,

work page doi:10.1145/2858787 2022

[16] [16]

Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva

doi:10.1109/FOCS54457.2022.00059. 24 Marvin Künnemann and Dániel Marx. Finding small satisfying assignments faster than brute force: A fine-grained perspective into boolean constraint satisfaction. In Shubhangi Saraf, editor,35th Computational Complexity Conference, CCC 2020, July 28-31, 2020, Saarbrücken, Germany (Virtual Conference), volume 169 ofLIPIcs...

work page doi:10.1109/focs54457.2022.00059 2022

[17] [17]

27,doi:10.4230/LIPICS.CCC.2020.27

URL:https://doi.org/10.4230/LIPIcs.CCC.2020. 27,doi:10.4230/LIPICS.CCC.2020.27. 25 Andrea Lincoln, Virginia Vassilevska Williams, and R. Ryan Williams. Tight hardness for shortest cycles and paths in sparse graphs. In Artur Czumaj, editor,Proceedings of the Twenty- Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, Ja...

work page doi:10.4230/lipics.ccc.2020 2020

[18] [18]

URL: https://doi.org/10.1016/j.tcs.2005.10.007, doi:10.1016/J.TCS.2005.10

work page doi:10.1016/j.tcs.2005.10.007 2005

[19] [19]

Fourteenth Computing: The Australasian Theory Symposium (CATS 2008), Wollongong, NSW, Australia, January 22-25,

Proc. Fourteenth Computing: The Australasian Theory Symposium (CATS 2008), Wollongong, NSW, Australia, January 22-25,

work page 2008

[20] [20]

Schaefer

30 Thomas J. Schaefer. The complexity of satisfiability problems. InProceedings of the 10th Annual ACM Symposium on Theory of Computing, May 1-3, 1978, San Diego, California, USA, pages 216–226, 1978.doi:10.1145/800133.804350. 31 Virginia Vassilevska and Ryan Williams. Finding a maximum weight triangle in n3-delta time, with applications. In Jon M. Kleinb...

work page doi:10.1145/800133.804350 1978

[21] [21]

34 Or Zamir

AAI3274191. 34 Or Zamir. Algorithmic applications of hypergraph and partition containers. In Barna Saha and Rocco A. Servedio, editors,Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023, pages 985–998. ACM,

work page 2023

[22] [22]

35 Dmitriy Zhuk

doi:10.1145/3564246.3585163. 35 Dmitriy Zhuk. A proof of CSP dichotomy conjecture. InProc. 58th IEEE Annual Symposium on Foundations of Computer Science (FOCS 2017), pages 331–342,

work page doi:10.1145/3564246.3585163 2017

[23] [23]

doi:10.1109/FOCS. 2017.38. 36 Dmitriy Zhuk. A proof of the CSP dichotomy conjecture.J. ACM, 67(5):30:1–30:78,

work page doi:10.1109/focs 2017

[24] [24]

37 Uri Zwick

doi:10.1145/3402029. 37 Uri Zwick. All pairs shortest paths using bridging sets and rectangular matrix multiplication. J. ACM, 49(3):289–317, 2002.doi:10.1145/567112.567114

work page doi:10.1145/3402029 2002