3 citations · 5 across the 5 of their papers we have counts for
6 papers
On the extension complexity of polytopes separating subsets of the Boolean cube
Pavel Hrubeš, Navid Talebanfard
We show that 1. for every , there exists a polytope with and extension complexity , 2. there ex…
On the distribution of runners on a circle
Pavel Hrubes
Consider runners running on a circular track of unit length with constant speeds such that of the speeds are distinct. We show that, at some time, there will exist a sector…
A learning problem that is independent of the set theory ZFC axioms
Shai Ben-David, Pavel Hrubes, Shay Moran +2
We consider the following statistical estimation problem: given a family F of real valued functions over some domain X and an i.i.d. sample drawn from an unknown distribution P ove…
Short Proofs for the Determinant Identities
Pavel Hrubes, Iddo Tzameret
We study arithmetic proof systems P_c(F) and P_f(F) operating with arithmetic circuits and arithmetic formulas, respectively, that prove polynomial identities over a field F. We es…
Homogeneous formulas and symmetric polynomials
Pavel Hrubes, Amir Yehudayoff
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 lea…
On hierarchies of universal predicates
Pavel Hrubes
We investigate a hierarchy of arithmetical structures obtained by a transfinite addition of a canonic universal predicate, where the canonic universal predicate for M is defined as…