Paul Spirakis

Georgios Birmpas, Georgios Chionas, Efthyvoulos Drousiotis et al.

We study instant-runoff voting (IRV) under metric preferences induced by an unweighted graph where each vertex hosts a voter, candidates occupy some vertices (with a single candidate allowed in such a vertex), and voters rank candidates by shortest-path distance with fixed deterministic tie-breaking. We focus on exclusion zones, vertex sets S such that whenever some candidate lies in S, the IRV winner must also lie in S. While testing whether a given set S is an exclusion zone is co-NP-Complete and finding the minimum exclusion zone is NP-hard in general graphs, we show here that both problems can be solved in polynomial time on trees. Our approach solves zone testing by designing a Kill membership test (can a designated candidate be forced to lose using opponents from a restricted set?) and shows that Kill can be decided in polynomial time on trees via a bottom-up dynamic program that certifies whether the designated candidate can be eliminated in round 1. A greedy shrinking process then recovers the minimum zone under a standard nesting assumption. To clarify the limits of tractability beyond trees, we also identify a rule level property (Strong Forced Elimination) that abstracts the key IRV behavior used in prior reductions, and show that both exclusion-zone verification and minimum- zone computation remain co-NP-complete and NP-hard, respectively, for any deterministic rank-based elimination rule satisfying this property. Finally, we relate IRV to utilitarian distortion in this discrete setting, and we present upper and lower bounds with regard to the distortion of IRV for several scenarios, including perfect binary trees and unweighted graphs.

Vasiliki Liagkou, Panayotis Nastou, Paul Spirakis et al.

The Panopticon (which means "watcher of everything") is a well-known structure of continuous surveillance and discipline proposed by Bentham in 1785. This device was, later, used by Foucault and other philosophers as a paradigm and metaphor for the study of constitutional power and knowledge as well as a model of individuals' deprivation of freedom. Nowadays, technological achievements have given rise to new, non-physical (unlike prisons), means of constant surveillance that transcend physical boundaries. This, combined with the confession of some governmental institutions that they actually collaborate with these Internet giants to collect or deduce information about people, creates a worrisome situation of several co-existing Panopticons that can act separately or in close collaboration. Thus, they can only be detected and identified through the expense of (perhaps considerable) effort. In this paper we provide a theoretical framework for studying the detectability status of Panopticons that fall under two theoretical, but not unrealistic, definitions. We show, using Oracle Turing Machines, that detecting modern day, ICT-based, Panopticons is an undecidable problem. Furthermore, we show that for each sufficiently expressive formal system, we can effectively construct a Turing Machine for which it is impossible to prove, within the formal system, either that it is a Panopticon or it is not a Panopticon.

Dimitris Fotakis, Vasilis Kontonis, Piotr Krysta et al.

We introduce the problem of simultaneously learning all powers of a Poisson Binomial Distribution (PBD). A PBD of order $n$ is the distribution of a sum of $n$ mutually independent Bernoulli random variables $X_i$, where $\mathbb{E}[X_i] = p_i$. The $k$'th power of this distribution, for $k$ in a range $[m]$, is the distribution of $P_k = \sum_{i=1}^n X_i^{(k)}$, where each Bernoulli random variable $X_i^{(k)}$ has $\mathbb{E}[X_i^{(k)}] = (p_i)^k$. The learning algorithm can query any power $P_k$ several times and succeeds in learning all powers in the range, if with probability at least $1- δ$: given any $k \in [m]$, it returns a probability distribution $Q_k$ with total variation distance from $P_k$ at most $ε$. We provide almost matching lower and upper bounds on query complexity for this problem. We first show a lower bound on the query complexity on PBD powers instances with many distinct parameters $p_i$ which are separated, and we almost match this lower bound by examining the query complexity of simultaneously learning all the powers of a special class of PBD's resembling the PBD's of our lower bound. We study the fundamental setting of a Binomial distribution, and provide an optimal algorithm which uses $O(1/ε^2)$ samples. Diakonikolas, Kane and Stewart [COLT'16] showed a lower bound of $Ω(2^{1/ε})$ samples to learn the $p_i$'s within error $ε$. The question whether sampling from powers of PBDs can reduce this sampling complexity, has a negative answer since we show that the exponential number of samples is inevitable. Having sampling access to the powers of a PBD we then give a nearly optimal algorithm that learns its $p_i$'s. To prove our two last lower bounds we extend the classical minimax risk definition from statistics to estimating functions of sequences of distributions.