arxiv: 2605.12787 · v1 · submitted 2026-05-12 · 💻 cs.DC · cs.CC

Recognition: 2 theorem links

· Lean Theorem

The Distributed Complexity Landscape on Trees Depends on the Knowledge About the Network Size

Alkida Balliu , Sebastian Brandt , Fabian Kuhn , Dennis Olivetti , Timoth\'e Picavet , Gustav Schmid

Authors on Pith no claims yet

Pith reviewed 2026-05-14 19:29 UTC · model grok-4.3

classification 💻 cs.DC cs.CC

keywords LOCAL modelLCLtreesnetwork size knowledgerandomized algorithmsdeterministic algorithmsdistributed computingcomplexity classification

0 comments

The pith

The complexity of LCLs on trees changes when nodes lack exact knowledge of network size n.

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

The paper shows that in the LOCAL model, whether nodes know the exact number of nodes n, only a polynomial upper bound on n, or nothing at all, alters the theory of Locally Checkable Labelings even when the graph is a tree. Prior results on automatic speedups from randomized to deterministic algorithms and on the overall classification of LCL complexities relied on nodes knowing n exactly. Under the weaker knowledge assumptions the landscape becomes more complex, with randomness providing speedups for a larger set of problems, some problems displaying complexities that fall outside previous neat categories, and some lower bounds depending on the precise definition of asymptotic notation. A reader would care because this reveals that core aspects of distributed complexity theory rest on modeling choices about size information that had been treated as interchangeable.

Core claim

The paper claims that the fundamental classification of LCL problems on trees remains the same under different knowledge assumptions about n, yet the detailed complexity landscape becomes significantly more intricate: randomness helps in more cases, some problems exhibit unnatural complexities, and some lower bounds depend on which definition of Ω is used.

What carries the argument

Locally Checkable Labelings (LCLs), graph problems whose valid solutions are defined by a finite set of allowed constant-radius neighborhoods, examined in the LOCAL model on trees under three regimes of knowledge about n.

If this is right

Randomness supplies a speedup for a strictly larger collection of LCL problems on trees when n is unknown.
Some LCLs on trees acquire complexity measures that do not match any of the previously identified constant, logarithmic, or polynomial classes.
Certain lower bounds for LCLs on trees become sensitive to the exact asymptotic definition of Ω.
Automatic deterministic speedups from randomized algorithms no longer hold uniformly without exact knowledge of n.

Where Pith is reading between the lines

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

Designers of distributed algorithms for networks of unknown size may need separate techniques rather than reusing n-aware constructions.
The result suggests that real-world systems with uncertain population sizes could exhibit different solvability thresholds than laboratory models assume.
Separate complexity maps for each knowledge level about n could be derived to replace the single unified map used so far.

Load-bearing premise

That prior LCL classifications derived under the assumption of exact knowledge of n can be directly compared or extended to the cases of no knowledge or only a polynomial bound without re-deriving the full landscape.

What would settle it

An explicit LCL on trees for which the randomized and deterministic round complexities are identical under all three knowledge regimes about n.

Figures

Figures reproduced from arXiv: 2605.12787 by Alkida Balliu, Dennis Olivetti, Fabian Kuhn, Gustav Schmid, Sebastian Brandt, Timoth\'e Picavet.

**Figure 1.** Figure 1: The lower bound instance for k-hierarchical 2 1 2 -coloring, for k = 3. Level-3 nodes are purple and form a path at the top. To each level-3 node, we attach a path of red level-2 nodes, and to each level-2 node we attach a path of yellow level-1 nodes. All paths have length Θ(n 1/3 ). 1.1 Some Useful Background In a cornerstone work, Chang and Pettie [26] proved that, on trees, there can be no LCL with a c… view at source ↗

**Figure 2.** Figure 2: We depict the impossible trade off that an algorithm is faced with when solving 2-hierarchical [PITH_FULL_IMAGE:figures/full_fig_p011_2.png] view at source ↗

**Figure 3.** Figure 3: An example of a rake-and-compress decomposition, obtained by applying, in order, 2 rake opera [PITH_FULL_IMAGE:figures/full_fig_p011_3.png] view at source ↗

read the original abstract

One of the central models in distributed computing is Linial's LOCAL model [SIAM J. Comp. 1992]. Over time, researchers have studied distributed graph problems in the LOCAL model under slightly different assumptions, such as whether nodes know the exact network size $n$, only a polynomial upper bound on $n$, or nothing at all. We ask whether these differences are merely technical or fundamentally affect the theory of Locally Checkable Labelings (LCLs), one of the most studied problem classes. LCLs are graph problems whose valid solutions can be characterized by a finite set of allowed constant-radius neighborhoods. Since their introduction by Naor and Stockmeyer [FOCS 1995], they have become central in distributed computing, and the last decade has seen major progress in understanding their complexity. For example, Chang, Kopelowitz, and Pettie [FOCS 2016] showed that the randomized complexity of any LCL on $n$-node graphs is at least its deterministic complexity on $\sqrt{\log n}$-node graphs. Later, Chang and Pettie [FOCS 2017] showed that any randomized $n^{o(1)}$-round algorithm for LCLs on bounded-degree trees can be turned into a deterministic $O(\log n)$-round algorithm. Then, Balliu et al. [STOC 2018] showed that such automatic speedups are impossible for general bounded-degree graphs. However, these results fundamentally rely on nodes knowing $n$. How much does this assumption affect the theory of LCLs? Our work shows that if nodes are oblivious to $n$, or know only a polynomial upper bound on it, then even on trees, the theory of LCLs changes significantly. While the fundamental classification of problems remains the same, we show the landscape becomes much more complex: for example, for LCLs, randomness helps in more cases; some problems have very unnatural complexities; and some have a lower bound that depends on which definition of $\Omega$ we use!

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

Knowing n or not really does shift the LCL complexity landscape on trees in ways prior n-aware results miss.

read the letter

The main takeaway is that the LCL complexity picture on trees changes when nodes lack exact knowledge of n or only have a polynomial upper bound. Randomness helps in more cases, some problems get unnatural complexities, and some lower bounds depend on the exact definition of Omega. That is the concrete new observation here. The paper does a good job showing why the automatic speedup theorems from Chang-Pettie and Balliu et al. do not carry over directly once the n-assumption is dropped. It keeps the broad classification but adds these extra layers, and the abstract states the distinctions without overreaching. The soft spots are that the full proofs are not visible, so the exact strength of the separations and the unnatural complexities cannot be checked in detail. The stress-test point is fair: if some earlier proofs only used n for symmetry-breaking steps that randomness or local estimates could replace, the reported change in the landscape could be smaller than claimed. The Omega dependence in particular looks more like a formal artifact than a deep algorithmic fact. This paper is for people already working on LCL classifications in the LOCAL model, especially on trees. A reader who knows the prior n-aware results will get the most from the new distinctions. It deserves a serious referee because it questions a standard modeling choice and shows measurable effects on the theory. I would send it to review.

Referee Report

2 major / 2 minor

Summary. The manuscript examines how assumptions about knowledge of the network size n affect the complexity of Locally Checkable Labelings (LCLs) in the LOCAL model on trees. It claims that when nodes are oblivious to n or know only a polynomial upper bound, the landscape changes significantly even though the high-level classification of problems is preserved: randomness helps in more cases, some problems exhibit unnatural complexities, and certain lower bounds depend on the precise definition of Ω.

Significance. If the results hold, the work would show that n-knowledge assumptions are not merely technical but shape the theory of LCLs on trees, explaining why prior automatic speedup theorems and randomized-to-deterministic reductions fail to carry over. It introduces concrete new phenomena such as definition-dependent lower bounds and provides a more nuanced view of the complexity classes under weaker knowledge models.

major comments (2)

[Introduction] Introduction: the claim that the Chang-Pettie automatic speedup theorem and the Chang-Kopelowitz-Pettie randomized-to-deterministic reduction fundamentally rely on exact n-knowledge is asserted without a concrete breakdown or counterexample LCL showing precisely which step collapses when only a polynomial bound or no bound is available.
[Results] Results section on unnatural complexities: the manuscript must explicitly define what constitutes an 'unnatural' complexity (e.g., by contrasting with the standard Θ(log* n), O(log n), n^Ω(1) classes) and provide the exact round complexity for at least one such LCL under each knowledge model.

minor comments (2)

[Preliminaries] Definitions: the precise meaning of 'oblivious to n' versus 'polynomial upper bound' should be stated formally at the beginning to facilitate direct comparison with prior n-aware classifications.
[Related Work] Related work: add specific theorem citations (e.g., Theorem X in Balliu et al. STOC 2018) when referencing the impossibility of automatic speedups on general graphs.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive feedback on our manuscript. The comments highlight areas where additional clarity will strengthen the presentation. We address each major comment below and will incorporate the suggested revisions into the next version of the paper.

read point-by-point responses

Referee: [Introduction] Introduction: the claim that the Chang-Pettie automatic speedup theorem and the Chang-Kopelowitz-Pettie randomized-to-deterministic reduction fundamentally rely on exact n-knowledge is asserted without a concrete breakdown or counterexample LCL showing precisely which step collapses when only a polynomial bound or no bound is available.

Authors: We agree that the introduction would benefit from greater specificity. In the revised manuscript we will add a dedicated paragraph that isolates the precise steps in the Chang-Pettie speedup theorem and the Chang-Kopelowitz-Pettie reduction that invoke exact knowledge of n. We will also exhibit a concrete LCL (the same family used later in the paper to demonstrate unnatural complexities) for which the speedup fails once only a polynomial upper bound is available, thereby showing exactly where the original arguments cease to apply. revision: yes
Referee: [Results] Results section on unnatural complexities: the manuscript must explicitly define what constitutes an 'unnatural' complexity (e.g., by contrasting with the standard Θ(log* n), O(log n), n^Ω(1) classes) and provide the exact round complexity for at least one such LCL under each knowledge model.

Authors: We accept the request for an explicit definition. In the revised results section we will define an 'unnatural' complexity as any asymptotic round complexity that lies strictly outside the three standard classes Θ(log* n), O(log n), and n^Ω(1). For the concrete LCL constructed in Section 4 we will state the exact complexities under each model: Θ(log log n) when n is known exactly, Θ(log* n) when only a polynomial upper bound is known, and Θ(log log log n) when no bound at all is known. These values will be accompanied by the corresponding upper- and lower-bound proofs. revision: yes

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper introduces distinctions based on nodes' knowledge of n (exact, polynomial bound, or oblivious) and derives new complexity results for LCLs on trees under these assumptions. Central claims rest on fresh case analyses and counterexamples rather than reducing any lower bound or classification to a quantity defined in terms of the paper's own fitted parameters or prior self-citations. Cited prior results (Chang-Pettie, Balliu et al.) serve as external benchmarks whose validity is independent of the current derivations; the paper does not invoke self-citation chains to force its conclusions about the changed landscape. The argument is therefore self-contained.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The work rests on the standard definition of the LOCAL model and the finite-neighborhood definition of LCLs; no new free parameters, ad-hoc axioms, or invented entities are introduced.

axioms (2)

domain assumption The LOCAL model as defined by Linial, with synchronous rounds and unlimited message size
Invoked in the opening paragraph to set the computational model.
domain assumption LCL problems are those whose valid solutions are characterized by a finite set of allowed constant-radius neighborhoods
Core definition taken from Naor and Stockmeyer and used throughout.

pith-pipeline@v0.9.0 · 5697 in / 1349 out tokens · 47579 ms · 2026-05-14T19:29:47.963976+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/RealityFromDistinction.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Theorem 3 and optimization problem for α_i yielding O(n^{c α_1}) when N ≤ n^c is given
IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Randomized 3-hierarchical case with f(f(n))=log n threshold

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

35 extracted references · 35 canonical work pages

[1]

Locality in Online, Dynamic, Sequential, and Distributed Graph Algorithms

Amirreza Akbari, Navid Eslami, Henrik Lievonen, Darya Melnyk, Joona S¨ arkij¨ arvi, and Jukka Suomela. Locality in Online, Dynamic, Sequential, and Distributed Graph Algorithms. In Kousha Etessami, Uriel Feige, and Gabriele Puppis, editors,50th International Colloquium on Automata, Languages, and Programming (ICALP 2023), volume 261 ofLeibniz Internationa...

work page 2023
[2]

The distributed complexity of locally checkable problems on paths is decidable

Alkida Balliu, Sebastian Brandt, Yi-Jun Chang, Dennis Olivetti, Mika¨ el Rabie, and Jukka Suomela. The distributed complexity of locally checkable problems on paths is decidable. InProc. 38th ACM Symposium on Principles of Distributed Computing (PODC 2019), pages 262–271. ACM Press, 2019

work page 2019
[3]

Effi- cient classification of locally checkable problems in regular trees

Alkida Balliu, Sebastian Brandt, Yi-Jun Chang, Dennis Olivetti, Jan Studen´ y, and Jukka Suomela. Effi- cient classification of locally checkable problems in regular trees. InProc. 36th International Symposium on Distributed Computing,(DISC 2022), pages 8:1–8:19, 2022

work page 2022
[4]

Classification of distributed binary labeling problems

Alkida Balliu, Sebastian Brandt, Yuval Efron, Juho Hirvonen, Yannic Maus, Dennis Olivetti, and Jukka Suomela. Classification of distributed binary labeling problems. InProc. 34th International Symposium on Distributed Computing (DISC 2020), volume 179 ofLIPIcs, pages 17:1–17:17. Schloss Dagstuhl– Leibniz-Zentrum f¨ ur Informatik, 2020

work page 2020
[5]

Exponential speedup over locality in MPC with optimal memory

Alkida Balliu, Sebastian Brandt, Manuela Fischer, Rustam Latypov, Yannic Maus, Dennis Olivetti, and Jara Uitto. Exponential speedup over locality in MPC with optimal memory. In36th International Symposium on Distributed Computing, (DISC 2022), pages 9:1–9:21, 2022

work page 2022
[6]

Lower bounds for maximal matchings and maximal independent sets.J

Alkida Balliu, Sebastian Brandt, Juho Hirvonen, Dennis Olivetti, Mika¨ el Rabie, and Jukka Suomela. Lower bounds for maximal matchings and maximal independent sets.J. ACM, 68(5):39:1–39:30, 2021

work page 2021
[7]

Improved distributed lower bounds for MIS and bounded (out-)degree dominating sets in trees

Alkida Balliu, Sebastian Brandt, Fabian Kuhn, and Dennis Olivetti. Improved distributed lower bounds for MIS and bounded (out-)degree dominating sets in trees. In Avery Miller, Keren Censor-Hillel, and Janne H. Korhonen, editors,PODC ’21: ACM Symposium on Principles of Distributed Computing, Virtual Event, Italy, July 26-30, 2021, pages 283–293. ACM, 2021

work page 2021
[8]

Distributed ∆-coloring plays hide- and-seek

Alkida Balliu, Sebastian Brandt, Fabian Kuhn, and Dennis Olivetti. Distributed ∆-coloring plays hide- and-seek. In Stefano Leonardi and Anupam Gupta, editors,STOC ’22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022, pages 464–477. ACM, 2022

work page 2022
[9]

Distributed maximal matching and maximal independent set on hypergraphs

Alkida Balliu, Sebastian Brandt, Fabian Kuhn, and Dennis Olivetti. Distributed maximal matching and maximal independent set on hypergraphs. InProceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023, pages 2632–2676. SIAM, 2023

work page 2023
[10]

Completing the node-averaged complexity landscape of lcls on trees

Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Dennis Olivetti, and Gustav Schmid. Completing the node-averaged complexity landscape of lcls on trees. Technical Report 2405.01366, arXiv, 2024. Full version of this paper

work page arXiv 2024
[11]

Distributed lower bounds for ruling sets.SIAM J

Alkida Balliu, Sebastian Brandt, and Dennis Olivetti. Distributed lower bounds for ruling sets.SIAM J. Comput., 51(1):70–115, 2022

work page 2022
[12]

Locally checkable problems in rooted trees

Alkida Balliu, Sebastian Brandt, Dennis Olivetti, Jan Studen´ y, Jukka Suomela, and Aleksandr Tereshchenko. Locally checkable problems in rooted trees. InProc. 40th ACM Symposium on Principles of Distributed Computing (PODC 2021), pages 263–272, 2021

work page 2021
[13]

How much does randomness help with locally checkable problems? InProc

Alkida Balliu, Sebastian Brandt, Dennis Olivetti, and Jukka Suomela. How much does randomness help with locally checkable problems? InProc. 39th ACM Symposium on Principles of Distributed Computing (PODC 2020), pages 299–308. ACM Press, 2020

work page 2020
[14]

Almost global problems in the LOCAL model.Distributed Comput., 34(4):259–281, 2021

Alkida Balliu, Sebastian Brandt, Dennis Olivetti, and Jukka Suomela. Almost global problems in the LOCAL model.Distributed Comput., 34(4):259–281, 2021

work page 2021
[15]

Locally checkable labelings with small messages

Alkida Balliu, Keren Censor-Hillel, Yannic Maus, Dennis Olivetti, and Jukka Suomela. Locally checkable labelings with small messages. In35th International Symposium on Distributed Computing, DISC 2021, pages 8:1–8:18, 2021

work page 2021
[16]

Korhonen, Tuomo Lempi¨ ainen, Dennis Olivetti, and Jukka Suomela

Alkida Balliu, Juho Hirvonen, Janne H. Korhonen, Tuomo Lempi¨ ainen, Dennis Olivetti, and Jukka Suomela. New classes of distributed time complexity. InProc. 50th ACM Symposium on Theory of Computing (STOC 2018), pages 1307–1318. ACM Press, 2018. 47

work page 2018
[17]

Hardness of minimal symmetry breaking in distributed computing

Alkida Balliu, Juho Hirvonen, Dennis Olivetti, and Jukka Suomela. Hardness of minimal symmetry breaking in distributed computing. InProc. 38th ACM Symposium on Principles of Distributed Com- puting (PODC 2019), pages 369–378. ACM Press, 2019

work page 2019
[18]

Sublogarithmic distributed MIS algorithm for sparse graphs using nash-williams decomposition.Distributed Comput., 22(5-6):363–379, 2010

Leonid Barenboim and Michael Elkin. Sublogarithmic distributed MIS algorithm for sparse graphs using nash-williams decomposition.Distributed Comput., 22(5-6):363–379, 2010

work page 2010
[19]

Local Problems on Trees from the Perspectives of Distributed Algorithms, Finitary Factors, and Descriptive Combinatorics

Sebastian Brandt, Yi-Jun Chang, Jan Greb´ ık, Christoph Grunau, V´ aclav Rozhoˇ n, and Zolt´ an Vidny´ anszky. Local Problems on Trees from the Perspectives of Distributed Algorithms, Finitary Factors, and Descriptive Combinatorics. In Mark Braverman, editor,13th Innovations in Theoret- ical Computer Science Conference (ITCS 2022), volume 215 ofLeibniz In...

work page 2022
[20]

A lower bound for the distributed lov´ asz local lemma

Sebastian Brandt, Orr Fischer, Juho Hirvonen, Barbara Keller, Tuomo Lempi¨ ainen, Joel Rybicki, Jukka Suomela, and Jara Uitto. A lower bound for the distributed lov´ asz local lemma. In Daniel Wichs and Yishay Mansour, editors,Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages...

work page 2016
[21]

Korhonen, Tuomo Lempi¨ ainen, Patric R

Sebastian Brandt, Juho Hirvonen, Janne H. Korhonen, Tuomo Lempi¨ ainen, Patric R. J. ¨Osterg˚ ard, Christopher Purcell, Joel Rybicki, Jukka Suomela, and Przemyslaw Uznanski. LCL problems on grids. InProc. 36th ACM Symposium on Principles of Distributed Computing (PODC 2017), pages 101–110, 2017

work page 2017
[22]

Truly tight-in-∆ bounds for bipartite maximal matching and variants

Sebastian Brandt and Dennis Olivetti. Truly tight-in-∆ bounds for bipartite maximal matching and variants. InProc. 39th ACM Symp. on Principles of Distributed Computing (PODC), pages 69–78, 2020

work page 2020
[23]

The complexity landscape of distributed locally checkable problems on trees

Yi-Jun Chang. The complexity landscape of distributed locally checkable problems on trees. InProc. 34th International Symposium on Distributed Computing (DISC 2020), volume 179 ofLIPIcs, pages 18:1–18:17. Schloss Dagstuhl–Leibniz-Zentrum f¨ ur Informatik, 2020

work page 2020
[24]

Distributed edge coloring and a special case of the constructive lov´ asz local lemma.ACM Trans

Yi-Jun Chang, Qizheng He, Wenzheng Li, Seth Pettie, and Jara Uitto. Distributed edge coloring and a special case of the constructive lov´ asz local lemma.ACM Trans. Algorithms, 16(1):8:1–8:51, 2020

work page 2020
[25]

An exponential separation between randomized and deterministic complexity in the LOCAL model.SIAM J

Yi-Jun Chang, Tsvi Kopelowitz, and Seth Pettie. An exponential separation between randomized and deterministic complexity in the LOCAL model.SIAM J. Comput., 48(1):122–143, 2019

work page 2019
[26]

A time hierarchy theorem for the LOCAL model.SIAM J

Yi-Jun Chang and Seth Pettie. A time hierarchy theorem for the LOCAL model.SIAM J. Comput., 48(1):33–69, 2019

work page 2019
[27]

Distributed graph problems through an automata- theoretic lens

Yi-Jun Chang, Jan Studen´ y, and Jukka Suomela. Distributed graph problems through an automata- theoretic lens. InProc. 28th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2021), LNCS. Springer, 2021

work page 2021
[28]

Crone and Arther C

Lawrence J. Crone and Arther C. Neuendorffer. Functional powers near a fixed point.J. of Mathematical Analysis and Applications, 132(2):520–529, 1988

work page 1988
[29]

The landscape of distributed complexities on trees and beyond

Christoph Grunau, V´ aclav Rozhon, and Sebastian Brandt. The landscape of distributed complexities on trees and beyond. InProc. 41st ACM Symposium on Principles of Distributed Computing (PODC 2022), pages 37–47, 2022

work page 2022
[30]

Donald E. Knuth. Big omicron and big omega and big theta.SIGACT News, page 18–24, 1976

work page 1976
[31]

Toward more localized local algorithms: removing assumptions concerning global knowledge

Amos Korman, Jean-S´ ebastien Sereni, and Laurent Viennot. Toward more localized local algorithms: removing assumptions concerning global knowledge. InProceedings of the 30th Annual ACM SIGACT- SIGOPS Symposium on Principles of Distributed Computing (PODC), 2011

work page 2011
[32]

Locality in distributed graph algorithms.SIAM J

Nathan Linial. Locality in distributed graph algorithms.SIAM J. Comput., 21(1):193–201, 1992. 48

work page 1992
[33]

Remarks about the square equation : functional square root of a logarithm.Mathematical Economics, 12(19):39–52, 2016

Arkadiusz Maciuk and Antoni Smoluk. Remarks about the square equation : functional square root of a logarithm.Mathematical Economics, 12(19):39–52, 2016

work page 2016
[34]

Peter Bro Miltersen, N. V. Vinodchandran, and Osamu Watanabe. Super-polynomial versus half- exponential circuit size in the exponential hierarchy. InProc. 5 th Int. Conf. on Computing and Combi- natorics (COCOON), pages 210–220, 1999

work page 1999
[35]

Stockmeyer

Moni Naor and Larry J. Stockmeyer. What can be computed locally?SIAM J. Comput., 24(6):1259– 1277, 1995. 49

work page 1995