Sökning: id:"swepub:oai:DiVA.org:kth-235160" >
Separation Between ...
Separation Between Deterministic and Randomized Query Complexity
-
- Mukhopadhyay, Sagnik (författare)
- KTH,Teoretisk datalogi, TCS
-
- Radhakrishnan, Jaykumar (författare)
- Tata Inst Fundamental Res, Bombay, Maharashtra, India.
-
- Sanyal, Swagato (författare)
- IIT Kharagpur, Dept Comp Sci & Engn, Kharagpur, W Bengal, India.
-
(creator_code:org_t)
- Siam Publications, 2018
- 2018
- Engelska.
-
Ingår i: SIAM journal on computing (Print). - : Siam Publications. - 0097-5397 .- 1095-7111. ; 47:4, s. 1644-1666
- Relaterad länk:
-
https://urn.kb.se/re...
-
visa fler...
-
https://doi.org/10.1...
-
visa färre...
Abstract
Ämnesord
Stäng
- Saks and Wigderson 27th FOGS, IEEE Computer Society, as Alamitos, CA, 1986, pp. 29-38] conjectured that R-0(f) = Omega (D(f)(0.753...)) for all Boolean functions f, here R-0 denotes the randomized complexity and D denotes 10 determinist is query CCATI p1exit;,yr. We,show t hat for the pointer function GPW(rxs) defined by Goos. Pitassi, arid Watson [in Proceedings of the 56th FOCS, IEEE, Piscataway, NJ, 2015, pp. 1077-1088] the following hold: s) s) and (b) R-1(GPW(rxs)) = Irs), cyhere R1 denotes the randomized one-sided error query complexity. These results imply that (i) R-0(GPW(s2xs)) = O(D(GPW(s2xs))2/3) t hereby refuting the; conjecture of Saks and Wigdorson, and (ii) R-1 (GPW(sxs))- O(R-0(GPW(sxs))(2/3)), thereby providing a polynomial separation between the randomized zero -error and one-sided error query complexity measures.
Ämnesord
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
- NATURVETENSKAP -- Matematik (hsv//swe)
- NATURAL SCIENCES -- Mathematics (hsv//eng)
Nyckelord
- deterministic decision tree
- randomized decision tree
- query complexity
- models of computation
Publikations- och innehållstyp
- ref (ämneskategori)
- art (ämneskategori)
Hitta via bibliotek
Till lärosätets databas