![](https://dblp1.uni-trier.de/img/logo.ua.320x120.png)
![](https://dblp1.uni-trier.de/img/dropdown.dark.16x16.png)
![](https://dblp1.uni-trier.de/img/peace.dark.16x16.png)
Остановите войну!
for scientists:
![search dblp search dblp](https://dblp1.uni-trier.de/img/search.dark.16x16.png)
![search dblp](https://dblp1.uni-trier.de/img/search.dark.16x16.png)
default search action
Pavel Hrubes
Person information
Refine list
![note](https://dblp1.uni-trier.de/img/note-mark.dark.12x12.png)
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
Journal Articles
- 2023
- [j23]Pavel Hrubes, Navid Talebanfard
:
On the Extension Complexity of Polytopes Separating Subsets of the Boolean Cube. Discret. Comput. Geom. 70(1): 268-278 (2023) - 2020
- [j22]Pavel Hrubes:
On ε-sensitive monotone computations. Comput. Complex. 29(2): 6 (2020) - [j21]Pavel Hrubes:
On the distribution of runners on a circle. Eur. J. Comb. 89: 103137 (2020) - [j20]Pavel Hrubes:
On the Complexity of Computing a Random Boolean Function Over the Reals. Theory Comput. 16: 1-12 (2020) - 2019
- [j19]Shai Ben-David, Pavel Hrubes, Shay Moran, Amir Shpilka
, Amir Yehudayoff
:
Learnability can be undecidable. Nat. Mach. Intell. 1(1): 44-48 (2019) - [j18]Shai Ben-David, Pavel Hrubes, Shay Moran, Amir Shpilka
, Amir Yehudayoff
:
Author Correction: Learnability can be undecidable. Nat. Mach. Intell. 1(2): 121 (2019) - 2018
- [j17]Pavel Hrubes, Pavel Pudlák:
A note on monotone real circuits. Inf. Process. Lett. 131: 15-19 (2018) - 2017
- [j16]Pavel Hrubes:
On Families of Anticommuting Matrices. FLAP 4(10): 3261-3276 (2017) - 2016
- [j15]Pavel Hrubes:
On Hardness of Multilinearization and VNP-Completeness in Characteristic 2. ACM Trans. Comput. Theory 9(1): 1:1-1:14 (2016) - 2015
- [j14]Veronika Vlcková, Pavel Hrubes:
Dopravní nehoda, systémový model a shluková analýza v prostředí GIS. Acta Informatica Pragensia 4(1): 64-79 (2015) - [j13]Pavel Hrubes, Iddo Tzameret:
Short Proofs for the Determinant Identities. SIAM J. Comput. 44(2): 340-383 (2015) - [j12]Pavel Hrubes, Avi Wigderson:
Non-Commutative Arithmetic Circuits with Division. Theory Comput. 11: 357-393 (2015) - 2013
- [j11]Pavel Hrubes:
On the Real τ-Conjecture and the Distribution of Complex Roots. Theory Comput. 9: 403-411 (2013) - 2012
- [j10]Pavel Hrubes:
On the nonnegative rank of distance matrices. Inf. Process. Lett. 112(11): 457-461 (2012) - 2011
- [j9]Pavel Hrubes, Amir Yehudayoff:
Homogeneous Formulas and Symmetric Polynomials. Comput. Complex. 20(3): 559-578 (2011) - [j8]Pavel Hrubes, Amir Yehudayoff:
Arithmetic Complexity in Ring Extensions. Theory Comput. 7(1): 119-129 (2011) - 2010
- [j7]Pavel Hrubes, Stasys Jukna
, Alexander S. Kulikov
, Pavel Pudlák:
On convex complexity measures. Theor. Comput. Sci. 411(16-18): 1842-1854 (2010) - 2009
- [j6]Pavel Hrubes:
On lengths of proofs in non-classical logics. Ann. Pure Appl. Log. 157(2-3): 194-205 (2009) - [j5]Pavel Hrubes, Amir Yehudayoff:
Monotone separations for constant degree polynomials. Inf. Process. Lett. 110(1): 1-3 (2009) - [j4]Pavel Hrubes:
Kreisel's Conjecture with minimality principle. J. Symb. Log. 74(3): 976-988 (2009) - 2007
- [j3]Pavel Hrubes:
A lower bound for intuitionistic logic. Ann. Pure Appl. Log. 146(1): 72-90 (2007) - [j2]Pavel Hrubes:
Theories very close to PA where Kreisel's Conjecture is false. J. Symb. Log. 72(1): 123-137 (2007) - [j1]Pavel Hrubes:
Lower bounds for modal logics. J. Symb. Log. 72(3): 941-958 (2007)
Conference and Workshop Papers
- 2024
- [c21]Pavel Hrubes:
A Subquadratic Upper Bound on Sum-Of-Squares Composition Formulas. CCC 2024: 12:1-12:11 - [c20]Pavel Hrubes:
Hard Submatrices for Non-Negative Rank and Communication Complexity. CCC 2024: 13:1-13:12 - 2023
- [c19]Prerona Chatterjee
, Pavel Hrubes:
New Lower Bounds Against Homogeneous Non-Commutative Circuits. CCC 2023: 13:1-13:10 - 2021
- [c18]Pavel Hrubes, Amir Yehudayoff:
Shadows of Newton Polytopes. CCC 2021: 9:1-9:23 - [c17]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: 417-422 - [c16]Shai Ben-David, Pavel Hrubes, Shay Moran
, Amir Shpilka
, Amir Yehudayoff:
Learnability can be independent of set theory (invited paper). STOC 2021: 11 - 2019
- [c15]Pavel Hrubes, Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao, Amir Yehudayoff:
Lower Bounds on Balancing Sets and Depth-2 Threshold Circuits. ICALP 2019: 72:1-72:14 - 2017
- [c14]Pavel Hrubes, Pavel Pudlák:
Random Formulas, Monotone Circuits, and Interpolation. FOCS 2017: 121-131 - 2016
- [c13]Pavel Hrubes, Amir Yehudayoff:
On Isoperimetric Profiles and Computational Complexity. ICALP 2016: 89:1-89:12 - [c12]Yuval Filmus, Pavel Hrubes, Massimo Lauria
:
Semantic Versus Syntactic Cutting Planes. STACS 2016: 35:1-35:13 - 2015
- [c11]Pavel Hrubes, Anup Rao:
Circuits with Medium Fan-In. CCC 2015: 381-391 - 2014
- [c10]Pavel Hrubes, Avi Wigderson:
Non-commutative arithmetic circuits with division. ITCS 2014: 49-66 - [c9]J. Robin B. Cockett, Pieter J. W. Hofstra, Pavel Hrubes:
Total Maps of Turing Categories. MFPS 2014: 129-146 - 2013
- [c8]Pavel Hrubes, Amir Yehudayoff:
Formulas are Exponentially Stronger than Monotone Circuits in Non-commutative Setting. CCC 2013: 10-14 - 2012
- [c7]Pavel Hrubes, Iddo Tzameret:
Short proofs for the determinant identities. STOC 2012: 193-212 - [c6]J. Robin B. Cockett, Joaquín Díaz-Boïls
, Jonathan Gallagher, Pavel Hrubes:
Timed Sets, Functional Complexity, and Computability. MFPS 2012: 117-137 - 2010
- [c5]Pavel Hrubes, Avi Wigderson, Amir Yehudayoff:
Relationless Completeness and Separations. CCC 2010: 280-290 - [c4]Pavel Hrubes, Avi Wigderson, Amir Yehudayoff:
Non-commutative circuits and the sum-of-squares problem. STOC 2010: 667-676 - 2009
- [c3]Pavel Hrubes, Iddo Tzameret:
The Proof Complexity of Polynomial Identities. CCC 2009: 41-51 - [c2]Pavel Hrubes, Premysl Derbek:
Emission load estimation and modeling in relation to the real input traffic data. EATIS 2009: 14 - 2004
- [c1]Pavel Hrubes, Josef Faber, Mirko Novák:
Analysis of EEG signals during micro-sleeps. SMC (4) 2004: 3775-3780
Informal and Other Publications
- 2024
- [i29]Pavel Hrubes:
Hard submatrices for non-negative rank and communication complexity }. Electron. Colloquium Comput. Complex. TR24 (2024) - [i28]Pavel Hrubes:
A subquadratic upper bound on sum-of-squares compostion formulas. Electron. Colloquium Comput. Complex. TR24 (2024) - [i27]Pavel Hrubes:
A subquadratic upper bound on Hurwitz's problem and related non-commutative polynomials. Electron. Colloquium Comput. Complex. TR24 (2024) - [i26]Pavel Hrubes, Pushkar S. Joglekar:
On read-k projections of the determinant. Electron. Colloquium Comput. Complex. TR24 (2024) - 2023
- [i25]Prerona Chatterjee, Pavel Hrubes:
New Lower Bounds against Homogeneous Non-Commutative Circuits. CoRR abs/2301.01676 (2023) - [i24]Prerona Chatterjee, Pavel Hrubes:
New Lower Bounds against Homogeneous Non-Commutative Circuits. Electron. Colloquium Comput. Complex. TR23 (2023) - 2021
- [i23]Pavel Hrubes, Navid Talebanfard
:
On the extension complexity of polytopes separating subsets of the Boolean cube. CoRR abs/2105.11996 (2021) - 2020
- [i22]Pavel Hrubes, Amir Yehudayoff:
Shadows of Newton polytopes. Electron. Colloquium Comput. Complex. TR20 (2020) - 2019
- [i21]Pavel Hrubes:
On the distribution of runners on a circle. CoRR abs/1906.02511 (2019) - [i20]Pavel Hrubes:
On $\epsilon$-sensitive monotone computations. Electron. Colloquium Comput. Complex. TR19 (2019) - [i19]Pavel Hrubes:
On the complexity of computing a random Boolean function over the reals. Electron. Colloquium Comput. Complex. TR19 (2019) - [i18]Pavel Hrubes, Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao, Amir Yehudayoff:
Lower Bounds on Balancing Sets and Depth-2 Threshold Circuits. Electron. Colloquium Comput. Complex. TR19 (2019) - 2017
- [i17]Shai Ben-David, Pavel Hrubes, Shay Moran, Amir Shpilka, Amir Yehudayoff:
A learning problem that is independent of the set theory ZFC axioms. CoRR abs/1711.05195 (2017) - [i16]Pavel Hrubes, Pavel Pudlák:
Random formulas, monotone circuits, and interpolation. Electron. Colloquium Comput. Complex. TR17 (2017) - [i15]Pavel Hrubes, Pavel Pudlák:
A note on monotone real circuits. Electron. Colloquium Comput. Complex. TR17 (2017) - 2015
- [i14]Pavel Hrubes:
On hardness of multilinearization, and VNP completeness in characteristics two. Electron. Colloquium Comput. Complex. TR15 (2015) - [i13]Pavel Hrubes, Amir Yehudayoff:
On isoperimetric profiles and computational complexity. Electron. Colloquium Comput. Complex. TR15 (2015) - 2014
- [i12]Pavel Hrubes:
On families of anticommuting matrices. CoRR abs/1412.5893 (2014) - [i11]Pavel Hrubes, Anup Rao:
Circuits with Medium Fan-In. Electron. Colloquium Comput. Complex. TR14 (2014) - 2013
- [i10]Pavel Hrubes:
A note on semantic cutting planes. Electron. Colloquium Comput. Complex. TR13 (2013) - 2012
- [i9]Pavel Hrubes:
A note on the real $\tau$-conjecture and the distribution of roots. Electron. Colloquium Comput. Complex. TR12 (2012) - [i8]Pavel Hrubes, Amir Yehudayoff:
Formulas are exponentially stronger than monotone circuits in non-commutative setting. Electron. Colloquium Comput. Complex. TR12 (2012) - 2011
- [i7]Pavel Hrubes, Iddo Tzameret:
Short Proofs for the Determinant Identities. CoRR abs/1112.6265 (2011) - [i6]Pavel Hrubes:
How much commutativity is needed to prove polynomial identities? Electron. Colloquium Comput. Complex. TR11 (2011) - [i5]Pavel Hrubes, Iddo Tzameret:
Short Proofs for the Determinant Identities. Electron. Colloquium Comput. Complex. TR11 (2011) - 2010
- [i4]Pavel Hrubes, Avi Wigderson, Amir Yehudayoff:
Non-commutative circuits and the sum-of-squares problem. Electron. Colloquium Comput. Complex. TR10 (2010) - [i3]Pavel Hrubes, Avi Wigderson, Amir Yehudayoff:
Relationless completeness and separations. Electron. Colloquium Comput. Complex. TR10 (2010) - 2009
- [i2]Pavel Hrubes, Amir Yehudayoff:
Homogeneous formulas and symmetric polynomials. CoRR abs/0907.2621 (2009) - [i1]Pavel Hrubes, Stasys Jukna, Alexander S. Kulikov, Pavel Pudlák:
On convex complexity measures. Electron. Colloquium Comput. Complex. TR09 (2009)
Coauthor Index
![](https://dblp1.uni-trier.de/img/cog.dark.24x24.png)
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from ,
, and
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and
to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from .
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-08-10 01:22 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint