Sökning: (WFRF:(Chaturvedi Sarika)) >
Simulation Theorems...
Simulation Theorems via Pseudo-random Properties
-
- Chattopadhyay, Arkadev (författare)
- Tata Institute of Fundamental Research, Mumbai, Mumbai, India
-
- Koucký, Michal (författare)
- Charles University, Prague Praha, Czech Republic
-
- Loff, Bruno (författare)
- INESC-TEC & U. Porto, Porto, Portugal
-
visa fler...
-
- Mukhopadhyay, Sagnik, 1987- (författare)
- KTH,Teoretisk datalogi, TCS
-
visa färre...
-
(creator_code:org_t)
- 2019-07-18
- 2019
- Engelska.
-
Ingår i: Computational Complexity. - : Springer. - 1016-3328 .- 1420-8954. ; 28:4, s. 617-659
- Relaterad länk:
-
https://doi.org/10.1...
-
visa fler...
-
https://kth.diva-por... (primary) (Raw object)
-
https://link.springe...
-
https://urn.kb.se/re...
-
https://doi.org/10.1...
-
visa färre...
Abstract
Ämnesord
Stäng
- We generalize the deterministic simulation theorem of Raz & McKenzie (Combinatorica 19(3):403–435, 1999), to any gadget which satisfies a certainhitting property. We prove that inner product and gap-Hammingsatisfy this property, and as a corollary, we obtain a deterministic simulationtheorem for these gadgets, where the gadget’s input size is logarithmicin the input size of the outer function. This yields the firstdeterministic simulation theorem with a logarithmic gadget size, answeringan open question posed by Göös, Pitassi & Watson (in: Proceedingsof the 56th FOCS, 2015). Our result also implies the previous results for the indexing gadget, withbetter parameters than was previously known. Moreover, a simulationtheorem with logarithmic-sized gadget implies a quadratic separationin the deterministic communication complexity and the logarithm ofthe 1-partition number, no matter how high the 1-partition number iswith respect to the input size—something which is not achievable by previous results of Göös, Pitassi & Watson (2015).
Ämnesord
- NATURVETENSKAP -- Data- och informationsvetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences (hsv//eng)
Nyckelord
- Computer Science
- Datalogi
Publikations- och innehållstyp
- ref (ämneskategori)
- art (ämneskategori)
Hitta via bibliotek
Till lärosätets databas