[图书][B] An introduction to Kolmogorov complexity and its applications
Ming Li Paul Vitányi Fourth Edition Page 1 An Introduction to Kolmogorov Complexity and Its
Applications Ming Li Paul Vitányi Fourth Edition Texts in Computer Science Page 2 Texts in …
Applications Ming Li Paul Vitányi Fourth Edition Texts in Computer Science Page 2 Texts in …
[PDF][PDF] Stanford encyclopedia of philosophy
Notice: This PDF version was distributed by request to members of the Friends of the SEP
Society and by courtesy to SEP content contributors. It is solely for their fair use …
Society and by courtesy to SEP content contributors. It is solely for their fair use …
[PDF][PDF] Beating brute force for compression problems
S Hirahara, R Ilango, RR Williams - … of the 56th Annual ACM Symposium …, 2024 - dl.acm.org
A compression problem is defined with respect to an efficient encoding function f; given a
string x, our task is to find the shortest y such that f (y)= x. The obvious brute-force algorithm …
string x, our task is to find the shortest y such that f (y)= x. The obvious brute-force algorithm …
Aerial lidar data classification using adaboost
SK Lodha, DM Fitzpatrick… - … Conference on 3-D …, 2007 - ieeexplore.ieee.org
We use the AdaBoost algorithm to classify 3D aerial lidar scattered height data into four
categories: road, grass, buildings, and trees. To do so we use five features: height, height …
categories: road, grass, buildings, and trees. To do so we use five features: height, height …
Capturing one-way functions via np-hardness of meta-complexity
S Hirahara - Proceedings of the 55th Annual ACM Symposium on …, 2023 - dl.acm.org
A one-way function is a function that is easy to compute but hard to invert* on average*. We
establish the first characterization of a one-way function by* worst-case* hardness …
establish the first characterization of a one-way function by* worst-case* hardness …
On one-way functions and the worst-case hardness of time-bounded kolmogorov complexity
Whether one-way functions (OWF) exist is arguably the most important problem in
Cryptography, and beyond. While lots of candidate constructions of one-way functions are …
Cryptography, and beyond. While lots of candidate constructions of one-way functions are …
Average-case hardness of NP from exponential worst-case hardness assumptions
S Hirahara - Proceedings of the 53rd Annual ACM SIGACT …, 2021 - dl.acm.org
A long-standing and central open question in the theory of average-case complexity is to
base average-case hardness of NP on worst-case hardness of NP. A frontier question along …
base average-case hardness of NP on worst-case hardness of NP. A frontier question along …
Learning in Pessiland via Inductive Inference
S Hirahara, M Nanashima - 2023 IEEE 64th Annual Symposium …, 2023 - ieeexplore.ieee.org
Pessiland is one of Impagliazzo's five possible worlds in which NP is hard on average, yet
no one-way function exists. This world is considered the most pessimistic because it offers …
no one-way function exists. This world is considered the most pessimistic because it offers …
[图书][B] Alternative concepts of God: essays on the metaphysics of the divine
A Buckareff, Y Nagasawa - 2016 - books.google.com
The concept of God according to traditional Judeo-Christian-Islamic theism minimally
includes the following theses:(i) There is one God;(ii) God is an omniscient, omnipotent, and …
includes the following theses:(i) There is one God;(ii) God is an omniscient, omnipotent, and …
On worst-case learning in relativized heuristica
S Hirahara, M Nanashima - 2021 IEEE 62nd Annual …, 2022 - ieeexplore.ieee.org
A PAC learning model involves two worst-case requirements: a learner must learn all
functions in a class on all example distributions. However, basing the hardness of learning …
functions in a class on all example distributions. However, basing the hardness of learning …