Number of the records: 1
The Layer complexity of Arthur-Merlin-like communication
- 1.0546785 - MÚ 2022 RIV US eng J - Journal Article
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
R&D Projects: GA ČR(CZ) GX19-27871X
Institutional support: RVO:67985840
Keywords : communication complexity * complexity classes
OECD category: Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Impact factor: 0.816, year: 2021
Method of publishing: 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.
Permanent Link: http://hdl.handle.net/11104/0323166
File Download Size Commentary Version Access Gavinsky1.pdf 2 321.6 KB Publisher’s postprint open-access
Number of the records: 1