8 papers
From the Social Choice Problem to a Collusion-Proof Tendering Mechanism for Dynamic Stochastic Projects
Endre Csóka
The VCG family and the AGV mechanism are two classical approaches to efficient implementation in the static social choice problem. In 2024, Csóka et al. showed that AGV has critica…
Quantitative indistinguishability and sparse and dense clusters in factor of IID percolations
Endre Csóka, Péter Mester, Gábor Pete
Chifan-Ioana (2010) implies that, for any factor of IID percolation on any nonamenable Cayley graph , there is a countable set of (strong) indistinguishability classes for non-h…
Prior-free Collusion-proof Dynamic Mechanisms
Endre Csóka
For a general class of dynamic stochastic multi-player problems, Csóka, Liu, Rodivilov, and Teytelboym (2024) proposed prior-dependent efficient collusion-proof mechanisms. The pre…
Bisection width, max-cut and internal partitions of 5-regular graphs
Endre Csóka, Panna Tímea Fekete, Zoltán Lóránt Nagy +1
In this paper, we present a new factor of IID process based on the local algorithm introduced by Díaz, Serna, and Wormald (2007). This new approach allows us to improve the previou…
FIID homomorphisms and entropy inequalities
Endre Csoka, Zoltan Vidnyanszky
We investigate the existence of FIID homomorphisms from regular trees to finite graphs. Using entropy inequalities we show that there are graphs with arbitrarily large chromatic nu…
Block partitions in higher dimensions
Endre Csóka
Consider a set which is 1-dense, namely, it intersects every unit ball. We show that we can get from any point to any other point in in …
Finding cliques and dense subgraphs using edge queries
Endre Csóka, András Pongrácz
We consider the problem of finding a large clique in an Erdős--Rényi random graph where we are allowed unbounded computational time but can only query a limited number of edges. Re…
Local algorithms for the maximum flow and minimum cut in bounded-degree networks
Endre Csóka, András Pongrácz
We show a deterministic constant-time local algorithm for constructing an approximately maximum flow and minimum fractional cut in multisource-multitarget networks with bounded deg…