Allender, Eric; Mertz, Ian Complexity of regular functions. (English) Zbl 1435.68139 J. Comput. Syst. Sci. 104, 5-16 (2019). MSC: 68Q45 68Q25 × Cite Format Result Cite Review PDF Full Text: DOI
Krebs, Andreas; Limaye, Nutan; Ludwig, Michael A unified method for placing problems in polylogarithmic depth. (English) Zbl 1485.68112 Lokam, Satya (ed.) et al., 37th IARCS annual conference on foundations of software technology and theoretical computer science, FSTTCS 2017, IIT Kanpur, India, December 12–14, 2017. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 93, Article 36, 15 p. (2018). MSC: 68Q25 08A70 68Q45 68R10 68W10 × Cite Format Result Cite Review PDF Full Text: DOI
Beckmann, Arnold; Buss, Sam The NP search problems of Frege and extended Frege proofs. (English) Zbl 1407.03071 ACM Trans. Comput. Log. 18, No. 2, Article No. 11, 19 p. (2017). MSC: 03F20 03F30 × Cite Format Result Cite Review PDF Full Text: DOI Link
Gál, Anna; Jang, Jing-Tang A generalization of Spira’s theorem and circuits with small segregators or separators. (English) Zbl 1353.68083 Inf. Comput. 251, 252-262 (2016). MSC: 68Q05 68Q15 68Q25 94C10 × Cite Format Result Cite Review PDF Full Text: DOI
Krebs, Andreas; Limaye, Nutan; Ludwig, Michael Cost register automata for nested words. (English) Zbl 1477.68154 Dinh, Thang N. (ed.) et al., Computing and combinatorics. 22nd international conference, COCOON 2016, Ho Chi Minh City, Vietnam, August 2–4, 2016. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 9797, 587-598 (2016). MSC: 68Q45 × Cite Format Result Cite Review PDF Full Text: DOI
Buhrman, Harry; Loff, Bruno; Torenvliet, Leen Hardness of approximation for knapsack problems. (English) Zbl 1328.68073 Theory Comput. Syst. 56, No. 2, 372-393 (2015). MSC: 68Q17 68W25 90C27 × Cite Format Result Cite Review PDF Full Text: DOI Link
Elberfeld, Michael; Stockhusen, Christoph; Tantau, Till On the space and circuit complexity of parameterized problems: classes and completeness. (English) Zbl 1312.68099 Algorithmica 71, No. 3, 661-701 (2015). MSC: 68Q25 68Q15 68Q17 × Cite Format Result Cite Review PDF Full Text: DOI
Mundhenk, Martin; Wei, Felix An \(\mathsf{AC}^{1}\)-complete model checking problem for intuitionistic logic. (English) Zbl 1522.68336 Comput. Complexity 23, No. 4, 637-669 (2014). MSC: 68Q60 03B20 06D20 68Q17 × Cite Format Result Cite Review PDF Full Text: DOI
Mahajan, Meena; Raghavendra Rao, B. V.; Sreenivasaiah, Karteek Monomials, multilinearity and identity testing in simple read-restricted circuits. (English) Zbl 1285.68068 Theor. Comput. Sci. 524, 90-102 (2014). MSC: 68Q25 68Q17 × Cite Format Result Cite Review PDF Full Text: DOI
Das, Bireswar; Datta, Samir; Nimbhorkar, Prajakta Log-space algorithms for paths and matchings in \(k\)-trees. (English) Zbl 1281.68132 Theory Comput. Syst. 53, No. 4, 669-689 (2013). MSC: 68Q25 68Q17 68R10 05C05 × Cite Format Result Cite Review PDF Full Text: DOI
Krebs, Andreas; Limaye, Nutan; Mahajan, Meena Counting paths in VPA is complete for \(\#\mathrm{NC}^1\). (English) Zbl 1282.68140 Algorithmica 64, No. 2, 279-294 (2012). MSC: 68Q25 68Q15 68Q17 68Q45 × Cite Format Result Cite Review PDF Full Text: DOI
Gál, Anna; Jang, Jing-Tang A generalization of Spira’s theorem and circuits with small segregators or separators. (English) Zbl 1298.68090 Bieliková, Mária (ed.) et al., SOFSEM 2012: Theory and practice of computer science. 38th conference on current trends in theory and practice of computer science, Špindlerův Mlýn, Czech Republic, January 21–27, 2012. Proceedings. Berlin: Springer (ISBN 978-3-642-27659-0/pbk). Lecture Notes in Computer Science 7147, 264-276 (2012). MSC: 68Q05 94C10 × Cite Format Result Cite Review PDF Full Text: DOI
Limaye, Nutan; Mahajan, Meena; Raghavendra Rao, B. V. Arithmetizing classes around {NC}\(^{1}\) and {L}. (English) Zbl 1204.68098 Theory Comput. Syst. 46, No. 3, 499-522 (2010). MSC: 68Q15 × Cite Format Result Cite Review PDF Full Text: DOI
Longpré, Luc; McKenzie, Pierre The complexity of solitaire. (English) Zbl 1194.68123 Theor. Comput. Sci. 410, No. 50, 5252-5260 (2009). MSC: 68Q17 × Cite Format Result Cite Review PDF Full Text: DOI Backlinks: MO
Allender, Eric; Mix Barrington, David A.; Chakraborty, Tanmoy; Datta, Samir; Roy, Sambuddha Planar and grid graph reachability problems. (English) Zbl 1183.68409 Theory Comput. Syst. 45, No. 4, 675-723 (2009). MSC: 68R10 × Cite Format Result Cite Review PDF Full Text: DOI
Jakoby, Andreas; Tantau, Till Logspace algorithms for computing shortest and longest paths in series-parallel graphs. (English) Zbl 1135.68518 Arvind, V. (ed.) et al., FSTTCS 2007: Foundations of software technology and theoretical computer science. 27th international conference, New Delhi, India, December 12–14, 2007. Proceedings. Berlin: Springer (ISBN 978-3-540-77049-7/pbk). Lecture Notes in Computer Science 4855, 216-227 (2007). MSC: 68R10 05C85 × Cite Format Result Cite Review PDF Full Text: DOI
Beigel, Richard; Fu, Bin Circuits over PP and PL. (English) Zbl 0956.68069 J. Comput. Syst. Sci. 60, No. 2, 422-441 (2000). MSC: 68Q25 × Cite Format Result Cite Review PDF Full Text: DOI Link
Cai, Jin-Yi; Sivakumar, D. Sparse hard sets for P: Resolution of a conjecture of Hartmanis. (English) Zbl 0936.68046 J. Comput. Syst. Sci. 58, No. 2, 280-296 (1999). MSC: 68Q15 × Cite Format Result Cite Review PDF Full Text: DOI Link
Caussinus, Hervé; McKenzie, Pierre; Thérien, Denis; Vollmer, Heribert Nondeterministic \(\mathrm{NC}^1\) computation. (English) Zbl 0921.68029 J. Comput. Syst. Sci. 57, No. 2, 200-212 (1998). MSC: 68Q05 68Q15 × Cite Format Result Cite Review PDF Full Text: DOI
Takeuti, Gaisi Frege proof system and TNC\(^\circ\). (English) Zbl 0959.03047 J. Symb. Log. 63, No. 2, 709-738 (1998). MSC: 03F20 03F07 03B05 03F30 68Q15 × Cite Format Result Cite Review PDF Full Text: DOI
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
Cai, Liming; Chen, Jianer On input read-modes of alternating Turing machines. (English) Zbl 0873.68055 Theor. Comput. Sci. 148, No. 1, 33-55 (1995). MSC: 68Q05 × Cite Format Result Cite Review PDF Full Text: DOI
Àlvarez, Carme; Jenner, Birgit On adaptive DLOGTIME and POLYLOGTIME reductions. (English) Zbl 0873.68069 Theor. Comput. Sci. 148, No. 2, 183-205 (1995). MSC: 68Q15 × Cite Format Result Cite Review PDF Full Text: DOI
Takeuti, Gaisi Frege proof system and TNC\(^\circ\). (English) Zbl 1540.03103 Leivant, Daniel (ed.), Logic and computational complexity. International workshop, LCC ’94, Indianapolis, IN, USA, October 13–16, 1994. Selected Papers. Berlin: Springer-Verlag. Lect. Notes Comput. Sci. 960, 221-252 (1995). MSC: 03F20 03D15 68Q15 × Cite Format Result Cite Review PDF Full Text: DOI
Cai, Liming; Chen, Jianer On log-time alternating Turing machines of alternation depth \(k\) (extended abstract). (English) Zbl 1527.68062 Du, Ding-Zhu (ed.) et al., Computing and combinatorics. 1st international conference, COCOON ’95, Xi’an, China, August 24–26, 1995. Proceedings. Berlin: Springer-Verlag. Lect. Notes Comput. Sci. 959, 282-291 (1995). MSC: 68Q04 68Q06 68Q15 × Cite Format Result Cite Review PDF Full Text: DOI
Mak, Louis Speedup of determinism by alternation for multidimensional Turing machines. (English) Zbl 0938.68650 Theor. Comput. Sci. 134, No. 2, 427-453 (1994). MSC: 68Q05 × Cite Format Result Cite Review PDF Full Text: DOI
Allender, Eric; Bruschi, Danilo; Pighizzini, Giovanni The complexity of computing maximal word functions. (English) Zbl 0802.68061 Comput. Complexity 3, No. 4, 368-391 (1993). MSC: 68Q25 68Q45 68Q15 68W15 68P20 68P25 × Cite Format Result Cite Review PDF Full Text: DOI
Allender, Eric; Gore, Vivek Rudimentary reductions revisited. (English) Zbl 0748.68017 Inf. Process. Lett. 40, No. 2, 89-95 (1991). MSC: 68Q15 03D15 × Cite Format Result Cite Review PDF Full Text: DOI
Barrington, David A. Mix; Immerman, Neil; Straubing, Howard On uniformity within \(NC^ 1\). (English) Zbl 0719.68023 J. Comput. Syst. Sci. 41, No. 3, 274-306 (1990). Reviewer: S.P.Yukna (Vilnius) MSC: 68Q15 94C10 03D20 × Cite Format Result Cite Review PDF Full Text: DOI