The Symposium on Discrete Algorithms (SODA) is sponsored by the SIAM Activity Group on Discrete Mathematics and the ACM Special Interest Group on Algorithms and Computation Theory. The symposium focuses on research topics related to design and analysis of efficient algorithms and data structures for discrete problems. It is a highly selective conference with an average acceptance rate of around 31.6%. This success follows the Foundations of Computer Science research group's previous acceptances at two other prestigious conferences: STOC and FOCS.
This research led by Dr Maksim Zhukovski investigates labeling schemes for graph structures, which involve assigning unique codes to vertices for reconstructing vertex connections. It particularly focuses on hereditary graph classes, those resilient to changes upon vertex removal.
Recent research, by Hatami and Hatami, has disproved the ‘Implicit Graph Conjecture’ - which suggests that graphs from small hereditary classes could always be labeled in a very efficient way.
In the paper submitted by Maksim and his team they proved that the conjecture is false even in a stronger form: They found much smaller hereditary classes that cannot be efficiently labeled with short codes.
Maksim said “I am delighted our paper has been accepted to this prestigious conference. Our research - the discovery of tiny hereditary classes not admitting efficient labeling schemes - is important because it shows strong limitations for encoding adjacencies in a local fashion. .”
You can read the preprint here: https://arxiv.org/pdf/2307.11225.pdf