Uniformity within Parameterized Circuit Classes

Alfons Laarman; Jan Martens; Steef Hegeman

REVIEW 2 major objections 4 minor 16 references

Uniformity within Parameterized Circuit Classes

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

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

Pith's one-line read For shallow parameterized circuit classes, three different uniformity conditions — linear-time, logtime, and first-order — define the same class of problems.

desk verdict A real contribution to parameterized uniformity, but the main proof rests on an unproved folklore claim and a misapplied theorem—both likely fixable, so it should go to peer review with requests for revision. read the letter →

arxiv 2509.09657 v1 pith:F7IIK7A3 submitted 2025-09-11 cs.CC cs.LO

Steef Hegeman , Jan Martens , Alfons Laarman This is my paper · ORCID

classification cs.CCcs.LO MSC 68Q1568Q19

keywords parameterizedcomplexitycircuituniformityAC⁰para-AC⁰logtimefirst-orderdefinabilityfamilies

topics P versus NP

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

In parameterized circuit complexity, shallow circuit classes like para-AC⁰ and para-AC⁰↑ are usually defined with a uniformity condition that says the circuits must be easy to construct, but the precise condition used in the literature is often left vague or unproved. The paper formalizes parameterized analogues of three standard uniformity conditions — linear-time (with bound f(k)+n), logtime random-access, and first-order definable — and proves that, when imposed on para-AC⁰ or para-AC⁰↑, they all yield the same class of parameterized problems. The main result (Theorem 21) is the equality of the three classes; an extended version covers uniformity notions that describe paths through circuits. This matters because logtime-uniformity is technical and rarely proved directly: the theorem makes FO-definability a sufficient certificate for the existence of a logtime-uniform family, which substantiates uniformity claims in recent literature and repairs a known gap. The proof works by a layered 'simgate' construction: from an FO-uniform or logtime-uniform family, one builds a linear-BD-uniform family by simulating each gate with a block that queries the original circuit's connection language.

What carries the argument

The load-bearing mechanism is the parameterized direct connection language LD(C), the set of strings ⟨G,a,p,z,z′⟩ describing gate types and predecessor relations of each circuit Cn,k, together with its binary version LBD(C). Uniformity conditions are defined by the decision complexity of these languages: linear-BD-uniformity requires DTIME(n+f(k)), logtime-D-uniformity requires DTIMER(log n+f(k)) on random-access Turing machines, and FO-D-uniformity requires the language to be in parameterized first-order logic. The equivalences are proved by a substitution lemma (Lemma 23) showing that linear-BD-uniform families are closed under replacing marked gates by other linear-BD-uniform families, an

What would settle it

A separation of the two non-parameterized classes in Theorem 12 — an AC⁰ language with a linear-BD-uniform circuit family but no equivalent logtime-D-uniform family — would falsify the parameterized equivalence, since the non-parameterized case embeds into para-AC⁰ with constant parameter. The first place to look is whether the paper's simgate construction actually preserves logtime-uniformity when depth and parameter are constant, since that construction is the only evidence given for Theorem 12.

Watch

Extended reading notes

Core claim

The central claim is Theorem 21: for both para-AC⁰ and para-AC⁰↑, the classes of parameterized problems decided by linear-BD-uniform, logtime-D-uniform, and FO-D-uniform circuit families coincide. In other words, the three parameterized uniformity conditions — defined here for the first time in a unified way — are interchangeable at the level of complexity classes for shallow families. The paper also proves the analogous statement for extended uniformity notions (logtime-E-uniform and FO-E-uniform), where the connection language contains paths, and derives the self-uniformity corollary that (FO-D-uniform para-AC⁰↑)-uniform para-AC⁰↑ equals FO-D-uniform para-AC⁰↑. The authors intend this as a

Load-bearing premise

The proof that logtime-D-uniformity implies FO-D-uniformity for parameterized families rests on the unproved folklore equivalence between linear-BD-uniform AC⁰ and logtime-D-uniform AC⁰ (Theorem 12); if that non-parameterized equivalence should fail, the main chain collapses even though the paper states it can be proved by the same simgate argument.

Editorial extensions

If this is right

To prove logtime-uniformity of a shallow parameterized circuit family, it suffices to give a first-order description of its direct connection language; this is typically far easier than designing a logtime random-access Turing machine.
The equivalence holds separately for para-AC⁰ (constant depth) and para-AC⁰↑ (depth f(k)), so the convenience applies to the full range of shallow parameterized circuit classes.
Extended uniformity notions that trace paths in circuits — logtime-E-uniform and FO-E-uniform — collapse to the same classes as well, so path-based uniformity adds no extra power for these classes.
The result gives (FO-D-uniform para-AC⁰↑)-uniform para-AC⁰↑ = FO-D-uniform para-AC⁰↑, meaning a family that is uniform in a strong sense is itself FO-D-uniform.
The framework yields a descriptive-complexity counterpart: the union over computable f of para-FO[f(k)] equals FO-D-uniform para-AC⁰↑, linking logtime-uniformity to iterated first-order logic.

Reading between the lines

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

The proof actually shows more than the statement: the simgate construction gives an explicit algorithm converting an FO-D-uniform description into a linear-BD-uniform family, so in principle one can mechanically extract a logtime-uniform family rather than merely knowing one exists.
Because the conversion costs a polynomial blow-up in size (roughly from O(f(k)n^c) to O(f'(k)n^{3c+1})), the equivalence is not a work-preserving simulation; any theorem that relies on exact circuit sizes for parameterized parallel complexity would need a different, finer-grained argument.
The same layered-simulation strategy may transfer to other parameterized circuit classes where a substitution lemma holds, so the 'three uniformities are one' phenomenon could recur for e.g. parameterized ACC or NC-like classes, though the paper does not claim this.

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.

Desk Editor's Note

read the letter

Colleague, here's my take on arXiv:2509.09657.

The paper does something genuinely useful: it gives the first systematic treatment of uniformity for parameterized Boolean circuit classes. The definitions of linear-BD-, logtime-D-, and FO-D-uniformity in the parameterized setting are natural, and the main theorem (for para-AC0 and para-AC0↑ these three notions yield the same classes) is exactly the kind of toolkit the area needs. The simgate layering construction is new and, as far as I can tell, sound in its own right. The authors also deserve credit for being straight about what they don't prove—the class-level versus family-level distinction and the size blow-up in their conversion are stated plainly.

That said, there are two holes in the proof as written, and both are load-bearing. First, Lemma 20 uses Theorem 12, the folklore equivalence linear-BD-uniform AC0 = logtime-D-uniform AC0, to chain logtime-D-uniformity into FO-D-uniformity. The paper only says it can be proved 'similarly' to Lemma 24, and points out that the stronger family-level equivalence is actually open. Since the central equality in Theorem 21 rests on this step, the proof is incomplete without a proof of Theorem 12. The authors likely have the argument—the simgate construction in Lemma 24 should adapt—but it needs to be written out.

Second, Lemma 25's proof appears to misapply Theorem 14. Theorem 14 says linear-BD-uniform para-AC0 equals Para(linear-BD-uniform AC0). The proof of Lemma 25 uses it to jump from Para(logtime-D-uniform AC0) to logtime-D-uniform para-AC0. That is not what the theorem states. There may be an intended use of Theorem 12 there, or a separate argument, but as written the implication from FO-D-uniform to linear-BD-uniform is not established by the cited results.

These are not fatal objections to the ideas. I suspect both can be fixed with the techniques already in the paper. But they are genuine gaps, not stylistic ones, and the main theorem does not go through as written. A referee should ask for a real proof of Theorem 12 and a corrected chain in Lemma 25.

Bottom line: this is a solid, niche contribution for people working on parameterized circuit complexity and descriptive complexity. The definitions alone could become the standard reference. I would send it to a serious referee rather than desk reject, and condition acceptance on filling those two holes.

Referee Report

2 major / 4 minor

Summary. The paper defines parameterized analogues of three direct uniformity conditions for Boolean circuit families—linear-BD-uniformity, logtime-D-uniformity, and FO-D-uniformity—along with extended variants, and proves that for the shallow parameterized classes para-AC0 and para-AC0^↑ these conditions induce the same complexity classes (Theorem 21 and Corollary 31). The proof strategy is: first show linear-BD ⇒ logtime-D ⇒ FO-D for individual circuit families (Lemmas 18 and 20); then prove the reverse inclusions up to equivalent families by a layered simulation using 'simgates' that evaluate gates of a logtime- or FO-uniform circuit by querying its direct connection language; a substitution lemma (Lemma 23) is used to compose the query-answering circuits. Applications to uniformity claims in the recent parameterized-circuit literature are discussed in Sections 6 and 7.

Significance. If the identified proof gaps are repaired, this is a useful and timely contribution. It removes a real ambiguity in the parameterized circuit-complexity literature, where logtime-uniformity is often invoked informally or left as an exercise, and it extends the classical Barrington–Immerman–Straubing equivalence to the parameterized setting, including the non-constant-depth class para-AC0^↑. The simgate construction and the substitution lemma are interesting technical tools in their own right. The paper also contains substantial appendix proofs and is honest about limitations, noting that the equivalences hold at the class level rather than the family level and that the conversion has a polynomial overhead gap.

major comments (2)

[§2.5, Theorem 12; used in §3, Lemma 20] Theorem 12, the equality linear-BD-uniform AC0 = logtime-D-uniform AC0, is stated as folklore with only 'can be proved similarly' and no proof. This equality is load-bearing: Lemma 20 derives logtime-D-uniform ⇒ FO-D-uniform through the chain Lemma 19 → Theorem 14 → Theorems 11 and 12 → para-FO, and the step '= Para(FO)' depends entirely on Theorem 12. The manuscript itself notes that the stronger family-level equivalence is open, so Theorem 12 is not a routine corollary of cited results. Please supply a proof (a non-parameterized version of Lemma 24 appears to provide exactly the needed argument), or an explicit citable source containing a proof, and state this dependency before Lemma 20 uses it.
[§4.2, Lemma 25] The step 'Theorem 11 gives that (LD(C),π4) is in Para(logtime-D-uniform AC0), which by Theorem 14 is equal to logtime-D-uniform para-AC0' misstates Theorem 14. Theorem 14 is stated for linear-BD-uniform para-AC0 and Para(linear-BD-uniform AC0), not for logtime-D-uniform para-AC0. The intended conclusion can be obtained only by additionally applying Theorem 12 and Lemma 18 (or by proving a logtime analogue of Theorem 14). As written, this is a direct misapplication at a load-bearing point of the proof of (3)⇒(1) in Theorem 21. Please rewrite this step and make the full chain explicit.

minor comments (4)

[§3, Definition 17] The definition of FO-D-uniformity says '(LD(C),π4) is in para-FO', but Definition 1 requires a parameter function κ : 2* → N, while π4 is a string projection. The intended parameter is |π4(w)|, i.e. |z'|. Please add an explicit convention that π4 is shorthand for the parameter function κ(w)=|π4(w)|, consistently with Table 1.
[§3, Lemma 20] The line 'From the inclusions ... = Para(FO) by Theorems 11 and 12' mixes inclusions and equalities; what is meant is a chain of class inclusions and equalities. Clarify the notation to avoid suggesting that Theorem 12 is being cited for an inclusion rather than a class equality.
[Appendix B.4, proof of Lemma 30] In the runtime analysis, the text says 'this takes O(g(k) log log n) bits' and later 'also O(g(k) log log n) bits for some computable g'. These should be 'time', not 'bits'. Also, the sentence 'Managing the finite number of special steps ... take O(log n + g(k)) time each' should say 'takes' for grammatical agreement.
[§4.2, Lemma 24] The final subcircuit that propagates the output of the correct simgate is described only briefly. Since this is part of the construction whose uniformity is being claimed, a sentence explaining how the output-gate information is obtained from LD(C) in the same complexity bound would help the reader verify that the admissible numbering and the connection language check remain uniform.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the uniformity equivalences are proved by explicit simulation and substitution constructions; the unproved Theorem 12 is a proof gap, not a circular dependence.

full rationale

The central claim (Theorem 21) is established by four inclusions. The forward inclusions use Lemma 18 (constructing a random-access logtime machine from a linear-time machine for LBD), Lemma 19 (explicit constant-depth circuit simulation of DTIMER(logn+f(k))), and Lemma 20, which chains Lemma 19 with the external Chen-Flum Theorem 14 and the external Barrington-Immerman-Straubing Theorem 11. No parameter is fitted and no target conclusion is assumed: each step builds a new circuit family and verifies its connection language directly. The reverse inclusions are proved by Lemmas 24 and 25, which explicitly construct layered simgate families that simulate the original family by querying LD(C), and then substitute uniform circuits for those queries via Lemma 23; the uniformity of the resulting family is verified from LBD(D), not assumed. The equivalence is therefore not built into the definitions of the three uniformity notions. The only load-bearing item that is not fully proved is Theorem 12 ("Linear-BD-uniform AC0 equals logtime-D-uniform AC0"), which is invoked in Lemma 20 and stated as folklore with the note that it can be proved similarly to Lemma 24. This is a missing-support/correctness risk, not circularity: Theorem 12 is an external class-level statement, is not a self-citation, and is not derived from the parameterized result it supports. Lemma 25 also appears to cite Theorem 14 for a logtime-D-uniform para-AC0 equality that Theorem 14 as stated does not cover; again this is a proof gap rather than a self-referential reduction. No step of the derivation reduces to its own input by definition, no fitted parameter is renamed as a prediction, and no uniqueness claim is imported from the authors' prior work.

Assumptions & free parameters 0 free parameters · 5 assumptions · 1 invented entities

The central claim rests on standard complexity-theoretic theorems and on the domain convention that parameter functions are FO-computable. No numbers are fitted to data; the constants in size bounds are existential and derived. The main unproved input is the folklore Theorem 12, which the paper does not fully prove.

assumptions (5)

domain assumption Parameter function kappa is FO-computable, equivalently computable by logtime-D-uniform AC0 circuits.
Used in Definition 1 to make para-FO and the equivalence proofs go through. The authors note in Appendix A that it can be removed by switching to pFO with computable kappa and |kappa(x)| bounded by a polynomial in |x|.
standard math Barrington-Immerman-Straubing Theorem 11: logtime-D-uniform AC0 = FO-D-uniform AC0 = FO.
Used in Lemmas 20 and 25 as an external black box.
standard math Theorem 12 (folklore): Linear-BD-uniform AC0 = logtime-D-uniform AC0.
Stated as folklore and claimed proved similarly to Lemma 24, but the proof is not given. Used in the Lemma 20 chain to get Para(linear-BD-uniform AC0) = Para(FO).
standard math Theorem 14 (Chen-Flum): Linear-BD-uniform para-AC0 = Para(linear-BD-uniform AC0).
Used in Lemma 20 and misapplied in Lemma 25, where a logtime-D analogue would be needed.
standard math Random-access Turing machines can add m-bit numbers and count in binary in O(m) time, Lemma 33.
Used in the list-encoding machinery of Appendix B.

invented entities (1)

Simgates (layered simulation gates)
purpose: Construct a linear-BD-uniform circuit family D that simulates a logtime-D-uniform or FO-D-uniform family C by iteratively approximating gate values layer by layer, using queries to LD(C).
A proof gadget introduced in Lemmas 24 and 30; its correctness is proven in-paper, no external empirical handle. Not a postulated physical entity.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Uniformity within Parameterized Circuit Classes." pith.science (2026). https://pith.science/paper/F7IIK7A3

@misc{pith2026250909657,
  author       = {Pith},
  title        = {Pith review of: Uniformity within Parameterized Circuit Classes},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/F7IIK7A3}},
  note         = {Machine review of arXiv:2509.09657}
}

abstract

We study uniformity conditions for parameterized Boolean circuit families. Uniformity conditions require that the infinitely many circuits in a circuit family are in some sense easy to construct from one shared description. For shallow circuit families, logtime-uniformity is often desired but quite technical to prove. Despite that, proving it is often left as an exercise for the reader -- even for recently introduced classes in parameterized circuit complexity, where uniformity conditions have not yet been explicitly studied. We formally define parameterized versions of linear-uniformity, logtime-uniformity, and FO-uniformity, and prove that these result in equivalent complexity classes when imposed on $\text{para-}\textsf{AC}^0$ and $\text{para-}\textsf{AC}^{0\uparrow}$. Overall, we provide a convenient way to verify uniformity for shallow parameterized circuit classes, and thereby substantiate claims of uniformity in the literature.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

16 extracted references · 7 canonical work pages

[1]

Fast Parallel Fixed -parameter Algorithms via Color Coding

Max Bannach, Christoph Stockhusen, and Till Tantau. Fast Parallel Fixed -parameter Algorithms via Color Coding . In Leibniz International Proceedings in Informatics , IPEC '15, page 12, 2015. Extended version at arXiv:1509.06984 http://arxiv.org/abs/1509.06984. https://doi.org/10.4230/LIPICS.IPEC.2015.224 doi:10.4230/LIPICS.IPEC.2015.224

arXiv 2015
[2]

Parallel Multivariate Meta - Theorems

Max Bannach and Till Tantau. Parallel Multivariate Meta - Theorems . In Leibniz International Proceedings in Informatics , IPEC '16. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2017. https://doi.org/10.4230/LIPIcs.IPEC.2016.4 doi:10.4230/LIPIcs.IPEC.2016.4

work page doi:10.4230/lipics.ipec.2016.4 2017
[3]

Some lower bounds in parameterized AC0

Yijia Chen and Jörg Flum. Some lower bounds in parameterized AC0 . Information and Computation , 267:116--134, 2019. https://doi.org/10.1016/j.ic.2019.03.008 doi:10.1016/j.ic.2019.03.008

work page doi:10.1016/j.ic.2019.03.008 2019
[4]

Slicewise Definability in First - Order Logic with Bounded Quantifier Rank

Yijia Chen, Jörg Flum, and Xuangui Huang. Slicewise Definability in First - Order Logic with Bounded Quantifier Rank . In 26th EACSL Annual Conference on Computer Science Logic ( CSL 2017) , pages 19:1--19:16. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2017. https://doi.org/10.4230/LIPIcs.CSL.2017.19 doi:10.4230/LIPIcs.CSL.2017.19

work page doi:10.4230/lipics.csl.2017.19 2017
[5]

On the Space and Circuit Complexity of Parameterized Problems : Classes and Completeness

Michael Elberfeld, Christoph Stockhusen, and Till Tantau. On the Space and Circuit Complexity of Parameterized Problems : Classes and Completeness . Algorithmica , 71(3):661--701, 2015. https://doi.org/10.1007/s00453-014-9944-y doi:10.1007/s00453-014-9944-y

doi:10.1007/s00453-014-9944-y 2015
[6]

Describing parameterized complexity classes

Jörg Flum and Martin Grohe. Describing parameterized complexity classes. Information and Computation , 187(2):291--319, 2003. https://doi.org/10.1016/S0890-5401(03)00161-5 doi:10.1016/S0890-5401(03)00161-5

work page doi:10.1016/s0890-5401(03)00161-5 2003
[7]

Parameterized complexity theory

Jörg Flum and Martin Grohe. Parameterized complexity theory . Texts in theoretical computer science an EATCS series. Springer, Berlin Heidelberg, 2006. https://doi.org/10.1007/3-540-29953-X doi:10.1007/3-540-29953-X

doi:10.1007/3-540-29953-x 2006
[8]

Integer multiplication in time O (n n)

David Harvey and Joris van der Hoeven. Integer multiplication in time O (n n) . Annals of Mathematics , 193(2):563--617, 2021. https://doi.org/10.4007/annals.2021.193.2.4 doi:10.4007/annals.2021.193.2.4

doi:10.4007/annals.2021.193.2.4 2021

Show all 16 references

[9]

Descriptive Complexity

Neil Immerman. Descriptive Complexity . Springer New York, New York, NY, 1999. https://doi.org/10.1007/978-1-4612-0539-5 doi:10.1007/978-1-4612-0539-5

1999 doi
[10]

Mix Barrington and Neil Immerman

David A. Mix Barrington and Neil Immerman. Time, hardware, and uniformity. In Proceedings of IEEE 9th Annual Conference on Structure in Complexity Theory , pages 176--185. IEEE Comput. Soc. Press, 1994. https://doi.org/10.1109/SCT.1994.315806 doi:10.1109/SCT.1994.315806

1994
[11]

Mix Barrington, Neil Immerman, and Howard Straubing

David A. Mix Barrington, Neil Immerman, and Howard Straubing. On uniformity within NC ^1 . Journal of Computer and System Sciences , 41(3):274--306, 1990. https://doi.org/10.1016/0022-0000(90)90022-D doi:10.1016/0022-0000(90)90022-D

1990 doi
[12]

Parameterized circuit complexity of model-checking on sparse structures

Micha Pilipczuk, Sebastian Siebertz, and Szymon Toru \'n czyk. Parameterized circuit complexity of model-checking on sparse structures. In Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science , pages 789--798, 2018. https://doi.org/10.1145/3209108.320...

2018
[13]

Regan and Heribert Vollmer

Kenneth W. Regan and Heribert Vollmer. Gap-languages and log-time complexity classes. Theoretical Computer Science , 188(1):101--116, 1997. https://doi.org/10.1016/S0304-3975(96)00288-5 doi:10.1016/S0304-3975(96)00288-5

1997 doi
[14]

Walter L. Ruzzo. On uniform circuit complexity. Journal of Computer and System Sciences , 22(3):365--383, 1981. https://doi.org/10.1016/0022-0000(81)90038-6 doi:10.1016/0022-0000(81)90038-6

1981 doi
[15]

On Uniformity and Circuit Lower Bounds

Rahul Santhanam and Ryan Williams. On Uniformity and Circuit Lower Bounds . computational complexity , 23(2):177--205, 2014. https://doi.org/10.1007/s00037-014-0087-y doi:10.1007/s00037-014-0087-y

2014 doi
[16]

Introduction to Circuit Complexity : A Uniform Approach

Heribert Vollmer. Introduction to Circuit Complexity : A Uniform Approach . Texts in Theoretical Computer Science . Springer, 1999. https://doi.org/10.1007/978-3-662-03927-4 doi:10.1007/978-3-662-03927-4

1999 doi

Pith tools

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

[1] [1]

Fast Parallel Fixed -parameter Algorithms via Color Coding

Max Bannach, Christoph Stockhusen, and Till Tantau. Fast Parallel Fixed -parameter Algorithms via Color Coding . In Leibniz International Proceedings in Informatics , IPEC '15, page 12, 2015. Extended version at arXiv:1509.06984 http://arxiv.org/abs/1509.06984. https://doi.org/10.4230/LIPICS.IPEC.2015.224 doi:10.4230/LIPICS.IPEC.2015.224

arXiv 2015

[2] [2]

Parallel Multivariate Meta - Theorems

Max Bannach and Till Tantau. Parallel Multivariate Meta - Theorems . In Leibniz International Proceedings in Informatics , IPEC '16. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2017. https://doi.org/10.4230/LIPIcs.IPEC.2016.4 doi:10.4230/LIPIcs.IPEC.2016.4

work page doi:10.4230/lipics.ipec.2016.4 2017

[3] [3]

Some lower bounds in parameterized AC0

Yijia Chen and Jörg Flum. Some lower bounds in parameterized AC0 . Information and Computation , 267:116--134, 2019. https://doi.org/10.1016/j.ic.2019.03.008 doi:10.1016/j.ic.2019.03.008

work page doi:10.1016/j.ic.2019.03.008 2019

[4] [4]

Slicewise Definability in First - Order Logic with Bounded Quantifier Rank

Yijia Chen, Jörg Flum, and Xuangui Huang. Slicewise Definability in First - Order Logic with Bounded Quantifier Rank . In 26th EACSL Annual Conference on Computer Science Logic ( CSL 2017) , pages 19:1--19:16. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2017. https://doi.org/10.4230/LIPIcs.CSL.2017.19 doi:10.4230/LIPIcs.CSL.2017.19

work page doi:10.4230/lipics.csl.2017.19 2017

[5] [5]

On the Space and Circuit Complexity of Parameterized Problems : Classes and Completeness

Michael Elberfeld, Christoph Stockhusen, and Till Tantau. On the Space and Circuit Complexity of Parameterized Problems : Classes and Completeness . Algorithmica , 71(3):661--701, 2015. https://doi.org/10.1007/s00453-014-9944-y doi:10.1007/s00453-014-9944-y

doi:10.1007/s00453-014-9944-y 2015

[6] [6]

Describing parameterized complexity classes

Jörg Flum and Martin Grohe. Describing parameterized complexity classes. Information and Computation , 187(2):291--319, 2003. https://doi.org/10.1016/S0890-5401(03)00161-5 doi:10.1016/S0890-5401(03)00161-5

work page doi:10.1016/s0890-5401(03)00161-5 2003

[7] [7]

Parameterized complexity theory

Jörg Flum and Martin Grohe. Parameterized complexity theory . Texts in theoretical computer science an EATCS series. Springer, Berlin Heidelberg, 2006. https://doi.org/10.1007/3-540-29953-X doi:10.1007/3-540-29953-X

doi:10.1007/3-540-29953-x 2006

[8] [8]

Integer multiplication in time O (n n)

David Harvey and Joris van der Hoeven. Integer multiplication in time O (n n) . Annals of Mathematics , 193(2):563--617, 2021. https://doi.org/10.4007/annals.2021.193.2.4 doi:10.4007/annals.2021.193.2.4

doi:10.4007/annals.2021.193.2.4 2021