SwePub
Sök i SwePub databas

  Utökad sökning

Träfflista för sökning "WFRF:(Sanyal Swagato) "

Sökning: WFRF:(Sanyal Swagato)

  • Resultat 1-1 av 1
Sortera/gruppera träfflistan
   
NumreringReferensOmslagsbildHitta
1.
  • Mukhopadhyay, Sagnik, et al. (författare)
  • Separation Between Deterministic and Randomized Query Complexity
  • 2018
  • Ingår i: SIAM journal on computing (Print). - : Siam Publications. - 0097-5397 .- 1095-7111. ; 47:4, s. 1644-1666
  • Tidskriftsartikel (refereegranskat)abstract
    • 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.
  •  
Skapa referenser, mejla, bekava och länka
  • Resultat 1-1 av 1
Typ av publikation
tidskriftsartikel (1)
Typ av innehåll
refereegranskat (1)
Författare/redaktör
Mukhopadhyay, Sagnik (1)
Radhakrishnan, Jayku ... (1)
Sanyal, Swagato (1)
Lärosäte
Kungliga Tekniska Högskolan (1)
Språk
Engelska (1)
Forskningsämne (UKÄ/SCB)
Naturvetenskap (1)
År
2018 (1)

Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.

 
pil uppåt Stäng

Kopiera och spara länken för att återkomma till aktuell vy