Salamon, András Z.; Wehar, Michael Effective guessing has unlikely consequences. (English) Zbl 07719397 Theory Comput. Syst. 67, No. 3, 548-568 (2023). MSC: 68Qxx 94Cxx 68Pxx PDFBibTeX XMLCite \textit{A. Z. Salamon} and \textit{M. Wehar}, Theory Comput. Syst. 67, No. 3, 548--568 (2023; Zbl 07719397) Full Text: DOI arXiv
Nagao, Atsuki; Seto, Kazuhisa; Teruyama, Junichi Satisfiability algorithm for syntactic read-\(k\)-times branching programs. (English) Zbl 1506.68039 Theory Comput. Syst. 64, No. 8, 1392-1407 (2020). MSC: 68Q25 68P05 68R07 68W05 PDFBibTeX XMLCite \textit{A. Nagao} et al., Theory Comput. Syst. 64, No. 8, 1392--1407 (2020; Zbl 1506.68039) Full Text: DOI
Borodin, Allan; Boyar, Joan; Larsen, Kim S.; Pankratov, Denis Advice complexity of priority algorithms. (English) Zbl 1444.68299 Theory Comput. Syst. 64, No. 4, 593-625 (2020). MSC: 68W27 68Q17 90C59 PDFBibTeX XMLCite \textit{A. Borodin} et al., Theory Comput. Syst. 64, No. 4, 593--625 (2020; Zbl 1444.68299) Full Text: DOI arXiv
Kiyomi, Masashi; Ono, Hirotaka; Otachi, Yota; Schweitzer, Pascal; Tarui, Jun Space-efficient algorithms for longest increasing subsequence. (English) Zbl 1433.68632 Theory Comput. Syst. 64, No. 3, 522-541 (2020). MSC: 68W32 11Y16 11Y55 68P10 68W40 PDFBibTeX XMLCite \textit{M. Kiyomi} et al., Theory Comput. Syst. 64, No. 3, 522--541 (2020; Zbl 1433.68632) Full Text: DOI Link
Beyersdorff, Olaf; Blinkhorn, Joshua Lower bound techniques for QBF expansion. (English) Zbl 1471.03081 Theory Comput. Syst. 64, No. 3, 400-421 (2020). Reviewer: Ariel Germán Fernández (Buenos Aires) MSC: 03F20 PDFBibTeX XMLCite \textit{O. Beyersdorff} and \textit{J. Blinkhorn}, Theory Comput. Syst. 64, No. 3, 400--421 (2020; Zbl 1471.03081) Full Text: DOI
Franklin, Johanna N. Y.; McNicholl, Timothy H.; Rute, Jason Algorithmic randomness and Fourier analysis. (English) Zbl 1454.03054 Theory Comput. Syst. 63, No. 3, 567-586 (2019). MSC: 03D32 03D78 42B10 PDFBibTeX XMLCite \textit{J. N. Y. Franklin} et al., Theory Comput. Syst. 63, No. 3, 567--586 (2019; Zbl 1454.03054) Full Text: DOI arXiv
Scharpfenecker, Patrick Bounded-depth succinct encodings and the structure they imply on graphs. (English) Zbl 1397.68109 Theory Comput. Syst. 62, No. 5, 1125-1143 (2018). MSC: 68Q25 68Q17 68R10 PDFBibTeX XMLCite \textit{P. Scharpfenecker}, Theory Comput. Syst. 62, No. 5, 1125--1143 (2018; Zbl 1397.68109) Full Text: DOI
Lohrey, Markus; Schmidt-Schauß, Manfred Processing succinct matrices and vectors. (English) Zbl 1378.68087 Theory Comput. Syst. 61, No. 2, 322-351 (2017). MSC: 68Q25 15B33 68P05 68W30 PDFBibTeX XMLCite \textit{M. Lohrey} and \textit{M. Schmidt-Schauß}, Theory Comput. Syst. 61, No. 2, 322--351 (2017; Zbl 1378.68087) Full Text: DOI arXiv
Braverman, Mark; Garg, Ankit; Pankratov, Denis; Weinstein, Omri Information lower bounds via self-reducibility. (English) Zbl 1356.68086 Theory Comput. Syst. 59, No. 2, 377-396 (2016). MSC: 68Q17 PDFBibTeX XMLCite \textit{M. Braverman} et al., Theory Comput. Syst. 59, No. 2, 377--396 (2016; Zbl 1356.68086) Full Text: DOI
Kovásznai, Gergely; Fröhlich, Andreas; Biere, Armin Complexity of fixed-size bit-vector logics. (English) Zbl 1357.68086 Theory Comput. Syst. 59, No. 2, 323-376 (2016). MSC: 68Q25 68Q17 PDFBibTeX XMLCite \textit{G. Kovásznai} et al., Theory Comput. Syst. 59, No. 2, 323--376 (2016; Zbl 1357.68086) Full Text: DOI
Pauly, Arno The computational complexity of iterated elimination of dominated strategies. (English) Zbl 1346.91005 Theory Comput. Syst. 59, No. 1, 52-75 (2016). MSC: 91A05 68Q25 PDFBibTeX XMLCite \textit{A. Pauly}, Theory Comput. Syst. 59, No. 1, 52--75 (2016; Zbl 1346.91005) Full Text: DOI Link
Capelli, Florent; Durand, Arnaud; Mengel, Stefan The arithmetic complexity of tensor contraction. (English) Zbl 1339.68097 Theory Comput. Syst. 58, No. 4, 506-527 (2016). MSC: 68Q15 15A69 PDFBibTeX XMLCite \textit{F. Capelli} et al., Theory Comput. Syst. 58, No. 4, 506--527 (2016; Zbl 1339.68097) Full Text: DOI
Graça, Daniel S.; Zhong, Ning An analytic system with a computable hyperbolic sink whose basin of attraction is non-computable. (English) Zbl 1336.03051 Theory Comput. Syst. 57, No. 2, 478-520 (2015). MSC: 03D78 03D10 34D20 37M99 PDFBibTeX XMLCite \textit{D. S. Graça} and \textit{N. Zhong}, Theory Comput. Syst. 57, No. 2, 478--520 (2015; Zbl 1336.03051) Full Text: DOI arXiv
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 PDFBibTeX XMLCite \textit{H. Buhrman} et al., Theory Comput. Syst. 56, No. 2, 372--393 (2015; Zbl 1328.68073) Full Text: DOI Link
Bilò, Vittorio; Mavronicolas, Marios Complexity of rational and irrational Nash equilibria. (English) Zbl 1380.91029 Theory Comput. Syst. 54, No. 3, 491-527 (2014). MSC: 91A35 90C33 90C60 91A10 PDFBibTeX XMLCite \textit{V. Bilò} and \textit{M. Mavronicolas}, Theory Comput. Syst. 54, No. 3, 491--527 (2014; Zbl 1380.91029) 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 PDFBibTeX XMLCite \textit{B. Das} et al., Theory Comput. Syst. 53, No. 4, 669--689 (2013; Zbl 1281.68132) 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 PDFBibTeX XMLCite \textit{J. A. Montoya} and \textit{M. Müller}, Theory Comput. Syst. 52, No. 2, 221--270 (2013; Zbl 1288.68082) Full Text: DOI
Fortnow, Lance; Lutz, Jack H.; Mayordomo, Elvira Inseparability and strong hypotheses for disjoint NP pairs. (English) Zbl 1282.68113 Theory Comput. Syst. 51, No. 2, 229-247 (2012). MSC: 68Q15 68Q17 PDFBibTeX XMLCite \textit{L. Fortnow} et al., Theory Comput. Syst. 51, No. 2, 229--247 (2012; Zbl 1282.68113) Full Text: DOI Link
Hirsch, Edward A.; Itsykson, Dmitry; Monakhov, Ivan; Smal, Alexander On optimal heuristic randomized semidecision procedures, with applications to proof complexity and cryptography. (English) Zbl 1261.03158 Theory Comput. Syst. 51, No. 2, 179-195 (2012). MSC: 03F20 03B05 03D15 68W20 94A60 PDFBibTeX XMLCite \textit{E. A. Hirsch} et al., Theory Comput. Syst. 51, No. 2, 179--195 (2012; Zbl 1261.03158) Full Text: DOI
Gu, Xiaoyang; Hitchcock, John M.; Pavan, A. Collapsing and separating completeness notions under average-case and worst-case hypotheses. (English) Zbl 1253.68150 Theory Comput. Syst. 51, No. 2, 248-265 (2012). MSC: 68Q17 68Q25 PDFBibTeX XMLCite \textit{X. Gu} et al., Theory Comput. Syst. 51, No. 2, 248--265 (2012; Zbl 1253.68150) Full Text: DOI Link
Bergstra, Jan A.; Bethke, Inge On the contribution of backward jumps to instruction sequence expressiveness. (English) Zbl 1279.68182 Theory Comput. Syst. 50, No. 4, 706-720 (2012). MSC: 68Q55 68N15 68Q65 PDFBibTeX XMLCite \textit{J. A. Bergstra} and \textit{I. Bethke}, Theory Comput. Syst. 50, No. 4, 706--720 (2012; Zbl 1279.68182) Full Text: DOI
Thierauf, Thomas; Wagner, Fabian The isomorphism problem for planar 3-connected graphs is in unambiguous logspace. (English) Zbl 1203.05104 Theory Comput. Syst. 47, No. 3, 655-673 (2010). MSC: 05C60 05C85 68R10 68Q25 PDFBibTeX XMLCite \textit{T. Thierauf} and \textit{F. Wagner}, Theory Comput. Syst. 47, No. 3, 655--673 (2010; Zbl 1203.05104) Full Text: DOI Link
Bauland, Michael; Böhler, Elmar; Creignou, Nadia; Reith, Steffen; Schnoor, Henning; Vollmer, Heribert The complexity of problems for quantified constraints. (English) Zbl 1204.68182 Theory Comput. Syst. 47, No. 2, 454-490 (2010). MSC: 68T20 PDFBibTeX XMLCite \textit{M. Bauland} et al., Theory Comput. Syst. 47, No. 2, 454--490 (2010; Zbl 1204.68182) Full Text: DOI
Torán, Jacobo Reductions to graph isomorphism. (English) Zbl 1205.68167 Theory Comput. Syst. 47, No. 1, 288-299 (2010). MSC: 68Q15 03D30 05C60 68Q25 PDFBibTeX XMLCite \textit{J. Torán}, Theory Comput. Syst. 47, No. 1, 288--299 (2010; Zbl 1205.68167) Full Text: DOI
Beyersdorff, Olaf The deduction theorem for strong propositional proof systems. (English) Zbl 1202.03064 Theory Comput. Syst. 47, No. 1, 162-178 (2010). MSC: 03F20 03B05 68Q15 PDFBibTeX XMLCite \textit{O. Beyersdorff}, Theory Comput. Syst. 47, No. 1, 162--178 (2010; Zbl 1202.03064) Full Text: DOI Link
Dal Lago, Ugo; Hofmann, Martin A semantic proof of polytime soundness of light affine logic. (English) Zbl 1205.68169 Theory Comput. Syst. 46, No. 4, 673-689 (2010). MSC: 68Q17 PDFBibTeX XMLCite \textit{U. Dal Lago} and \textit{M. Hofmann}, Theory Comput. Syst. 46, No. 4, 673--689 (2010; Zbl 1205.68169) 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 PDFBibTeX XMLCite \textit{N. Limaye} et al., Theory Comput. Syst. 46, No. 3, 499--522 (2010; Zbl 1204.68098) Full Text: DOI
Mahajan, Meena; Sarma, Jayalal M. N. On the complexity of matrix rank and rigidity. (English) Zbl 1183.68295 Theory Comput. Syst. 46, No. 1, 9-26 (2010). MSC: 68Q15 PDFBibTeX XMLCite \textit{M. Mahajan} and \textit{J. M. N. Sarma}, Theory Comput. Syst. 46, No. 1, 9--26 (2010; Zbl 1183.68295) Full Text: DOI
Li, Chung-Chih Speed-up theorems in type-2 computations using oracle Turing machines. (English) Zbl 1185.68331 Theory Comput. Syst. 45, No. 4, 880-896 (2009). MSC: 68Q05 03D15 03D65 68Q25 PDFBibTeX XMLCite \textit{C.-C. Li}, Theory Comput. Syst. 45, No. 4, 880--896 (2009; Zbl 1185.68331) Full Text: DOI
Danner, Norman; Royer, James S. Two algorithms in search of a type-system. (English) Zbl 1187.68308 Theory Comput. Syst. 45, No. 4, 787-821 (2009). MSC: 68Q55 68N99 68W05 PDFBibTeX XMLCite \textit{N. Danner} and \textit{J. S. Royer}, Theory Comput. Syst. 45, No. 4, 787--821 (2009; Zbl 1187.68308) Full Text: DOI arXiv
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 PDFBibTeX XMLCite \textit{E. Allender} et al., Theory Comput. Syst. 45, No. 4, 675--723 (2009; Zbl 1183.68409) Full Text: DOI
Case, John Resource restricted computability theoretic learning: Illustrative topics and problems. (English) Zbl 1187.68382 Theory Comput. Syst. 45, No. 4, 773-786 (2009). MSC: 68T05 PDFBibTeX XMLCite \textit{J. Case}, Theory Comput. Syst. 45, No. 4, 773--786 (2009; Zbl 1187.68382) Full Text: DOI
Le Gall, François Exponential separation of quantum and classical online space complexity. (English) Zbl 1183.68292 Theory Comput. Syst. 45, No. 2, 188-202 (2009). MSC: 68Q12 68Q05 81P68 68Q10 PDFBibTeX XMLCite \textit{F. Le Gall}, Theory Comput. Syst. 45, No. 2, 188--202 (2009; Zbl 1183.68292) Full Text: DOI arXiv
Friedl, Katalin; Ivanyos, Gábor; Santha, Miklos; Verhoeven, Yves F. On the black-box complexity of Sperner’s Lemma. (English) Zbl 1187.68233 Theory Comput. Syst. 45, No. 3, 629-646 (2009). MSC: 68Q10 81P68 68Q15 PDFBibTeX XMLCite \textit{K. Friedl} et al., Theory Comput. Syst. 45, No. 3, 629--646 (2009; Zbl 1187.68233) Full Text: DOI arXiv
Robertson, Edward L.; Saxton, Lawrence V.; Van Gucht, Dirk; Vansummeren, Stijn Structural recursion as a query language on lists and ordered trees. (English) Zbl 1192.68219 Theory Comput. Syst. 44, No. 4, 590-619 (2009). MSC: 68P15 68P05 PDFBibTeX XMLCite \textit{E. L. Robertson} et al., Theory Comput. Syst. 44, No. 4, 590--619 (2009; Zbl 1192.68219) Full Text: DOI
Bauland, Michael; Hemaspaandra, Edith Isomorphic implication. (English) Zbl 1173.68024 Theory Comput. Syst. 44, No. 1, 117-139 (2009). MSC: 68Q25 03B05 68Q17 PDFBibTeX XMLCite \textit{M. Bauland} and \textit{E. Hemaspaandra}, Theory Comput. Syst. 44, No. 1, 117--139 (2009; Zbl 1173.68024) Full Text: DOI arXiv
Gál, Anna; Koucký, Michal; McKenzie, Pierre Incremental branching programs. (English) Zbl 1141.68031 Theory Comput. Syst. 43, No. 2, 159-184 (2008). MSC: 68Q05 68Q17 PDFBibTeX XMLCite \textit{A. Gál} et al., Theory Comput. Syst. 43, No. 2, 159--184 (2008; Zbl 1141.68031) Full Text: DOI Link
Beyersdorff, Olaf Tuples of disjoint \(\mathsf{NP}\)-sets. (English) Zbl 1148.68021 Theory Comput. Syst. 43, No. 2, 118-135 (2008). MSC: 68Q15 03F20 PDFBibTeX XMLCite \textit{O. Beyersdorff}, Theory Comput. Syst. 43, No. 2, 118--135 (2008; Zbl 1148.68021) Full Text: DOI
Hitchcock, John M.; Pavan, A.; Vinodchandran, N. V. Partial bi-immunity, scaled dimension, and NP-completeness. (English) Zbl 1141.68032 Theory Comput. Syst. 42, No. 2, 131-142 (2008). MSC: 68Q15 68Q17 PDFBibTeX XMLCite \textit{J. M. Hitchcock} et al., Theory Comput. Syst. 42, No. 2, 131--142 (2008; Zbl 1141.68032) Full Text: DOI
Macarie, I. I. Multihead two-way probabilistic finite automata. (English) Zbl 0870.68100 Theory Comput. Syst. 30, No. 1, 91-109 (1997). MSC: 68Q45 PDFBibTeX XMLCite \textit{I. I. Macarie}, Theory Comput. Syst. 30, No. 1, 91--109 (1997; Zbl 0870.68100) Full Text: DOI
Damm, C.; Holzer, M.; Rossmanith, P. Expressing uniformity via oracles. (English) Zbl 0872.68047 Theory Comput. Syst. 30, No. 4, 355-366 (1997). MSC: 68Q15 PDFBibTeX XMLCite \textit{C. Damm} et al., Theory Comput. Syst. 30, No. 4, 355--366 (1997; Zbl 0872.68047) Full Text: DOI