Konstantinos Panagiotou

TCS Journal 2019 Journal Article

Asymptotically optimal amplifiers for the Moran process

• Leslie Ann Goldberg
• John Lapinskas
• Johannes Lengler
• Florian Meier
• Konstantinos Panagiotou
• Pascal Pfister

We study the Moran process as adapted by Lieberman, Hauert and Nowak. This is a model of an evolving population on a graph or digraph where certain individuals, called “mutants” have fitness r and other individuals, called “non-mutants” have fitness 1. We focus on the situation where the mutation is advantageous, in the sense that r > 1. A family of digraphs is said to be strongly amplifying if the extinction probability tends to 0 when the Moran process is run on digraphs in this family. The most-amplifying known family of digraphs is the family of megastars of Galanis et al. We show that this family is optimal, up to logarithmic factors, since every strongly-connected n-vertex digraph has extinction probability Ω ( n − 1 / 2 ). Next, we show that there is an infinite family of undirected graphs, called dense incubators, whose extinction probability is O ( n − 1 / 3 ). We show that this is optimal, up to constant factors. Finally, we introduce sparse incubators, for varying edge density, and show that the extinction probability of these graphs is O ( n / m ), where m is the number of edges. Again, we show that this is optimal, up to constant factors.

SODA Conference 2018 Conference Paper

Labeling Schemes for Nearest Common Ancestors through Minor-Universal Trees

• Pawel Gawrychowski
• Fabian Kuhn
• Jakub Lopuszanski
• Konstantinos Panagiotou
• Pascal Su

Preprocessing a tree for finding the nearest common ancestor of two nodes is a basic tool with multiple applications. Quite a few linear-space constant-time solutions are known and the problem seems to be well-understood. This is however not so clear if we want to design a labeling scheme. In this model, the structure should be distributed: every node receives a distinct binary string, called its label, so that given the labels of two nodes (and no further information about the topology of the tree) we can compute the label of their nearest common ancestor. The goal is to make the labels as short as possible. Alstrup, Gavoille, Kaplan, and Rauhe [Theor. Comput. Syst. 37(3): 441–456 2004] showed that O (log n )-bit labels are enough, with a somewhat large constant. More recently, Alstrup, Halvorsen, and Larsen [SODA 2014] refined this to only 2. 772 log n, and provided a lower bound of 1. 008 log n. We connect the question of designing a labeling scheme for nearest common ancestors to the existence of a tree, called a minor-universal tree, that contains every tree on n nodes as a topological minor. Even though it is not clear if a labeling scheme must be based on such a notion, we argue that all already existing schemes can be reformulated as such. Further, we show that this notion allows us to easily obtain clean and good bounds on the length of the labels. As the main upper bound, we show that 2. 318 log n -bit labels are enough. Surprisingly, the notion of a minor-universal tree for binary trees on n nodes has been already used in a different context by Hrubes et al. [CCC 2010], and Young, Chu, and Wong [J. ACM 46(3): 416–435, 1999] introduced a very closely related (but not equivalent) notion of a universal tree. On the lower bound side, we show that any minor-universal tree for trees on n nodes must contain at least Ω( n 2. 174 ) nodes. This highlights a natural limitation for all approaches based on defining a minor-universal tree. We complement the existential results with a generic transformation that allows us, for any labeling scheme for nearest common ancestors based on a minor-universal tree, to decrease the query time to constant, while increasing the length of the labels only by lower order terms.

TCS Journal 2014 Journal Article

Multi-target ray searching problems

• Spyros Angelopoulos
• Alejandro López-Ortiz
• Konstantinos Panagiotou

We consider the problem of exploring m concurrent rays using a searcher. The rays are disjoint with the exception of a single common point, and in each ray at most one potential target may be located. The objective is to design search strategies for locating t targets (with t ⩽ m ) while minimizing the search distance traversed. This setting generalizes the extensively studied ray search (or star search) problem, in which the searcher seeks a single target. We apply two different measures for evaluating the efficiency of the search strategy. The first measure is the standard metric in the context of ray-search problems, and compares the total search cost to the cost of an optimal algorithm that has full information on the targets. We present a simple strategy that achieves optimal competitive ratio under this metric. Our main result pertains to the second measure, which is based on a weakening of the optimal cost as proposed by Kirkpatrick [ESA 2009] and McGregor et al. [ESA 2009]. For this model, we present an asymptotically optimal strategy that is within a multiplicative factor of Θ ( log ( m − t ) ) from the optimal search cost. Our results demonstrate that, for both problems, the problem of locating t targets in m rays is essentially as difficult as the problem of locating a single target in m − ( t − 1 ) rays.

STOC Conference 2013 Conference Paper

Going after the k-SAT threshold

• Amin Coja-Oghlan
• Konstantinos Panagiotou

Random k -SAT is the single most intensely studied example of a random constraint satisfaction problem. But despite substantial progress over the past decade, the threshold for the existence of satisfying assignments is not known precisely for any k≥3. The best current results, based on the second moment method, yield upper and lower bounds that differ by an additive k ⋅ {ln2}/2, a term that is unbounded in k (Achlioptas, Peres: STOC 2003). The basic reason for this gap is the inherent asymmetry of the Boolean values 'true' and 'false' in contrast to the perfect symmetry, e.g., among the various colors in a graph coloring problem. Here we develop a new asymmetric second moment method that allows us to tackle this issue head on for the first time in the theory of random CSPs. This technique enables us to compute the k-SAT threshold up to an additive ln2-1/2+O(1/k) ~0.19. Independently of the rigorous work, physicists have developed a sophisticated but non-rigorous technique called the "cavity method" for the study of random CSPs (Mezard, Parisi, Zecchina: Science~2002). Our result matches the best bound that can be obtained from the so-called "replica symmetric" version of the cavity method, and indeed our proof directly harnesses parts of the physics calculations.

STOC Conference 2012 Conference Paper

Catching the k-NAESAT threshold

• Amin Coja-Oghlan
• Konstantinos Panagiotou

The best current estimates of the thresholds for the existence of solutions in random constraint satisfaction problems ('CSPs') mostly derive from the first and the second moment method . Yet apart from a very few exceptional cases these methods do not quite yield matching upper and lower bounds. According to deep but non-rigorous arguments from statistical mechanics, this discrepancy is due to a change in the geometry of the set of solutions called condensation that occurs shortly before the actual threshold for the existence of solutions (Krzakala, Montanari, Ricci-Tersenghi, Semerjian, Zdeborova: PNAS~2007). To cope with condensation, physicists have developed a sophisticated but non-rigorous formalism called Survey Propagation (Me-zard, Parisi, Zecchina: Science 2002). This formalism yields precise conjectures on the threshold values of many random CSPs. Here we develop a new Survey Propagation inspired second moment method for the random k-NAESAT problem, which is one of the standard benchmark problems in the theory of random CSPs. This new technique allows us to overcome the barrier posed by condensation rigorously. We prove that the threshold for the existence of solutions in random k-NAESAT is 2 k-1 ln2-(ln/2 2+1/4)+ε k , where |ε k | ≤ 2 -(1-o k (1))k , thereby verifying the statistical mechanics conjecture for this problem.

SODA Conference 2012 Conference Paper

The maximum degree of random planar graphs

• Michael Drmota
• Omer Giménez
• Marc Noy
• Konstantinos Panagiotou
• Angelika Steger

SODA Conference 2012 Conference Paper

Ultra-fast rumor spreading in social networks

• Nikolaos Fountoulakis
• Konstantinos Panagiotou
• Thomas Sauerwald

SODA Conference 2011 Conference Paper

On the Degree Distribution of Random Planar Graphs

• Konstantinos Panagiotou
• Angelika Steger

SODA Conference 2011 Conference Paper

The Multiple-Orientability Thresholds for Random Hypergraphs

• Nikolaos Fountoulakis
• Megha Khosla
• Konstantinos Panagiotou

SODA Conference 2010 Conference Paper

Synchrony and Asynchrony in Neural Networks

• Fabian Kuhn
• Konstantinos Panagiotou
• Joel Spencer
• Angelika Steger

SODA Conference 2010 Conference Paper

Vertices of Degree k in Random Maps

• Daniel Johannsen
• Konstantinos Panagiotou

SODA Conference 2009 Conference Paper

Maximal biconnected subgraphs of random planar graphs

• Konstantinos Panagiotou
• Angelika Steger

SODA Conference 2008 Conference Paper

On properties of random dissections and triangulations

• Nicla Bernasconi
• Konstantinos Panagiotou
• Angelika Steger

SODA Conference 2007 Conference Paper

On extremal subgraphs of random graphs

• Graham R. Brightwell
• Konstantinos Panagiotou
• Angelika Steger

STOC Conference 2006 Conference Paper

On adequate performance measures for paging

• Konstantinos Panagiotou
• Alexander Souza

Memory management is a fundamental problem in computer architecture and operating systems. We consider a two-level memory system with fast, but small cache and slow, but large main memory. The underlying theoretical problem is known as the paging problem. A sequence of requests to pages has to be served by making each requested page available in the cache. A paging strategy replaces pages in the cache with requested ones. The aim is to minimize the number of page faults that occur whenever a requested page is not in the cache.Experience shows that the paging strategy LEAST-RECENTLY-USED (LRU) usually achieves a factor around 2 to 3 compared to the optimum number of faults. This contrasts the theoretical worst case, in which this factor can be as large as the cache size k.One difficulty in analyzing the paging problem was the lack of an appropriate lower bound for the minimum number of page faults. We address this issue and propose a general lower bound which provides insight into the global structure of a given request sequence. In addition, we derive a characterization for the number of faults incurred by LRU.We give a theoretical explanation why LRU performs well in practice. We classify the set of all request sequences according to certain parameters and prove a bound on the competitive ratio of LRU, which depends on them. This bound varies between 2 and k, i.e., it includes the worst-case, but explains for which sequences LRU achieves constant competitive ratio. The classification is motivated from the structure of request sequences of practical applications: locality of reference and characteristic data access patterns. We argue that this structure yields values around 2 for our bound. Indeed, it is between 2 and 5 in extensive practical experiments.Furthermore, we study the paging problem with variable cache size, which was already considered previously. We show that this approach is not appropriate to explain the usual good performance of LRU. We measure the performance of LRU with the expected competitive ratio E[ALG]/E[OPT] and the expected performance ratio E[ALG]/E[OPT] in a diffuse adversary model and compare both measures. Our analysis yields that the expected competitive ratio gives a misleading answer.