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 gadget’s input-size is logarithmic in the input-size of the outer function. This answers an open question posed by Göös, 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?)
About
Help
contact arXivClick here to contact arXiv
Contact
subscribe to arXiv mailingsClick here to subscribe
Subscribe
Copyright
Privacy Policy
Web Accessibility Assistance
arXiv Operational Status
Get status notifications via email or slack