Pavel Hrubeš
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Pavel Hrubeš has a total of 4 co-authors. Here are the top co-authors by number of shared publications:
- Alexander S. Kulikov
Research JetBrains
1 shared publication - Amir Yehudayoff
University of Copenhagen, Copenhagen, Denmark
1 shared publication - Pavel Pudlák
Institute of Mathematics Czech Academy of Sciences
1 shared publication - Stasys Jukna
Faculty of Mathematics and Informatics, Vilnius University
1 shared publication
Latest Publications
- 1 March 2010
- Published by Elsevier in Theoretical Computer Science
- Vol. 411 (16-18) , 1842-1854
On convex complexity measures
- 1 March 2010
- Published by Elsevier in Theoretical Computer Science
- Vol. 411 (16-18) , 1842-1854
On convex complexity measures
- Open Access
Homogeneous formulas and symmetric polynomials
We investigate the arithmetic formula complexity of the elementary symmetric polynomials S(k,n). We show that every multilinear homogeneous formula computing S(k,n) has size at least k^(Omega(log k))n, and that product-depth d multilinear homogeneous formulas for S(k,n) have size at least 2^(Omega(k^{1/d}))n. Since S(n,2n) has a multilinear formula of size O(n^2), we obtain a superpolynomial separation between multilinear and multilinear homogeneous formulas. We also show that S(k,n) can be computed by homogeneous formulas of size k^(O(log k))n, answering a question of Nisan and Wigderson. Finally, we present a superpolynomial separation between monotone and non-monotone formulas in the noncommutative setting, answering a question of Nisan.
Open AccessHomogeneous formulas and symmetric polynomials
We investigate the arithmetic formula complexity of the elementary symmetric polynomials S(k,n). We show that every multilinear homogeneous formula computing S(k,n) has size at least k^(Omega(log k))n, and that product-depth d multilinear homogeneous formulas for S(k,n) have size at least 2^(Omega(k^{1/d}))n. Since S(n,2n) has a multilinear formula of size O(n^2), we obtain a superpolynomial separation between multilinear and multilinear homogeneous formulas. We also show that S(k,n) can be computed by homogeneous formulas of size k^(O(log k))n, answering a question of Nisan and Wigderson. Finally, we present a superpolynomial separation between monotone and non-monotone formulas in the noncommutative setting, answering a question of Nisan.
- 1 September 2007
- Published by Cambridge University Press (CUP) in The Journal of Symbolic Logic
- Vol. 72 (3) , 941-958
Lower bounds for modal logics
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 ψi. The result extends, for the same sequence of K-tautologies, to the systems K4, Gödel–Löb's logic, S andS4. We also determine some speed-up relations between different systems of modal logic on formulas of modal-depth one.
- 1 September 2007
- Published by Cambridge University Press (CUP) in The Journal of Symbolic Logic
- Vol. 72 (3) , 941-958
Lower bounds for modal logics
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 ψi. The result extends, for the same sequence of K-tautologies, to the systems K4, Gödel–Löb's logic, S andS4. We also determine some speed-up relations between different systems of modal logic on formulas of modal-depth one.
- 12 March 2007
- Published by Cambridge University Press (CUP) in The Journal of Symbolic Logic
- Vol. 72 (1) , 123-137
Theories very close to PA where Kreisel's Conjecture is false
We give four examples of theories in which Kreisel's Conjecture is false: (1) the theory PA(-) obtained by adding a function symbol minus, ‘—’, to the language of PA, and the axiom ∀x∀y∀z (x − y = z) ≡ (x = y + z ∨ (x < y ∧ z = 0)); (2) the theory L of integers; (3) the theory PA(q) obtained by adding a function symbol q (of arity ≥ 1) to PA, assuming nothing about q; (4) the theory PA(N) containing a unary predicate N(x) meaning ‘x is a natural number’. In Section 6 we suggest a counterexample to the so called Sharpened Kreisel's Conjecture.
- 12 March 2007
- Published by Cambridge University Press (CUP) in The Journal of Symbolic Logic
- Vol. 72 (1) , 123-137
Theories very close to PA where Kreisel's Conjecture is false
We give four examples of theories in which Kreisel's Conjecture is false: (1) the theory PA(-) obtained by adding a function symbol minus, ‘—’, to the language of PA, and the axiom ∀x∀y∀z (x − y = z) ≡ (x = y + z ∨ (x < y ∧ z = 0)); (2) the theory L of integers; (3) the theory PA(q) obtained by adding a function symbol q (of arity ≥ 1) to PA, assuming nothing about q; (4) the theory PA(N) containing a unary predicate N(x) meaning ‘x is a natural number’. In Section 6 we suggest a counterexample to the so called Sharpened Kreisel's Conjecture.