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

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

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)

Cites Work

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

Cited In (3)

• A Randomized Algorithm for BBCSPs in the Prover-Verifier Model
• Real-time, constant-space, constant-randomness verifiers
• 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)