scientific article; zbMATH DE number 3573787
From MaRDI portal
Publication:4145647
zbMath0367.94079MaRDI QIDQ4145647
Publication date: 1977
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Turing machines and related notions (03D10)
Related Items
Randomized algorithms in combinatorial optimization: A survey, Quantum Hashing and Fingerprinting for Quantum Cryptography and Computations, Algorithms for NP-Hard Problems via Rank-Related Parameters of Matrices, Multiple Usage of Random Bits in Finite Automata, New studies of randomized augmentation and additive preprocessing, Tape versus queue and stacks: The lower bounds, Certifying equality with limited interaction, Complexity of probabilistic versus deterministic automata, Sample(x)=(a*x<=t) Is a Distinguisher with Probability 1/8, Simulating two pushdown stores by one tape in \(O(n^{1.5}\,\sqrt{\log \,n})\) time, Efficiently correcting matrix products, Efficiently Correcting Matrix Products, Quantum Complexity of Boolean Matrix Multiplication and Related Problems, Skew-polynomial-sparse matrix multiplication, Verifying the product of generalized Boolean matrix multiplication and its applications to detect small subgraphs, Learning and Verifying Graphs Using Queries with a Focus on Edge Counting, Certifying algorithms, Speeding-up verification of digital signatures, Bounds for Semi-disjoint Bilinear Forms in a Unit-Cost Computational Model, Lower space bounds for randomized computation, О понятии квантового хеширования, Lower time bounds for randomized computation, Lower bounds on the length of universal traversal sequences, Gaussian variant of Freivalds' algorithm for efficient and reliable matrix product verification, Going beyond dual execution: MPC for functions with efficient verification, Properties of probabilistic pushdown automata, The time-precision tradeoff problem on on-line probabilistic Turing machines, A probabilistic lower bound for checking disjointness of sets, Probabilistic Turing machines and recursively enumerable Dedekind cuts
