NDLI: An Improved Analysis of Linear Mergers

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

An Improved Analysis of Linear Mergers

Content Provider	Springer Nature Link
Author	Dvir, Zeev Shpilka, Amir
Copyright Year	2007
Abstract	Mergers are procedures that, with the aid of a short random string, transform k (possibly dependent) random sources into a single random source, in a way that ensures that if one of the input sources has min-entropy rate δ then the output has min-entropy rate close to δ. Mergers were first introduced by Ta-Shma [28th STOC, pp. 276-285, 1996] and have proven to be a very useful tool in explicit constructions of extractors and condensers. In this work we present a new analysis of the merger construction of Lu et al [35th STOC, pp. 602-611, 2003]. We prove that the merger’s output is close to a distribution with min-entropy rate of at least $$\frac{6}{11}\delta$$ . We show that the distance from this distribution is polynomially related to the number of additional random bits that were used by the merger (i.e., its seed). We are also able to prove a bound of $$\frac{4}{7}\delta$$ on the min-entropy rate at the cost of increasing the statistical error. Both results are improvements to the previous known lower bound of $$\frac{1}{2}\delta$$ (however, in the $$\frac{1}{2}\delta$$ result the error decreases exponentially in the length of the seed). To obtain our results we deviate from the usual linear algebra methods that were used by Lu et al and introduce techniques from additive number theory.
Starting Page	34
Ending Page	59
Page Count	26
File Format	PDF
ISSN	10163328
Journal	Computational complexity
Volume Number	16
Issue Number	1
e-ISSN	14208954
Language	English
Publisher	Birkhäuser-Verlag
Publisher Date	2007-01-01
Publisher Place	Basel
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Mergers extractors Kakeya randomness Algorithm Analysis and Problem Complexity Computational Mathematics and Numerical Analysis
Content Type	Text
Resource Type	Article
Subject	Theoretical Computer Science Computational Theory and Mathematics Computational Mathematics

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

On The Randomness Complexity of Property Testing

Extractors And Rank Extractors For Polynomial Sources

Extractors for varieties

Weak Derandomization of Weak Algorithms: Explicit Versions of Yao’s Lemma

Incompressible Functions, Relative-Error Extractors, and the Power of Nondeterministic Reductions

Derandomized Parallel Repetition Theorems for Free Games

Exposure-Resilient Extractors and the Derandomization of Probabilistic Sublinear Time

Affine extractors over large fields with exponential error

Improved Approximation of Linear Threshold Functions

An Improved Analysis of Linear Mergers

Similar Documents

On The Randomness Complexity of Property Testing

Extractors And Rank Extractors For Polynomial Sources

Extractors for varieties

Weak Derandomization of Weak Algorithms: Explicit Versions of Yao’s Lemma

Incompressible Functions, Relative-Error Extractors, and the Power of Nondeterministic Reductions

Derandomized Parallel Repetition Theorems for Free Games

Exposure-Resilient Extractors and the Derandomization of Probabilistic Sublinear Time

Affine extractors over large fields with exponential error

Improved Approximation of Linear Threshold Functions

An Improved Analysis of Linear Mergers