Relationships among $PL$, $\#L$, and the determinant
RAIRO-Theor. Inf. Appl., 30 1 (1996) 1-21
Published online: 2017-02-01
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):
Robustness for Space-Bounded Statistical Zero Knowledge
Eric Allender, Jacob Gray, Saachi Mutreja, Harsha Tirumala and Pengxiang WangACM Transactions on Computation Theory 17 (1) 1 (2025)
https://doi.org/10.1145/3708508
Power of counting by nonuniform families of polynomial-size finite automata
Tomoyuki YamakamiInformation and Computation 307 105372 (2025)
https://doi.org/10.1016/j.ic.2025.105372
The Power Word Problem in Graph Products
Markus Lohrey, Florian Stober and Armin WeißTheory of Computing Systems 68 (3) 403 (2024)
https://doi.org/10.1007/s00224-024-10173-z
Guest Column
Eric AllenderACM SIGACT News 54 (1) 63 (2023)
https://doi.org/10.1145/3586165.3586175
14292 421 (2023)
https://doi.org/10.1007/978-3-031-43587-4_30
Guest column: A panorama of counting problems the decision version of which is in P
Eleni Bakali, Aggeliki Chalki, Andreas Göbel, Aris Pagourtzis and Stathis ZachosACM SIGACT News 53 (3) 46 (2022)
https://doi.org/10.1145/3561064.3561072
1343 (2021)
https://doi.org/10.1145/3406325.3451051
Emptiness problems for integer circuits
Dominik Barth, Moritz Beck, Titus Dose, Christian Glaßer, Larissa Michler and Marc TechnauTheoretical Computer Science 824-825 11 (2020)
https://doi.org/10.1016/j.tcs.2020.03.023
New Insights on the (Non-)Hardness of Circuit Minimization and Related Problems
Eric Allender and Shuichi HiraharaACM Transactions on Computation Theory 11 (4) 1 (2019)
https://doi.org/10.1145/3349616
1 (2017)
https://doi.org/10.1109/LICS.2017.8005081
Asymptotic Perturbation Bounds for Probabilistic Model Checking with Empirically Determined Probability Parameters
Guoxin Su, Yuan Feng, Taolue Chen and David S. RosenblumIEEE Transactions on Software Engineering 42 (7) 623 (2016)
https://doi.org/10.1109/TSE.2015.2508444
Perspectives in Computational Complexity
Vikraman ArvindPerspectives in Computational Complexity 1 (2014)
https://doi.org/10.1007/978-3-319-05446-9_1
Computer Science – Theory and Applications
Mikhail N. VyalyiLecture Notes in Computer Science, Computer Science – Theory and Applications 7913 271 (2013)
https://doi.org/10.1007/978-3-642-38536-0_24
On expressive power of regular realizability problems
M. N. VyalyiProblems of Information Transmission 49 (3) 276 (2013)
https://doi.org/10.1134/S0032946013030058
Encyclopedia of Complexity and Systems Science
John WatrousEncyclopedia of Complexity and Systems Science 1 (2013)
https://doi.org/10.1007/978-3-642-27737-5_428-3
On the complexity of the multivariate resultant
Bruno Grenet, Pascal Koiran and Natacha PortierJournal of Complexity 29 (2) 142 (2013)
https://doi.org/10.1016/j.jco.2012.10.001
The Parallel Complexity of Graph Canonization Under Abelian Group Action
V. Arvind and Johannes KöblerAlgorithmica 67 (2) 247 (2013)
https://doi.org/10.1007/s00453-013-9805-0
Computational Complexity
John WatrousComputational Complexity 2361 (2012)
https://doi.org/10.1007/978-1-4614-1800-9_147
Counting classes and the fine structure between NC1 and L
Samir Datta, Meena Mahajan, B.V. Raghavendra Rao, Michael Thomas and Heribert VollmerTheoretical Computer Science 417 36 (2012)
https://doi.org/10.1016/j.tcs.2011.05.050
The orbit problem is in the GapL hierarchy
V. Arvind and T. C. VijayaraghavanJournal of Combinatorial Optimization 21 (1) 124 (2011)
https://doi.org/10.1007/s10878-009-9243-8
Computing and Combinatorics
V. Arvind and Johannes KöblerLecture Notes in Computer Science, Computing and Combinatorics 6842 444 (2011)
https://doi.org/10.1007/978-3-642-22685-4_39
139 (2010)
https://doi.org/10.1109/CCC.2010.21
On the Complexity of Matrix Rank and Rigidity
Meena Mahajan and Jayalal M. N. SarmaTheory of Computing Systems 46 (1) 9 (2010)
https://doi.org/10.1007/s00224-008-9136-8
Mathematical Foundations of Computer Science 2010
Samir Datta, Meena Mahajan, B. V. Raghavendra Rao, Michael Thomas and Heribert VollmerLecture Notes in Computer Science, Mathematical Foundations of Computer Science 2010 6281 306 (2010)
https://doi.org/10.1007/978-3-642-15155-2_28
Equivalence Problems for Circuits over Sets of Natural Numbers
Christian Glaßer, Katrin Herr, Christian Reitwießner, Stephen Travers and Matthias WaldherrTheory of Computing Systems 46 (1) 80 (2010)
https://doi.org/10.1007/s00224-008-9144-8
Amplifying lower bounds by means of self-reducibility
Eric Allender and Michal KouckýJournal of the ACM 57 (3) 1 (2010)
https://doi.org/10.1145/1706591.1706594
Computer Science Logic
Stephen Cook and Lila FontesLecture Notes in Computer Science, Computer Science Logic 6247 245 (2010)
https://doi.org/10.1007/978-3-642-15205-4_21
7174 (2009)
https://doi.org/10.1007/978-0-387-30440-3_428
Computing and Combinatorics
V. Arvind and T. C. VijayaraghavanLecture Notes in Computer Science, Computing and Combinatorics 5092 160 (2008)
https://doi.org/10.1007/978-3-540-69733-6_17
Mathematical Foundations of Computer Science 2007
Fabian WagnerLecture Notes in Computer Science, Mathematical Foundations of Computer Science 2007 4708 572 (2007)
https://doi.org/10.1007/978-3-540-74456-6_51
28 (2005)
https://doi.org/10.1109/CCC.2005.28
13 (2005)
https://doi.org/10.1109/CCC.2005.7
ON THE MINIMAL POLYNOMIAL OF A MATRIX
THANH MINH HOANG and THOMAS THIERAUFInternational Journal of Foundations of Computer Science 15 (01) 89 (2004)
https://doi.org/10.1142/S0129054104002327
204 (2004)
https://doi.org/10.1109/CCC.2004.1313844
On the Hardness of Graph Isomorphism
Jacobo ToránSIAM Journal on Computing 33 (5) 1093 (2004)
https://doi.org/10.1137/S009753970241096X
Mathematical Foundations of Computer Science 2003
Hubie ChenLecture Notes in Computer Science, Mathematical Foundations of Computer Science 2003 2747 328 (2003)
https://doi.org/10.1007/978-3-540-45138-9_27
SIGACT News complexity theory column 41
Lane A. HemaspaandraACM SIGACT News 34 (3) 26 (2003)
https://doi.org/10.1145/945526.945535
The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes
Maciej Liśkiewicz, Mitsunori Ogihara and Seinosuke TodaTheoretical Computer Science 304 (1-3) 129 (2003)
https://doi.org/10.1016/S0304-3975(03)00080-X
FST TCS 2002: Foundations of Software Technology and Theoretical Computer Science
Thanh Minh Hoang and Thomas ThieraufLecture Notes in Computer Science, FST TCS 2002: Foundations of Software Technology and Theoretical Computer Science 2556 206 (2002)
https://doi.org/10.1007/3-540-36206-1_19
Computing and Combinatorics
Thanh Minh Hoang and Thomas ThieraufLecture Notes in Computer Science, Computing and Combinatorics 2387 37 (2002)
https://doi.org/10.1007/3-540-45655-4_6
Foundations of Information Technology in the Era of Network and Mobile Computing
Alina Beygelzimer and Mitsunori OgiharaFoundations of Information Technology in the Era of Network and Mobile Computing 59 (2002)
https://doi.org/10.1007/978-0-387-35608-2_6
Algorithms and Computation
Andreas Jakoby and Maciej LiśkiewiczLecture Notes in Computer Science, Algorithms and Computation 2223 562 (2001)
https://doi.org/10.1007/3-540-45678-3_48
Complexity of finite-horizon Markov decision process problems
Martin Mundhenk, Judy Goldsmith, Christopher Lusena and Eric AllenderJournal of the ACM 47 (4) 681 (2000)
https://doi.org/10.1145/347476.347480
70 (2000)
https://doi.org/10.1109/CCC.2000.856737
A note on closure properties of logspace MOD classes
Ulrich Hertrampf, Steffen Reith and Heribert VollmerInformation Processing Letters 75 (3) 91 (2000)
https://doi.org/10.1016/S0020-0190(00)00091-0
Making Nondeterminism Unambiguous
Klaus Reinhardt and Eric AllenderSIAM Journal on Computing 29 (4) 1118 (2000)
https://doi.org/10.1137/S0097539798339041
On TC0, AC0, and Arithmetic Circuits
Manindra Agrawal, Eric Allender and Samir DattaJournal of Computer and System Sciences 60 (2) 395 (2000)
https://doi.org/10.1006/jcss.1999.1675
180 (2000)
https://doi.org/10.1109/SFCS.2000.892080
341 (1999)
https://doi.org/10.1109/SFFCS.1999.814605
Isolation, Matching, and Counting Uniform and Nonuniform Upper Bounds
Eric Allender, Klaus Reinhardt and Shiyu ZhouJournal of Computer and System Sciences 59 (2) 164 (1999)
https://doi.org/10.1006/jcss.1999.1646
Space-Bounded Quantum Complexity
John WatrousJournal of Computer and System Sciences 59 (2) 281 (1999)
https://doi.org/10.1006/jcss.1999.1655
Non-commutative arithmetic circuits: depth reduction and size lower bounds
Eric Allender, Jia Jiao, Meena Mahajan and V. VinayTheoretical Computer Science 209 (1-2) 47 (1998)
https://doi.org/10.1016/S0304-3975(97)00227-2
272 (1998)
https://doi.org/10.1109/CCC.1998.694621
92 (1998)
https://doi.org/10.1109/CCC.1998.694594
210 (1998)
https://doi.org/10.1109/CCC.1998.694607
244 (1997)
https://doi.org/10.1109/SFCS.1997.646113
Mathematical Foundations of Computer Science 1997
Martin Mundhenk, Judy Goldsmith and Eric AllenderLecture Notes in Computer Science, Mathematical Foundations of Computer Science 1997 1295 129 (1997)
https://doi.org/10.1007/BFb0029956