Zobrazeno 1 - 10
of 165
pro vyhledávání: '"Pavel Pudlák"'
Autor:
Petr Hájek, Pavel Pudlák
Since their inception, the Perspectives in Logic and Lecture Notes in Logic series have published seminal works by leading logicians. Many of the original books in the series have been unavailable for years, but they are now in print once again. This
Autor:
Dmitry Gavinsky, Pavel Pudlák
Publikováno v:
Theory of Computing Systems. 64:1140-1154
The notion of semi-random sources, also known as Santha-Vazirani (SV) sources, stands for a sequence of n bits, where the dependence of the i’th bit on the previousi − 1 bits is limited for every i ∈ [n]. If the dependence of the i’th bit on
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::a1d9e6880384f2b0096cabd3ae840791
https://doi.org/10.1007/s00224-020-09975-8
https://doi.org/10.1007/s00224-020-09975-8
Publikováno v:
ACM Transactions on Computation Theory. 11:1-31
We introduce the notion of monotone linear programming circuits (MLP circuits), a model of computation for partial Boolean functions. Using this model, we prove the following results. 1 (1) MLP circuits are superpolynomially stronger than monotone Bo
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::a701991f827f9c50feb3984afe24e3f8
https://doi.org/10.1145/3337787
https://doi.org/10.1145/3337787
Autor:
Pavel Pudlák
Motivated by a concept studied in [1] , we consider a property of matrices over finite fields that generalizes triangular totally nonsingular matrices to block matrices. We show that (1) matrices with this property suffice to construct asymptotically
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::c9f494cc018dea7b78ebe740939d0899
Autor:
Pavel Pudlák
The canonical pair of a proof system P is the pair of disjoint NP sets where one set is the set of all satisfiable CNF formulas and the other is the set of CNF formulas that have P-proofs bounded by some polynomial. We give a combinatorial characteri
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::94c6a4f52cc8f21e1500e0366d13ec1d
http://arxiv.org/abs/1912.03013
http://arxiv.org/abs/1912.03013
Autor:
Pavel Pudlák, Pavel Hrubes
Publikováno v:
Information Processing Letters. 131:15-19
We show that if a Boolean function f : { 0 , 1 } n → { 0 , 1 } can be computed by a monotone real circuit of size s using k-ary monotone gates then f can be computed by a monotone real circuit of size O ( s n k − 2 ) which uses unary or binary mo
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::f77d44295b95d247742241a57bbd5c91
https://doi.org/10.1016/j.ipl.2017.11.002
https://doi.org/10.1016/j.ipl.2017.11.002
Autor:
Pavel Pudlák
Publikováno v:
The Bulletin of Symbolic Logic. 23:405-441
Motivated by the problem of finding finite versions of classical incompleteness theorems, we present some conjectures that go beyondNP≠coNP. These conjectures formally connect computational complexity with the difficulty of proving some sentences,
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::e87984b5bb5b0d14a4116d221ea6ae34
https://doi.org/10.1017/bsl.2017.32
https://doi.org/10.1017/bsl.2017.32
Autor:
Dmitry Gavinsky, Pavel Pudlák
Publikováno v:
Commentationes Mathematicae Universitatis Carolinae. 57:333-343
How low can the joint entropy of $n$ $d$-wise independent (for $d\geq 2$) discrete random variables be, subject to given constraints on the individual distributions (say, no value may be taken by a variable with probability greater than $p$, for $p<
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::b655dd82ba5d67b841e62aa4e65e30f6
https://doi.org/10.14712/1213-7243.2015.169
https://doi.org/10.14712/1213-7243.2015.169
Autor:
Pavel Pudlák
Publikováno v:
Linear Algebra and its Applications. 490:124-144
We reduce the problem of constructing asymptotically good tree codes to the construction of triangular totally nonsingular matrices over fields with polynomially many elements. We show a connection of this problem to Birkhoff interpolation in finite
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::b004b947f6e8e95a6ac9bf668b0d7b81
https://doi.org/10.1016/j.laa.2015.10.030
https://doi.org/10.1016/j.laa.2015.10.030
Autor:
Pavel Pudlák, Pavel Hrubes
Publikováno v:
FOCS
We prove new lower bounds on the sizes of proofs in the Cutting Plane proof system, using a concept that we call unsatisfiability certificate. This approach is, essentially, equivalent to the well-known feasible interpolation method, but is applicabl
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::3bd1bf543b811d6a626fb5eea5af419d
https://doi.org/10.1109/focs.2017.20
https://doi.org/10.1109/focs.2017.20