File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Results on communication complexity classes

TitleResults on communication complexity classes
Authors
Issue Date1992
PublisherAcademic Press. The Journal's web site is located at http://www.elsevier.com/locate/jcss
Citation
Journal Of Computer And System Sciences, 1992, v. 44 n. 2, p. 324-342 How to Cite?
AbstractDeterministic, probabilistic, nondeterministic, and alternating complexity classes defined by polylogarithmic communication are considered. Main results are (1) extending work of Ja'Ja', Prasanna Kumar, and Simon, we give a simple technique allowing translation of most known separation and containment results for complexity classes of the fixed partition model to the more difficult optimal partition model, where few results were previously known; and (2) demonstration that a certain natural language (block-equality) in ∑2 CC is also, unexpectedly, in π2 CC.
Persistent Identifierhttp://hdl.handle.net/10722/152233
ISSN
2023 Impact Factor: 1.1
2023 SCImago Journal Rankings: 1.370
ISI Accession Number ID

 

DC FieldValueLanguage
dc.contributor.authorLam, TWen_US
dc.date.accessioned2012-06-26T06:36:39Z-
dc.date.available2012-06-26T06:36:39Z-
dc.date.issued1992en_US
dc.identifier.citationJournal Of Computer And System Sciences, 1992, v. 44 n. 2, p. 324-342en_US
dc.identifier.issn0022-0000en_US
dc.identifier.urihttp://hdl.handle.net/10722/152233-
dc.description.abstractDeterministic, probabilistic, nondeterministic, and alternating complexity classes defined by polylogarithmic communication are considered. Main results are (1) extending work of Ja'Ja', Prasanna Kumar, and Simon, we give a simple technique allowing translation of most known separation and containment results for complexity classes of the fixed partition model to the more difficult optimal partition model, where few results were previously known; and (2) demonstration that a certain natural language (block-equality) in ∑2 CC is also, unexpectedly, in π2 CC.en_US
dc.languageengen_US
dc.publisherAcademic Press. The Journal's web site is located at http://www.elsevier.com/locate/jcssen_US
dc.relation.ispartofJournal of Computer and System Sciencesen_US
dc.titleResults on communication complexity classesen_US
dc.typeArticleen_US
dc.identifier.emailLam, TW:twlam@cs.hku.hken_US
dc.identifier.authorityLam, TW=rp00135en_US
dc.description.naturelink_to_subscribed_fulltexten_US
dc.identifier.doi10.1016/0022-0000(92)90025-Een_US
dc.identifier.scopuseid_2-s2.0-0026853225en_US
dc.identifier.volume44en_US
dc.identifier.issue2en_US
dc.identifier.spage324en_US
dc.identifier.epage342en_US
dc.identifier.isiWOS:A1992HR25000009-
dc.publisher.placeUnited Statesen_US
dc.identifier.scopusauthoridLam, TW=7202523165en_US
dc.identifier.issnl0022-0000-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats