Marcin Kardas, Piotr Czapla, Pontus Stenetorp, Sebastian Ruder, Sebastian Riedel, Ross Taylor, Robert Stojnic. Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP). 2020.

Julian Eisenschlos, Sebastian Ruder, Piotr Czapla, Marcin Kadras, Sylvain Gugger, Jeremy Howard. Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP). 2019.

Recently, the need for efficient representations of data conveyed by graphical structures has emerged in many different contexts. While compressing such data one must consider two types of information. The first type is the information carried by the labels embedded in the structure. The second type is the information conveyed by the structure itself. In this extended abstract we address the latter type, namely we study the information carried by the structure of Uniform Random Intersection Graphs (URIGs). Random Intersection Graphs emerge in many scenarios, e.g., they correspond to the topology of many social networks and secure wireless networks, and they are induced in the clusterization process. We analyze algebraic properties of an automorphism group of the underlying structure of URIGs and derive a precise asymptotic formula for their structural entropy for various values of model parameters.

In this paper we investigate leader election protocols for single-hop radio networks from the perspective of energetic complexity. We discuss different models of energy consumption and their impact on time complexity. We also present some results about energy consumption in classic protocols optimal with respect to time complexity - we show that some very basic, intuitive algorithms for simpler model (with known number of stations) do not have to be optimal when energy of stations is restricted. We show that they can be significantly improved by introducing very simple modifications. Our main technical result is however a protocol for solving leader election problem in case of unknown number of stations n, with expected time O(log epsilon n), such that each station transmits O(1) number of times and no station is awake for more than O(log log log n) rounds.

In this paper we consider the problem of listing all active stations in a single hop radio network in such a way that the outer adversary observing communication could not gain any significant information about the real number of stations. We also consider a counterpart of this problem such that only a good approximation of the number of activated stations is needed. This problem is motivated mainly by military applications of sensors networks, however we present how our approach can be extended to other natural problems and similar models. In our paper we present two algorithms for secure listing and size approximation of the set of activated stations. Both of them are fairly practical (in terms of volume of communication, time of execution and computational complexity) and provably secure for the assumed adversarial model.