Please use this identifier to cite or link to this item: https://hdl.handle.net/10356/89383
Full metadata record
DC FieldValueLanguage
dc.contributor.authorAnshu, Anuragen
dc.contributor.authorGavinsky, Dmitryen
dc.contributor.authorJain, Rahulen
dc.contributor.authorKundu, Srijitaen
dc.contributor.authorLee, Troyen
dc.contributor.authorMukhopadhyay, Priyankaen
dc.contributor.authorSantha, Miklosen
dc.contributor.authorSanyal, Swagatoen
dc.date.accessioned2018-10-03T08:57:36Zen
dc.date.accessioned2019-12-06T17:24:17Z-
dc.date.available2018-10-03T08:57:36Zen
dc.date.available2019-12-06T17:24:17Z-
dc.date.issued2018en
dc.identifier.citationAnshu, A., Gavinsky, D., Jain, R., Kundu, S., Lee, T., Mukhopadhyay, P., . . . Sanyal, S. (2018). A composition theorem for randomized query complexity. Leibniz International Proceedings in Informatics, 93, 10-. doi:10.4230/LIPIcs.FSTTCS.2017.10en
dc.identifier.urihttps://hdl.handle.net/10356/89383-
dc.description.abstractLet the randomized query complexity of a relation for error probability epsilon be denoted by R_epsilon(). We prove that for any relation f contained in {0,1}^n times R and Boolean function g:{0,1}^m -> {0,1}, R_{1/3}(f o g^n) = Omega(R_{4/9}(f).R_{1/2-1/n^4}(g)), where f o g^n is the relation obtained by composing f and g. We also show using an XOR lemma that R_{1/3}(f o (g^{xor}_{O(log n)})^n) = Omega(log n . R_{4/9}(f) . R_{1/3}(g))$, where g^{xor}_{O(log n)} is the function obtained by composing the XOR function on O(log n) bits and g.en
dc.description.sponsorshipNRF (Natl Research Foundation, S’pore)en
dc.format.extent13 p.en
dc.language.isoenen
dc.relation.ispartofseriesLeibniz International Proceedings in Informaticsen
dc.rights© 2018 Anurag Anshu, Dmitry Gavinsky, Rahul Jain, Srijita Kundu, Troy Lee, Priyanka Mukhopadhyay, Miklos Santha, and Swagato Sanyal; licensed under Creative Commons License CC-BY.en
dc.subjectDecision Treesen
dc.subjectDRNTU::Science::Mathematicsen
dc.subjectQuery Algorithms And Complexityen
dc.titleA composition theorem for randomized query complexityen
dc.typeJournal Articleen
dc.contributor.schoolSchool of Physical and Mathematical Sciencesen
dc.identifier.doi10.4230/LIPIcs.FSTTCS.2017.10en
dc.description.versionPublished versionen
item.fulltextWith Fulltext-
item.grantfulltextopen-
Appears in Collections:SPMS Journal Articles
Files in This Item:
File Description SizeFormat 
A composition theorem for randomized query complexity.pdf541.52 kBAdobe PDFThumbnail
View/Open

SCOPUSTM   
Citations

1
checked on Sep 2, 2020

Page view(s)

143
checked on Sep 26, 2020

Download(s)

27
checked on Sep 26, 2020

Google ScholarTM

Check

Altmetric


Plumx

Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.