Author
|
Conference
|
Journal
|
Organization
|
Year
|
DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all domains
Limit my searches in the following domains
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(2)
kolmogorov complexity
Probability Distribution
Subscribe
Academic
Publications
Possibilities and impossibilities in Kolmogorov complexity extraction
Edit
Possibilities and impossibilities in Kolmogorov complexity extraction
(
Citations: 2
)
BibTex
|
RIS
|
RefWorks
Download
Marius Zimand
Randomness extraction is the process of constructing a source of randomness of high quality from one or several sources of randomness of lower quality. The problem can be modeled using probability distributions and min-entropy to measure their quality and also by using individual strings and
Kolmogorov complexity
to measure their quality. Complexity theorists are more familiar with the rst approach. In this paper we discuss the second approach. We present the connection between extractors and Kolmogorov extractors and the basic positive and negative results concerning
Kolmogorov complexity
extraction.
Journal:
Computing Research Repository - CORR
, vol. abs/1104.0, 2011
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
www.informatik.uni-trier.de
)
(
arxiv.org
)
(
triton.towson.edu
)
Citation Context
(1)
...The recent paper [
Zim10
] is a survey of this field...
...[HPV09] and also the survey paper [
Zim10
])...
Marius Zimand
.
Symmetry of information and bounds on nonuniform randomness extraction...
References
(30)
Constructive Dimension and Turing Degrees
(
Citations: 6
)
Laurent Bienvenu
,
David Doty
,
Frank Stephan
Journal:
Theory of Computing Systems / Mathematical Systems Theory - MST
, vol. 45, no. 4, pp. 740-755, 2009
Increasing Kolmogorov Complexity
(
Citations: 10
)
Harry Buhrman
,
Lance Fortnow
,
Ilan Newman
,
Nikolai K. Vereshchagin
Journal:
Electronic Colloquium on Computational Complexity - ECCC
, no. 081, 2004
Extracting Randomness Using Few Independent Sources
(
Citations: 63
)
Boaz Barak
,
Russell Impagliazzo
,
Avi Wigderson
Conference:
IEEE Symposium on Foundations of Computer Science - FOCS
, pp. 384-393, 2004
More on the Sum-Product Phenomenon in Prime Fields and its Applications
(
Citations: 74
)
J. Bourgain
Published in 2005.
Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
(
Citations: 253
)
Benny Chor
,
Oded Goldreich
Journal:
Siam Journal on Computing - SIAMCOMP
, vol. 17, no. 2, pp. 230-261, 1988
Order by:
Citations
(2)
On the optimal compression of sets in PSPACE
Marius Zimand
Journal:
Computing Research Repository - CORR
, vol. abs/1104.2, 2011
Symmetry of information and bounds on nonuniform randomness extraction via Kolmogorov extractors
Marius Zimand
Conference:
Annual IEEE Conference on Computational Complexity - CCC
, vol. abs/1103.5, pp. 148-156, 2011