Konstantinos Panagiotou
Catching the k-NAESAT Threshold.
Tue, 11/08/2011 - 15:01 — SomNambulAuthors: Konstantinos Panagiotou, Amin Coja-Oghlan
Subjects: Discrete Mathematics
AbstractThe 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.- Read more
- 2 comments
- login or register to post comments
On the Insertion Time of Cuckoo Hashing.
Tue, 06/08/2010 - 15:01 — SomNambulAuthors: Konstantinos Panagiotou, Angelika Steger, Nikolaos Fountoulakis
Subjects: Data Structures and Algorithms
AbstractCuckoo hashing is an efficient technique for creating large hash tables with
high space utilization and guaranteed constant access times. There, each item
can be placed in a location given by any one out of k different hash functions.
In this paper we investigate further the random walk heuristic for inserting in
an online fashion new items into the hash table.Rumor Spreading on Random Regular Graphs and Expanders.
Mon, 02/22/2010 - 16:01 — SomNambulAuthors: Konstantinos Panagiotou, Nikolaos Fountoulakis
Subjects: Combinatorics
AbstractBroadcasting algorithms are important building blocks of distributed systems.
In this work we investigate the typical performance of the classical and
well-studied push model. Assume that initially one node in a given network
holds some piece of information. In each round, every one of the informed nodes
chooses independently a neighbor uniformly at random and transmits the message
to it.Sharp Load Thresholds for Cuckoo Hashing.
Wed, 10/28/2009 - 16:01 — SomNambulAuthors: Konstantinos Panagiotou, Nikolaos Fountoulakis
Subjects: Data Structures and Algorithms
AbstractThe paradigm of many choices has influenced significantly the design of
efficient data structures and, most notably, hash tables. Cuckoo hashing is a
technique that extends this concept. There,we are given a table with $n$
locations, and we assume that each location can hold one item. Each item to be
inserted chooses randomly k>1 locations and has to be placed in any one of
them. How much load can cuckoo hashing handle before collisions prevent the
successful assignment of the available items to the chosen locations?Extremal Subgraphs of Random Graphs: an Extended Version.
Thu, 08/27/2009 - 13:23 — SomNambulAuthors: Graham Brightwell, Konstantinos Panagiotou, Angelika Steger
Subjects: Probability
AbstractWe prove that there is a constant $c >0$, such that whenever $p \ge n^{-c}$,
with probability tending to 1 when $n$ goes to infinity, every maximum
triangle-free subgraph of the random graph $G_{n,p}$ is bipartite. This answers
a question of Babai, Simonovits and Spencer (Journal of Graph Theory, 1990).Extremal Subgraphs of Random Graphs: an Extended Version.
Thu, 08/27/2009 - 13:23 — SomNambulAuthors: Graham Brightwell, Konstantinos Panagiotou, Angelika Steger
Subjects: Probability
AbstractWe prove that there is a constant $c >0$, such that whenever $p \ge n^{-c}$,
with probability tending to 1 when $n$ goes to infinity, every maximum
triangle-free subgraph of the random graph $G_{n,p}$ is bipartite. This answers
a question of Babai, Simonovits and Spencer (Journal of Graph Theory, 1990).
User login
