Division in logspace-uniform NC1
RAIRO-Theor. Inf. Appl., 35 3 (2001) 259-275
Published online: 2002-04-15
Articles citing this article
The Citing articles tool gives a list of articles citing the current article.
The citing articles come from EDP Sciences database, as well as other publishers participating in CrossRef Cited-by Linking Program. You can set up your personal account to receive an email alert each time this article is cited by a new article (see the menu on the right-hand side of the abstract page).
Cited article:
This article has been cited by the following article(s):
The complexity of computing the period and the exponent of a digraph
Stefan Kiefer and Andrew RyzhikovInformation Processing Letters 191 106590 (2026)
https://doi.org/10.1016/j.ipl.2025.106590
15764 237 (2025)
https://doi.org/10.1007/978-3-031-95908-0_17
Reachability in Two-Parametric Timed Automata with one Parameter is EXPSPACE-Complete
Stefan Göller and Mathieu HilaireTheory of Computing Systems 68 (4) 900 (2024)
https://doi.org/10.1007/s00224-023-10121-3
14527 53 (2024)
https://doi.org/10.1007/978-981-97-0945-8_4
https://doi.org/10.1002/9781394213139.biblio
The Parallelism Tradeoff: Limitations of Log-Precision Transformers
William Merrill and Ashish SabharwalTransactions of the Association for Computational Linguistics 11 531 (2023)
https://doi.org/10.1162/tacl_a_00562
On the complexity of algebraic numbers, and the bit-complexity of straight-line programs
Eric Allender, Nikhil Balaji, Samir Datta and Rameshwar PratapComputability 12 (2) 145 (2023)
https://doi.org/10.3233/COM-220407
Generation of small complexity classes using logical formulas, schemes and operations of bounded concatenation
Igor Vladimirovich Savitskii and Sergey Seraphimovich MarchenkovMathematical Problems of Cybernetics (21) 52 (2023)
https://doi.org/10.20948/mvk-2023-52
Iterated multiplication in $$ VTC ^0$$
Emil JeřábekArchive for Mathematical Logic 61 (5-6) 705 (2022)
https://doi.org/10.1007/s00153-021-00810-6
Unary Coded PSPACE-Complete Languages in ASPACE(loglog n)
Viliam GeffertTheory of Computing Systems 63 (4) 688 (2019)
https://doi.org/10.1007/s00224-018-9844-7
Parallel Identity Testing for Skew Circuits with Big Powers and Applications
Daniel Konig and Markus LohreyInternational Journal of Algebra and Computation (2018)
https://doi.org/10.1142/S0218196718500431
A transfer method from bounded existential Diophantine equations to Tarski algebra formulas
B. LitowTheoretical Computer Science 708 91 (2018)
https://doi.org/10.1016/j.tcs.2017.10.013
10304 141 (2017)
https://doi.org/10.1007/978-3-319-58747-9_14
1 (2017)
https://doi.org/10.1145/3109453.3109458
On Space Efficiency of Algorithms Working on Structural Decompositions of Graphs
Michał Pilipczuk and Marcin WrochnaACM Transactions on Computation Theory 9 (4) 1 (2017)
https://doi.org/10.1145/3154856
Dual VP Classes
Eric Allender, Anna Gál and Ian Mertzcomputational complexity 26 (3) 583 (2017)
https://doi.org/10.1007/s00037-016-0146-7
The Fine Classification of Conjunctive Queries and Parameterized Logarithmic Space
Hubie Chen and Moritz MüllerACM Transactions on Computation Theory 7 (2) 1 (2015)
https://doi.org/10.1145/2751316
Open induction in a bounded arithmetic for TC0
Emil JeřábekArchive for Mathematical Logic 54 (3-4) 359 (2015)
https://doi.org/10.1007/s00153-014-0414-7
Space-Bounded Church-Turing Thesis and Computational Tractability of Closed Systems
Mark Braverman, Jonathan Schneider and Cristóbal RojasPhysical Review Letters 115 (9) (2015)
https://doi.org/10.1103/PhysRevLett.115.098701
Parallel algorithms for matroid intersection and matroid parity
Jinyu HuangDiscrete Mathematics, Algorithms and Applications 07 (02) 1550019 (2015)
https://doi.org/10.1142/S1793830915500196
The Compressed Word Problem for Groups
Markus LohreySpringerBriefs in Mathematics, The Compressed Word Problem for Groups 1 (2014)
https://doi.org/10.1007/978-1-4939-0748-9_1
Mathematical Foundations of Computer Science 2014
Eric Allender, Nikhil Balaji and Samir DattaLecture Notes in Computer Science, Mathematical Foundations of Computer Science 2014 8635 13 (2014)
https://doi.org/10.1007/978-3-662-44465-8_2
Mathematical Foundations of Computer Science 2014
Akitoshi Kawamura and Hiroyuki OtaLecture Notes in Computer Science, Mathematical Foundations of Computer Science 2014 8635 432 (2014)
https://doi.org/10.1007/978-3-662-44465-8_37
On parallel complexity of analytic functions
Fuxiang Yu and Ker-I KoTheoretical Computer Science 489-490 48 (2013)
https://doi.org/10.1016/j.tcs.2013.04.008
Branching-Time Model Checking of One-Counter Processes and Timed Automata
Stefan Göller and Markus LohreySIAM Journal on Computing 42 (3) 884 (2013)
https://doi.org/10.1137/120876435
Log-Space Algorithms for Paths and Matchings in k-Trees
Bireswar Das, Samir Datta and Prajakta NimbhorkarTheory of Computing Systems 53 (4) 669 (2013)
https://doi.org/10.1007/s00224-013-9469-9
Small Space Analogues of Valiant’s Classes and the Limitations of Skew Formulas
Meena Mahajan and B. V. Raghavendra Raocomputational complexity 22 (1) 1 (2013)
https://doi.org/10.1007/s00037-011-0024-2
Root finding with threshold circuits
Emil JeřábekTheoretical Computer Science 462 59 (2012)
https://doi.org/10.1016/j.tcs.2012.09.001
Developments in Language Theory
Viliam Geffert and Dana PardubskáLecture Notes in Computer Science, Developments in Language Theory 7410 166 (2012)
https://doi.org/10.1007/978-3-642-31653-1_16
Counting Paths in VPA Is Complete for #NC 1
Andreas Krebs, Nutan Limaye and Meena MahajanAlgorithmica 64 (2) 279 (2012)
https://doi.org/10.1007/s00453-011-9501-x
On the complexity of regular-grammars with integer attributes
M. Manna, F. Scarcello and N. LeoneJournal of Computer and System Sciences 77 (2) 393 (2011)
https://doi.org/10.1016/j.jcss.2010.05.006
175 (2011)
https://doi.org/10.1109/LICS.2011.8
Automata, Languages and Programming
Stefan Göller, Christoph Haase, Joël Ouaknine and James WorrellLecture Notes in Computer Science, Automata, Languages and Programming 6199 575 (2010)
https://doi.org/10.1007/978-3-642-14162-1_48
Arithmetizing Classes Around $\textsf{NC}$ 1 and $\textsf{L}$
Nutan Limaye, Meena Mahajan and B. V. Raghavendra RaoTheory of Computing Systems 46 (3) 499 (2010)
https://doi.org/10.1007/s00224-009-9233-3
143 (2010)
https://doi.org/10.1109/FOCS.2010.21
SOFSEM 2009: Theory and Practice of Computer Science
Viliam Geffert and Dana PardubskáLecture Notes in Computer Science, SOFSEM 2009: Theory and Practice of Computer Science 5404 291 (2009)
https://doi.org/10.1007/978-3-540-95891-8_28
Fast arithmetics using Chinese remaindering
George Davida, Bruce Litow and Guangwu XuInformation Processing Letters 109 (13) 660 (2009)
https://doi.org/10.1016/j.ipl.2009.02.024
Space complexity of Abelian groups
Douglas Cenzer, Rodney G. Downey, Jeffrey B. Remmel and Zia UddinArchive for Mathematical Logic 48 (1) 115 (2009)
https://doi.org/10.1007/s00153-008-0113-3
Physically-relativized Church–Turing Hypotheses: Physical foundations of computing and complexity theory of computational physics
Martin ZieglerApplied Mathematics and Computation 215 (4) 1431 (2009)
https://doi.org/10.1016/j.amc.2009.04.062
Census algorithms for chinese remainder pseudorank
David Laing and Bruce LitowRAIRO - Theoretical Informatics and Applications 42 (2) 309 (2008)
https://doi.org/10.1051/ita:2007024
FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science
Andreas Jakoby and Till TantauLecture Notes in Computer Science, FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science 4855 216 (2007)
https://doi.org/10.1007/978-3-540-77050-3_18
STACS 2007
Manindra Agrawal, Thanh Minh Hoang and Thomas ThieraufLecture Notes in Computer Science, STACS 2007 4393 489 (2007)
https://doi.org/10.1007/978-3-540-70918-3_42
STACS 2007
Nutan Limaye, Meena Mahajan and B. V. Raghavendra RaoLecture Notes in Computer Science, STACS 2007 4393 477 (2007)
https://doi.org/10.1007/978-3-540-70918-3_41
Logical Approaches to Computational Barriers
Douglas Cenzer and Zia UddinLecture Notes in Computer Science, Logical Approaches to Computational Barriers 3988 75 (2006)
https://doi.org/10.1007/11780342_8
STACS 2006
Lance Fortnow and Adam R. KlivansLecture Notes in Computer Science, STACS 2006 3884 469 (2006)
https://doi.org/10.1007/11672142_38
Space efficient algorithms for directed series–parallel graphs
Andreas Jakoby, Maciej Liśkiewicz and Rüdiger ReischukJournal of Algorithms 60 (2) 85 (2006)
https://doi.org/10.1016/j.jalgor.2004.06.010
On the Hardness of Graph Isomorphism
Jacobo ToránSIAM Journal on Computing 33 (5) 1093 (2004)
https://doi.org/10.1137/S009753970241096X
On the reducibility of sets inside NP to sets with low information content
Mitsunori Ogihara and Till TantauJournal of Computer and System Sciences 69 (4) 499 (2004)
https://doi.org/10.1016/j.jcss.2004.03.003
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
Dan Gutfreund and Emanuele ViolaLecture Notes in Computer Science, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques 3122 381 (2004)
https://doi.org/10.1007/978-3-540-27821-4_34
204 (2004)
https://doi.org/10.1109/CCC.2004.1313844
The dynamic complexity of transitive closure is in DynTC0
William HesseTheoretical Computer Science 296 (3) 473 (2003)
https://doi.org/10.1016/S0304-3975(02)00740-5
Uniform constant-depth threshold circuits for division and iterated multiplication
William Hesse, Eric Allender and David A. Mix BarringtonJournal of Computer and System Sciences 65 (4) 695 (2002)
https://doi.org/10.1016/S0022-0000(02)00025-9
Automata, Languages and Programming
Andreas Jakoby and Maciej LiskiewiczLecture Notes in Computer Science, Automata, Languages and Programming 2380 269 (2002)
https://doi.org/10.1007/3-540-45465-9_24