Zobrazeno 1 - 8
of 8
pro vyhledávání: '"Gezer, M. Utkan"'
Autor:
Say, A. C. Cem, Gezer, M. Utkan
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 computation that is impossible for classical computers. Existing approach
Externí odkaz:
http://arxiv.org/abs/2412.02662
Autor:
Gezer, M. Utkan, Say, A. C. Cem
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 under reasonably large space bounds. The language verification power
Externí odkaz:
http://arxiv.org/abs/2306.09542
Publikováno v:
Lecture Notes in Computer Science vol. 13266 (2022) pp. 212-224
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 size of their inputs. Since any further restriction on the verifiers w
Externí odkaz:
http://arxiv.org/abs/2206.00968
Autor:
Gezer, M. Utkan, Say, A. C. Cem
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 are restricted to toss some fixed nonzero number of coins regardless o
Externí odkaz:
http://arxiv.org/abs/2006.12330
Publikováno v:
In Theoretical Computer Science 17 October 2023 976
Autor:
Gezer, M. Utkan
Publikováno v:
Lecture Notes in Computer Science vol. 12038 (2020) pp. 184-195
Every language in NL has a $k$-head two-way nondeterministic finite automaton (2nfa($k$)) recognizing it. It is known how to build a constant-space verifier algorithm from a 2nfa($k$) for the same language with constant-randomness, but with error pro
Externí odkaz:
http://arxiv.org/abs/1912.01382
Autor:
Gezer, M. Utkan, Say, A.C. Cem
Publikováno v:
In Information and Computation October 2022 288
Autor:
Gezer, M. Utkan, Say, A. C. Cem
We consider the effects of allowing a finite state verifier in an interactive proof system to use a bounded number of private coins, in addition to "public" coins whose outcomes are visible to the prover. Although swapping between private and public-
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::7061ed678b663b2e04c2d68e8001ade1