The Layer complexity of Arthur-Merlin-like communication

0546785 - MÚ 2022 RIV US eng J - Článek v odborném periodiku
Gavinsky, Dmitry
The Layer complexity of Arthur-Merlin-like communication.
Theory of Computing. Roč. 17, č. 1 (2021), č. článku 8. ISSN 1557-2862. E-ISSN 1557-2862
Grant CEP: GA ČR(CZ) GX19-27871X
Institucionální podpora: RVO:67985840
Klíčová slova: communication complexity * complexity classes
Obor OECD: Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Impakt faktor: 0.816, rok: 2021
Způsob publikování: Open access
http://dx.doi.org/10.4086/toc.2021.v017a008

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.
Trvalý link: http://hdl.handle.net/11104/0323166