Pavel Hrubes

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