Real-time, constant-space, constant-randomness verifiers

DOI10.1016/J.TCS.2023.114155MaRDI QIDQ6077068zbMATH OpenFDO

Authors Mehmet Utkan Gezer, Özdeniz Dolu, Nevzat Ersoy, A. C. Cem Say

Publication date 17 October 2023

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.TCS.2023.114155

zbMATH Keywords

multihead finite automatarandomized finite automatareal-time verifiers

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• k + 1 Heads Are Better than k
• Complexity of multi-head finite automata: origins and directions
• Computational Complexity
• Constant-space, constant-randomness verifiers with arbitrarily small error
• Finite state verifiers with constant randomness
• Interactive proof systems with polynomially bounded strategies
• On 3-head versus 2-head finite automata
• On Multi-Head Finite Automata
• Probabilistic checking of proofs
• Proof verification and the hardness of approximation problems
• Real-time, constant-space, constant-randomness verifiers
• Set automata
• The complexity of debate checking

Cited in

(4)

• Constant-space, constant-randomness verifiers with arbitrarily small error
• Lattice-based accumulator with constant time list update and constant time verification
• Unconditional proofs of quantumness between small-space machines
• \(\mathrm{P}\) has polynomial-time finite-state verifiers

This page was built for publication: Real-time, constant-space, constant-randomness verifiers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6077068)