Languages with Bounded Multiparty Communication Complexity
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F07%3A00084614" target="_blank" >RIV/67985840:_____/07:00084614 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
Languages with Bounded Multiparty Communication Complexity
Original language description
We study languages with bounded communication complexity in the multiparty "input on the forehead" model with worst-case partition. In the two party case,it is known that such languages are exactly those that are recognized by programs over commutative monoids.This can be used to show that these languages can be computed by shallow ACC^0 circuits. In contrast, we use coding techniques to show that there are languages of arbitrarily large circuit complexity than can be computed by k players using constant communication, if>=3. However, if the language has a neutral letter and constant communication complexity for k players for some fixed k, then the language is in fact regular. We give an algebraic characterization of regular languages with this property. We also prove than a symmetric language has bounded k-party communication complexity for some fixed k iff it has bounded 2-party communication complexity.
Czech name
Jazyky s omezenou komunikační složitostí pro více hráčů
Czech description
Zabýváme se výpočetní složitostí funkcí, jež mají omezenou komunikační složitost v komunikačních hrách více hráčů.
Classification
Type
D - Article in proceedings
CEP classification
BA - General mathematics
OECD FORD branch
—
Result continuities
Project
<a href="/en/project/GA201%2F05%2F0124" target="_blank" >GA201/05/0124: Online algorithms, randomness, and extremal problems</a><br>
Continuities
Z - Vyzkumny zamer (s odkazem do CEZ)
Others
Publication year
2007
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Proceeding of the 24th Annual Symposium on Theoretical Aspects of Computer Science (STACS), 2007
ISBN
978-3-540-70917-6
ISSN
—
e-ISSN
—
Number of pages
11
Pages from-to
500-511
Publisher name
Springer-Verlag
Place of publication
Berlin
Event location
Aachen
Event date
Feb 22, 2007
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—