Comparing computational entropies below majority (or: When is the dense model theorem false?)

Russell Impagliazzo, Sam McGuire

Type: Preprint

Publication Date: 2020-01-01

Citations: 0

DOI: https://doi.org/10.48550/arxiv.2011.06166

View Publication

Locations

arXiv (Cornell University) - View
DataCite API - View

Similar Works

Action	Title	Year	Authors
+	New Proofs of the Green-Tao-Ziegler Dense Model Theorem: An Exposition	2008	Omer Reingold Luca Trevisan Madhur Tulsiani Salil Vadhan
+	Distinguishing, Predicting, and Certifying: On the Long Reach of Partial Notions of Pseudorandomness	2024	Jiatu Li Edward Pyne Roei Tell
+ PDF Chat	Key developments in algorithmic randomness	2020	Johanna N. Y. Franklin Christopher P. Porter
+	Complexity-Theoretic Implications of Multicalibration	2023	Sílvia Casacuberta Cynthia Dwork Salil Vadhan
+	Unifying computational entropies via Kullback-Leibler divergence	2019	Rohit Agrawal Yi-Hsiu Chen Thibaut Horel Salil Vadhan
+	Complexity-Theoretic Implications of Multicalibration	2024	Sílvia Casacuberta Cynthia Dwork Salil Vadhan
+	Aspects of Chaitin's Omega	2017	George Barmpalias
+	Computational Complexity, Random Sequences, and Probability	1973	Terrence L. Fine
+ PDF Chat	Book Review: Kolmogorov complexity and algorithmic randomness	2019	J. Maurice Rojas
+	Algorithmic Complexity and Pseudo-Random Sequences	1988	Ivan Kramosil
+	Modulus Computational Entropy	2013	Maciej Skórski
+	Modulus Computational Entropy	2013	Maciej Skórski
+ PDF Chat	Special issue from RANDOM’09: Editors’ Foreword	2012	Oded Goldreich Salil Vadhan
+	Analysis of discrete data: Rerandomization methods and complexity	1993	Jenny A. Baglivo Donald Olivier Michele Pagano
+	Generative Models of Huge Objects	2023	Lunjia Hu Inbal Livni-Navon Omer Reingold
+ PDF Chat	Bad oracles in higher computability and randomness	2021	Laurent Bienvenu Noam Greenberg Benoît Monin
+	Key developments in algorithmic randomness	2020	Johanna N. Y. Franklin Christopher P. Porter
+	Lowness, randomness, and computable analysis	2016	André Nies
+	Lowness, randomness, and computable analysis	2016	André Nies
+	Complexity of computing pseudorandom sequences	1968	V. N. Agafonov

Works That Cite This (0)

Action	Title	Year	Authors

Works Cited by This (18)

Action	Title	Year	Authors
+ PDF Chat	Dense Subsets of Pseudorandom Sets	2008	Omer Reingold Luca Trevisan Madhur Tulsiani Salil Vadhan
+	A polynomial bound in Freiman's theorem	2002	Mei-Chu Chang
+	Theory and application of trapdoor functions	1982	Andrew Chi-Chih Yao
+	How much are increasing sets positively correlated?	1996	Michel Talagrand
+ PDF Chat	The primes contain arbitrarily long polynomial progressions	2008	Terence Tao Tamar Ziegler
+ PDF Chat	The primes contain arbitrarily long arithmetic progressions	2008	Benjamin Green Terence Tao
+ PDF Chat	An Entropic Proof of Chang's Inequality	2014	Russell Impagliazzo Cristopher Moore Alexander Russell
+	On sets of integers containing no four elements in arithmetic progression	1969	Endre Szemerédi
+	On representations by low-degree polynomials	2002	Roman Smolensky
+ PDF Chat	Simple Constructions of Almost k‐wise Independent Random Variables	1992	Noga Alon Oded Goldreich Johan Håstad René Peralta