66 citations · 66 across the 6 of their papers we have counts for
10 papers
Query complexity of Boolean functions on the middle slice of the cube
Dániel Gerbner, Balázs Keszegh, Dániel T. Nagy +4
We study the query complexity on slices of Boolean functions. Among other results we show that there exists a Boolean function for which we need to query all but 7 input bits to co…
Cooperation in Combinatorial Search
Dániel Gerbner, Balázs Keszegh, Kartal Nagy +2
In the game theoretical approach of the basic problem in Combinatorial Search an adversary thinks of a defective element of an -element pool , and the questioner needs to…
On graphs that contain exactly k copies of a subgraph, and a related problem in search theory
Dániel Gerbner, Balázs Keszegh, Dániel Lenger +5
We study , the largest number of edges in an -vertex graph that contains exactly copies of a given subgraph . The case is the Turán number…
Adaptive Majority Problems for Restricted Query Graphs and for Weighted Sets
Gábor Damásdi, Dániel Gerbner, Gyula O. H. Katona +8
Suppose that the vertices of a graph are colored with two colors in an unknown way. The color that occurs on more than half of the vertices is called the majority color (if it…
On the minimum leaf number of cubic graphs
Jan Goedgebeur, Kenta Ozeki, Nico Van Cleemput +1
The \emph{minimum leaf number} of a connected graph is defined as the minimum number of leaves of the spanning trees of . We present new results concerning t…
Finding a non-minority ball with majority answers
Dániel Gerbner, Balázs Keszegh, Dömötör Pálvölgyi +3
Suppose we are given a set of balls each colored either red or blue in some way unknown to us. To find out some information about the colors, we can query…
Search for the end of a path in the d-dimensional grid and in other graphs
Dániel Gerbner, Balázs Keszegh, Dömötör Pálvölgyi +2
We consider the worst-case query complexity of some variants of certain \cl{PPAD}-complete search problems. Suppose we are given a graph and a vertex . We denote th…
Density-based group testing
Dániel Gerbner, Balázs Keszegh, Dömötör Pálvölgyi +1
In this paper we study a new, generalized version of the well-known group testing problem. In the classical model of group testing we are given n objects, some of which are conside…
Computing Majority with Triple Queries
Gianluca De Marco, Evangelos Kranakis, Gabor Wiener
Consider a bin containing balls colored with two colors. In a -query, balls are selected by a questioner and the oracle's reply is related (depending on the computation…
The ultimate question
Gábor Wiener, Makoto Araya
We present a planar hypohamiltonian graph on 42 vertices and show some consequences.