The Layer complexity of Arthur-Merlin-like communication

Number of the records: 1

1.

SYSNO ASEP	0546785
Document Type	J - Journal Article
R&D Document Type	Journal Article
Subsidiary J	Článek ve WOS
Title	The Layer complexity of Arthur-Merlin-like communication
Author(s)	Gavinsky, Dmitry (MU-W)_{RID, SAI, ORCID}
Article number	8
Source Title	Theory of Computing. - : University of Chicago - ISSN 1557-2862 Roč. 17, č. 1 (2021)
Number of pages	28 s.
Language	eng - English
Country	US - United States
Keywords	communication complexity ; complexity classes
Subject RIV	IN - Informatics, Computer Science
OECD category	Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
R&D Projects	GX19-27871X GA ČR - Czech Science Foundation (CSF)
Method of publishing	Open access
Institutional support	MU-W - RVO:67985840
UT WOS	000813437700001
EID SCOPUS	85124905781
DOI	10.4086/toc.2021.v017a008
Annotation	In communication complexity the Arthur-Merlin (AM) model is the most natural one that allows both randomness and nondeterminism. Presently we do not have any super-logarithmic lower bound for the AM-complexity of an explicit function. Obtaining such a bound is a fundamental challenge to our understanding of communication phenomena.
Workplace	Mathematical Institute
Contact	Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757
Year of Publishing	2022
Electronic address	http://dx.doi.org/10.4086/toc.2021.v017a008

Number of the records: 1