Zobrazeno 1 - 10
of 21
pro vyhledávání: '"Pavel Hrubeš"'
Autor:
Veronika Vlčková, Pavel Hrubeš
Publikováno v:
Acta Informatica Pragensia, Vol 4, Iss 1, Pp 64-79 (2015)
One of the many often frequented topics as normal journalism, so the professional public, is the problem of traffic accidents. This article illustrates the orientation of considerations to a less known context of accidents, with the help of construct
Externí odkaz:
https://doaj.org/article/1410f411a2d848399facf82f7801a5a3
Autor:
Pavel Hrubeš, Navid Talebanfard
We show that 1. for every $A\subseteq \{0, 1\}^n$, there exists a polytope $P\subseteq \mathbb{R}^n$ with $P \cap \{0, 1\}^n = A$ and extension complexity $O(2^{n/2})$, 2. there exists an $A\subseteq \{0, 1\}^n$ such that the extension complexity of
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::81a9d191bb8ade5212175c2e791c94cf
Autor:
Pavel Hrubeš
Publikováno v:
computational complexity. 29
We show that strong-enough lower bounds on monotone arithmetic circuits or the nonnegative rank of a matrix imply unconditional lower bounds in arithmetic or Boolean circuit complexity. First, we show that if a polynomial $$f\in \mathbb {R}[x_1,\dots
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::7d390e884157d90ac8a9045894cdce4c
https://doi.org/10.1007/s00037-020-00196-6
https://doi.org/10.1007/s00037-020-00196-6
Autor:
Avi Wigderson, Pavel Hrubeš
Publikováno v:
Theory of Computing. 11:357-393
We initiate the study of the complexity of arithmetic circuits with division gates over non-commuting variables. Such circuits and formulas compute non-commutative rational functions, which, despite their name, can no longer be expressed as ratios of
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::848cdbbe244df4eceace3c8a7258ccbe
https://doi.org/10.4086/toc.2015.v011a014
https://doi.org/10.4086/toc.2015.v011a014
Publikováno v:
MFPS
The construction of various categories of “timed sets” is described in which the timing of maps is considered modulo a “complexity order”. The properties of these categories are developed: under appropriate conditions they form discrete, dist
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::a58932f5a6dac052b1a41ce247ef6993
Autor:
Pavel Hrubeš
Publikováno v:
Information Processing Letters. 112:457-461
For real numbers a"1,...,a"n, let Q(a"1,...,a"n) be the nxn matrix whose i,j-th entry is (a"i-a"j)^2. We show that Q(1,...,n) has nonnegative rank at most 2log"2n+2. This refutes a conjecture from Beasley and Laffey (2009) [1] (and contradicts a ''th
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::14bd97c1462bf1498ca238661a142375
https://doi.org/10.1016/j.ipl.2012.02.009
https://doi.org/10.1016/j.ipl.2012.02.009
Publikováno v:
Journal of the American Mathematical Society. 24:871-898
We initiate a direction for proving lower bounds on the size of non-commutative arithmetic circuits. This direction is based on a connection between lower bounds on the size of non-commutative arithmetic circuits and a problem about commutative degre
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::250e95d567a4c401908182ecf8c8b094
https://doi.org/10.1090/s0894-0347-2011-00694-2
https://doi.org/10.1090/s0894-0347-2011-00694-2
Autor:
Amir Yehudayoff, Pavel Hrubeš
Publikováno v:
Theory of Computing. 7:119-129
Given a polynomial f with coefficients from a field F, is it easier to compute f over an extension ring R than over F? We address this question, and show the following. For every polynomial f , there is a noncommutative extension ring R such that F i
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::d79ff35e847fabe9d14d9382334dd69f
https://doi.org/10.4086/toc.2011.v007a008
https://doi.org/10.4086/toc.2011.v007a008
Autor:
Pavel Hrubeš
Publikováno v:
J. Symbolic Logic 72, iss. 3 (2007), 941-958
We give an exponential lower bound on number of proof-lines in the proof system K of modal logic, i.e., we give an example of K-tautologies ψ1, ψ2, … s.t. every K-proof of ψi must have a number of proof-lines exponential in terms of the size of
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::712133bac255c5ec38435dc986cfabef
https://doi.org/10.2178/jsl/1191333849
https://doi.org/10.2178/jsl/1191333849
Autor:
Pavel Hrubeš
Publikováno v:
Annals of Pure and Applied Logic. 146(1):72-90
We give an exponential lower bound on the number of proof-lines in intuitionistic propositional logic, I L , axiomatised in the usual Frege-style fashion; i.e., we give an example of I L -tautologies A 1 , A 2 , … s.t. every I L -proof of A i must
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::893676496c5ac813cfce296a4e6217cd