Constant-space, constant-randomness verifiers with arbitrarily small error
type: Item
instance of: scholarly article
title: Constant-space, constant-randomness verifiers with arbitrarily small error
author: A. C. Cem Say
author: Mehmet Utkan Gezer
published in: Information and Computation
publication date: 2022-10-13T00:00:00Z
full work available at URL: https://arxiv.org/abs/2006.12330
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68Q10
zbMATH DE Number: 7601276
zbMATH Keywords: interactive proof systems
zbMATH Keywords: multi-head finite automata
zbMATH Keywords: probabilistic finite automata
MaRDI profile type: Publication
OpenAlex ID: W3037402156
cites work: Windable heads and recognizing \textsf{NL} with constant randomness
cites work: Interactive proof systems with polynomially bounded strategies
cites work: Finite state verifiers I
cites work: An application of quantum finite automata to interactive proof systems
cites work: Interactive proofs with quantum finite automata
cites work: Power of the interactive proof systems with verifiers modeled by semi-quantum two-way finite automata
cites work: Multi-oracle interactive protocols with constant space verifiers
cites work: The complexity of debate checking
cites work: Debates with small transparent quantum verifiers
cites work: Finite state verifiers with constant randomness
cites work: Complexity of multi-head finite automata: origins and directions
cites work: On non-determinacy in simple computing devices
cites work: Q3885190
cites work: Transforming Two-Way Alternating Finite Automata to One-Way Nondeterministic Automata
cites work: Descriptional and computational complexity of finite automata -- a survey
cites work: The complexity of the max word problem and the power of one-way interactive proof systems
cites work: Q4668733
cites work: A time-space tradeoff for language recognition
DOI: 10.1016/J.IC.2021.104744
Recommended article: Real-time, constant-space, constant-randomness verifiers
Recommended article: Finite state verifiers with constant randomness
Recommended article: Finite State Verifiers with Constant Randomness
Recommended article: Sub-constant error probabilistically checkable proof of almost-linear size
Recommended article: Verifiable random functions with optimal tightness
Recommended article: Constructing Verifiable Random Functions with Large Input Spaces
Recommended article: The price of verifiability: lower bounds for verifiable random functions
Recommended article: A generic approach to constructing and proving verifiable random functions
Recommended article: Constant-Error Pseudorandomness Proofs from Hardness Require Majority
description: scientific article; zbMATH DE number 7601276