747 citations
- University of Maryland, College ParkUS52 papers
- European Southern ObservatoryCL31 papers
- Johns Hopkins UniversityUS24 papers
- Centro de AstrobiologíaES22 papers
- Goddard Space Flight CenterUS20 papers
- Atacama Large Millimeter Submillimeter ArrayCL19 papers
- Space Telescope Science InstituteUS19 papers
- RIKENJP16 papers
- Center for Astrophysics Harvard & SmithsonianUS14 papers
- Arcetri Astrophysical ObservatoryIT13 papers
- Australian Defence Force AcademyAU13 papers
- North Carolina State UniversityUS13 papers
9 papers · 1 filter
On optimal language compression for sets in PSPACE/poly
N. V. Vinodchandran, Marius Zimand
We show that if DTIME[2^O(n)] is not included in DSPACE[2^o(n)], then, for every set B in PSPACE/poly, all strings x in B of length n can be represented by a string compressed(x) o…
Short lists with short programs in short time - a short proof
Marius Zimand
Bauwens, Mahklin, Vereshchagin and Zimand [ECCC TR13-007] and Teutsch [arxiv:1212.6104] have shown that given a string x it is possible to construct in polynomial time a list conta…
On efficient constructions of short lists containing mostly Ramsey graphs
Marius Zimand
One of the earliest and best-known application of the probabilistic method is the proof of existence of a 2 log n$-Ramsey graph, i.e., a graph with n nodes that contains no clique…
Nonuniform Kolmogorov extractors
Marius Zimand
We establish tight bounds on the amount on nonuniformity that is necessary for extracting a string with randomness rate 1 from a single source of randomness with lower randomness r…
Possibilities and impossibilities in Kolmogorov complexity extraction
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 u…
Symmetry of information and bounds on nonuniform randomness extraction via Kolmogorov extractors
Marius Zimand
We prove a strong Symmetry of Information relation for random strings (in the sense of Kolmogorov complexity) and establish tight bounds on the amount on nonuniformity that is nece…