Antonelli, Melissa; Dal Lago, Ugo; Pistone, Paolo On counting propositional logic and Wagner’s hierarchy. (English) Zbl 07699965 Theor. Comput. Sci. 966-967, Article ID 113928, 21 p. (2023). MSC: 68Qxx × Cite Format Result Cite Review PDF Full Text: DOI
Gharibian, Sevag; Santha, Miklos; Sikora, Jamie; Sundaram, Aarthi; Yirka, Justin Quantum generalizations of the polynomial hierarchy with applications to \(\mathrm{QMA(2)}\). (English) Zbl 1512.68101 Comput. Complexity 31, No. 2, Paper No. 13, 52 p. (2022). MSC: 68Q12 68Q15 81P68 90C22 × Cite Format Result Cite Review PDF Full Text: DOI
Barthe, Gilles; Jacomme, Charlie; Kremer, Steve Universal equivalence and majority of probabilistic programs over finite fields. (English) Zbl 1496.68186 Proceedings of the 2020 35th annual ACM/IEEE symposium on logic in computer science, LICS 2020, virtual event, July 8–11, 2020. New York, NY: Association for Computing Machinery (ACM). 155-166 (2020). MSC: 68Q60 11Y16 68N30 68P27 94A60 × Cite Format Result Cite Review PDF Full Text: DOI HAL
Cozman, Fabio Gagliardi; Mauá, Denis Deratani The joy of probabilistic answer set programming: semantics, complexity, expressivity, inference. (English) Zbl 1490.68072 Int. J. Approx. Reasoning 125, 218-239 (2020). MSC: 68N17 68N19 68Q19 68Q25 68Q55 × Cite Format Result Cite Review PDF Full Text: DOI
Mauá, Denis Deratani; Cozman, Fabio Gagliardi Complexity results for probabilistic answer set programming. (English) Zbl 1468.68215 Int. J. Approx. Reasoning 118, 133-154 (2020). MSC: 68T27 68N17 68Q25 × Cite Format Result Cite Review PDF Full Text: DOI
Cozman, Fabio Gagliardi; Mauá, Denis Deratani The finite model theory of Bayesian network specifications: descriptive complexity and zero/one laws. (English) Zbl 1460.68042 Int. J. Approx. Reasoning 110, 107-126 (2019). MSC: 68Q19 03B48 03C13 62H22 68Q60 68T27 × Cite Format Result Cite Review PDF Full Text: DOI
Cozman, Fabio G.; Mauá, Denis D. The complexity of Bayesian networks specified by propositional and relational languages. (English) Zbl 1451.68257 Artif. Intell. 262, 96-141 (2018). MSC: 68T27 62H22 68P15 × Cite Format Result Cite Review PDF Full Text: DOI arXiv
Allender, Eric; Holden, Dhiraj; Kabanets, Valentine The minimum oracle circuit size problem. (English) Zbl 1408.68065 Comput. Complexity 26, No. 2, 469-496 (2017). MSC: 68Q17 68Q30 × Cite Format Result Cite Review PDF Full Text: DOI Link
Mauá, Denis Deratani; Cozman, Fabio Gagliardi The effect of combination functions on the complexity of relational Bayesian networks. (English) Zbl 1419.68172 Int. J. Approx. Reasoning 85, 178-195 (2017). MSC: 68T37 68Q17 68Q25 × Cite Format Result Cite Review PDF Full Text: DOI
Lechner, Antonia; Ouaknine, Joel; Worrell, James On the complexity of linear arithmetic with divisibility. (English) Zbl 1401.03070 Proceedings of the 2015 30th annual ACM/IEEE symposium on logic in computer science, LICS 2015, Kyoto, Japan, July 6–10, 2015. Los Alamitos, CA: IEEE Computer Society (ISBN 978-1-4799-8875-4). 667-676 (2015). MSC: 03D15 03B25 03F30 68Q25 × 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
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
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
Jansen, Maurice; Santhanam, Rahul Marginal hitting sets imply super-polynomial lower bounds for permanent. (English) Zbl 1347.68161 Proceedings of the 3rd conference on innovations in theoretical computer science, ITCS’12, Cambridge, MA, USA, January 8–10, 2012. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-1115-1). 496-506 (2012). MSC: 68Q15 68Q17 68W20 × Cite Format Result Cite Review PDF Full Text: DOI
Jansen, Maurice Towards a tight hardness-randomness connection between permanent and arithmetic circuit identity testing. (English) Zbl 1259.68073 Inf. Process. Lett. 112, No. 24, 969-975 (2012). MSC: 68Q15 68Q25 68W20 × Cite Format Result Cite Review PDF Full Text: DOI
Jansen, Maurice; Santhanam, Rahul Permanent does not have succinct polynomial size arithmetic circuits of constant depth. (English) Zbl 1333.68123 Aceto, Luca (ed.) et al., Automata, languages and programming. 38th international colloquium, ICALP 2011, Zurich, Switzerland, July 4–8, 2011. Proceedings, Part I. Berlin: Springer (ISBN 978-3-642-22005-0/pbk). Lecture Notes in Computer Science 6755, 724-735 (2011). MSC: 68Q17 15A15 68W20 94C10 × Cite Format Result Cite Review PDF Full Text: DOI
Kontinen, Juha; Niemistö, Hannu Extensions of MSO and the monadic counting hierarchy. (English) Zbl 1215.68105 Inf. Comput. 209, No. 1, 1-19 (2011). Reviewer: Galina Jiraskova (Košice) MSC: 68Q19 03C80 × Cite Format Result Cite Review PDF Full Text: DOI
Faliszewski, Piotr; Ogihara, Mitsunori On the autoreducibility of functions. (English) Zbl 1209.68262 Theory Comput. Syst. 46, No. 2, 222-245 (2010). MSC: 68Q15 × Cite Format Result Cite Review PDF Full Text: DOI Link
Spakowski, Holger; Tripathi, Rahul LWPP and WPP are not uniformly gap-definable. (English) Zbl 1105.68045 J. Comput. Syst. Sci. 72, No. 4, 660-689 (2006). MSC: 68Q15 × Cite Format Result Cite Review PDF Full Text: DOI
Chateau, Annie; More, Malika The ultra-weak Ash conjecture and some particular cases. (English) Zbl 1090.03006 Math. Log. Q. 52, No. 1, 4-13 (2006). MSC: 03C13 68Q15 68Q19 × 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
Cai, Jin-Yi; Chakaravarthy, Venkatesan T.; Hemaspaandra, Lane A.; Ogihara, Mitsunori Competing provers yield improved Karp-Lipton collapse results. (English) Zbl 1066.68050 Inf. Comput. 198, No. 1, 1-23 (2005). MSC: 68Q15 × 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
Damm, Carsten; Krause, Matthias; Meinel, Christoph; Waack, Stephan On relations between counting communication complexity classes. (English) Zbl 1159.68465 J. Comput. Syst. Sci. 69, No. 2, 259-280 (2004). MSC: 68Q15 68M12 × Cite Format Result Cite Review PDF Full Text: DOI
Eiter, Thomas; Lukasiewicz, Thomas Complexity results for structure-based causality. (English) Zbl 1043.68100 Artif. Intell. 142, No. 1, 53-89 (2002). MSC: 68T99 × Cite Format Result Cite Review PDF Full Text: DOI
Durand, Arnaud; More, Malika Nonerasing, counting, and majority over the linear time hierarchy. (English) Zbl 1009.68051 Inf. Comput. 174, No. 2, 132-142 (2002). MSC: 68Q15 68Q05 68Q25 × Cite Format Result Cite Review PDF Full Text: DOI
Borchert, B.; Silvestri, R. Dot operators. (English) Zbl 0983.68095 Theor. Comput. Sci. 262, No. 1-2, 501-523 (2001). MSC: 68Q45 × Cite Format Result Cite Review PDF Full Text: DOI
Rothe, J. Immunity and simplicity for exact counting and other counting classes. (English) Zbl 0946.68051 Theor. Inform. Appl. 33, No. 2, 159-176 (1999). MSC: 68Q15 68Q10 03D15 × Cite Format Result Cite Review PDF Full Text: DOI arXiv EuDML
Hemaspaandra, Lane A.; Ogihara, Mitsunori Universally serializable computation. (English) Zbl 0901.68065 J. Comput. Syst. Sci. 55, No. 3, 547-560 (1997). MSC: 68Q05 × Cite Format Result Cite Review PDF Full Text: DOI Link
Allender, Eric; Ogihara, Mitsunori Relationships among \(PL\), \(\# L\), and the determinant. (English) Zbl 0851.68033 RAIRO, Inform. Théor. Appl. 30, No. 1, 1-21 (1996). MSC: 68Q15 68Q45 × Cite Format Result Cite Review PDF Full Text: DOI EuDML
Köbler, J.; Toda, Seinosuke On the power of generalized MOD-classes. (English) Zbl 0840.68044 Math. Syst. Theory 29, No. 1, 33-46 (1996). MSC: 68Q15 × Cite Format Result Cite Review PDF Full Text: DOI
Vollmer, Heribert Relations among parallel and sequential computation models. (English) Zbl 1541.68140 Jaffar, Joxan (ed.) et al., Concurrency and parallelism, programming, networking, and security. Second Asian computing science conference, ASIAN ’96, Singapore, December 2–5, 1996. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1179, 23-32 (1996). MSC: 68Q06 68Q04 68Q10 68Q15 × Cite Format Result Cite Review PDF Full Text: DOI
Borchert, Bernd On the acceptance power of regular languages. (English) Zbl 0873.68121 Theor. Comput. Sci. 148, No. 2, 207-225 (1995). MSC: 68Q45 68Q15 × Cite Format Result Cite Review PDF Full Text: DOI
Thierauf, Thomas; Toda, Seinosuke; Watanabe, Osamu On closure properties of GapP. (English) Zbl 0812.68074 Comput. Complexity 4, No. 3, 242-261 (1994). MSC: 68Q15 × Cite Format Result Cite Review PDF Full Text: DOI
Beigel, Richard; Chang, Richard; Ogiwara, Mitsunori A relationship between difference hierarchies and relativized polynomial hierarchies. (English) Zbl 0776.68043 Math. Syst. Theory 26, No. 3, 293-310 (1993). Reviewer: U.Schöning (Ulm) MSC: 68Q15 × Cite Format Result Cite Review PDF Full Text: DOI
Beigel, Richard; Gill, John Counting classes: Thresholds, parity, mods, and fewness. (English) Zbl 0760.68028 Theor. Comput. Sci. 103, No. 1, 3-23 (1992). Reviewer: R.Beigel MSC: 68Q15 03D25 × Cite Format Result Cite Review PDF Full Text: DOI
Köbler, Johannes; Schöning, Uwe; Torán, Jacobo Graph isomorphism is low for PP. (English) Zbl 0770.68055 Comput. Complexity 2, No. 4, 301-330 (1992). MSC: 68Q15 68R10 68Q25 05C60 × Cite Format Result Cite Review PDF Full Text: DOI