Pavel Hrubes

According to our database, Pavel Hrubes authored at least 52 papers between 2004 and 2025.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2025

On Read-k Projections of the Determinant.

Pavel Hrubes, Pushkar S. Joglekar

Proceedings of the 42nd International Symposium on Theoretical Aspects of Computer Science, 2025

2024

On read-<i>k</i> projections of the determinant.

Pavel Hrubes, Pushkar S. Joglekar

Electron. Colloquium Comput. Complex., 2024

A subquadratic upper bound on Hurwitz's problem and related non-commutative polynomials.

Pavel Hrubes

Electron. Colloquium Comput. Complex., 2024

A subquadratic upper bound on sum-of-squares compostion formulas.

Pavel Hrubes

Electron. Colloquium Comput. Complex., 2024

Hard Submatrices for Non-Negative Rank and Communication Complexity.

Pavel Hrubes

Proceedings of the 39th Computational Complexity Conference, 2024

A Subquadratic Upper Bound on Sum-Of-Squares Composition Formulas.

Pavel Hrubes

Proceedings of the 39th Computational Complexity Conference, 2024

2023

On the Extension Complexity of Polytopes Separating Subsets of the Boolean Cube.

Pavel Hrubes, Navid Talebanfard

Discret. Comput. Geom., July, 2023

New Lower Bounds Against Homogeneous Non-Commutative Circuits.

Prerona Chatterjee, Pavel Hrubes

Proceedings of the 38th Computational Complexity Conference, 2023

2021

Learnability can be independent of set theory (invited paper).

Shai Ben-David, Pavel Hrubes, Shay Moran, Amir Shpilka, Amir Yehudayoff

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

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.

Zuzana Purkrabkova, Pavel Hrubes

Proceedings of the ICIT 2021: IoT and Smart City, Guangzhou, China, December 22 - 25, 2021, 2021

Shadows of Newton Polytopes.

Pavel Hrubes, Amir Yehudayoff

Proceedings of the 36th Computational Complexity Conference, 2021

2020

On the distribution of runners on a circle.

Pavel Hrubes

Eur. J. Comb., 2020

On ε-sensitive monotone computations.

Pavel Hrubes

Comput. Complex., 2020

2019

Author Correction: Learnability can be undecidable.

Shai Ben-David, Pavel Hrubes, Shay Moran, Amir Shpilka, Amir Yehudayoff

Nat. Mach. Intell., 2019

Learnability can be undecidable.

Shai Ben-David, Pavel Hrubes, Shay Moran, Amir Shpilka, Amir Yehudayoff

Nat. Mach. Intell., 2019

On the complexity of computing a random Boolean function over the reals.

Pavel Hrubes

Electron. Colloquium Comput. Complex., 2019

On $\epsilon$-sensitive monotone computations.

Pavel Hrubes

Electron. Colloquium Comput. Complex., 2019

Lower Bounds on Balancing Sets and Depth-2 Threshold Circuits.

Pavel Hrubes, Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao, Amir Yehudayoff

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

2017

On Families of Anticommuting Matrices.

Pavel Hrubes

FLAP, 2017

A note on monotone real circuits.

Pavel Hrubes, Pavel Pudlák

Electron. Colloquium Comput. Complex., 2017

A learning problem that is independent of the set theory ZFC axioms.

Shai Ben-David, Pavel Hrubes, Shay Moran, Amir Shpilka, Amir Yehudayoff

CoRR, 2017

Random Formulas, Monotone Circuits, and Interpolation.

Pavel Hrubes, Pavel Pudlák

Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

2016

On Hardness of Multilinearization and VNP-Completeness in Characteristic 2.

Pavel Hrubes

ACM Trans. Comput. Theory, 2016

Semantic Versus Syntactic Cutting Planes.

Yuval Filmus, Pavel Hrubes, Massimo Lauria

Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science, 2016

On Isoperimetric Profiles and Computational Complexity.

Pavel Hrubes, Amir Yehudayoff

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

2015

On hardness of multilinearization, and VNP completeness in characteristics two.

Pavel Hrubes

Electron. Colloquium Comput. Complex., 2015

Dopravní nehoda, systémový model a shluková analýza v prostředí GIS.

Veronika Vlcková, Pavel Hrubes

Acta Informatica Pragensia, 2015

Circuits with Medium Fan-In.

Pavel Hrubes, Anup Rao

Proceedings of the 30th Conference on Computational Complexity, 2015

2014

Total Maps of Turing Categories.

J. Robin B. Cockett, Pieter J. W. Hofstra, Pavel Hrubes

Proceedings of the 30th Conference on the Mathematical Foundations of Programming Semantics, 2014

Non-commutative arithmetic circuits with division.

Pavel Hrubes, Avi Wigderson

Proceedings of the Innovations in Theoretical Computer Science, 2014

2013

On the Real τ-Conjecture and the Distribution of Complex Roots.

Pavel Hrubes

Theory Comput., 2013

A note on semantic cutting planes.

Pavel Hrubes

Electron. Colloquium Comput. Complex., 2013

Formulas are Exponentially Stronger than Monotone Circuits in Non-commutative Setting.

Pavel Hrubes, Amir Yehudayoff

Proceedings of the 28th Conference on Computational Complexity, 2013

2012

On the nonnegative rank of distance matrices.

Pavel Hrubes

Inf. Process. Lett., 2012

Timed Sets, Functional Complexity, and Computability.

J. Robin B. Cockett, Joaquín Díaz-Boïls, Jonathan Gallagher, Pavel Hrubes

Proceedings of the 28th Conference on the Mathematical Foundations of Programming Semantics, 2012

A note on the real $\tau$-conjecture and the distribution of roots.

Pavel Hrubes

Electron. Colloquium Comput. Complex., 2012

Short proofs for the determinant identities.

Pavel Hrubes, Iddo Tzameret

Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

2011

Arithmetic Complexity in Ring Extensions.

Pavel Hrubes, Amir Yehudayoff

Theory Comput., 2011

How much commutativity is needed to prove polynomial identities?

Pavel Hrubes

Electron. Colloquium Comput. Complex., 2011

Homogeneous Formulas and Symmetric Polynomials.

Pavel Hrubes, Amir Yehudayoff

Comput. Complex., 2011

2010

Non-commutative circuits and the sum-of-squares problem.

Pavel Hrubes, Avi Wigderson, Amir Yehudayoff

Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

Relationless Completeness and Separations.

Pavel Hrubes, Avi Wigderson, Amir Yehudayoff

Proceedings of the 25th Annual IEEE Conference on Computational Complexity, 2010

2009

Kreisel's Conjecture with minimality principle.

Pavel Hrubes

J. Symb. Log., 2009

Monotone separations for constant degree polynomials.

Pavel Hrubes, Amir Yehudayoff

Inf. Process. Lett., 2009

On convex complexity measures.

Pavel Hrubes, Stasys Jukna, Alexander S. Kulikov, Pavel Pudlák

Electron. Colloquium Comput. Complex., 2009

On lengths of proofs in non-classical logics.

Pavel Hrubes

Ann. Pure Appl. Log., 2009

Emission load estimation and modeling in relation to the real input traffic data.

Pavel Hrubes, Premysl Derbek

Proceedings of the 2009 Euro American conference on Telematics and Information Systems: New Opportunities to increase Digital Citizenship, 2009

The Proof Complexity of Polynomial Identities.

Pavel Hrubes, Iddo Tzameret

Proceedings of the 24th Annual IEEE Conference on Computational Complexity, 2009

2007

Lower bounds for modal logics.

Pavel Hrubes

J. Symb. Log., 2007

Theories very close to <i>PA</i> where Kreisel's Conjecture is false.

Pavel Hrubes

J. Symb. Log., 2007

A lower bound for intuitionistic logic.

Pavel Hrubes

Ann. Pure Appl. Log., 2007

2004

Analysis of EEG signals during micro-sleeps.

Pavel Hrubes, Josef Faber, Mirko Novák

Proceedings of the IEEE International Conference on Systems, 2004