Kartal Nagy

dblp:358/2829 · DBLP profile ↗
← Back
2ranked-venue papers
0as first author
2since 2021 · last 2026
0000-0002-9504-7551ORCID · corroborated

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 2 · 2 since 2021
YearPublicationVenuePosition
2026 Finding the diameter of a tree with distance queries
Dániel Gerbner, András Imolay, Kartal Nagy, Balázs Patkós, Kristóf Zólomy
Discret. Appl. Math.3
2025 Query complexity of Boolean functions on the middle slice of the cube
abstract
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 compute its value, even if we know beforehand that the number of 0’s and 1’s in the input are the same, i.e., when our input is from the middle slice. This answers a question of Byramji. Our proof is non-constructive, but we also propose a concrete candidate function that might have the above property. Our results are related to certain natural discrepancy type questions that, somewhat surprisingly, have not been studied before.
Dániel Gerbner, Balázs Keszegh, Dániel T. Nagy, Kartal Nagy, Dömötör Pálvölgyi, Balázs Patkós, Gábor Wiener
Discret. Appl. Math.4