Zobrazeno 1 - 10
of 23
pro vyhledávání: '"Shuichi Hirahara"'
Autor:
LIJIE CHEN1 lijieche@mit.edu, SHUICHI HIRAHARA2 s_hirahara@nii.ac.jp, OLIVEIRA, IGOR CARBONI3 igor.oliveira@warwick.ac.uk, PICH, JÁN4 jan.pich@cs.ox.ac.uk, RAJGOPAL, NINAD3 ninad.rajgopal@warwick.ac.uk, SANTHANAM, RAHUL4 rahul.santhanam@cs.ox.ac.uk
Publikováno v:
Journal of the ACM. Jul2022, Vol. 69 Issue 4, p1-49. 49p.
A version of time-bounded Kolmogorov complexity, denoted KT, has received attention in the past several years, due to its close connection to circuit complexity and to the Minimum Circuit Size Problem MCSP. Essentially all results about the complexit
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::811370386e56ef5b730787d6b31caafb
Autor:
SHUICHI HIRAHARA1 s.hirahara@nii.ac.jp
Publikováno v:
SIAM Journal on Computing. 2023, Vol. 52 Issue 6, p1-34. 34p.
Publikováno v:
Proceedings of the 55th Annual ACM Symposium on Theory of Computing.
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::e22ea93b9ba3b8d9dcebbffb807ab99f
https://doi.org/10.1145/3564246.3585138
https://doi.org/10.1145/3564246.3585138
Autor:
Shuichi Hirahara, Nobutaka Shimizu
Publikováno v:
Proceedings of the 55th Annual ACM Symposium on Theory of Computing.
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::d4774d3373e03055182007bd70d97add
https://doi.org/10.1145/3564246.3585189
https://doi.org/10.1145/3564246.3585189
Autor:
Shuichi Hirahara
Publikováno v:
Proceedings of the 55th Annual ACM Symposium on Theory of Computing.
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::359cdca334f67c9dbaaaad12c669dc9c
https://doi.org/10.1145/3564246.3585130
https://doi.org/10.1145/3564246.3585130
Publikováno v:
Theory of Computing Systems.
For a size parameter s: ℕ → ℕ, the Minimum Circuit Size Problem (denoted by MCSP[s(n)]) is the problem of deciding whether the minimum circuit size of a given function f : {0,1}ⁿ → {0,1} (represented by a string of length N : = 2ⁿ) is at
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::2f75f30edf77310f78c40013e4f48001
https://doi.org/10.1007/s00224-022-10113-9
https://doi.org/10.1007/s00224-022-10113-9
Autor:
Shuichi Hirahara, Nobutaka Shimizu
Publikováno v:
2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS).
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::46bde33d9ed5333f8403aac3b13dcd0b
https://doi.org/10.1109/focs54457.2022.00058
https://doi.org/10.1109/focs54457.2022.00058
Autor:
Shuichi Hirahara
Publikováno v:
2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS).
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::ad18c772544ba2592ca1c70129bf531d
https://doi.org/10.1109/focs54457.2022.00095
https://doi.org/10.1109/focs54457.2022.00095
Autor:
Shuichi Hirahara, Mikito Nanashima
Publikováno v:
2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS).
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::b52001f47847997a96119e68d03b9a1d
https://doi.org/10.1109/focs52979.2021.00078
https://doi.org/10.1109/focs52979.2021.00078