scientific article; zbMATH DE number 3573787
From MaRDI portal
Publication:4145647
Cited in
(33)- Randomized algorithms in combinatorial optimization: A survey
- Tape versus queue and stacks: The lower bounds
- Simulating two pushdown stores by one tape in \(O(n^{1.5}\,\sqrt{\log \,n})\) time
- Lower bounds on the length of universal traversal sequences
- Properties of probabilistic pushdown automata
- The time-precision tradeoff problem on on-line probabilistic Turing machines
- Gaussian variant of Freivalds' algorithm for efficient and reliable matrix product verification
- Going beyond dual execution: MPC for functions with efficient verification
- Speeding-up verification of digital signatures
- Efficiently correcting matrix products
- Multiple usage of random bits in finite automata
- Efficiently correcting matrix products
- Quantum complexity of Boolean matrix multiplication and related problems
- Bounds for semi-disjoint bilinear forms in a unit-cost computational model
- New studies of randomized augmentation and additive preprocessing
- Certifying equality with limited interaction
- Learning and Verifying Graphs Using Queries with a Focus on Edge Counting
- Complexity of probabilistic versus deterministic automata
- \texttt{Sample(x)=(a*x<=t)} is a distinguisher with probability \(1/8\)
- Lower space bounds for randomized computation
- Lower time bounds for randomized computation
- Certifying algorithms
- Quantum Hashing and Fingerprinting for Quantum Cryptography and Computations
- Algorithms for NP-Hard Problems via Rank-Related Parameters of Matrices
- On the concept of quantum hashing
- Skew-polynomial-sparse matrix multiplication
- Verifying the product of generalized Boolean matrix multiplication and its applications to detect small subgraphs
- Correcting matrix products over the ring of integers
- Corrigimus, verificamus, vincimus: ensuring algorithmic accuracy in an age of uncertainty
- SNARK lower bounds via communication complexity
- A simplified reduction for error correcting matrix multiplication algorithms
- A probabilistic lower bound for checking disjointness of sets
- Probabilistic Turing machines and recursively enumerable Dedekind cuts
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)
