Antonelli, Melissa; Dal Lago, Ugo; Pistone, Paolo Towards logical foundations for probabilistic computation. (English) Zbl 07870393 Ann. Pure Appl. Logic 175, No. 9, Article ID 103341, 51 p. (2024). MSC: 03F03 03D15 68Q10 68Q15 68N18 × Cite Format Result Cite Review PDF Full Text: DOI
Yamakami, Tomoyuki Power of counting by nonuniform families of polynomial-size finite automata. (English) Zbl 07856035 Fernau, Henning (ed.) et al., Fundamentals of computation theory. 24th international symposium, FCT 2023, Trier, Germany, September 18–21, 2023. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 14292, 421-435 (2023). MSC: 68Qxx × Cite Format Result Cite Review PDF Full Text: DOI arXiv
Haak, Anselm; Meier, Arne; Prakash, Om; Rao, B. V. Raghavendra Parameterised counting in logspace. (English) Zbl 07746789 Algorithmica 85, No. 10, 2923-2961 (2023). MSC: 68Wxx 05Cxx 68Q15 × Cite Format Result Cite Review PDF Full Text: DOI arXiv
Hemaspaandra, Lane A.; Juvekar, Mandar; Nadjimzadah, Arian; Phillips, Patrick A. Gaps, ambiguity, and establishing complexity-class containments via iterative constant-setting. (English) Zbl 07893095 Szeider, Stefan (ed.) et al., 47th international symposium on mathematical foundations of computer science, MFCS 2022, Vienna, Austria, August 22–26, 2022. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 241, Article 57, 15 p. (2022). MSC: 68Qxx × Cite Format Result Cite Review PDF Full Text: DOI arXiv
Kołodziejczyk, Leszek Aleksander; Thapen, Neil Approximate counting and NP search problems. (English) Zbl 07632519 J. Math. Log. 22, No. 3, Article ID 2250012, 31 p. (2022). MSC: 03F30 03D15 68Q15 68Q17 03F20 × Cite Format Result Cite Review PDF Full Text: DOI arXiv
Dal Lago, Ugo; Kahle, Reinhard; Oitavem, Isabel Implicit recursion-theoretic characterizations of counting classes. (English) Zbl 1506.03096 Arch. Math. Logic 61, No. 7-8, 1129-1144 (2022). Reviewer: Marat M. Arslanov (Kazan) MSC: 03D15 68Q15 × Cite Format Result Cite Review PDF Full Text: DOI
Colombo, João Guilherme Fritsche; Marchi, Jerusa A nondeterministic Turing machine variant to compute functions. (English) Zbl 1533.68065 Theor. Comput. Sci. 902, 54-63 (2022). MSC: 68Q04 68Q10 68Q15 × Cite Format Result Cite Review PDF Full Text: DOI
Arenas, Marcelo; Croquevielle, Luis Alberto; Jayaram, Rajesh; Riveros, Cristian #NFA admits an FPRAS: efficient enumeration, counting, and uniform generation for logspace classes. (English) Zbl 1499.68124 J. ACM 68, No. 6, Article No. 48, 40 p. (2021). MSC: 68Q15 68P15 68Q04 68Q25 68Q45 68W20 68W25 × Cite Format Result Cite Review PDF Full Text: DOI arXiv
Durand, Arnaud; Haak, Anselm; Kontinen, Juha; Vollmer, Heribert Descriptive complexity of #P functions: a new perspective. (English) Zbl 1467.68060 J. Comput. Syst. Sci. 116, 40-54 (2021). MSC: 68Q19 68Q06 × Cite Format Result Cite Review PDF Full Text: DOI Link
Leporati, Alberto; Manzoni, Luca; Mauri, Giancarlo; Porreca, Antonio E.; Zandron, Claudio Simulating counting oracles with cooperation. (English) Zbl 1469.68044 J. Membr. Comput. 2, No. 4, 303-310 (2020). MSC: 68Q07 68Q15 × Cite Format Result Cite Review PDF Full Text: DOI
Hemaspaandra, Edith; Hemaspaandra, Lane A.; Spakowski, Holger; Watanabe, Osamu The robustness of LWPP and WPP, with an application to graph reconstruction. (English) Zbl 1503.68074 Comput. Complexity 29, No. 2, Paper No. 7, 49 p. (2020). MSC: 68Q15 68R10 × Cite Format Result Cite Review PDF Full Text: DOI Link
de Campos, Cassio P.; Stamoulis, Georgios; Weyland, Dennis A structured view on weighted counting with relations to counting, quantum computation and applications. (English) Zbl 1496.68153 Inf. Comput. 275, Article ID 104627, 25 p. (2020). MSC: 68Q15 68Q10 81P68 × Cite Format Result Cite Review PDF Full Text: DOI arXiv
Haak, Anselm; Kontinen, Juha; Müller, Fabian; Vollmer, Heribert; Yang, Fan Counting of teams in first-order team logics. (English) Zbl 1541.68153 Rossmanith, Peter (ed.) et al., 44th international symposium on mathematical foundations of computer science, MFCS 2019, Aachen, Germany, August 26–30, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 138, Article 19, 15 p. (2019). MSC: 68Q19 03C13 68Q15 × Cite Format Result Cite Review PDF Full Text: DOI arXiv
Haak, Anselm; Vollmer, Heribert A model-theoretic characterization of constant-depth arithmetic circuits. (English) Zbl 1477.03120 Ann. Pure Appl. Logic 170, No. 9, 1008-1029 (2019). MSC: 03C13 68Q15 68Q04 68Q10 68Q19 × Cite Format Result Cite Review PDF Full Text: DOI arXiv
Grußien, Berit Capturing polynomial time using modular decomposition. (English) Zbl 1411.68045 Log. Methods Comput. Sci. 15, No. 1, Paper No. 24, 38 p. (2019). Reviewer: Gregory Loren McColm (Tampa) MSC: 68Q19 03B70 03C13 05C60 68Q15 68R10 × Cite Format Result Cite Review PDF Full Text: arXiv
Hemaspaandra, Edith; Hemaspaandra, Lane A.; Spakowski, Holger; Watanabe, Osamu The robustness of LWPP and WPP, with an application to graph reconstruction. (English) Zbl 1512.68103 Potapov, Igor (ed.) et al., 43rd international symposium on mathematical foundations of computer science. MFCS 2018, Liverpool, United Kingdom, August 27–31, 2018. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 117, Article 51, 14 p. (2018). MSC: 68Q15 68R10 × Cite Format Result Cite Review PDF Full Text: DOI arXiv
Durand, Arnaud; Haak, Anselm; Vollmer, Heribert Model-theoretic characterization of Boolean and arithmetic circuit classes of small depth. (English) Zbl 1497.68225 Proceedings of the 2018 33rd annual ACM/IEEE symposium on logic in computer science, LICS 2018, Oxford, UK, July 9–12, 2018. New York, NY: Association for Computing Machinery (ACM). 354-363 (2018). MSC: 68Q19 03C13 68Q06 × Cite Format Result Cite Review PDF Full Text: DOI arXiv
O’Donnell, Ryan; Say, A. C. Cem The weakness of CTC qubits and the power of approximate counting. (English) Zbl 1427.68090 ACM Trans. Comput. Theory 10, No. 2, Article No. 5, 22 p. (2018). MSC: 68Q12 68Q15 81P68 × Cite Format Result Cite Review PDF Full Text: DOI
Pin, Jean-Éric Open problems about regular languages, 35 years later. (English) Zbl 1402.68120 Konstantinidis, Stavros (ed.) et al., The role of theory in computer science. Essays dedicated to Janusz Brzozowski. Hackensack, NJ: World Scientific (ISBN 978-981-3148-19-2/hbk; 978-981-3148-21-5/ebook). 153-175 (2017). Reviewer: Ahmet A. Khusainov (Komsomolsk-om-Amur) MSC: 68Q45 20M35 68Q70 × Cite Format Result Cite Review PDF Full Text: DOI HAL
Leporati, Alberto; Manzoni, Luca; Mauri, Giancarlo; Porreca, Antonio E.; Zandron, Claudio Characterising the complexity of tissue P systems with fission rules. (English) Zbl 1374.68218 J. Comput. Syst. Sci. 90, 115-128 (2017). MSC: 68Q05 68Q15 68Q25 × Cite Format Result Cite Review PDF Full Text: DOI
Buss, Sam Uniform proofs of ACC representations. (English) Zbl 1406.03053 Arch. Math. Logic 56, No. 5-6, 639-669 (2017). Reviewer: Clément Aubert (Augusta) MSC: 03D15 03D20 68Q15 × Cite Format Result Cite Review PDF Full Text: DOI
Lukasiewicz, Thomas; Malizia, Enrico A novel characterization of the complexity class \(\Theta_k^{\mathrm{P}}\) based on counting and comparison. (English) Zbl 1373.68231 Theor. Comput. Sci. 694, 21-33 (2017). MSC: 68Q15 68Q17 × Cite Format Result Cite Review PDF Full Text: DOI
Curticapean, Radu Parity separation: a scientifically proven method for permanent weight loss. (English) Zbl 1388.68221 Chatzigiannakis, Ioannis (ed.) et al., 43rd international colloquium on automata, languages, and programming, ICALP 2016, Rome, Italy, July 12–15, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-013-2). LIPIcs – Leibniz International Proceedings in Informatics 55, Article 47, 14 p. (2016). MSC: 68R10 05C22 05C70 68Q15 68Q17 × Cite Format Result Cite Review PDF Full Text: DOI arXiv
Durand, Arnaud; Haak, Anselm; Kontinen, Juha; Vollmer, Heribert Descriptive complexity of #AC\(^0\) functions. (English) Zbl 1369.68220 Regnier, Laurent (ed.) et al., 25th EACSL annual conference and 30th workshop on computer science logic, CSL’16, Marseille, France, August 29 – September 1, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-022-4). LIPIcs – Leibniz International Proceedings in Informatics 62, Article 20, 16 p. (2016). MSC: 68Q19 68Q15 × Cite Format Result Cite Review PDF Full Text: DOI arXiv
Dorzweiler, Olga; Flamm, Thomas; Krebs, Andreas; Ludwig, Michael Positive and negative proofs for circuits and branching programs. (English) Zbl 1347.68158 Theor. Comput. Sci. 610, Part A, 24-36 (2016). Reviewer: Mihai Prunescu (Bucharest) MSC: 68Q15 03D15 × Cite Format Result Cite Review PDF Full Text: DOI
Durand, Arnaud; Ebbing, Johannes; Kontinen, Juha; Vollmer, Heribert Dependence logic with a majority quantifier. (English) Zbl 1368.03040 J. Logic Lang. Inf. 24, No. 3, 289-305 (2015). MSC: 03B60 03C80 03C85 03B15 68Q19 68Q15 × Cite Format Result Cite Review PDF Full Text: DOI Link
Leporati, Alberto; Manzoni, Luca; Mauri, Giancarlo; Porreca, Antonio E.; Zandron, Claudio Membrane division, oracles, and the counting hierarchy. (English) Zbl 1357.68064 Fundam. Inform. 138, No. 1-2, 97-111 (2015). MSC: 68Q05 68Q15 × Cite Format Result Cite Review PDF Full Text: DOI
Buss, Samuel R.; Kołodziejczyk, Leszek Aleksander; Zdanowski, Konrad Collapsing modular counting in bounded arithmetic and constant depth propositional proofs. (English) Zbl 1353.03071 Trans. Am. Math. Soc. 367, No. 11, 7517-7563 (2015). Reviewer: Emil Jeřábek (Praha) MSC: 03F20 03F30 03B05 68Q15 × Cite Format Result Cite Review PDF Full Text: DOI
Fournier, Hervé; Malod, Guillaume; Mengel, Stefan Monomials in arithmetic circuits: complete problems in the counting hierarchy. (English) Zbl 1331.68085 Comput. Complexity 24, No. 1, 1-30 (2015). MSC: 68Q15 68Q17 68Q25 × Cite Format Result Cite Review PDF Full Text: DOI arXiv Link
Goldberg, Leslie Ann; Jerrum, Mark The complexity of approximately counting tree homomorphisms. (English) Zbl 1321.68312 ACM Trans. Comput. Theory 6, No. 2, Article No. 8, 31 p. (2014). MSC: 68Q25 05C05 68Q15 68R10 82B20 82C20 × Cite Format Result Cite Review PDF Full Text: DOI arXiv
Chen, Ruiwen; Kabanets, Valentine; Kinne, Jeff Lower bounds against weakly-uniform threshold circuits. (English) Zbl 1314.68142 Algorithmica 70, No. 1, 47-75 (2014). MSC: 68Q17 68Q05 68Q15 94C10 × Cite Format Result Cite Review PDF Full Text: DOI
Bulatov, Andrei A. The complexity of the counting constraint satisfaction problem. (English) Zbl 1281.68130 J. ACM 60, No. 5, Article No. 34, 41 p. (2013). MSC: 68Q25 08A40 08A70 68Q15 68T20 × Cite Format Result Cite Review PDF Full Text: DOI
Arvind, V.; Köbler, Johannes The parallel complexity of graph canonization under abelian group action. (English) Zbl 1277.68082 Algorithmica 67, No. 2, 247-276 (2013). MSC: 68Q15 68Q17 05C60 05C78 05C65 05C15 × Cite Format Result Cite Review PDF Full Text: DOI
Montoya, Juan Andrés; Müller, Moritz Parameterized random complexity. (English) Zbl 1288.68082 Theory Comput. Syst. 52, No. 2, 221-270 (2013). MSC: 68Q15 68W20 × Cite Format Result Cite Review PDF Full Text: DOI
Cai, Jin-Yi; Lu, Pinyan; Xia, Mingji Holographic algorithms by Fibonacci gates. (English) Zbl 1257.05004 Linear Algebra Appl. 438, No. 2, 690-707 (2013). MSC: 05A15 68Q17 68Q10 68Q15 × Cite Format Result Cite Review PDF Full Text: DOI Link
Azar, Pablo Daniel; Micali, Silvio Rational proofs. (English) Zbl 1286.68127 Karloff, Howard J. (ed.) et al., Proceedings of the 44th annual ACM symposium on theory of computing, STOC 2012. New York, NY, USA, May 19–22, 2012. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-1245-5). 1017-1028 (2012). MSC: 68Q05 68Q15 94A60 × Cite Format Result Cite Review PDF Full Text: DOI Link
Chen, Ruiwen; Kabanets, Valentine Lower bounds against weakly uniform circuits. (English) Zbl 1364.68217 Gudmundsson, Joachim (ed.) et al., Computing and combinatorics. 18th annual international conference, COCOON 2012, Sydney, Australia, August 20–22, 2012. Proceedings. Berlin: Springer (ISBN 978-3-642-32240-2/pbk). Lecture Notes in Computer Science 7434, 408-419 (2012). MSC: 68Q17 68Q05 68Q15 94C10 × Cite Format Result Cite Review PDF Full Text: DOI
Fournier, Hervé; Malod, Guillaume; Mengel, Stefan Monomials in arithmetic circuits: complete problems in the counting hierarchy. (English) Zbl 1245.68087 Dürr, Christoph (ed.) et al., STACS 2012. 29th international symposium on theoretical aspects of computer science, Paris, France, February 29th – March 3rd, 2012. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-35-4). LIPIcs – Leibniz International Proceedings in Informatics 14, 362-373, electronic only (2012). MSC: 68Q15 68Q17 68Q25 × Cite Format Result Cite Review PDF Full Text: DOI
Bulatov, Andrei A.; Dyer, Martin; Goldberg, Leslie Ann; Jerrum, Mark Log-supermodular functions, functional clones and counting CSPs. (English) Zbl 1245.68100 Dürr, Christoph (ed.) et al., STACS 2012. 29th international symposium on theoretical aspects of computer science, Paris, France, February 29th – March 3rd, 2012. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-35-4). LIPIcs – Leibniz International Proceedings in Informatics 14, 302-313, electronic only (2012). MSC: 68Q25 68Q15 × Cite Format Result Cite Review PDF Full Text: DOI
Lu, Pinyan Complexity dichotomies of counting problems. (English) Zbl 1253.68140 Ji, Lizhen (ed.) et al., Fifth international congress of Chinese mathematicians. Proceedings of the ICCM ’10, Beijing, China, December 17–22, 2010. Part 2. Providence, RI: American Mathematical Society (AMS); Somerville, MA: International Press (ISBN 978-0-8218-7587-2/pbk; 978-0-8218-7555-1/set). AMS/IP Studies in Advanced Mathematics 51, pt.2, 677-696 (2012). MSC: 68Q15 05A15 05C60 68Q25 × Cite Format Result Cite Review PDF
Bulatov, Andrei; Dyer, Martin; Goldberg, Leslie Ann; Jalsenius, Markus; Jerrum, Mark; Richerby, David The complexity of weighted and unweighted \(\#\)CSP. (English) Zbl 1282.68110 J. Comput. Syst. Sci. 78, No. 2, 681-688 (2012). MSC: 68Q15 × Cite Format Result Cite Review PDF Full Text: DOI
Datta, Samir; Mahajan, Meena; Raghavendra Rao, B. V.; Thomas, Michael; Vollmer, Heribert Counting classes and the fine structure between \(\mathrm{NC}^1\) and \(L\). (English) Zbl 1282.68111 Theor. Comput. Sci. 417, 36-49 (2012). MSC: 68Q15 × Cite Format Result Cite Review PDF Full Text: DOI
Riesel, Hans Prime numbers and computer methods for factorization. Reprint of the 2nd ed. 1994. (English) Zbl 1272.11001 Modern Birkhäuser Classics. New York, NY: Birkhäuser/Springer (ISBN 978-0-8176-8297-2/pbk; 978-0-8176-8298-9/ebook). xviii, 464 p. (2012). Reviewer: Olaf Ninnemann (Berlin) MSC: 11-01 11-02 11Yxx 11-04 11Y05 11Y11 11Y16 11N05 11N13 11A41 11A51 68W30 94A60 × Cite Format Result Cite Review PDF Full Text: DOI
Durand, Arnaud; Ebbing, Johannes; Kontinen, Juha; Vollmer, Heribert Dependence logic with a majority quantifier. (English) Zbl 1246.68126 Chakraborthy, Supraik (ed.) et al., IARCS annual conference on foundations of software technology and theoretical computer science (FSTTCS 2011), Mumbai, India, December 12–14, 2011. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-34-7). LIPIcs – Leibniz International Proceedings in Informatics 13, 252-263, electronic only (2011). MSC: 68Q19 03C13 68Q15 × Cite Format Result Cite Review PDF Full Text: DOI arXiv
Dyer, Martin; Richerby, David The #CSP dichotomy is decidable. (English) Zbl 1230.68078 Schwentick, Thomas (ed.) et al., STACS 2011. 28th international symposium on theoretical aspects of computer science, Dortmund, Germany, March 10–12, 2011. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-25-5). LIPIcs – Leibniz International Proceedings in Informatics 9, 261-272, electronic only (2011). MSC: 68Q15 68Q17 × Cite Format Result Cite Review PDF Full Text: DOI Link
Guo, Heng; Huang, Sangxia; Lu, Pinyan; Xia, Mingji The complexity of weighted Boolean #CSP modulo \(k\). (English) Zbl 1230.68080 Schwentick, Thomas (ed.) et al., STACS 2011. 28th international symposium on theoretical aspects of computer science, Dortmund, Germany, March 10–12, 2011. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-25-5). LIPIcs – Leibniz International Proceedings in Informatics 9, 249-260, electronic only (2011). MSC: 68Q15 68Q25 × Cite Format Result Cite Review PDF Full Text: DOI Link
Aydinlioǧlu, Bariş; Gutfreund, Dan; Hitchcock, John M.; Kawachi, Akinori Derandomizing Arthur-Merlin games and approximate counting implies exponential-size lower bounds. (English) Zbl 1230.68076 Comput. Complexity 20, No. 2, 329-366 (2011). MSC: 68Q15 68Q17 × Cite Format Result Cite Review PDF Full Text: DOI
Homer, Steven; Selman, Alan L. Computability and complexity theory. 2nd ed. (English) Zbl 1248.68192 Texts in Computer Science. New York, NY: Springer (ISBN 978-1-4614-0681-5/hbk; 978-1-4614-0682-2/ebook). xvi, 298 p. (2011). Reviewer: Heribert Vollmer (Hannover) MSC: 68Q01 68Q05 68Q10 68Q15 68Q17 68Q25 × Cite Format Result Cite Review PDF Full Text: DOI
Montoya, J. Andrés On the parameterized complexity of approximate counting. (English) Zbl 1234.68121 RAIRO, Theor. Inform. Appl. 45, No. 2, 197-223 (2011). MSC: 68Q15 68Q17 × Cite Format Result Cite Review PDF Full Text: DOI EuDML Link
Arvind, V.; Vijayaraghavan, T. C. The orbit problem is in the GapL hierarchy. (English) Zbl 1298.65075 J. Comb. Optim. 21, No. 1, 124-137 (2011). Reviewer: Sonia Pérez Díaz (Madrid) MSC: 65F30 68Q15 × Cite Format Result Cite Review PDF Full Text: DOI Link
Datta, Samir; Kulkarni, Raghav; Limaye, Nutan; Mahajan, Meena Planarity, determinants, permanents, and (unique) matchings. (English) Zbl 1322.05088 ACM Trans. Comput. Theory 1, No. 3, Article No. 10, 20 p. (2010). MSC: 05C50 05C10 05C70 15A15 68Q17 68Q25 × Cite Format Result Cite Review PDF Full Text: DOI
Hansen, Kristoffer Arnsfelt; Koucký, Michal A new characterization of \(\text{ACC}^{0}\) and probabilistic \(\text{CC}^{0}\). (English) Zbl 1213.68262 Comput. Complexity 19, No. 2, 211-234 (2010). MSC: 68Q05 68Q15 68Q17 68Q87 × Cite Format Result Cite Review PDF Full Text: DOI
Arvind, V.; Vijayaraghavan, T. C. Classifying problems on linear congruences and Abelian permutation groups using logspace counting classes. (English) Zbl 1204.68096 Comput. Complexity 19, No. 1, 57-98 (2010). MSC: 68Q15 15A03 15A06 20B05 × Cite Format Result Cite Review PDF Full Text: DOI
Kontinen, Juha A logical characterization of the counting hierarchy. (English) Zbl 1367.68106 ACM Trans. Comput. Log. 10, No. 1, Article No. 7, 21 p. (2009). MSC: 68Q19 03C13 68Q15 × Cite Format Result Cite Review PDF Full Text: DOI
Juma, Ali; Kabanets, Valentine; Rackoff, Charles; Shpilka, Amir The black-box query complexity of polynomial summation. (English) Zbl 1213.68263 Comput. Complexity 18, No. 1, 59-79 (2009). MSC: 68Q05 68Q15 68Q17 68Q25 × Cite Format Result Cite Review PDF Full Text: DOI
Allender, Eric; Bürgisser, Peter; Kjeldgaard-Pedersen, Johan; Miltersen, Peter Bro On the complexity of numerical analysis. (English) Zbl 1191.68329 SIAM J. Comput. 38, No. 5, 1987-2006 (2009). MSC: 68Q15 68Q17 × Cite Format Result Cite Review PDF Full Text: DOI Link
Hermann, Miki; Pichler, Reinhard Complexity of counting the optimal solutions. (English) Zbl 1171.68011 Theor. Comput. Sci. 410, No. 38-40, 3814-3825 (2009). MSC: 68Q15 68Q25 × Cite Format Result Cite Review PDF Full Text: DOI
Ferreira, Gilda The counting hierarchy in binary notation. (English) Zbl 1163.68321 Port. Math. (N.S.) 66, No. 1, 81-94 (2009). MSC: 68Q15 03D15 03F35 03F30 × Cite Format Result Cite Review PDF Full Text: DOI Link
Fournier, Hervé; Malod, Guillaume Universal relations and #P-completeness. (English) Zbl 1152.68018 Theor. Comput. Sci. 407, No. 1-3, 97-109 (2008). MSC: 68Q17 68Q15 × Cite Format Result Cite Review PDF Full Text: DOI
Williams, R. Ryan Time-space tradeoffs for counting NP solutions modulo integers. (English) Zbl 1149.68034 Comput. Complexity 17, No. 2, 179-219 (2008). MSC: 68Q15 68Q17 × Cite Format Result Cite Review PDF Full Text: DOI Link
Cai, Jin-Yi; Lu, Pinyan Holographic algorithms: from art to science. (English) Zbl 1232.68055 STOC’07. Proceedings of the 39th annual ACM symposium on theory of computing, San Diego, CA, USA, June 11–13, 2007. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-59593-631-8). 401-410 (2007). MSC: 68Q15 68Q17 68W05 × Cite Format Result Cite Review PDF
T’kindt, Vincent; Bouibede-Hocine, Karima; Esswein, Carl Counting and enumeration complexity with application to multicriteria scheduling. (English) Zbl 1142.68038 Ann. Oper. Res. 153, 215-234 (2007). MSC: 68Q25 68Q15 90B35 90C27 90C29 90C60 × Cite Format Result Cite Review PDF Full Text: DOI
Beaudry, Martin; Holzer, Markus The complexity of tensor circuit evaluation. (English) Zbl 1173.68021 Comput. Complexity 16, No. 1, 60-111 (2007). MSC: 68Q15 15A69 68Q05 × Cite Format Result Cite Review PDF Full Text: DOI
Koiran, Pascal; Perifel, Sylvain The complexity of two problems on arithmetic circuits. (English) Zbl 1154.68564 Theor. Comput. Sci. 389, No. 1-2, 172-181 (2007). MSC: 68W05 68W30 68Q25 × Cite Format Result Cite Review PDF Full Text: DOI
Jeřábek, Emil Approximate counting in bounded arithmetic. (English) Zbl 1123.03051 J. Symb. Log. 72, No. 3, 959-993 (2007). Reviewer: Roman Murawski (Poznań) MSC: 03F30 03D15 68Q15 68W20 × Cite Format Result Cite Review PDF Full Text: DOI Euclid Link
Bürgisser, Peter; Lotz, Martin The complexity of computing the Hilbert polynomial of smooth equidimensional complex projective varieties. (English) Zbl 1108.68059 Found. Comput. Math. 7, No. 1, 51-86 (2007). MSC: 68Q17 68Q15 14N15 13P10 × Cite Format Result Cite Review PDF Full Text: DOI arXiv
Cai, Jin-Yi \(\text{S}_{2}^{\text{P}} \subseteq \text{ZPP}^{\text{NP}}\). (English) Zbl 1133.68020 J. Comput. Syst. Sci. 73, No. 1, 25-35 (2007). MSC: 68Q15 03F20 × Cite Format Result Cite Review PDF Full Text: DOI
Shaltiel, Ronen; Umans, Christopher Pseudorandomness for approximate counting and sampling. (English) Zbl 1125.68058 Comput. Complexity 15, No. 4, 298-341 (2006). MSC: 68Q15 × Cite Format Result Cite Review PDF Full Text: DOI
Hemaspaandra, Lane A.; Homan, Christopher M.; Kosub, Sven; Wagner, Klaus W. The complexity of computing the size of an interval. (English) Zbl 1123.68041 SIAM J. Comput. 36, No. 5, 1264-1300 (2006). MSC: 68Q15 03D15 06A06 68Q05 68Q10 68Q17 × Cite Format Result Cite Review PDF Full Text: DOI
Porschen, Stefan Counting all solutions of minimum weight exact satisfiability. (English) Zbl 1183.68314 Calamoneri, Tiziana (ed.) et al., Algorithms and complexity. 6th Italian conference, CIAC 2006, Rome, Italy, May 29–31, 2006. Proceedings. Berlin: Springer (ISBN 3-540-34375-X/pbk). Lecture Notes in Computer Science 3998, 50-59 (2006). MSC: 68Q25 68Q15 × Cite Format Result Cite Review PDF Full Text: DOI
Arratia, Argimiro; Ortiz, Carlos E. Expressive power and complexity of a logic with quantifiers that count proportions of sets. (English) Zbl 1118.03020 J. Log. Comput. 16, No. 6, 817-840 (2006). MSC: 03B70 03C13 68Q19 03C80 68Q15 03B15 × Cite Format Result Cite Review PDF Full Text: DOI Link
Böhler, Elmar; Glaßer, Christian; Meister, Daniel Error-bounded probabilistic computations between MA and AM. (English) Zbl 1100.68023 J. Comput. Syst. Sci. 72, No. 6, 1043-1076 (2006). MSC: 68Q05 68Q15 × Cite Format Result Cite Review PDF Full Text: DOI
Arvind, V.; Kurur, Piyush P. Graph Isomorphism is in SPP. (English) Zbl 1110.68090 Inf. Comput. 204, No. 5, 835-852 (2006). MSC: 68R10 68Q15 05C60 × Cite Format Result Cite Review PDF Full Text: DOI
McCartin, Catherine Parameterized counting problems. (English) Zbl 1133.68027 Ann. Pure Appl. Logic 138, No. 1-3, 147-182 (2006). MSC: 68Q25 68Q15 68Q17 × Cite Format Result Cite Review PDF Full Text: DOI
Durand, Arnaud; Hermann, Miki; Kolaitis, Phokion G. Subtractive reductions and complete problems for counting complexity classes. (English) Zbl 1077.68033 Theor. Comput. Sci. 340, No. 3, 496-513 (2005). MSC: 68Q15 × Cite Format Result Cite Review PDF Full Text: DOI
T’kindt, Vincent; Bouibede-Hocine, Karima; Esswein, Carl Counting and enumeration complexity with application to multicriteria scheduling. (English) Zbl 1090.90097 4OR 3, No. 1, 1-21 (2005). MSC: 90B35 68Q15 90-02 90C29 × Cite Format Result Cite Review PDF Full Text: DOI
Spakowski, Holger; Thakur, Mayur; Tripathi, Rahul Quantum and classical complexity classes: Separations, collapses, and closure properties. (English) Zbl 1161.68481 Inf. Comput. 200, No. 1, 1-34 (2005). MSC: 68Q15 × Cite Format Result Cite Review PDF Full Text: DOI Link
McKenzie, Pierre; Vollmer, Heribert; Wagner, Klaus W. Arithmetic circuits and polynomial replacement systems. (English) Zbl 1101.68567 SIAM J. Comput. 33, No. 6, 1513-1531 (2004). MSC: 68Q05 68Q17 11C08 × Cite Format Result Cite Review PDF Full Text: DOI
Flum, Jörg; Grohe, Martin The parameterized complexity of counting problems. (English) Zbl 1105.68042 SIAM J. Comput. 33, No. 4, 892-922 (2004). MSC: 68Q15 68Q19 68Q25 × Cite Format Result Cite Review PDF Full Text: DOI
Dalmau, Víctor; Jonsson, Peter The complexity of counting homomorphisms seen from the other side. (English) Zbl 1086.68054 Theor. Comput. Sci. 329, No. 1-3, 315-323 (2004). MSC: 68Q25 05A15 68Q15 68R10 × Cite Format Result Cite Review PDF Full Text: DOI
Hemaspaandra, Lane A.; Thakur, Mayur Lower bounds and the hardness of counting properties. (English) Zbl 1105.68048 Theor. Comput. Sci. 326, No. 1-3, 1-28 (2004). MSC: 68Q17 68Q15 03D15 × Cite Format Result Cite Review PDF Full Text: DOI
Dahllöf, Vilhelm; Jonsson, Peter; Beigel, Richard Algorithms for four variants of the exact satisfiability problem. (English) Zbl 1068.68068 Theor. Comput. Sci. 320, No. 2-3, 373-394 (2004). MSC: 68Q25 68Q15 68W40 × Cite Format Result Cite Review PDF Full Text: DOI
Hsiang, Jieh; Hsu, D. Frank; Shieh, Yuh-Pyng On the hardness of counting problems of complete mappings. (English) Zbl 1069.68050 Discrete Math. 277, No. 1-3, 87-100 (2004). MSC: 68Q15 68Q17 68W30 × Cite Format Result Cite Review PDF Full Text: DOI
Bürgisser, Peter; Cucker, Felipe Counting complexity classes for numeric computations. I: Semilinear sets. (English) Zbl 1069.68049 SIAM J. Comput. 33, No. 1, 227-260 (2003). MSC: 68Q15 68Q17 55-04 65Y20 × Cite Format Result Cite Review PDF Full Text: DOI
Hoang, Thanh Minh; Thierauf, Thomas The complexity of the characteristic and the minimal polynomial. (English) Zbl 1045.68067 Theor. Comput. Sci. 295, No. 1-3, 205-222 (2003). MSC: 68Q25 × Cite Format Result Cite Review PDF Full Text: DOI
Damm, Carsten; Holzer, Markus; McKenzie, Pierre The complexity of tensor calculus. (English) Zbl 1033.15025 Comput. Complexity 11, No. 1-2, 54-89 (2002). Reviewer: Yueh-er Kuo (Knoxville) MSC: 15A69 68Q05 03D10 03D40 68R15 68Q15 68Q17 68Q70 × Cite Format Result Cite Review PDF Full Text: DOI
Libkin, Leonid; Wong, Limsoon Lower bounds for invariant queries in logics with counting. (English) Zbl 1058.03030 Theor. Comput. Sci. 288, No. 1, 153-180 (2002). MSC: 03B70 68Q15 68Q19 03C13 × Cite Format Result Cite Review PDF Full Text: DOI
Blass, Andreas; Gurevich, Yuri; Shelah, Saharon On polynomial time computation over unordered structures. (English) Zbl 1020.03038 J. Symb. Log. 67, No. 3, 1093-1125 (2002). Reviewer: U.Schöning (Ulm) MSC: 03D15 68Q19 05C70 × Cite Format Result Cite Review PDF Full Text: DOI arXiv
Krajíček, Jan On the degree of ideal membership proofs from uniform families of polynomials over a finite field. (English) Zbl 0984.03044 Ill. J. Math. 45, No. 1, 41-73 (2001). MSC: 03F20 12L12 12E12 68Q15 13L05 × Cite Format Result Cite Review PDF
Goldberg, Leslie Ann Computation in permutation groups: Counting and randomly sampling orbits. (English) Zbl 0978.68067 Hirschfeld, J. W. P. (ed.), Surveys in combinatorics, 2001. Proceedings of the 18th British combinatorial conference, University of Sussex, Brighton, UK, July 1-6, 2001. Cambridge: Cambridge University Press. Lond. Math. Soc. Lect. Note Ser. 288, 109-143 (2001). MSC: 68Q15 68Q05 × Cite Format Result Cite Review PDF
Esbelin, H.-A. Counting modulo finite semigroups. (English) Zbl 0976.03048 Theor. Comput. Sci. 257, No. 1-2, 107-114 (2001). MSC: 03D15 68Q15 20M35 68Q70 × Cite Format Result Cite Review PDF Full Text: DOI
Hermann, Miki; Kolaitis, Phokion G. Unification algorithms cannot be combined in polynomial time. (English) Zbl 1045.68568 Inf. Comput. 162, No. 1-2, 24-42 (2000). MSC: 68Q25 03B35 68Q15 68Q17 68T15 × Cite Format Result Cite Review PDF Full Text: DOI Link
Krajíček, Jan; Scanlon, Thomas Combinatorics with definable sets: Euler characteristics and Grothendieck rings. (English) Zbl 0968.03036 Bull. Symb. Log. 6, No. 3, 311-330 (2000). MSC: 03C07 03F20 68Q15 03C62 × Cite Format Result Cite Review PDF Full Text: DOI Link
Borchert, Bernd; Stephan, Frank Looking for an analogue of Rice’s theorem in circuit complexity theory. (English) Zbl 0964.03039 Math. Log. Q. 46, No. 4, 489-504 (2000). MSC: 03D15 68Q15 × Cite Format Result Cite Review PDF Full Text: DOI
Wechsung, Gerd Lectures on complexity theory. (Vorlesungen zur Komplexitätstheorie.) (German) Zbl 0965.68024 Teubner-Texte zur Informatik. 32. Stuttgart: Teubner. 312 S. (2000). Reviewer: Armin Hemmerling (Greifswald) MSC: 68Q15 68-01 68Q25 68Q10 68Q17 × Cite Format Result Cite Review PDF
Hertrampf, Ulrich; Reith, Steffen; Vollmer, Heribert A note on closure properties of logspace MOD classes. (English) Zbl 0953.68549 Inf. Process. Lett. 75, No. 3, 91-93 (2000). MSC: 68Q15 × Cite Format Result Cite Review PDF Full Text: DOI
Flum, Jörg; Grohe, Martin On fixed-point logic with counting. (English) Zbl 0960.03025 J. Symb. Log. 65, No. 2, 777-787 (2000). Reviewer: Heribert Vollmer (Würzburg) MSC: 03C13 68Q19 68Q15 68Q17 × Cite Format Result Cite Review PDF Full Text: DOI
Noilhan, Fabrice; Santha, Miklos Semantical counting circuits. (English) Zbl 0961.68055 Bongiovanni, Giancarlo (ed.) et al., Algorithms and complexity. 4th Italian conference, CIAC 2000, Rome, Italy, March 1-3, 2000. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1767, 87-101 (2000). MSC: 68Q15 × Cite Format Result Cite Review PDF
Simon, Janos; Tsai, Shi-Chun On the bottleneck counting argument. (English) Zbl 0943.68071 Theor. Comput. Sci. 237, No. 1-2, 429-437 (2000). MSC: 68Q15 × Cite Format Result Cite Review PDF Full Text: DOI
Pacholski, Leszek; Szwast, Wiesław; Tendera, Lidia Complexity results for first-order two-variable logic with counting. (English) Zbl 0956.03039 SIAM J. Comput. 29, No. 4, 1083-1117 (2000). Reviewer: U.Schöning (Ulm) MSC: 03D15 68Q15 03B10 68Q25 03B25 × Cite Format Result Cite Review PDF Full Text: DOI