scientific article; zbMATH DE number 3573787
From MaRDI portal
Publication:4145647
zbMATH Open0367.94079MaRDI QIDQ4145647FDOQ4145647
Authors: Rūsiņš Freivalds 
Publication date: 1977
Title of this publication is not available (Why is that?)
Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Turing machines and related notions (03D10)
Cited In (30)
- Correcting matrix products over the ring of integers
- Speeding-up verification of digital signatures
- The time-precision tradeoff problem on on-line probabilistic Turing machines
- Simulating two pushdown stores by one tape in \(O(n^{1.5}\,\sqrt{\log \,n})\) time
- On the concept of quantum hashing
- \texttt{Sample(x)=(a*x<=t)} is a distinguisher with probability \(1/8\)
- Properties of probabilistic pushdown automata
- Lower space bounds for randomized computation
- Randomized algorithms in combinatorial optimization: A survey
- Skew-polynomial-sparse matrix multiplication
- Gaussian variant of Freivalds' algorithm for efficient and reliable matrix product verification
- Verifying the product of generalized Boolean matrix multiplication and its applications to detect small subgraphs
- Bounds for semi-disjoint bilinear forms in a unit-cost computational model
- Learning and Verifying Graphs Using Queries with a Focus on Edge Counting
- Tape versus queue and stacks: The lower bounds
- Efficiently correcting matrix products
- Efficiently correcting matrix products
- New studies of randomized augmentation and additive preprocessing
- Complexity of probabilistic versus deterministic automata
- Going beyond dual execution: MPC for functions with efficient verification
- Lower bounds on the length of universal traversal sequences
- Certifying equality with limited interaction
- Algorithms for NP-Hard Problems via Rank-Related Parameters of Matrices
- Certifying algorithms
- Probabilistic Turing machines and recursively enumerable Dedekind cuts
- Quantum Hashing and Fingerprinting for Quantum Cryptography and Computations
- A probabilistic lower bound for checking disjointness of sets
- Lower time bounds for randomized computation
- Multiple usage of random bits in finite automata
- Quantum complexity of Boolean matrix multiplication and related problems
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4145647)
