--- references: - id: Ben-DavidLearnability2019 accessed: - year: 2019 month: 1 day: 14 author: - family: Ben-David given: Shai - family: Hrubeš given: Pavel - family: Moran given: Shay - family: Shpilka given: Amir - family: Yehudayoff given: Amir citation-key: Ben-DavidLearnability2019 container-title: Nature Machine Intelligence DOI: 10.1038/s42256-018-0002-3 ISSN: 2522-5839 issue: '1' issued: - year: 2019 month: 1 language: En page: '44' title: Learnability can be undecidable type: article-journal volume: '1' - id: BhattacharyyaAverage2019 accessed: - year: 2019 month: 6 day: 3 author: - family: Bhattacharyya given: Arnab - family: John given: Philips George - family: Ghoshal given: Suprovat - family: Meka given: Raghu citation-key: BhattacharyyaAverage2019 issued: - year: 2019 number: '079' title: Average Bias and Polynomial Sources type: report URL: https://eccc.weizmann.ac.il/report/2019/079/ - id: BlumerOccam1987 accessed: - year: 2019 month: 1 day: 14 author: - family: Blumer given: Anselm - family: Ehrenfeucht given: Andrzej - family: Haussler given: David - family: Warmuth given: Manfred K. citation-key: BlumerOccam1987 container-title: Information Processing Letters container-title-short: Information Processing Letters DOI: 10.1016/0020-0190(87)90114-1 ISSN: 0020-0190 issue: '6' issued: - year: 1987 month: 4 day: 6 page: 377-380 title: Occam's Razor type: article-journal volume: '24' - id: BravermanPolylogarithmic2008 accessed: - year: 2014 month: 8 day: 18 author: - family: Braverman given: Mark citation-key: BravermanPolylogarithmic2008 container-title: J. ACM DOI: 10.1145/1754399.1754401 ISSN: 0004-5411 issue: '5' issued: - year: 2008 month: 6 page: 28:1–28:10 title: Polylogarithmic Independence Fools AC0 Circuits type: article-journal URL: http://doi.acm.org/10.1145/1754399.1754401 volume: '57' - id: CaludeInformation2002 author: - family: Calude given: Cristian S citation-key: CaludeInformation2002 ISBN: 3-540-43466-6 issued: - year: 2002 publisher: Springer title: 'Information and Randomness : An Algorithmic Perspective' type: book - id: ChaitinAlgorithmic1977 author: - family: Chaitin given: Gregory J citation-key: ChaitinAlgorithmic1977 container-title: IBM journal of research and development ISSN: '0521343062' issued: - year: 1977 title: Algorithmic information theory type: article-journal - id: ChaitinInformation1988 author: - family: Chaitin given: Gregory J citation-key: ChaitinInformation1988 ISBN: 9971-5-0480-4 issued: - year: 1988 publisher: World Scientific Pub Co Inc title: >- Information, Randomness and Incompleteness: Papers on Algorithmic Information Theory (World Scientific Series in Computer Science, Vol 8) type: book - id: ChaitinIntelligibility2002 author: - family: Chaitin given: Gregory J citation-key: ChaitinIntelligibility2002 issued: - year: 2002 title: >- The intelligibility of the universe and the notions of simplicity, complexity and irreducibility type: article-journal - id: ChaitinLength1966 author: - family: Chaitin given: Gregory J citation-key: ChaitinLength1966 container-title: Journal of the ACM (JACM) issue: '4' issued: - year: 1966 page: 547-569 title: On the length of programs for computing finite binary sequences type: article-journal volume: '13' - id: ChaitinSimplicity1969 accessed: - year: 2012 month: 10 day: 21 author: - family: Chaitin given: Gregory J. citation-key: ChaitinSimplicity1969 container-title: J. ACM DOI: 10.1145/321526.321530 ISSN: 0004-5411 issue: '3' issued: - year: 1969 month: 7 page: 407-422 title: >- On the Simplicity and Speed of Programs for Computing Infinite Sets of Natural Numbers type: article-journal URL: http://doi.acm.org/10.1145/321526.321530 volume: '16' - id: ChazelleDiscrepancy2001 author: - family: Chazelle given: Bernard citation-key: ChazelleDiscrepancy2001 edition: 1st paperback ed event-place: Cambridge ISBN: 978-0-521-00357-5 issued: - year: 2001 language: eng number-of-pages: '475' publisher: Cambridge Univ. Press publisher-place: Cambridge title: 'The discrepancy method: randomness and complexity' type: book URL: http://www.cs.princeton.edu/~chazelle/book.html - id: ClarkPlanar2006 accessed: - year: 2014 month: 8 day: 18 author: - family: Clark given: Alexander - family: Florêncio given: Christophe Costa - family: Watkins given: Chris - family: Serayet given: Mariette citation-key: ClarkPlanar2006 collection-number: '4201' collection-title: Lecture Notes in Computer Science container-title: 'Grammatical Inference: Algorithms and Applications' editor: - family: Sakakibara given: Yasubumi - family: Kobayashi given: Satoshi - family: Sato given: Kengo - family: Nishino given: Tetsuro - family: Tomita given: Etsuji ISBN: 978-3-540-45264-5 978-3-540-45265-2 issued: - year: 2006 month: 1 day: 1 language: en page: 148-160 publisher: Springer Berlin Heidelberg title: Planar Languages and Learnability type: chapter URL: http://link.springer.com/chapter/10.1007/11872436_13 - id: CohenIndependence1963 accessed: - year: 2019 month: 1 day: 14 author: - family: Cohen given: Paul J. citation-key: CohenIndependence1963 container-title: Proceedings of the National Academy of Sciences container-title-short: PNAS DOI: 10.1073/pnas.50.6.1143 ISSN: 0027-8424, 1091-6490 issue: '6' issued: - year: 1963 month: 12 day: 1 language: en page: 1143-1148 PMID: '16578557' title: The Independence of the Continuum Hypothesis type: article-journal volume: '50' - id: CohenIndependence1964 accessed: - year: 2019 month: 1 day: 14 author: - family: Cohen given: Paul J. citation-key: CohenIndependence1964 container-title: Proceedings of the National Academy of Sciences container-title-short: PNAS DOI: 10.1073/pnas.51.1.105 ISSN: 0027-8424, 1091-6490 issue: '1' issued: - year: 1964 month: 1 day: 1 language: en page: 105-110 PMID: '16591132' title: The Independence of the Continuum Hypothesis, Ii type: article-journal volume: '51' - id: CortesComputation2008 accessed: - year: 2014 month: 8 day: 18 author: - family: Cortes given: Corinna - family: Mohri given: Mehryar - family: Rastogi given: Ashish - family: Riley given: Michael citation-key: CortesComputation2008 container-title: International Journal of Foundations of Computer Science container-title-short: Int. J. Found. Comput. Sci. DOI: 10.1142/S0129054108005644 ISSN: 0129-0541 issue: '01' issued: - year: 2008 month: 2 day: 1 page: 219-242 title: On the computation of the relative entropy of probabilistic automata type: article-journal URL: http://www.worldscientific.com/doi/abs/10.1142/S0129054108005644 volume: '19' - id: CoverKolmogorov1989 accessed: - year: 2014 month: 7 day: 23 author: - family: Cover given: Thomas M. - family: Gács given: Péter - family: Gray given: Robert M. citation-key: CoverKolmogorov1989 container-title: The Annals of Probability container-title-short: Ann. Probab. DOI: 10.1214/aop/1176991250 ISSN: 0091-1798, 2168-894X issue: '3' issued: - year: 1989 month: 7 language: EN page: 840-865 title: Kolmogorov's Contributions to Information Theory and Algorithmic Complexity type: article-journal volume: '17' - id: CrumillerEstimating2011 accessed: - year: 2021 month: 9 day: 25 author: - family: Crumiller given: Marshall - family: Knight given: Bruce - family: Yu given: Yunguo - family: Kaplan given: Ehud citation-key: CrumillerEstimating2011 container-title: Frontiers in Neuroscience DOI: 10.3389/fnins.2011.00090 ISSN: 1662-453X issued: - year: 2011 page: '90' title: Estimating the Amount of Information Conveyed by a Population of Neurons type: article-journal volume: '5' - id: DaviesImplications2007 author: - family: Davies given: Paul C W citation-key: DaviesImplications2007 container-title: arXiv:quant-ph/0703041 issued: - year: 2007 title: >- The Implications of a Cosmological Information Bound for Complexity, Quantum Information and the Nature of Physical Law type: article-journal URL: http://arxiv.org/abs/quant-ph/0703041 - id: DiakonikolasBounded2009 accessed: - year: 2014 month: 8 day: 18 author: - family: Diakonikolas given: Ilias - family: Gopalan given: Parikshit - family: Jaiswal given: Ragesh - family: Servedio given: Rocco - family: Viola given: Emanuele citation-key: DiakonikolasBounded2009 issued: - year: 2009 number: '016' title: Bounded Independence Fools Halfspaces type: report URL: http://eccc.hpi-web.de/report/2009/016/ - id: FeldmanBrief2002 accessed: - year: 2023 month: 9 day: 4 author: - family: Feldman given: David P citation-key: FeldmanBrief2002 issued: - year: 2002 title: >- A Brief Introduction to: Information Theory, Excess Entropy and Computational Mechanics type: article URL: http://hornacek.coa.edu/dave/Tutorial/notes.pdf - id: GacsAlgorithmic2001 author: - family: Gács given: Péter - family: Tromp given: JohnT. - family: Vitányi given: Paul M.B. citation-key: GacsAlgorithmic2001 container-title: IEEE Transactions on Information Theory DOI: 10.1109/18.945257 ISSN: 0018-9448 issue: '6' issued: - year: 2001 month: 9 page: 2443-2463 title: Algorithmic statistics type: article-journal URL: http://arxiv.org/abs/math/0006233 volume: '47' - id: GodelConsistency1940 author: - family: Gödel given: K. citation-key: GodelConsistency1940 issued: - year: 1940 title: The Consistency of the Continuum Hypothesis type: book - id: GoedelUeber1931 accessed: - year: 2019 month: 1 day: 14 author: - family: Gödel given: Kurt citation-key: GoedelUeber1931 container-title: Monatshefte für Mathematik und Physik container-title-short: Monatsh. f. Mathematik und Physik DOI: 10.1007/BF01700692 ISSN: 1436-5081 issue: '1' issued: - year: 1931 month: 12 day: 1 language: de page: 173-198 title: >- Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I type: article-journal volume: '38' - id: HansenModel2001 accessed: - year: 2012 month: 10 day: 21 author: - family: Hansen given: Mark H. - family: Yu given: Bin citation-key: HansenModel2001 container-title: Journal of the American Statistical Association container-title-short: Journal of the American Statistical Association ISSN: 0162-1459 issue: '454' issued: - year: 2001 month: 6 day: 1 page: 746-774 title: Model Selection and the Principle of Minimum Description Length type: article-journal URL: http://www.jstor.org/stable/2670311 volume: '96' - id: HaslingerComputational2010 accessed: - year: 2021 month: 9 day: 25 author: - family: Haslinger given: Robert - family: Klinkner given: Kristina Lisa - family: Shalizi given: Cosma Rohilla citation-key: HaslingerComputational2010 container-title: Neural computation container-title-short: Neural Comput DOI: 10.1162/neco.2009.12-07-678 ISSN: 0899-7667 issue: '1' issued: - year: 2010 month: 1 page: 121-157 PMCID: PMC2849313 PMID: '19764880' title: The Computational Structure of Spike Trains type: article-journal URL: https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2849313/ volume: '22' - id: HutterTheory2000 accessed: - year: 2022 month: 8 day: 9 author: - family: Hutter given: Marcus citation-key: HutterTheory2000 DOI: 10.48550/arXiv.cs/0004001 issued: - year: 2000 month: 4 day: 3 number: arXiv:cs/0004001 publisher: arXiv title: >- A Theory of Universal Artificial Intelligence based on Algorithmic Complexity type: article URL: http://arxiv.org/abs/cs/0004001 - id: JonasCould2017 accessed: - year: 2017 month: 10 day: 30 author: - family: Jonas given: Eric - family: Kording given: Konrad Paul citation-key: JonasCould2017 container-title: PLOS Computational Biology container-title-short: PLOS Computational Biology DOI: 10.1371/journal.pcbi.1005268 ISSN: 1553-7358 issue: '1' issued: - year: 2017 month: 1 day: 12 page: e1005268 publisher: Public Library of Science title: Could a Neuroscientist Understand a Microprocessor? type: article-journal volume: '13' - id: KolmogorovThree1968 author: - family: Kolmogorov given: A N citation-key: KolmogorovThree1968 container-title: International Journal of Computer Mathematics issue: '1' issued: - year: 1968 page: 157-168 title: Three approaches to the quantitative definition of information type: article-journal volume: '2' - id: KontorovichLearning2006 accessed: - year: 2014 month: 8 day: 18 author: - family: Kontorovich given: Leonid - family: Cortes given: Corinna - family: Mohri given: Mehryar citation-key: KontorovichLearning2006 collection-number: '4264' collection-title: Lecture Notes in Computer Science container-title: Algorithmic Learning Theory editor: - family: Balcázar given: José L. - family: Long given: Philip M. - family: Stephan given: Frank ISBN: 978-3-540-46649-9 978-3-540-46650-5 issued: - year: 2006 month: 1 day: 1 language: en page: 288-303 publisher: Springer Berlin Heidelberg title: Learning Linearly Separable Languages type: chapter URL: http://link.springer.com/chapter/10.1007/11894841_24 - id: KuipersUniform2012 author: - family: Kuipers given: L. - family: Niederreiter given: H. citation-key: KuipersUniform2012 issued: - year: 2012 month: 5 day: 24 language: English number-of-pages: '416' publisher: Dover Publications title: Uniform Distribution of Sequences type: book - id: LeggThere2006 accessed: - year: 2014 month: 9 day: 9 author: - family: Legg given: Shane citation-key: LeggThere2006 collection-number: '4264' collection-title: Lecture Notes in Computer Science container-title: Algorithmic Learning Theory editor: - family: Balcázar given: José L. - family: Long given: Philip M. - family: Stephan given: Frank ISBN: 978-3-540-46649-9 978-3-540-46650-5 issued: - year: 2006 month: 1 day: 1 language: en page: 274-287 publisher: Springer Berlin Heidelberg title: Is There an Elegant Universal Theory of Prediction? type: chapter URL: http://link.springer.com/chapter/10.1007/11894841_23 - id: LiIntroduction2009 accessed: - year: 2014 month: 8 day: 18 author: - family: Li given: Ming - family: Vitányi given: Paul MB citation-key: LiIntroduction2009 edition: '3' ISBN: 0-387-33998-1 978-0-387-33998-6 issued: - year: 2009 publisher: Springer title: An introduction to Kolmogorov complexity and its applications type: book URL: >- http://books.google.com/books?hl=en&lr=&id=25fue3UYDN0C&oi=fnd&pg=PR3&ots=U62oahU4ci&sig=dcCX1ETvTRC1X_2MVB0Vo5gH49g - id: LittlestoneRelating1986 author: - family: Littlestone given: N. - family: Warmuth given: M. K. citation-key: LittlestoneRelating1986 issued: - year: 1986 title: Relating Data Compression and Learnability type: book - id: MezardInformation2009 author: - family: Mezard given: Marc - family: Montanari given: Andrea call-number: QC174.8 .M49 2009 citation-key: MezardInformation2009 collection-title: Oxford graduate texts edition: 1 edition event-place: Oxford ; New York ISBN: 978-0-19-857083-7 issued: - year: 2009 number-of-pages: '569' publisher: Oxford University Press publisher-place: Oxford ; New York title: Information, physics, and computation type: book URL: http://web.stanford.edu/~montanar/RESEARCH/book.html - id: NemenmanEntropy2004 accessed: - year: 2021 month: 9 day: 25 author: - family: Nemenman given: Ilya - family: Bialek given: William - family: Ruyter van Steveninck given: Rob non-dropping-particle: de citation-key: NemenmanEntropy2004 container-title: Physical Review E container-title-short: Phys. Rev. E DOI: 10.1103/PhysRevE.69.056111 ISSN: 1539-3755, 1550-2376 issue: '5' issued: - year: 2004 month: 5 day: 24 language: en page: '056111' title: >- Entropy and information in neural spike trains: Progress on the sampling problem type: article-journal URL: https://www.princeton.edu/~wbialek/our_papers/nemenman+al_03.pdf volume: '69' - id: NortonAll2013 accessed: - year: 2014 month: 3 day: 17 author: - family: Norton given: John D. citation-key: NortonAll2013 container-title: Entropy DOI: 10.3390/e15104432 issue: '10' issued: - year: 2013 month: 10 day: 17 language: en page: 4432-4483 title: >- All Shook Up: Fluctuations, Maxwell’s Demon and the Thermodynamics of Computation type: article-journal URL: http://www.mdpi.com/1099-4300/15/10/4432 volume: '15' - id: PerekrestenkoConstructive2020 author: - family: Perekrestenko given: Dmytro - family: Müller given: Stephan - family: Bölcskei given: Helmut citation-key: PerekrestenkoConstructive2020 issued: - year: 2020 language: en publisher: arXiv title: >- Constructive Universal High-Dimensional Distribution Generation through Deep ReLU Networks type: article-journal URL: https://arxiv.org/abs/2006.16664 version: '2' - id: PerekrestenkoHighdimensional2021 accessed: - year: 2023 month: 9 day: 8 author: - family: Perekrestenko given: Dmytro - family: Eberhard given: Léandre - family: Bölcskei given: Helmut citation-key: PerekrestenkoHighdimensional2021 container-title: Partial Differential Equations and Applications container-title-short: Partial Differ. Equ. Appl. DOI: 10.1007/s42985-021-00115-6 ISSN: 2662-2963, 2662-2971 issue: '5' issued: - year: 2021 month: 10 language: en page: '64' publisher: arXiv title: High-dimensional distribution generation through deep neural networks type: article-journal URL: https://arxiv.org/abs/2107.12466 version: '3' volume: '2' - id: ReyzinUnprovability2019 accessed: - year: 2019 month: 1 day: 14 author: - family: Reyzin given: Lev citation-key: ReyzinUnprovability2019 container-title: Nature DOI: 10.1038/d41586-019-00012-4 issue: '7738' issued: - year: 2019 month: 1 language: EN page: '166' title: Unprovability comes to machine learning type: article-journal volume: '565' - id: RieglerLossy2023 accessed: - year: 2023 month: 9 day: 7 author: - family: Riegler given: Erwin - family: Bölcskei given: Helmut - family: Koliander given: Günther citation-key: RieglerLossy2023 DOI: 10.48550/arXiv.2111.12312 issued: - year: 2023 month: 6 day: 2 number: arXiv:2111.12312 publisher: arXiv title: Lossy Compression of General Random Variables type: article URL: http://arxiv.org/abs/2111.12312 - id: RissanenInformation2007 author: - family: Rissanen given: Jorma call-number: QA276.A1 R57 2007 citation-key: RissanenInformation2007 collection-title: Information science and statistics event-place: New York ISBN: 978-0-387-68812-1 issued: - year: 2007 number-of-pages: '142' publisher: Springer publisher-place: New York title: Information and complexity in statistical modeling type: book URL: http://www.springer.com/mathematics/probability/book/978-0-387-36610-4 - id: ShibataProbabilistic2006 accessed: - year: 2014 month: 9 day: 9 author: - family: Shibata given: Takeshi - family: Yoshinaka given: Ryo - family: Chikayama given: Takashi citation-key: ShibataProbabilistic2006 collection-number: '4264' collection-title: Lecture Notes in Computer Science container-title: Algorithmic Learning Theory editor: - family: Balcázar given: José L. - family: Long given: Philip M. - family: Stephan given: Frank ISBN: 978-3-540-46649-9 978-3-540-46650-5 issued: - year: 2006 month: 1 day: 1 language: en page: 348-362 publisher: Springer Berlin Heidelberg title: >- Probabilistic Generalization of Simple Grammars and Its Application to Reinforcement Learning type: chapter URL: http://link.springer.com/chapter/10.1007/11894841_28 - id: SolomonoffFormal1964 accessed: - year: 2012 month: 10 day: 21 author: - family: Solomonoff given: R.J. citation-key: SolomonoffFormal1964 container-title: Information and Control container-title-short: Information and Control DOI: 10.1016/S0019-9958(64)90131-7 ISSN: 0019-9958 issue: '2' issued: - year: 1964 month: 6 page: 224-254 title: A formal theory of inductive inference. Part II type: article-journal volume: '7' - id: SolomonoffFormal1964a accessed: - year: 2012 month: 10 day: 21 author: - family: Solomonoff given: R.J. citation-key: SolomonoffFormal1964a container-title: Information and Control container-title-short: Information and Control DOI: 10.1016/S0019-9958(64)90223-2 ISSN: 0019-9958 issue: '1' issued: - year: 1964 month: 3 page: 1-22 title: A formal theory of inductive inference. Part I type: article-journal volume: '7' - id: SterkenburgSolomonoff2016 accessed: - year: 2020 month: 8 day: 5 author: - family: Sterkenburg given: Tom F. citation-key: SterkenburgSolomonoff2016 container-title: Philosophy of Science container-title-short: Philosophy of Science DOI: 10.1086/687257 ISSN: 0031-8248 issue: '4' issued: - year: 2016 month: 10 day: 1 page: 459-479 publisher: The University of Chicago Press title: Solomonoff Prediction and Occam’s Razor type: article-journal URL: https://www.journals.uchicago.edu/doi/abs/10.1086/687257 volume: '83' - id: ValiantTheory1984 accessed: - year: 2012 month: 9 day: 28 author: - family: Valiant given: L. G. citation-key: ValiantTheory1984 container-title: Commun. ACM DOI: 10.1145/1968.1972 ISSN: 0001-0782 issue: '11' issued: - year: 1984 month: 11 page: 1134-1142 title: A theory of the learnable type: article-journal URL: http://doi.acm.org/10.1145/1968.1972 volume: '27' - id: VapnikUniform1971 accessed: - year: 2015 month: 4 day: 2 author: - family: Vapnik given: V. - family: Chervonenkis given: A. citation-key: VapnikUniform1971 container-title: Theory of Probability & Its Applications container-title-short: Theory Probab. Appl. DOI: 10.1137/1116025 ISSN: 0040-585X issue: '2' issued: - year: 1971 month: 1 day: 1 page: 264-280 title: >- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities type: article-journal URL: https://courses.engr.illinois.edu/ece544na/fa2014/vapnik71.pdf volume: '16' - id: VereshchaginKolmogorov2004 author: - family: Vereshchagin given: N.K. - family: Vitányi given: Paul MB citation-key: VereshchaginKolmogorov2004 container-title: IEEE Transactions on Information Theory DOI: 10.1109/TIT.2004.838346 ISSN: 0018-9448 issue: '12' issued: - year: 2004 month: 12 page: 3265-3290 title: Kolmogorov's structure functions and model selection type: article-journal URL: http://homepages.cwi.nl/~paulv/papers/structure.pdf volume: '50' - id: VereshchaginRate2010 author: - family: Vereshchagin given: N.K. - family: Vitányi given: Paul MB citation-key: VereshchaginRate2010 container-title: IEEE Transactions on Information Theory DOI: 10.1109/TIT.2010.2048491 ISSN: 0018-9448 issue: '7' issued: - year: 2010 month: 7 page: 3438-3454 title: Rate Distortion and Denoising of Individual Data Using Kolmogorov Complexity type: article-journal volume: '56' - id: VitanyiMeaningful2006 author: - family: Vitányi given: Paul M citation-key: VitanyiMeaningful2006 container-title: IEEE Transactions on Information Theory DOI: 10.1109/TIT.2006.881729 issue: '10' issued: - year: 2006 page: 4617-4626 title: Meaningful information type: article-journal volume: '52' ...