Constant-space, constant-randomness verifiers with arbitrarily small error

DOI10.1016/J.IC.2021.104744OpenAlexW3037402156MaRDI QIDQ2084769FDOQ2084769

Authors A. C. Cem Say, Mehmet Utkan Gezer 

Publication date 13 October 2022

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2006.12330

zbMATH Keywords

interactive proof systemsprobabilistic finite automatamulti-head finite automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Recommendations

• Real-time, constant-space, constant-randomness verifiers
• Real-time, constant-space, constant-randomness verifiers
• Finite state verifiers with constant randomness
• Finite state verifiers with constant randomness
• Sub-constant error probabilistically checkable proof of almost-linear size
• Verifiable random functions with optimal tightness
• Constructing verifiable random functions with large input spaces
• The price of verifiability: lower bounds for verifiable random functions
• A generic approach to constructing and proving verifiable random functions
• Constant-error pseudorandomness proofs from hardness require majority

Cites work

• scientific article; zbMATH DE number 3690693 (Why is no real title available?)
• scientific article; zbMATH DE number 2156275 (Why is no real title available?)
• A time-space tradeoff for language recognition
• An application of quantum finite automata to interactive proof systems
• Complexity of multi-head finite automata: origins and directions
• Debates with small transparent quantum verifiers
• Descriptional and computational complexity of finite automata -- a survey
• Finite state verifiers I
• Finite state verifiers with constant randomness
• Interactive proof systems with polynomially bounded strategies
• Interactive proofs with quantum finite automata
• Multi-oracle interactive protocols with constant space verifiers
• On non-determinacy in simple computing devices
• Power of the interactive proof systems with verifiers modeled by semi-quantum two-way finite automata
• The complexity of debate checking
• The complexity of the max word problem and the power of one-way interactive proof systems
• Transforming Two-Way Alternating Finite Automata to One-Way Nondeterministic Automata
• Windable heads and recognizing \textsf{NL} with constant randomness

Cited in

(3)

• Real-time, constant-space, constant-randomness verifiers
• A Randomized Algorithm for BBCSPs in the Prover-Verifier Model
• Special issue: Selected papers of the 14th international conference on language and automata theory and applications, LATA 2020

This page was built for publication: Constant-space, constant-randomness verifiers with arbitrarily small error

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