1 citations · 1 across the 4 of their papers we have counts for
4 papers · 1 filter
Black-Box PWPP Is Not Turing-Closed
Pavel Hubáček
We establish that adaptive collision-finding queries are strictly more powerful than non-adaptive ones by proving that the complexity class PWPP (Polynomial Weak Pigeonhole Princip…
PPP-Completeness and Extremal Combinatorics
Romain Bourneuf, Lukáš Folwarczný, Pavel Hubáček +2
Many classical theorems in combinatorics establish the emergence of substructures within sufficiently large collections of objects. Well-known examples are Ramsey's theorem on mono…
On Search Complexity of Discrete Logarithm
Pavel Hubáček, Jan Václavek
In this work, we study the discrete logarithm problem in the context of TFNP - the complexity class of search problems with a syntactically guaranteed existence of a solution for a…
ARRIVAL: Next Stop in CLS
Bernd Gärtner, Thomas Dueholm Hansen, Pavel Hubáček +3
We study the computational complexity of ARRIVAL, a zero-player game on -vertex switch graphs introduced by Dohrau, Gärtner, Kohler, Matoušek, and Welzl. They showed that the pr…