NDLI: Advice Lower Bounds for the Dense Model Theorem

Please wait, while we are loading the content...

Advice Lower Bounds for the Dense Model Theorem

Content Provider	ACM Digital Library
Author	Watson, Thomas
Copyright Year	2015
Abstract	We prove a lower bound on the amount of nonuniform advice needed by black-box reductions for the Dense Model Theorem of Green, Tao, and Ziegler, and of Reingold, Trevisan, Tulsiani, and Vadhan. The latter theorem roughly says that for every distribution $\textit{D}$ that is Δ-dense in a distribution that is $\textit{ε}′-indistinguishable$ from uniform, there exists a “dense model” for $\textit{D},$ that is, a distribution that is $\textit{Δ}-dense$ in the uniform distribution and is $\textit{ε}-indistinguishable$ from $\textit{D}.$ This $\textit{ε}-indistinguishability$ is with respect to an arbitrary small class of functions $\textit{F}.$ For the natural case where $\textit{ε}′$ ≥ $Ω(\textit{εΔ})$ and $\textit{ε}$ ≥ $\textit{Δ}\textit{O}(1),$ our lower bound implies that $Ω(√(1/\textit{ε})$ $log(1/\textit{Δ})·log\|\textit{F}\|)$ advice bits are necessary for a certain type of reduction that establishes a stronger form of the Dense Model Theorem (and which encompasses all known proofs of the Dense Model Theorem in the literature). There is only a polynomial gap between our lower bound and the best upper bound for this case (due to Zhang), which is $\textit{O}((1/\textit{ε}2)log(1/\textit{Δ})·log\|\textit{F}\|).$ Our lower bound can be viewed as an analogue of list size lower bounds for list-decoding of error-correcting codes, but for “dense model decoding” instead.
Starting Page	1
Ending Page	18
Page Count	18
File Format	PDF
ISSN	19423454
e-ISSN	19423462
DOI	10.1145/2676659
Volume Number	7
Issue Number	1
Journal	ACM Transactions on Computation Theory (TOCT)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2015-01-13
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Advice Dense model theorem Lower bounds
Content Type	Text
Resource Type	Article
Subject	Computational Theory and Mathematics Theoretical Computer Science

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Lower bounds for the polynomial calculus

Lower bounds for the bilinear complexity of associative algebras

Lower bounds for the multiplicative complexity of matrix multiplication

Exponential lower bounds for depth three Boolean circuits

Improved depth lower bounds for small distance connectivity

Lower bounds for the polynomial calculus and the Gröbner basis algorithm

Extractors and Lower Bounds for Locally Samplable Sources

Real Advantage

On lower bounds for the complexity of polynomials and their multiples

Advice Lower Bounds for the Dense Model Theorem

Similar Documents

Lower bounds for the polynomial calculus

Lower bounds for the bilinear complexity of associative algebras

Lower bounds for the multiplicative complexity of matrix multiplication

Exponential lower bounds for depth three Boolean circuits

Improved depth lower bounds for small distance connectivity

Lower bounds for the polynomial calculus and the Gröbner basis algorithm

Extractors and Lower Bounds for Locally Samplable Sources

Real Advantage

On lower bounds for the complexity of polynomials and their multiples

Advice Lower Bounds for the Dense Model Theorem