Andy Twigg

Dr Andy Twigg

Junior Research Fellow

Room Room 445, Wolfson Building, Parks Road, Oxford OX1 3QD

Interests

I'm a junior research fellow at St John's College in Computer Science. My research interests are in graph algorithms and networks, in particular routing, broadcasting, load balancing, etc. For my PhD I found a compact routing scheme for the `forbidden-set' problem: routing around induced forbidden subsets of a graph, with memory requirements O(k^2 polylog n) for treewidth k graphs.

If you wish to get in touch (and please do!) then use my email address is andy.twigg (at) cs.ox.ac.uk

From July 2009 I've taken a year off to work on a storage startup called Acunu. We're hiring people with expertise in algorithms, kernel hacking and storage systems (send us an email at jobs@acunu.com)!

Biography

From 1999-2002 I was an undergraduate at Warwick University. I did my PhD (forbidden-set compact routing) at the Computer Laboratory (and King's College) at Cambridge University from 2002-2006. I was a Marie Curie visiting fellow at BRICS in 2003 with Mogens Nielsen. After finishing my PhD I spent four months in 2006 at Microsoft Research Cambridge then a year from 2007-2008 as a Research Scientist at Thomson Research, Paris (my page there) where I worked on epidemic streaming algorithms mostly with Laurent Massoulie. From 2008-2012 I'm a junior research fellow (JRF) at St John's Oxford in the Department of Computer Science and the combinatorics group at the Maths Institute. A short cv can be found here. I've been lucky enough to work, visit and talk with many people, including Bruno Courcelle, Tim Griffin, Cyril Gavoille, Rahul Sami, Don Towsley, Laurent Massoulie, Elan Pavlov, Mihai Patrascu, Dan Tomozei, Peter Bro Miltersen and Mogens Nielsen.

Selected Publications

Rate-optimal algorithms for peer-to-peer streaming. With Laurent Massoulie. Journal of Performance Evaluation, 2008 (preliminary tech report)
Constrained compact routing for graphs of small treewidth and cliquewidth. With B Courcelle. Journal of Theory of Computer Systems, 2008.
Epidemic streaming algorithms: optimal performance tradeoffs. With Thomas Bonald, Fabien Mathieu, Deigo Perino, Laurent Massoulie. SIGMETRICS 2008 (PDF)
Forbidden-set connectivity labelling on 3-connected planar graphs. With Bruno Courcelle, Cyril Gavoille and M. Kante. Topological and Geometric Graph Theory, Paris, 2008.
Forbidden-set labeling schemes on graphs. With Bruno Courcelle, Cyril Gavoille and M. Kante. In LOCALITY workshop, PODC 2007. (PDF | slides)
Compact forbidden-set routing. PhD Thesis. Also available as technical report UCAM-CL-TR-678, University of Cambridge, Computer Laboratory, December 2006(PDF | slides i)
Randomized Decentralized Broadcasting Algorithms. With Laurent Massoulie, Christos Gkantsidis and Pablo Rodriguez. INFOCOM 2007: 1073-1081 (PDF | tech report | slides)
Compact Forbidden-Set Routing. With Bruno Courcelle. STACS 2007: 37-48 (PDF | slides )
The complexity of fixed point models of trust in distributed networks. With Karl Krukow. Theoretical Comput. Sci. 389(3): 528-549 (2007) (PDF | tech report)
Complexity of computing distributed fixed points. With Karl Krukow. ICDCS 2005 (PDF | slides)
Trading in trust, tokens and stamps. With Tim Moreton. In workshop of economics of P2P networks, Berkeley CA 2003. (PDF)

Not yet published

k-vertex witness in worst-case time. With Ken Clarkson (Bell Labs), 2006
Optimal labeling for connectivity checking in planar networks with subgraph obstacles. With B Courcelle, C Gavoille and M. Kante. 2007.
Communication complexity of some Markov chain quantities . With Rahul Sami. (PDF)