Pavel Hrubes

Publication Activity (10 Years)

Years Active: 2004-2024
Publications (10 Years): 34

Top Topics

Boolean Functions

Pac Learnability

Computational Load

Top Venues

Electron. Colloquium Comput. Complex.

Publications

Pavel Hrubes
Hard Submatrices for Non-Negative Rank and Communication Complexity. CCC (2024)
Pavel Hrubes
A subquadratic upper bound on Hurwitz's problem and related non-commutative polynomials. Electron. Colloquium Comput. Complex. (2024)
Pavel Hrubes
Hard submatrices for non-negative rank and communication complexity }. Electron. Colloquium Comput. Complex. (2024)
Pavel Hrubes
A Subquadratic Upper Bound on Sum-Of-Squares Composition Formulas. CCC (2024)
Pavel Hrubes, Pushkar S. Joglekar
projections of the determinant. Electron. Colloquium Comput. Complex. (2024)
Pavel Hrubes
A subquadratic upper bound on sum-of-squares compostion formulas. Electron. Colloquium Comput. Complex. (2024)
Pavel Hrubes, Navid Talebanfard
On the Extension Complexity of Polytopes Separating Subsets of the Boolean Cube. Discret. Comput. Geom. 70 (1) (2023)
Prerona Chatterjee, Pavel Hrubes
New Lower Bounds Against Homogeneous Non-Commutative Circuits. CCC (2023)
Prerona Chatterjee, Pavel Hrubes
New Lower Bounds against Homogeneous Non-Commutative Circuits. CoRR (2023)
Prerona Chatterjee, Pavel Hrubes
New Lower Bounds against Homogeneous Non-Commutative Circuits. Electron. Colloquium Comput. Complex. (2023)
Shai Ben-David, Pavel Hrubes, Shay Moran, Amir Shpilka, Amir Yehudayoff
Learnability can be independent of set theory (invited paper). STOC (2021)
Pavel Hrubes, Amir Yehudayoff
Shadows of Newton Polytopes. Computational Complexity Conference (2021)
Zuzana Purkrabkova, Pavel Hrubes
The possibility of using floating car data to monitor the occurrence of accidents: Initial analysis and results to verify whether it is possible to monitor the occurrence of accidents on the newly accessible data source. ICIT (2021)
Pavel Hrubes, Navid Talebanfard
On the extension complexity of polytopes separating subsets of the Boolean cube. CoRR (2021)
Pavel Hrubes
On ε-sensitive monotone computations. Comput. Complex. 29 (2) (2020)
Pavel Hrubes, Amir Yehudayoff
Shadows of Newton polytopes. Electron. Colloquium Comput. Complex. 27 (2020)
Pavel Hrubes
On the Complexity of Computing a Random Boolean Function Over the Reals. Theory Comput. 16 (2020)
Pavel Hrubes
On the distribution of runners on a circle. Eur. J. Comb. 89 (2020)
Shai Ben-David, Pavel Hrubes, Shay Moran, Amir Shpilka, Amir Yehudayoff
Learnability can be undecidable. Nat. Mach. Intell. 1 (1) (2019)
Shai Ben-David, Pavel Hrubes, Shay Moran, Amir Shpilka, Amir Yehudayoff
Author Correction: Learnability can be undecidable. Nat. Mach. Intell. 1 (2) (2019)
Pavel Hrubes, Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao, Amir Yehudayoff
Lower Bounds on Balancing Sets and Depth-2 Threshold Circuits. ICALP (2019)
Pavel Hrubes
On $\epsilon$-sensitive monotone computations. Electron. Colloquium Comput. Complex. 26 (2019)
Pavel Hrubes
On the distribution of runners on a circle. CoRR (2019)
Pavel Hrubes
On the complexity of computing a random Boolean function over the reals. Electron. Colloquium Comput. Complex. 26 (2019)
Pavel Hrubes, Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao, Amir Yehudayoff
Lower Bounds on Balancing Sets and Depth-2 Threshold Circuits. Electron. Colloquium Comput. Complex. 26 (2019)
Pavel Hrubes, Pavel Pudlák
A note on monotone real circuits. Inf. Process. Lett. 131 (2018)
Pavel Hrubes, Pavel Pudlák
Random Formulas, Monotone Circuits, and Interpolation. FOCS (2017)
Pavel Hrubes, Pavel Pudlák
A note on monotone real circuits. Electron. Colloquium Comput. Complex. 24 (2017)
Pavel Hrubes, Pavel Pudlák
Random formulas, monotone circuits, and interpolation. Electron. Colloquium Comput. Complex. 24 (2017)
Pavel Hrubes
On Families of Anticommuting Matrices. FLAP 4 (10) (2017)
Shai Ben-David, Pavel Hrubes, Shay Moran, Amir Shpilka, Amir Yehudayoff
A learning problem that is independent of the set theory ZFC axioms. CoRR (2017)
Yuval Filmus, Pavel Hrubes, Massimo Lauria
Semantic Versus Syntactic Cutting Planes. STACS (2016)
Pavel Hrubes
On Hardness of Multilinearization and VNP-Completeness in Characteristic 2. ACM Trans. Comput. Theory 9 (1) (2016)
Pavel Hrubes, Amir Yehudayoff
On Isoperimetric Profiles and Computational Complexity. ICALP (2016)
Pavel Hrubes, Anup Rao
Circuits with Medium Fan-In. Computational Complexity Conference (2015)
Pavel Hrubes, Amir Yehudayoff
On isoperimetric profiles and computational complexity. Electron. Colloquium Comput. Complex. 22 (2015)
Pavel Hrubes, Iddo Tzameret
Short Proofs for the Determinant Identities. SIAM J. Comput. 44 (2) (2015)
Pavel Hrubes, Avi Wigderson
Non-Commutative Arithmetic Circuits with Division. Theory Comput. 11 (2015)
Pavel Hrubes
On hardness of multilinearization, and VNP completeness in characteristics two. Electron. Colloquium Comput. Complex. 22 (2015)
Veronika Vlcková, Pavel Hrubes
Dopravní nehoda, systémový model a shluková analýza v prostředí GIS. Acta Informatica Pragensia 4 (1) (2015)
Pavel Hrubes
On families of anticommuting matrices. CoRR (2014)
J. Robin B. Cockett, Pieter J. W. Hofstra, Pavel Hrubes
Total Maps of Turing Categories. MFPS (2014)
Pavel Hrubes, Anup Rao
Circuits with Medium Fan-In. Electron. Colloquium Comput. Complex. 21 (2014)
Pavel Hrubes, Avi Wigderson
Non-commutative arithmetic circuits with division. ITCS (2014)
Pavel Hrubes
On the Real τ-Conjecture and the Distribution of Complex Roots. Theory Comput. 9 (2013)
Pavel Hrubes
A note on semantic cutting planes. Electron. Colloquium Comput. Complex. 20 (2013)
Pavel Hrubes, Amir Yehudayoff
Formulas are Exponentially Stronger than Monotone Circuits in Non-commutative Setting. Computational Complexity Conference (2013)
J. Robin B. Cockett, Joaquín Díaz-Boïls, Jonathan Gallagher, Pavel Hrubes
Timed Sets, Functional Complexity, and Computability. MFPS (2012)
Pavel Hrubes, Amir Yehudayoff
Formulas are exponentially stronger than monotone circuits in non-commutative setting. Electron. Colloquium Comput. Complex. 19 (2012)
Pavel Hrubes
A note on the real $\tau$-conjecture and the distribution of roots. Electron. Colloquium Comput. Complex. 19 (2012)
Pavel Hrubes
On the nonnegative rank of distance matrices. Inf. Process. Lett. 112 (11) (2012)
Pavel Hrubes, Iddo Tzameret
Short proofs for the determinant identities. STOC (2012)
Pavel Hrubes
How much commutativity is needed to prove polynomial identities? Electron. Colloquium Comput. Complex. 18 (2011)
Pavel Hrubes, Amir Yehudayoff
Arithmetic Complexity in Ring Extensions. Theory Comput. 7 (1) (2011)
Pavel Hrubes, Iddo Tzameret
Short Proofs for the Determinant Identities. Electron. Colloquium Comput. Complex. 18 (2011)
Pavel Hrubes, Iddo Tzameret
Short Proofs for the Determinant Identities CoRR (2011)
Pavel Hrubes, Amir Yehudayoff
Homogeneous Formulas and Symmetric Polynomials. Comput. Complex. 20 (3) (2011)
Pavel Hrubes, Stasys Jukna, Alexander S. Kulikov, Pavel Pudlák
On convex complexity measures. Theor. Comput. Sci. 411 (16-18) (2010)
Pavel Hrubes, Avi Wigderson, Amir Yehudayoff
Non-commutative circuits and the sum-of-squares problem. STOC (2010)
Pavel Hrubes, Avi Wigderson, Amir Yehudayoff
Relationless Completeness and Separations. Computational Complexity Conference (2010)
Pavel Hrubes, Avi Wigderson, Amir Yehudayoff
Relationless completeness and separations. Electron. Colloquium Comput. Complex. 17 (2010)
Pavel Hrubes, Avi Wigderson, Amir Yehudayoff
Non-commutative circuits and the sum-of-squares problem. Electron. Colloquium Comput. Complex. 17 (2010)
Pavel Hrubes, Iddo Tzameret
The Proof Complexity of Polynomial Identities. Computational Complexity Conference (2009)
Pavel Hrubes
On lengths of proofs in non-classical logics. Ann. Pure Appl. Log. 157 (2-3) (2009)
Pavel Hrubes, Stasys Jukna, Alexander S. Kulikov, Pavel Pudlák
On convex complexity measures. Electron. Colloquium Comput. Complex. 16 (2009)
Pavel Hrubes, Premysl Derbek
Emission load estimation and modeling in relation to the real input traffic data. EATIS (2009)
Pavel Hrubes
Kreisel's Conjecture with minimality principle. J. Symb. Log. 74 (3) (2009)
Pavel Hrubes, Amir Yehudayoff
Monotone separations for constant degree polynomials. Inf. Process. Lett. 110 (1) (2009)
Pavel Hrubes, Amir Yehudayoff
Homogeneous formulas and symmetric polynomials CoRR (2009)
Pavel Hrubes
Lower bounds for modal logics. J. Symb. Log. 72 (3) (2007)
Pavel Hrubes
A lower bound for intuitionistic logic. Ann. Pure Appl. Log. 146 (1) (2007)
Pavel Hrubes
where Kreisel's Conjecture is false. J. Symb. Log. 72 (1) (2007)
Pavel Hrubes, Josef Faber, Mirko Novák
Analysis of EEG signals during micro-sleeps. SMC (4) (2004)