Zobrazeno 1 - 10
of 24
pro vyhledávání: '"Ján Pich"'
Autor:
Ján Pich
Publikováno v:
Logical Methods in Computer Science, Vol Volume 11, Issue 2 (2015)
We present several known formalizations of theorems from computational complexity in bounded arithmetic and formalize the PCP theorem in the theory PV1 (no formalization of this theorem was known). This includes a formalization of the existence and o
Externí odkaz:
https://doaj.org/article/9e7c7dbc2e784a0eb132ee141577d60f
Publikováno v:
Theory of Computing. 17:1-38
This work continues the development of hardness magnification. The latter proposes a new strategy for showing strong complexity lower bounds by reducing them to a refined analysis of weaker models, where combinatorial techniques might be successful.W
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::e473bfd8b58fae61db8ad408d99651a2
https://doi.org/10.4086/toc.2021.v017a011
https://doi.org/10.4086/toc.2021.v017a011
Publikováno v:
UPCommons. Portal del coneixement obert de la UPC
Universitat Politècnica de Catalunya (UPC)
Universitat Politècnica de Catalunya (UPC)
We define and investigate Frege systems for quantified Boolean formulas (QBF). For these new proof systems, we develop a lower bound technique that directly lifts circuit lower bounds for a circuit class C to the QBF Frege system operating with lines
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::b1a71059526abcfaa4d32b866518de6d
https://doi.org/10.1145/3381881
https://doi.org/10.1145/3381881
Autor:
Ján Pich, Rahul Santhanam
Publikováno v:
STOC
We show unconditionally that Cook’s theory PV formalizing poly-time reasoning cannot prove, for any non-deterministic poly-time machine M defining a language L(M), that L(M) is inapproximable by co-nondeterministic circuits of sub-exponential size.
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::ce1e3f3a3e3998398a88fc1a75ceea24
https://doi.org/10.1145/3406325.3451117
https://doi.org/10.1145/3406325.3451117
Autor:
Ján Pich
Publikováno v:
Ján Pich
We revisit known constructions of efficient learning algorithms from various notions of constructive circuit lower bounds such as distinguishers breaking pseudorandom generators or efficient witnessing algorithms which find errors of small circuits a
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=arXiv_dedup_::5bd3425a8bdfeb7a2df5ba649f272dfd
http://arxiv.org/abs/2012.14095
http://arxiv.org/abs/2012.14095
We aim to understand inherent reasons for lower bounds for QBF proof systems and revisit and compare two previous approaches in this direction. The first of these relates size lower bounds for strong QBF Frege systems to circuit lower bounds via stra
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::d9f747209bc6ccc35014d6d6efe1d006
https://doi.org/10.1145/3378665
https://doi.org/10.1145/3378665
Autor:
Lijie Chen, Shuichi Hirahara, Igor Carboni Oliveira, Ján Pich, Ninad Rajgopal, Rahul Santhanam
Hardness magnification reduces major complexity separations (such as EXP ⊈ NC 1 ) to proving lower bounds for some natural problem Q against weak circuit models. Several recent works [ 11 , 13 , 14 , 40 , 42 , 43 , 46 ] have established results of
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::fcbd51fd8e7c238ae8d9fd7c6e9358ce
Autor:
Jan Vácha, Jan Pichrt
Publikováno v:
Acta Universitatis Carolinae. Iuridica, Vol 69, Iss 4, Pp 69-77 (2023)
The aim of this article is to draw attention to the non-compliance of Czech enactment and possibilities of collective bargaining in civil service in the light of non-legally binding interpretation of responsible state institution (Department of civil
Externí odkaz:
https://doaj.org/article/6da089a4814348b393d903fc224e6e2b
Autor:
Jan Pichrt
Publikováno v:
Acta Universitatis Carolinae. Iuridica, Vol 69, Iss 4, Pp 7-19 (2023)
This paper deals with the issue of individuals who are employees of the state (the Czech Republic), but are not civil servants under the Civil Service Act. The author points out the shortcomings that the legislature has committed in the past in defin
Externí odkaz:
https://doaj.org/article/68540c50215d45cb8d97597533a0ae6b
Autor:
Ján Pich, Rahul Santhanam
Publikováno v:
FOCS
We formalize and study the question of whether there are inherent difficulties to showing lower bounds on propositional proof complexity. We establish the following unconditional result: Propositional proof systems cannot efficiently show that truth
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::2701c0b60b9e01eb6c737422846c21e2
https://doi.org/10.1109/focs.2019.00080
https://doi.org/10.1109/focs.2019.00080