Takumi Araya

dblp:393/0417 · DBLP profile ↗
← Back
2ranked-venue papers
2as first author
2since 2021 · last 2026
—ORCID · none

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

Theory of computation · 2 · 2 first-author · 2 since 2021
YearPublicationVenuePosition
2026 Sublinear-time collision detection in population protocols with polynomially many states
abstract
This paper addresses the collision detection problem in population protocols. The network consists of state machines called agents. At each time step, exactly one pair of agents is chosen uniformly at random to interact, updating their states. The collision detection problem assumes that each agent starts with an input integer between 1 and n , where n is the number of agents, and requires the agents to determine whether there are any duplicate input values among them. Specifically, the goal is for all agents to output false if all input values are distinct, and true otherwise. This paper presents an algorithm that solves this problem in sublinear parallel time, both with high probability and in expectation, using only a polynomial number of states, thereby answering one of the open questions raised by Burman, Chen, Chen, Doty, Nowak, Severson, and Xu [PODC 2021].
Takumi Araya, Yuichi Sudo
Theor. Comput. Sci.1
2025 Sublinear-Time Collision Detection with a Polynomial Number of States in Population Protocols
Takumi Araya, Yuichi Sudo
SIROCCO1