Endre Csóka

Endre Csóka, Łukasz Grabowski, András Máthé et al.

We study a variant of the parallel Moser-Tardos Algorithm. We prove that if we restrict attention to a class of problems whose dependency graphs have subexponential growth, then the expected total number of random bits used by the algorithm is constant; in particular, it is independent from the number of variables. This is achieved by using the same random bits to resample variables which are far enough in the dependency graph. There are two corollaries. First, we obtain a deterministic algorithm for finding a satisfying assignment, which for any class of problems as in the previous paragraph runs in time O(n), where n is the number of variables. Second, we present a Borel version of the Lovász Local Lemma.

Domonkos Czifra, Endre Csóka, Zsolt Zombori et al.

Our paper explores the game theoretic value of the 7-in-a-row game. We reduce the problem to solving a finite board game, which we target using Proof Number Search. We present a number of heuristic improvements to Proof Number Search and examine their effect within the context of this particular game. Although our paper does not solve the 7-in-a-row game, our experiments indicate that we have made significant progress towards it.

Endre Csóka

We have a large number of samples and we want to find the infected ones using as few number of tests as possible. We can use group testing which tells about a small group of people whether at least one of them is infected. Group testing is particularly efficient if the infection rate is low. The goal of this article is to summarize and extend the mathematical knowledge about the most efficient group testing algorithms, focusing on real-life applications instead of pure mathematical motivations and approaches.

Endre Csóka

We present different versions of a conjecture which would express that first price mechanisms never work very badly in a very general class of problems. The definitions include most of the problems where there is a principal (seller) who has the right to exclude others from the game. The exact definitions are motivated by the "first price mechanism" in E Cs: "Efficient Teamwork", but the conjecture is relevant for most auction problems, e.g. for combinatorial auctions.