1 citations · 2 across the 6 of their papers we have counts for
11 papers
Fluctuations of Nonlinear Observables in Mean Field Neural Network Training
Arnaud Descours, Geoffrey Lacour
Mean field limits describe the training dynamics of wide neural networks through the evolution of the empirical distribution of their parameters. Although functional central limit…
Bolzano: Case Studies in LLM-Assisted Mathematical Research
Martin Balko, Jan Grebík, Pavel Hubáček +5
We report new results on eight problems in mathematics and theoretical computer science, produced with the assistance of Bolzano, an open-source multi-agent LLM system. Bolzano orc…
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…
Foundations of Fiat-Denominated Loans Collateralized by Cryptocurrencies
Pavel Hubáček, Jan Václavek, Michelle Yeo
The rising importance of cryptocurrencies as financial assets pushed their applicability from an object of speculation closer to standard financial instruments such as loans. In th…
Must the Communication Graph of MPC Protocols be an Expander?
Elette Boyle, Ran Cohen, Deepesh Data +1
Secure multiparty computation (MPC) on incomplete communication networks has been studied within two primary models: (1) Where a partial network is fixed a priori, and thus corrupt…
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…
Stronger Lower Bounds for Online ORAM
Pavel Hubáček, Michal Koucký, Karel Král +1
Oblivious RAM (ORAM), introduced in the context of software protection by Goldreich and Ostrovsky [JACM'96], aims at obfuscating the memory access pattern induced by a RAM computat…
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…
When Can Limited Randomness Be Used in Repeated Games?
Pavel Hubáček, Moni Naor, Jonathan Ullman
The central result of classical game theory states that every finite normal form game has a Nash equilibrium, provided that players are allowed to use randomized (mixed) strategies…
Cryptographically Blinded Games: Leveraging Players' Limitations for Equilibria and Profit
Pavel Hubáček, Sunoo Park
In this work we apply methods from cryptography to enable any number of mutually distrusting players to implement broad classes of mediated equilibria of strategic games without th…