4 citations · 5 across the 6 of their papers we have counts for
6 papers
Constant-Coin Complete-Information Debates for with Arbitrarily Small Strong Error
M. Utkan Gezer
We study complete-information debate systems in which a probabilistic finite-state verifier reads the alternating messages of a prover and a refuter. Demirci, Say, and Yakaryılmaz…
Unconditional proofs of quantumness between small-space machines
A. C. Cem Say, M. Utkan Gezer
A proof of quantumness is a protocol through which a classical machine can test whether a purportedly quantum device, with comparable time and memory resources, is performing a com…
has polynomial-time finite-state verifiers
M. Utkan Gezer, A. C. Cem Say
Interactive proof systems whose verifiers are constant-space machines have interesting features that do not have counterparts in the better studied case where the verifiers operate…
Real-Time, Constant-Space, Constant-Randomness Verifiers
M. Utkan Gezer, Özdeniz Dolu, Nevzat Ersoy +1
We study the class of languages that have membership proofs which can be verified by real-time finite-state machines using only a constant number of random bits, regardless of the…
Constant-Space, Constant-Randomness Verifiers with Arbitrarily Small Error
M. Utkan Gezer, A. C. Cem Say
We study the capabilities of probabilistic finite-state machines that act as verifiers for certificates of language membership for input strings, in the regime where the verifiers…
Windable Heads & Recognizing NL with Constant Randomness
M. Utkan Gezer
Every language in NL has a -head two-way nondeterministic finite automaton (2nfa()) recognizing it. It is known how to build a constant-space verifier algorithm from a 2nfa($…