6 citations · 29 across the 13 of their papers we have counts for
15 papers
Diameter Thresholds of Random Cayley Graphs
Demetres Christofides, Klas Markström, Christina Savvidou
Given a group , the model denotes the probability space of all Cayley graphs of where each element of is included in the generating set independently…
A fast algorithm for the gas station problem
Kleitos Papadopoulos, Demetres Christofides
In the gas station problem we want to find the cheapest path between two vertices of an -vertex graph. Our car has a specific fuel capacity and at each vertex we can fill our ca…
Graph Guessing Games and non-Shannon Information Inequalities
Rahil Baber, Demetres Christofides, Anh N. Dang +2
Guessing games for directed graphs were introduced by Riis for studying multiple unicast network coding problems. In a guessing game, the players toss generalised dice and can see…
The asymptotic complexity of matrix reduction over finite fields
Demetres Christofides
Consider an invertible n \times n matrix over some field. The Gauss-Jordan elimination reduces this matrix to the identity matrix using at most n^2 row operations and in general th…
First order convergence and roots
Demetres Christofides, Daniel Kral
Nesetril and Ossona de Mendez introduced the notion of first order convergence, which unifies the notions of convergence for sparse and dense graphs. They asked whether if G_i is a…
An approximate isoperimetric inequality for r-sets
Demetres Christofides, David Ellis, Peter Keevash
We prove a vertex-isoperimetric inequality for [n]^(r), the set of all r-element subsets of {1,2,...,n}, where x,y \in [n]^(r) are adjacent if |x Δy|=2. Namely, if \mathcal{A} \sub…