Moshkov, Mikhail Time and space complexity of deterministic and nondeterministic decision trees. (English) Zbl 07644142 Ann. Math. Artif. Intell. 91, No. 1, 45-74 (2023). MSC: 68Txx × Cite Format Result Cite Review PDF Full Text: DOI arXiv OA License
Moshkov, Mikhail Rough analysis of computation trees. (English) Zbl 07585580 Discrete Appl. Math. 321, 90-108 (2022). MSC: 68Rxx 68Txx 68Qxx × Cite Format Result Cite Review PDF Full Text: DOI arXiv OA License
Ezra, Esther; Sharir, Micha A nearly quadratic bound for point-location in hyperplane arrangements, in the linear decision tree model. (English) Zbl 1415.52017 Discrete Comput. Geom. 61, No. 4, 735-755 (2019). MSC: 52C35 52C45 68Q87 68Q25 × Cite Format Result Cite Review PDF Full Text: DOI
Gaßner, Christine Computation over algebraic structures and a classification of undecidable problems. (English) Zbl 1423.03139 Math. Struct. Comput. Sci. 27, No. 8, 1386-1413 (2017). MSC: 03D10 03D35 68Q05 × Cite Format Result Cite Review PDF Full Text: DOI
Rademacher, Luis; Vempala, Santosh Dispersion of mass and the complexity of randomized geometric algorithms. (English) Zbl 1149.68079 Adv. Math. 219, No. 3, 1037-1069 (2008). MSC: 68W20 68Q25 65Y20 68U05 × Cite Format Result Cite Review PDF Full Text: DOI arXiv
Woeginger, Gerhard J. Open problems around exact algorithms. (English) Zbl 1165.90613 Discrete Appl. Math. 156, No. 3, 397-405 (2008). MSC: 90C27 90C60 × Cite Format Result Cite Review PDF Full Text: DOI
Grigoriev, Dima; Karpinski, Marek; Meyer auf der Heide, Friedhelm; Smolensky, Roman A lower bound for randomized algebraic decision trees. (English) Zbl 0895.68049 Comput. Complexity 6(1996-97), No. 4, 357-375 (1997). MSC: 68Q15 68W30 68Q25 × Cite Format Result Cite Review PDF Full Text: DOI
Ben-Amram, Amir M.; Galil, Zvi Lower bounds on algebraic random access machines. (English) Zbl 1412.68057 Fülöp, Zoltán (ed.) et al., Automata, languages and programming. 22nd international colloquium, ICALP ’95, Szeged, Hungary, July 10–14, 1995. Proceedings. Berlin: Springer-Verlag. Lect. Notes Comput. Sci. 944, 360-371 (1995). MSC: 68Q05 68Q17 × Cite Format Result Cite Review PDF Full Text: DOI
Bürgisser, Peter; Lickteig, Thomas Test complexity of generic polynomials. (English) Zbl 0768.68034 J. Complexity 8, No. 3, 203-215 (1992). Reviewer: F.Cucker (Barcelona) MSC: 68Q25 14Q10 12D99 × Cite Format Result Cite Review PDF Full Text: DOI
Bürgisser, Peter; Lickteig, Thomas Verification complexity of linear prime ideals. (English) Zbl 0768.68035 J. Pure Appl. Algebra 81, No. 3, 247-267 (1992). Reviewer: Y.Kuo (Knoxville) MSC: 68Q25 14Q10 × Cite Format Result Cite Review PDF Full Text: DOI
Meyer auf der Heide, Friedhelm On genuinely time bounded computations. (English) Zbl 1492.68056 Monien, Burkhard (ed.) et al., STACS 89. 6th annual symposium on theoretical aspects of computer science, Paderborn, FRG, February 16–18, 1989. Proceedings. Berlin: Springer-Verlag. Lect. Notes Comput. Sci. 349, 1-16 (1989). MSC: 68Q15 03D15 × Cite Format Result Cite Review PDF Full Text: DOI
Just, Bettina; Meyer auf der Heide, Friedhelm; Wigderson, Avi On computations with integer division. (English) Zbl 0665.68027 RAIRO, Inf. Théor. Appl. 23, No. 1, 101-111 (1989). MSC: 68Q25 11H99 × Cite Format Result Cite Review PDF Full Text: DOI EuDML
Yao, Andrew Chi-chih On selecting the k largest with median tests. (English) Zbl 0664.68065 Algorithmica 4, No. 2, 293-300 (1989). MSC: 68P10 68Q25 × Cite Format Result Cite Review PDF Full Text: DOI
Babai, László; Just, Bettina; Meyer auf der Heide, Friedhelm On the limits of computations with the floor function. (English) Zbl 0659.68051 Inf. Comput. 78, No. 2, 99-107 (1988). Reviewer: J.Weinstein MSC: 68W99 26E05 28A05 54C50 × Cite Format Result Cite Review PDF Full Text: DOI
Dietzfelbinger, Martin; Maass, Wolfgang Lower bound arguments with “inaccessible” numbers. (English) Zbl 0652.68039 J. Comput. Syst. Sci. 36, No. 3, 313-335 (1988). MSC: 68Q25 68Q05 90C35 68R10 × Cite Format Result Cite Review PDF Full Text: DOI
Meyer auf der Heide, Friedhelm Simulating probabilistic by deterministic algebraic computation trees. (English) Zbl 0616.68051 Theor. Comput. Sci. 41, 325-330 (1985). MSC: 68Q05 68Q25 × Cite Format Result Cite Review PDF Full Text: DOI Link
Klein, Peter; Meyer auf der Heide, Friedhelm A lower time bound for the knapsack problem on random access machines. (English) Zbl 0515.68037 Acta Inf. 19, 385-395 (1983). MSC: 68Q25 90C10 68Q05 × Cite Format Result Cite Review PDF Full Text: DOI
Ukkonen, Esko Exponential lower bounds for some NP-complete problems in a restricted linear decision tree model. (English) Zbl 0512.90076 BIT 23, 181-192 (1983). MSC: 90C10 68Q25 × Cite Format Result Cite Review PDF Full Text: DOI
Snir, Marc Comparisons between linear functions can help. (English) Zbl 0496.68026 Theor. Comput. Sci. 19, 321-330 (1982). MSC: 68Q25 × Cite Format Result Cite Review PDF Full Text: DOI
Moravek, Jaroslav A geometrical method in combinatorial complexity. (English) Zbl 0454.68028 Apl. Mat. 26, 82-96 (1981). MSC: 68Q25 × Cite Format Result Cite Review PDF Full Text: DOI EuDML
Dobkin, David P.; Reiss, Steven P. The complexity of linear programming. (English) Zbl 0446.90049 Theor. Comput. Sci. 11, 1-18 (1980). MSC: 90C05 68Q25 × Cite Format Result Cite Review PDF Full Text: DOI
Dobkin, David P.; Lipton, Richard J. On the complexity of computations under varying sets of primitives. (English) Zbl 0409.68023 J. Comput. Syst. Sci. 18, 86-91 (1979). MSC: 68Q25 68R99 90B40 90C10 × Cite Format Result Cite Review PDF Full Text: DOI