Skip to main content
We gratefully acknowledge support from
the Simons Foundation and member institutions.
arXiv.org > cs > arXiv:1704.06807
Help | Advanced Search
All fields
Title
Author
Abstract
Comments
Journal reference
ACM classification
MSC classification
Report number
arXiv identifier
DOI
ORCID
arXiv author ID
Help pages
Full text
Search
Computer Science > Computational Complexity
[Submitted on 22 Apr 2017]
Simulation Theorems via Pseudorandom Properties
Arkadev Chattopadhyay, Michal Kouck, Bruno Loff, Sagnik Mukhopadhyay
We generalize the deterministic simulation theorem of Raz and McKenzie [RM99], to any gadget which satisfies certain hitting property. We prove that inner-product and gap-Hamming satisfy this property, and as a corollary we obtain deterministic simulation theorem for these gadgets, where the gadgets input-size is logarithmic in the input-size of the outer function. This answers an open question posed by Gs, Pitassi and Watson [GPW15]. Our result also implies the previous results for the Indexing gadget, with better parameters than was previously known. A preliminary version of the results obtained in this work appeared in [CKL+17].
Subjects:
Computational Complexity (cs.CC)
Cite as:
arXiv:1704.06807 [cs.CC]
(or arXiv:1704.06807v1 [cs.CC] for this version)
Submission history
From: Bruno Loff [view email]
[v1] Sat, 22 Apr 2017 14:27:50 UTC (26 KB)
Download:
PDF
PostScript
Other formats
(license)
Current browse context:
cs.CC
<prev | next>
new | recent | 1704
Change to browse by:
cs
References & Citations
NASA ADS
Google Scholar
Semantic Scholar
DBLP CS Bibliography
listing | bibtex
Arkadev Chattopadhyay
Michal Kouck
Bruno Loff
Sagnik Mukhopadhyay
Export Bibtex Citation
Bookmark
Bibliographic Tools
Bibliographic and Citation Tools
Bibliographic Explorer Toggle
Bibliographic Explorer (What is the Explorer?)
Code
Related Papers
About arXivLabs
Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)
AboutHelp
contact arXivClick here to contact arXivContactsubscribe to arXiv mailingsClick here to subscribeSubscribe
CopyrightPrivacy Policy
Web Accessibility AssistancearXiv Operational Status Get status notifications via email or slack
Reviews
There are no reviews yet.