I
am a Royal Society University
Research Fellow and a Reader
in Physics of Information. I obtained my PhD from Bristol
University, in the then newly created Quantum
Computation and Information Group. My advisor was Richard
Jozsa, whose advisor was Roger
Penrose. I was a visiting student at UC
Berkeley (and MSRI),
and previously I studied
Chemistry
at the University of
Siena
and
Philosophy (Logic) at the University
of Florence. I was a
Newton International Fellow at UCL,
a PostDoctoral Research Fellow of the Institute
for Quantum Computing and the Department
of Combinatorics & Optimization at the University
of Waterloo, mentored by Michele
Mosca, and a PostDoctoral Research Assistant in the Department
of Computer Science and the Department
of Mathematics at the University
of York. My long term scientific visits include CRI,
CWI, MIT,
Nankai, NUS
and RISCLinz. My research
interests are, broadly speaking, quantum information, combinatorics,
and complex systems. My links at UCL are Intelligent
Systems Group, UCL
Quantum Technologies, CoMPLEX
Research Group, UCL
Institute of Origins, Complex
Networks Interest Group, and London
Center for Nanotechnology.
Research
students:
Computer
Science: here
(PRISM); Centre for Doctoral Training in Delivering Quantum
Technologies: here;
Centre
for Mathematics, Physics and Engineering in the Life Sciences and
Experimental Biology (CoMPLEX): here.
Publications
My
research papers can be found in arXiv,
MathSciNet,
MPRA, PubMed,
and IRIS.
 C.
R. S. Banerji, P. Knopp, L. A. Moyle, S. Severini, R. W. Orrell, A.
E. Teschendorff, P. S. Zammitt, βcatenin is central to
DUX4driven network rewiring in Facioscapulohumeral muscular
dystrophy, accepted for publication in J. R. Soc. Interface. October
2014.

V.
I. Paulsen, S. Severini, D. Stahlke, I. G. Todorov, A. Winter,
Estimating
quantum chromatic numbers, arXiv:1407.6918
[math.OA]

B.H.
Wang, H.R. Xu, S. Campbell, S. Severini, Characterization
and properties of weakly optimal entanglement witnesses,
arXiv:1407.0870
[quantph]

T.
Cubitt, L. Mancinska, D. Roberson, S. Severini, D. Stahlke, and A.
Winter, Bounds
on entanglement assisted sourcechannel coding via the Lovasz theta
number and its variants, IEEE
Trans. Inf. Theory.
60:11, 73307340 (2014). arXiv:1310.7120
[quantph]

B.H.
Wang, H.R. Xu, S. Severini, Universal
methods for extending any entanglement witness from the bipartite to
the multipartite case,
Phys. Rev. A 90, 022312 (2014),
arXiv:1405.2021
[quantph]

A.
Chailloux, L. Mančinska, G. Scarpa, S. Severini,
Graphtheoretical Bounds on
the Entangled Value of Nonlocal Games, arXiv:1404.3640
[quantph], TQC2014.

J.Y.
Wu, M. Rossi, H. Kampermann, S. Severini, L.C. Kwek, C.
Macchiavello, D. Bruß, Randomized
graph states and their entanglement properties, Phys. Rev. A 89,
052335 (2014), Editor's choice, arXiv:1403.3828
[quantph]

Rethinking
GIP: Graph
Isomorphism Game on crowdcrafting.org;
Graph
Isomorphism: Quantum Ideas

W.
Vinci, S. Boixo, K. Markstrom, A. Roy, F. Spedalieri, P. Warburton,
S. Severini, Hearing
the Shape of the Ising Model with a Programmable
SuperconductingFlux Annealer, Sci. Rep. 4, Article Number:
5703, 2014. arXiv:1307.1114
[quantph]

H.
Buhrman, P. T. S. van der Gulik, S. Severini, D. Speijer, A
mathematical model of kinetoplastid mitochondrial gene scrambling
advantage, arXiv:1307.1163
[qbio.PE]

S.
Kirkland, S. Severini, alphaKuramoto
partitions: graph partitions from the frustrated Kuramoto model
generalise equitable partitions, accepted for publication in
Applicable Analysis and Discrete Mathematics (AADM), arXiv:1306.4299
[math.CO]
 C.
Godsil, D. Roberson, R. Samal, S. Severini, Sabidussi
versus Hedetniemi for three variations of the chromatic number,
accepted for publication in Combinatorica. arXiv:1305.5545
[math.CO]. Talk by Robert Samal at CanaDAM 2013: Hedetniemi
conjecture for strict vector chromatic number

N.
de Beaudrap, V. Giovannetti, S. Severini, R. Wilson, Interpreting
the von Neumann entropy of graphs Laplacians, and coentropic graphs,
April 2013. arXiv:1304.7946
[math.CO]

Z.H.
Ma, C. Yao, Z.H. Chen, S. Severini, A. Serafini, A
universal memoryassisted entropic uncertainty relation,
February 2013. arXiv:1302.1011
[quantph]

T.
Feng, S. Severini, Quantum
channels from association schemes, January 2013. arXiv:1301.1166
[quantph]

S.
Severini , F. Brandao (Eds.), 8th
Conference on the Theory of Quantum Computation, Communication and
Cryptography (TQC 2013), Revised Selected Papers, LIPIcsLeibniz
International Proceedings in Informatics, Vol. 22, 2013.
 C.
R. S. Banerji, T. Mansour, S. Severini, A
notion of graph likelihood and an infinite monkey theorem, J.
Phys. A: Math. Theor.
47
035101.
arXiv:1304.3600
[cs.DM]. See also Weisstein,
Eric W. "Graph Likelihood." From MathWorldA
Wolfram Web Resource.
http://mathworld.wolfram.com/GraphLikelihood.html.
The drawing in the paper (by A. Koroto) is featured on the cover
of J.
Phys. A: Math. Theor.

A.
Cabello, S. Severini, A. Winter, (Non)Contextuality
of Physical Theories as an Axiom, arXiv:1010.2163v1
[quantph]. See also F.
Moldoveanu, “Color
Me Surprised: Quantum Mechanics and Graph Theory are a Match Made in
Heaven”,
FQXi Community, 4 May 2011. And the following version:

A.
Cabello, S. Severini, A. Winter, Graphtheoretic
approach to quantum correlations, Phys. Rev. Lett. 112 (2014)
040401. arXiv:1401.7081
[quantph]
Two related papers that I like:

T.
Fritz, A.B. Sainz, R. Augusiak, J. Bohr Brask, R. Chaves, A.
Leverrier & A. Acín, Local
orthogonality as a multipartite principle for quantum correlations,
Nature Communications 4, Article number: 2263.

M.
Howard, J. Wallman, V. Veitch & J. Emerson, Contextuality
supplies the `magic' for quantum computation, Nature 510,
351355 (19 June 2014).
 D.
Burgarth, V. Giovannetti, L. Hogben, S. Severini, M. Young, Logic
circuits from zero forcing, Nat. Comput., July 2014 DOI
10.1007/s1104701494385. arXiv:1106.4403v1
[cs.DM]

C.
R. S. Banerji, D. MirandaSaavedra, S. Severini, M. Widschwendter,
T. Enver, J. X. Zhou, and A. E. Teschendorff,
Cellular
network entropy as the energy potential in Waddington's
differentiation landscape, Sci.
Rep. 3, Article number: 3039, 2013.

L.
C. Kwek, S. Severini, H. Su (Editors), The
Korepin Festschrift: from Statistical Mechanics to Quantum
Information Science: A Collection of Articles Written in Honor of
the 60th Birthday of Vladimir Korepin, World Scientific, 2013.
[Amazon]
See also L.C. Kwek, S. Severini, H.B. Su (guest Eds.), The
Korepin Festschrift: From Statistical Mechanics to Quantum
Information Science  A Collection of Articles Written in Honor of
the 60th Birthday of Vladimir Korepin, Int. J. Mod Phys B Vol.
26, No. 27&28 (2012). Preface

C.
Banerji, S. Severini, A. E. Teschendorff, Network
Transfer Entropy and Metric Space for Causality Inference, Phys.
Rev. E 87, 052814 (2013). arXiv:1303.0231
[condmat.disnn]

V.
Nicosia, T. Machida, R. Wilson, E. Hancock, N. Konno, V. Latora, S.
Severini, Coevolution
of networks and quantum dynamics: a generalization of the
BarabásiAlbert model of preferential attachment, J.
Stat. Mech. (2013)
P08016.
arXiv:1302.0887
[physics.socph]

A.
Cabello, M. GeoffreyParker, G. Scarpa, S. Severini, Exclusive
disjunction structures and graph representatives of local
complementation orbits, J.
Math. Phys. 54,
072202 (2013).
arXiv:1211.4250v1
[quantph]

V.
Giovannetti, S. Severini, The Kirchhoff's
MatrixTree Theorem revisited: counting spanning trees with the
quantum relative entropy, Advances in Network Complexity, A.
Mowshowitz M. Dehmer, and F.
EmmertStreib
(Eds.),
WileyVCH, 2013. arXiv:1102.2398v1
[quantph]

D.
Burgarth, D. D'Alessandro, L. Hogben, S. Severini, M. Young, Zero
forcing, linear and quantum controllability for systems evolving on
networks, IEEE
Trans.
Automat.
Contr., Vol. 99 (2013).
arXiv:1111.1475v1
[quantph]

T.
H. Hall, S. Severini, Locality
for quantum systems on graphs depends on the number field, J.
Phys. A: Math. Theor. 46
295301 (2013). arXiv:1204.3681v1
[quantph]

K.
T. Arasu, S. Severini, E. Velten, Block
weighing matrices, Cryptogr.
Commun.,
5 (2013), 201207.

L.
Mancinska, G. Scarpa, S. Severini, Generalized
KochenSpecker sets relate Quantum Coloring to EntanglementAssisted
Channel Capacity, IEEE
Trans. Inf. Theory, vol.
59:6
(2013), 18.

S.
Janson, S. Severini, An
example of graph limits of growing sequences of random graphs,
Journal of Combinatorics, Volume 4, Number 1, 67–80, 2013.
arXiv:1206.4586v1
[math.CO]

Z.H.
Chen, O. Guehne, Z.H. Ma, S. Severini, Estimating
entanglement monotones with a generalization of the Wootters
formula, Phys. Rev. Lett. 109, 200503 (2012). arXiv:1207.2889v1
[quantph] arXiv:1207.1111v1
[quantph]. Extended abstract in “AQIS2012,
Asian Quantum Information Science Conference, 2326 August, Suzhou,
China”.

Z.H.
Chen, Z.H. Ma, S. Han, S.M. Fei, S. Severini, Improved
bounds on negativity of superpositions, QIC, Vol. 12, No. 11&12
(2012) 0983–0988.

Z.H.
Chen, Z.H. Ma, J.L. Chen, S. Severini, Improved
lower bounds on generalizedmultipartiteentanglement concurrence,
Phys.
Rev. A 85, 062320 (2012). arXiv:1205.3057v1
[quantph]

H.
Buhrman, P. T. S. van der Gulik, S. Severini, D. Speijer, A
mathematical model of kinetoplastid mitochondrial gene scrambling
advantage, February 2012. arXiv:1307.1163
[qbio.PE]

C.
Godsil, S. Kirkland, S. Severini, J. Smith, Numbertheoretic
nature of communication in quantum spin systems, Phys. Rev.
Lett. 109, 050502 (2012). arXiv:1201.4822v1
[quantph] Here is a talk by S. Kirkland on this: State
Transfer in Quantum Spin Networks and the Matrix Exponential,
April 2013.

R.
Duan, S. Severini, A. Winter, On
zeroerror communication via quantum channels in the presence of
noiseless feedback, August 2011. [QIP2012]

J.
West, L. Lacasa, S. Severini, A. E. Teschendorff, Approximate
entropy of network parameters, Phys. Rev. E 85, 046111 (2012).
arXiv:1201.0045v1
[condmat.disnn]

J.
West, G. Bianconi, S. Severini, A. E. Teschendorff, Differential
network entropy reveals cancer system hallmarks, Sci. Rep. 2 :
802, 2012. See
also this version here: arXiv:1202.3015v1
[qbio.MN]. This is a talk by James West on the topic: Entropy
in the cancer cell, MoN11: Eleventh Mathematics of Networks
meeting – University of Warwick.

G.
Scarpa, S. Severini, On
KochenSpecker sets and the rank1 quantum chromatic number,
IEEE Trans. Inf. Theory, vol. 99 (2012). arXiv:1106.0712v1
[quantph] Extended abstract in “15^{th}
Workshop
in Quantum Information Processing, QIP2012,
1216 December, 2011, Montreal, Canada”. [Price for the Best
Artistic Poster] Poster

R.
Duan, S. Severini, A. Winter,
Zeroerror
communication via quantum channels and a quantum Lovasz theta
function,
IEEE
Trans. Inf. Theory, vol. PP:99 (2012). This is the extended journal
version of the following conference paper: Zeroerror communication
via quantum channels and a quantum Lovasz theta function, 2011 IEEE
International Symposium on Information Theory (IEEE ISIT 2011).
Available at IEEEXplore
[Talks]

S.
P. Jordan, T. Mansour, S. Severini, On
the degeneracy of SU(3)_k topological phases, Russ. J. Math.
Phys, Volume
19, Number 1,
(2012) 2126. arXiv:1009.0114v1
[math.CO]

K.
Anand, G. Bianconi, S. Severini, The Shannon
and the Von Neumann entropy of random networks with heterogeneous
expected degrees, Phys. Rev. E 83, 036109 (2011).
arXiv:1011.1565v2
[condmat.disnn]

K.
Zhao, A. Halu, S. Severini, G. Bianconi, Entropy
rate of nonequilibrium growing networks, Phys. Rev. E 84,
066113 (2011). arXiv:1109.0940v1
[condmat.disnn]

W.
van Dam, V. M. Kendon, S. Severini (Editors), Theory
of Quantum Computation, Communication, and Cryptography, 5th
Conference, TQC 2010, Leeds, UK, April 2010, Revised Selected
Papers, Lecture Notes in Computer Science 6519, Springer.

G.
Gutin, M. Mansour, S. Severini, A
characterization of horizontal visibility graphs and combinatorics
on words, Physica
A: Statistical Mechanics and its Applications, Volume 390, Issue 12,
15 June 2011, Pages 24212428.
arXiv:1010.1850v1
[physics.dataan]

S.
Kirkland, S. Severini, Spin
systems dynamics and faults detection in threshold networks,
Phys. Rev. A 83, 012310 (2011). arXiv:1009.3394v1
[quantph]

W.
Du, X. Li, Y. Li, S. Severini, A
note on the von Neumann entropy of random graphs, Linear Algebra
Appl., 443: 1112 (2010), 17221725.

A.
E. Teschendorff, S. Severini, Increased
entropy of signal transduction in the cancer metastasis phenotype,
BMC Systems Biology 2010, 4:104. arXiv:1007.0876v1
[qbio.MN] Qualified as 'Highly accessed'; Featured.

R.
Duan, S. Severini, A. Winter,
Zeroerror
communication via quantum channels, noncommutative graphs and a
quantum Lovasz theta function, February
2010. arXiv:1002.2514v1
[quantph]

S.
Severini, The
3dimensional cube is the only periodic, connected cubic graph with
perfect state transfer,
2010
J. Phys.: Conf. Ser. 254 012012 (invited paper in “Quantum
Groups, Quantum Foundations, and Quantum Information: a Festschrift
for Tony Sudbery”).
arXiv:1001.0674v1
[quantph]

A.
Casaccino, S. Mancini, S. Severini, Entanglement
manipulation via dynamics in multiple quantum spin systems,
Quantum. Inf. Process. June 07, 2010. arXiv:0912.5499v1
[quantph]

A.
Hamma, F. Markopoulou, F. Caravelli, S. Lloyd, S. Severini, K.
Markstrom, A quantum BoseHubbard
model with evolving graph as toy model for emergent spacetime,
Phys. Rev. D 81, 104032 (2010). arXiv:0911.5075v2
[grqc]

C.
Godsil, S. Severini, Control
by quantum dynamics on graphs,
Phys. Rev. A 81, 052316 (2010). arXiv:0910.5397v1
[quantph]

A.
Cosentino, S. Severini, Weight
of quadratic forms and graph states,
Phys.
Rev. A 80, 052309 (2009).
arXiv:0906.2488v1
[quantph]

F.
Markopoulou, S. Severini, A
note on observables for counting trails and paths in graphs,
JMMA, Vol. 8, No. 3, 2009. arXiv:0906.0043v1
[math.CO]

A.
Casaccino, S. Lloyd, S. Mancini, S. Severini, Quantum
state transfer through a qubit network with energy shifts and
fluctuations,
Int. J. Quantum Info 7:8, 14171427 (2009). arXiv:0904.4510v1
[quantph]

T.C.
Wei, S. Severini, Matrix
permanent and entanglement of permutation symmetric states,
J.
Math. Phys. 51, 092203 (2010).
arXiv:0905.0012v1
[quantph]

S.
Vazquez, S. Severini, Perturbation
theory in a pure exchange nonequilibrium economy,
Phys. Rev. E 81, 036102 (2010). arXiv:0904.1402v1
[qfin.TR]

A.
Hamma, D. Lidar, S. Severini, Entanglement
and area law with a fractal boundary in a topologically ordered
phase,
Phys. Rev. A 81, 010102(R) (2010). arXiv:0903.4444v1
[quantph]
[featured in PRB Kaleidoscope Images]

D.
Djokovic, S. Severini, F. Szöllösi, Rational
Orthogonal versus
Real
Orthogonal, ELA, Vol. 18, pp. 649673, October 2009.
arXiv:0903.2853v1
[math.CO]

S.
Bose, A. Casaccino, S. Mancini, S. Severini, Communication
in XYZ AlltoAll Quantum Networks with a Missing Link, Int. J.
Quantum Info., 2009, v.7, no. 3. arXiv:0808.0748v2
[quantph]

A.
Hamma, T. Mansour, S. Severini, Diffusion
on an Ising Chain with Kinks, Phys. Lett. A.,
Volume
373, Issue 31 (2009), Pages 26222628. arXiv:0806.4812v1
[math.CO]

S.
Klavzar, S. Severini, Tensor
2sums and entanglement,
J.
Phys. A: Math. Theor. 43 212001 Fast Track Comm. arXiv:0909.1039v2
[math.CO]

S.
Flammia, S. Severini, Weighing
matrices and optical quantum computing, J. Phys A: Math. Theor.
42 065302 (2009). arXiv:0808.2057v1
[quantph]

A.
Hamma, F. Markopoulou, I. PremontSchwarz, S. Severini,
LiebRobinson
bounds and the speed of light from topological order, Phys. Rev.
Lett. 102, 017204 (2009). arxiv:0808.2495v1
[quantph]

F.
Passerini, S. Severini, The
von Neumann entropy of networks,
December
2008. arXiv:0812.2597v1
[condmat.disnn].
See also Quantifying
complexity in networks: the von Neumann entropy,
in John Symons and Jorge Louçã (Eds.): Social
structures in communication networks, Int.
J. Agent Tech. Sys., Vol. 1, Issue 4. A version with title
“Quantifying Disorder in Networks: The von Neumann Entropy”
has been published in the book “Developments in Intelligent
Agent Technologies and MultiAgent Systems: Concepts and
Applications” (G. Trajkovski Ed.), IGI Global, 2011.

D.
Cheung , D. Maslov, S. Severini, Translation
Techniques Between Quantum Circuit Architectures, Nov 2012.

S.
Severini, Graphs of unitary matrices, Ars Comb., XC, January 2009.
arXiv:math/0303084v3
[math.CO]

A.
Bernasconi, C. Godsil, S. Severini, Quantum
Networks on Cubelike Graphs, Phys. Rev. A 78,052320 (2008).
arXiv:0808.0510v1
[quantph]

T.
Mansour, S. Severini, Counting
paths in Bratteli diagrams for SU(2)_k, EPL 86 33001.
arXiv:0806.4809v1
[math.CO]

M.
Arzano, A. Hamma, S. Severini, Hidden
entanglement at the Planck scale: loss of unitarity and the
information paradox, Mod. Phys. Lett. A25:437445, 2010.
arXiv:0806.2145v1
[hepth].
See also "A black hole's secret files: hiding information at
the Planck scale", Essay for “The Gravity Research
Foundation”, 2008.

A.
Casaccino, E. Galvao, S. Severini, Extrema
of discrete Wigner functions and applications, Phys. Rev. A 78,
022310 (2008). arXiv:0805.3466v1
[quantph]

S.
Severini, Nondiscriminatory
Propagation on Trees, J. Phys A: Math. Theor. 41 482002 (2008),
Fast Track Comm. arXiv:0805.0181v1
[math.CO]

T.
Konopka, F. Markopoulou, S. Severini, Quantum
Graphity: a model of emergent locality, Phys. Rev. D. 77, 104029
(2008). arXiv:0801.0861v1
[hepth].
See also the Cover Story of New
Scientist magazine, 3 May, 2008. M. Marshall, "Knowing
the mind of God: Seven theories of everything",
New
Scientist
(4
March 2010). K. Smith, Big
Bang theory challenged by big chill, 20 August, 2012.

M.
Batty, A. Casaccino, A. Duncan, S. Rees, S. Severini, An
application of the DeutschJozsa algorithm to formal languages and
the word problem for groups, LNCS 5106, Springer, 2008.
arXiv:0801.2801v1
[quantph]

D.
Emms, S. Severini, R. Wilson, E. Hancock, Coined
quantum walks lift the cospectrality of graphs and trees,
Pattern
Recognition, Vol 42, Issue 9 (2008), 19882002. [PDF]
 R.
Hildebrand, S. Mancini, S. Severini, Combinatorial
laplacians and positivity under partial transpose, Math. Struct.
in Comp. Science (2008), vol. 18, pp. 205–219.
arXiv:cs.CC/0607036

M.
Schork, T. Mansour, S. Severini, Noncrossing
normal ordering for functions of boson operators, Internat. J.
Theoret. Phys., Vol. 47, No 3 (2008), 832849.
arXiv:quantph/0607074

Q.H.
Hou, T. Mansour, S. Severini, Partial
transpose of permutation matrices, Integers, The Electronic
Journal of Combinatorial Number Theory, Vol. 8:1, (2008).
arXiv:0709.3547v1
[math.CO]

S.
Severini, F. Szöllösi, A
further look into combinatorial orthogonality, ELA, Vol. 17
(2008) pp. 376388. arXiv:0709.3651v1
[math.CO]

M.
Schork, T. Mansour, S. Severini, A
generalization of the boson normal ordering, Phys. Letters A,
364 (2007). arXiv:quantph/0608081v2

S.
Braunstein, S. Ghosh, S. Severini, Estimation
of pure qubits on circles, J. Phys. A: Math. Theor. 40 (2007)
18091834. arXiv:quantph/0412101v1
[IOP
Select  Best papers of 2006]

L.
Clarisse, S. Ghosh, A. Sudbery, S. Severini, The
disentangling power of unitaries, Physics Letters A, 365 (2007).
arXiv:quantph/0611075v2

S.
Mancini, S. Severini, The
Quantum Separability Problem for Gaussian States, Electron.
Notes Theor. Comput. Sci., 169, Elsevier Sci. B. V., Amsterdam,
2007. arXiv:cs/0603047v2
[cs.CC]

N.
Grayson , T. Keef, S. Severini, R. Twarock, SelfAssembly
of Viral Capsids via a Hamiltonian Paths Approach: The Case of
Bacteriophage MS2, Foundations of Nanoscience (FNANO) 2007. poster

T.
Mansour, S. Severini, Enumeration
of (k,2)noncrossing partitions, Discrete Math. 308:20 (2008)
45704577. arXiv:0808.1157v1
[math.CO]

N.
Saxena, S. Severini, I. Shparlinski, Parameters
of circulant integral graphs and periodic quantum dynamics, Int.
J. Quantum Info 5, 417430 (2007). arXiv:quantph/0703236v1

M.
Schork, T. Mansour, S. Severini, Wick’s
theorem for qdeformed boson operators, J. Phys. A: Math. Theor.
40 (2007) 83938401. arXiv:quantph/0703086v1

P.
J. Cameron, A. Montanaro, M. Newman, S. Severini, A. Winter, On
the quantum chromatic number of a graph, The Electronic Journal
of Combinatorics, R81 of Volume 14(1), 2007.
arXiv:quantph/0608016v3

T.
Mansour, S. Severini, Grid
polygons from permutations and their enumeration by the kernel
method, Proceedings of The 19th International Conference on
Formal Power Series and Algebraic Combinatorics (FPSAC2007), July
26, 2007. Nankai University, Tianjin, China. arXiv:math/0603225v1
[math.CO]

G.
Gutin, A. Rafiey, S. Severini, A. Yeo, Hamilton
Cycles in Digraphs of Unitary Matrices, Discrete Appl. Math. 173
(2006), no. 13, 6778. arXiv:math/0409228v2
[math.CO]

S.
Severini, Universal
quantum computation with unlabeled qubits, J. Phys. A: Math.
Theor. 39 (2006) 85078515. arXiv:quantph/0601078v3

D.
Emms, S. Severini, R. Wilson, E. Hancock, A
matrix representation of graphs and its spectrum as a graph
invariant, The Electronic Journal of Combinatorics, R34, Volume
13(1), 2006. arXiv:quantph/0505026v2
[See also K. J. Guo, Quantum
Walks on Strongly Regular Graphs, Master Dissertation,
University of Waterloo, 2010.]

S.
Severini, On the
structure of the adjacency matrix of the line digraph of a regular
digraph, Discrete Appl. Math. 154 (2006), no 12, 16631665.
arXiv:quantph/0210055v3

S.
Braunstein, S. Ghosh, S. Severini, The
laplacian of a graph as a density matrix: a basic combinatorial
approach to separability of mixed states, Ann. Comb., 10:3
(2006), 291317. arXiv:quantph/0406165v2

S.
Severini, Twocolorable
graph states with maximal Schmidt measure, Physics Letters A,
356 (2006). arXiv:quantph/0511147v1

T.
J. Osborne, S. Severini, Quantum
Algorithms and Covering Spaces, Quantum Computers and Computing,
6:1 (2006), 122. arXiv:quantph/0403127v3

S.
Braunstein, S. Ghosh, T. Mansour, S. Severini, R. Wilson, Some
families of density matrices for which separability is easily
tested, Phys. Rev. A, 73:1, 012320 (2006).
arXiv:quantph/0508020v3

K.
B. Reid, R. Lundgren, S. Severini, D. Stewart, Quadrangularity
and Strong Quadrangularity in Tournaments, Australas. J. Combin.
34 (2006), 247260. arXiv:math/0409474v1
[math.CO]

C.
Bebeacua, T. Mansour, A. Postnikov, S. Severini, On the Xrays of
permutations, ENDM, Vol. 20, 2005. arXiv:math/0506334v1
[math.CO] [Featured
in
Jeux
et Mathématiques]

L.
Clarisse, S. Ghosh, S. Severini, A. Sudbery, Entangling
power of permutations, Phys. Rev. A 72, 012314 (2005).
arXiv:quantph/0502040v2

G.
Gutin, N. Jones, A. Rafiey, S. Severini, A. Yeo, Mediated
Digraphs and Quantum Nonlocality, Discrete Appl. Math. 150
(2005), no. 13, 4150. arXiv:math/0411653v2
[math.CO]

S.
Severini, On
the digraph of a unitary matrix, SIAM J. Matrix Anal. Appl.
(SIMAX), 25:1 (2003), 295300. arXiv:math/0205187v2
[math.CO]
Meetings
 Citizen
Science 2015 (CitSci2015), San Jose, California, 1112 February
2015. (PC member)

Postquantum
research: addressing future challenges and directions, INI,
Cambridge, UK, 1819 September 2014. (Invited speaker) Video

Symposium
on Integrability and Exact Solvability as Avatars of Symmetry,
Centre
de recherches mathématiques (CRM), Montreal, QC, 2529 August
2014. (Invited speaker)

Interdisciplinary
Symposium on Complex Systems: Florence, Italy, 1518 September
2014. (PC member)

International
School on Complex Systems, Bertinoro, Italy, July 1418, 2014.
(Invited lecturer)

New
Frontiers of Quantum Information, Ascoli Piceno, Italy, July
711, 2014. (Invited speaker)

Algebraic
Combinatorics: Spectral Graph Theory, ErdosKoRado Theorems and
Quantum Information Theory, A Conference to celebrate the work
of Chris Godsil, Fields Institute, Toronto, ON, June 2327, 2014.
(Invited speaker)

11th
Central European Quantum Information Processing Workshop,
Znojmo, Czech Republic, 58 June 2014. (Invited speaker; PC member)

Quantum
Information Paris (QuPa),
Institut H. Poincare, Paris, France, 27 March 2014. (Invited
speaker)

Capacity
of Communication, Queen's University, Belfast, UK, 715 March
2014. (Invited speaker)

The
3^{rd}
Citizen
Cyberscience Summit,
London, UK, 2022 February, 2014. (Invited speaker)
 Workshop
on Quantum Correlations, Contextuality and All That, Natal,
December 913, 2013. (Invited speaker)

Heilbronn
Quantum Algorithms Meeting, Newton
Institute for Mathematical Science, Cambridge, 2728 November 2013.
(Invited speaker).

Video
of the talk: Graph
Isomorphism: quantum ideas

UCLParis
Quantum Connection, UCL, 45 November, 2013; including Peter
Shor's public lecture. (Coorganizer)

Interdisciplinary
Symposium on Complex Systems, Prague, Czech Republic, 1013
September 2013. (PC member)

Topological
Quantum Matter, Higgs Centre for Theoretical Physics, University
of Edinburgh, 23 September 2013. (Invited participant)

Mathematical
Challenges in Quantum Information, Newton Institute for
Mathematical Sciences, Cambridge, AugustDecember 2013 (Visiting
Fellow)

Quantum
Information and Foundations of Quantum Mechanics, University of
British Columbia, Vancouver, BC, 25 July 2013. (Invited speaker)

18th
Conference of the International Linear Algebra Society (ILAS),
Providence, Rhode Island, USA on June 37, 2013. Advances in
Combinatorial Matrix Theory and its Applications (Invited speaker)

IQC
Workshop on Quantum Computation and Complex Networks, Institute
for Quantum Computing, Waterloo, Ontario, 2426 May, 2013.
(Coorganizer)

The
8^{th}
Conference
on Theory of Quantum Computation, Communication and Cryptography,
TQC2013,
Guelph, Ontario, 2123 May, 2013. (PC Chair).

The
Oxford Future of Science Conference, Rigour
and Openess in 21^{st}
Century
Science,
1112 April 2013, Oxford. (Invited speaker)

Science
Hackday in London, Centre for Creative Collaboration, 16 March
2013. (Invited speaker)

UKRussia
Frontiers of Science, Kazan, Russia, 1115 March 2013. (Invited
delegate) [Local
website] [kpfu.ru]
[itartass]

Second
International Workshop on Adiabatic Quantum Computation,
Institute of Physics, London, UK, 68 March 2013. (Coorganizer)

Positive
Semidefinite Zeroforcing and Applications, Banff
International Research
Station
for
Mathematical Innovation and Discovery, Banff, Alberta, Canada, 2330
September, 2012. (Organizer)

Timevarying
Complex Network Analysis, University of Cambridge, 19th
September 2012. (Invited participant)

Quantum
Africa 2, 37 September, KwaZuluNatal, South Africa.
(Invited
keynote speaker)

International
Workshop on Quantum Computing and Quantum Information Processing,
August 31September 2, 2012, Beijing, China. (Invited speaker)

Quantum
Physics of Information, Summer School & Workshop, Shanghai
JiaoTong University, 2228 August 2012. (Lecturer; Program
committee) [2728, Satellite
workshop of AQIS2012]
[organized by David Cai, Runyao Duan, Andreas Winter, and me]

2012
Shanghai Conference in Algebraic Combinatorics, Shanghai
JiaoTong University, 1722 August 2012. (Contribute speaker)

2012
SIAM Conference on Applied Linear Algebra, June 18th22nd,
Valencia, Spain. (Invited speaker)

The
2012 South African School and Workshop on Theoretical Aspects of
Quantum Information and Quantum Computing, African Institute for
Mathematical Sciences, AIMS, Cape Town, South Africa. (Lecturer)

First
Cambridge Networks Day, The Sainsbury Laboratory, Cambridge, 18
May. (Invited Speaker)

Kavli
Royal Society International Scientific Centre – Function
Prediction in Complex Networks, 2829 May 2012. (Invited
participant/speaker)

Quantum
Technologies Programme 2012, Cumberland Lodge, Windsor, UK, 24
April, 2012. (Speaker)

BAMC
2012, British Applied Mathematics Colloquium 2012, 2729 March
2012. Minisymposium “Quantum Information”. (Invited
speaker)

Operator
structures in quantum information theory, Banff
International Research
Station
for
Mathematical Innovation and Discovery, Banff, Alberta, Canada, 26
February 2 March, 2012. (Invited participant)

Interdisciplinary
Symposium on Complex Systems, September 1925, 2012, Kos Island,
Greece. (Programme committee) Alan
Turing Year

Joint
Mathematics Meetings, AMS
Special Session on Matrices and Graphs, and AMS
Special Session on Mathematical Theory of Control of Quantum
Systems, John B. Hynes Veterans Memorial Convention Center,
Boston Marriott Hotel, and Boston Sheraton Hotel, Boston, MA,
January 47, 2012. (Invited speaker)

Newton
International Fellowship Day, The Royal Society, 25 October 2011.
(Invited speaker / Q&A panelist)

UCL
Town Meeting – Quantum Information and Quantum Technology,
November 9, 2011. (Programme comittee)

2011
Workshop on Algebraic Combinatorics, 1518 September 2011,
Shanghai JiaoTong University. (Invited speaker)

Quantum
Information Workshop, Benasque, Centro
de Ciencias de Benasque Pedro Pascual, July
2011. (Participant)

Quantum
Information: Codes, Geometry and Random Structures, Centre de
recherches mathematiques (CRM), Montreal, 2426/10, 2011. (Invited
speaker)

14^{th}
Workshop
in Quantum Information Processing, QIP2011,
1014 January, 2011, Singapore. Presentation Pdf
(Contributed talk)

Algebraic
Graph Theory Workshop, Banff
International Research
Station
for
Mathematical Innovation and Discovery, Banff, Alberta, Canada, 2429
April, 2011. (Invited Speaker)

Annual
International Academic Conference on Quantum and Molecular
Computing, QMC 2011,
Singapore, 1516 August 2011. (Technical Committee)

EuroComb'11,
Budapest, August 29September 2, 2011, Rényi Institute.
(Referee)

7th
Slovenian International Conference on Graph Theory, Bled,
Slovenia, June 1924, 2011. Minisymposium: Information Theory of
Graphs (Invited speaker)

5th
AsianPacific Conference on Quantum Information Science, in
conjunction with the Festschrift in honour of Vladimir Korepin,
Singapore, 2528 May 2011. (Programme Committee)

3rd
biennial Canadian Discrete and Algorithmic Mathematics Conference
(CanaDAM) May 31June 3, 2011, University of Victoria, BC, Canada.
(Invited speaker)

Interdisciplinary
Symposium on Complex Systems, 9th International Conference of
Numerical Analysis and Applied Mathematics (ICNAAM), Halkidiki,
Greece, September 1925, 2011. (Programme Committee)

The
6th
Conference
on Theory of Quantum Computation, Communication and Cryptography,
TQC2011, Madrid,
2426 May 2011. (Programme Committee)

The
5th Conference on Theory of Quantum Computation, Communication and
Cryptography, TQC2010,
University of Leeds, 1315 April, 2010. (Cochair of the Programme
Committee together with Wim van Dam)

The
3th Conference on Theory of Quantum Computation, Communication and
Cryptography, TQC2008,
The University of Tokyo, January 301 February, 2008. (Contributed
talk)

International
Program on Quantum Information (IPQI),
Institute of Physics, Bhubaneswar, Orissa, India, Jan 4th30th,
2010. (Invited lecturer)

Collaborative
Research Group for Mathematics of Quantum Information, Pacific
Institute for Mathematics Sciences (PIMS), Vancouver, BC, 20102012.
(Affiliate)

The
19th International Linear Algebra Society Conference, ILAS
2010, Pisa, 2125 June, 2010. Minisymposium: Linear Algebra and
Quantum Information Processing. (Programme Committee)

DocSpot:
Monsters From The Id, The Barbican, London, 26 May 2010. (Q&A
panelist)

AMS
2010 Fall
Southeastern Section Meeting, Richmond, VA, November 67, 2010.
Special
Session on Minimum Rank Problems. (Invited Speaker)

VideoClocks
Workshop, NABA, The New Academy of
Fine Arts, Milan (24 hours workshop), December 2009. (Lecturer with
Giuseppe Ragazzini)

CombPhys
II: "Quantum and Combinatorics" (Zakopane, Poland,
2009). (Invited speaker)

Italian
Quantum Information Science Conference, 2009,
58
November 2009, Scuola Normale Superiore, Pisa, Italy. (Contributed
talk)

Italian
Quantum Information Science Conference, 2008,
2429 October 2008, Palazzo Ducale, Camerino, Italy. (Contributed
talk)

CMS/CSHPM
Summer Meeting 2009. Memorial University of
Newfoundland, St. John's, Newfoundland,
June
6  8, 2009. (Invited speaker: Scientific Session on Algebraic
Combinatorics)

Quantum
Information and Graph Theory: emerging connections, Perimeter
Institute for Theoretical Physics, April
28  May 2, 2008. (Organizing Committee)

Joint
International Meeting of the AMS and Shanghai Math Society,
December
1721, 2008, Shanghai,
Peoples Republic of China. (Invited speaker: Special
Session on Combinatorics and Discrete Dynamical Systems)

Emergent
Gravity, August 2529, 2008, Massachusetts Institute of
Technology / Center for Theoretical Physics.

2007
International Conference on Combinatorial Physics, 2427
November, Krakow, Poland. (Invited speaker)

The
19th International Conference on Formal Power Series and Algebraic
Combinatorics (FPSAC2007), July 26, 2007, Nankai University,
Tianjin, China. (Contributed talk)

QCQC2007,
Centre for Theoretical
Studies, IIT Kharagpur,
India, December
1113, 2007. (Invited speaker)

ERATO
conference on Quantum Information Science 2005, August 2630,
2005  National Museum of Emerging Science and Innovation "Nihon
Kagaku Miraikan", JST, Tokyo, Japan. (Contributed talk)

KIASKAIST
Workshop on Quantum Information Science, Seoul, 2224 August
2005. (Invited speaker)

20th
British Combinatorial Conference
University
of Durham, 1115 July 2005. (Contributed talk)

Rutgers
Experimental Mathematics Seminar, 16 June, 2005, Rutgers
University, Department of Mathematics and
the Center for Discrete Mathematics and Theoretical Computer Science
(DIMACS).
(Invited
speaker; host: Doron
Zeilberger)

The
third conference on permutation patterns (PP2005), May 29–June
3, 2005, University of Haifa, Israel. (Invited speaker)

1st
AsiaPacific Conference on Quantum Information Science, Tainan,
Taiwan, December 1013, 2004. (Invited speaker)

Fifth
Haifa Workshop on Interdisciplinary Applications of Graph
theory, Combinatorics, and Algorithms
(Honoring
Michael O. Rabin), May 1619, 2005, CRI, Haifa, Israel. (Contributed
talk)

The
Third Haifa Workshop on Interdisciplinary Applications of Graph,
Combinatorics, and Algorithms (Honoring Peter Hammer), May
2729, 2003, 2003, CRI, Haifa, Israel. (Contributed talk)

Eurocomb'03,
Prague, Czech Republic, 812 September, 2003. (Contributed talk)
Professional
service
 I
have refereed papers for the following journals. IEEE
Transactions in Information Theory, Information
Processing Letters, Physical
Review Letters, Physical
Review A, Physical
Review E, Physical review
D, Quantum
Information and Computation, Journal
of Physics A: Mathematical and Theoretical, New
Journal of Physics, Physics
Letters A, Physics
Letter B, Physica
A, Physica
D, Journal
of Mathematical Physics, Europhysics
Letters, Chinese
Physics Letters, International
Journal of Theoretical Physics, International
Journal of Quantum Information;

Acta
Mathematica Sinica, Journal
of Difference Equations and Applications, Discrete
Mathematics, Computers
& Mathematics with Applications, Discrete
and Applied Mathematics, Electronic
Journal of Combinatorics, European
Journal of Combinatorics, The
Australasian Journal of Combinatorics, Applicable
Analysis and Discrete Mathematics, Automatica,
Applied
Mathematics Letters,

Journal
of Statistical Mechanics, Journal
of Machine Learning Research, Central
European Journal of Mathematics, Linear
Algebra and its Applications, Pure
Mathematics and Applications, Journal
of Integer Sequences, Nature
Communications, Complex
Adaptive Systems Modeling, Entropy,
Networks,
Scientific Reports,
Mathematical
Programming (Series A), Natural
Computing, Nonlinearity,
PLoS ONE.

Conferences.
International
Colloquium on Automata, Languages and Programming (ICALP), Quantum
Information Processing (QIP), Formal Power Series and Algebraic
Combinatorics Conference (FPSAC), The Asian Conference on Quantum
Information Science (AQIS), European Conference on Combinatorics,
Graph Theory and Applications (EuroComb), IEEE Conference on
Decision and Control.

Editorial
work:
Associate
Editor: Journal of Complex Networks (Oxford University Press),
Associate Editor: International Journal of Computer Mathematics
(Taylor & Francis), Editorial Advisory Board Member: Special
Matrices (Versita / De Gruyter), Review Editor: Frontiers in
Interdisciplinary Physics (Frontiers Media S. A.), Editor: Springer
Lecture Notes in Computer Science (1 proceedings), Editor: World
Scientific (1 multiauthor book), Editor: LIPIcs  Leibniz
International Proceedings in Informatics (1 proceeding), Guest
Editor: International Journal of Modern Physics B, Guest Editor:
Journal of Algebraic Combinatorics.

Grant
reviewer:
Engineering
and Physical Research Council, the Royal Society, US National
Security Agency  American Mathematical Society Grants Scheme,
European Commission  Directorate General for Communications
Networks, Content and Technology Future & Emerging Technologies,
the Research Council of Norway, the Austrian Science Fund,
Netherlands Organisation for Scientific Research, Member of the
Computer Science Evaluation Group at the Natural Sciences and
Engineering Research Council of Canada (20142017).
Notes
 Quantum
information and graphs: In
2008, at the Perimeter
Institute for Theoretical Physics, we organized a conference
titled Quantum
Information and Graph Theory: emerging connections. Below is an
incomplete list of references on this topic (Oct 2011):


Graph
states: R.
Raussendorf, D.E. Browne, H.J. Briegel, Measurementbased quantum
computation with cluster states, Phys. Rev. A 68, 022312 (2003).
arXiv:quantph/0301052v2;
M.
Hein, W. Dür, J. Eisert, R. Raussendorf, M. Van den Nest, H.J.
Briegel, Entanglement in Graph States and its Applications,
Proceedings of the International School of Physics "Enrico
Fermi" on "Quantum Computers, Algorithms and Chaos",
Varenna, Italy, July, 2005. arXiv:quantph/0602096v1

State
transfer on spin systems: M.
Christandl, N. Datta, T. C. Dorlas, A. Ekert, A. Kay, A. J. Landahl,
Perfect
Transfer of Arbitrary States in Quantum Spin Networks, Phys. Rev. A
71, 032312 (2005). arXiv:quantph/0411020v2;
C.
Godsil, State Transfer on Graphs, 2011. arXiv:1102.4898v2
[math.CO]

Quantum
expanders: A.
BenAroya, A. TaShma, Quantum
expanders and the quantum entropy difference problem, 2007.
arXiv:quantph/0702129v3;
A.
W. Harrow, R. A. Low, Efficient Quantum Tensor Product Expanders and
kdesigns, Proceedings of RANDOM 2009, LNCS, 5687:548561, 2009.
arXiv:0811.2597v3
[quantph]

Quantum
walks: D.
Aharonov, A. Ambainis, J. Kempe, U. Vazirani, Quantum
walks on graphs, Proceedings of ACM Symposium on Theory of
Computation (STOC'01), July 2001, p. 5059; A. Ambainis, Quantum
walks and their algorithmic applications, International Journal
of Quantum Information, 1:507518, 2003. arXiv:quantph/0403120v3;
M. Mohseni, P. Rebentrost, S. Lloyd, A. AspuruGuzik.
Environmentassisted
quantum walks in photosynthetic energy transfer, Journal of
Chemical Physics 129, 174106 (2008). arXiv:0805.2741v2
[quantph]; A. M. Childs, Universal
computation by quantum walk, Phys. Rev. Lett. 102, 180501
(2009). arXiv:0806.1972v1
[quantph]

Quantum
graphs: T.
Kottos and U. Smilansky, Quantum
Chaos on Graphs, Phys. Rev. Lett. 79, 4794797, (1997); U.
Smilansky, Quantum chaos on discrete graphs, 2007. arXiv:0704.3525v1
[mathph]

Graphs
of unitary matrices: L.
Deaett, The
minimum semidefinite rank of a trianglefree graph, Linear
Algebra and its Applications 434
(2011), 19451955; T. J. Osborne, Approximate Locality for Quantum
Systems on Graphs, Phys. Rev. Lett. 101, 140503 (2008).
arXiv:quantph/0611231v2

Complexity
metrics: R.
Jozsa, On the simulation of quantum circuits, 2006.
arXiv:quantph/0603163v1;
I. L. Markov, Y. Shi, Simulating quantum computation by contracting
tensor networks, SIAM Journal on Computing, 38(3):963981, 2008.
arXiv:quantph/0511069v7;
D. Aharonov, Z. Landau, J. Makowsky, The quantum FFT can be
classically simulated, 2006, arXiv:quantph/0611156v2

Isomorphism
(via encoding): K.
Audenaert, C. D. Godsil, G. F. Royle, T.
Rudolph,
Symmetric squares of graphs, J. Comb. Theory, Ser. B 97(1): 7490
(2007). arXiv:math/0507251v1
[math.CO]; J. K. Gamble, M. Friesen, D. Zhou, R. Joynt, S. N.
Coppersmith, Twoparticle quantum walks applied to the graph
isomorphism problem.
Phys. Rev. A, 81(5):052313, 2010. arXiv:1002.3003v1
[quantph]

Network
coding: M.
Hayashi, K. Iwama, H. Nishimura, R. Raymond, and S. Yamashita.
Quantum network coding. In STACS 2007, volume 4393 of Lecture Notes
in Computer Science, pages 610–621, 2007.
arXiv:quantph/0601088v2;
D.
Leung, J. Oppenheim, and A.Winter. Quantum network communication —
the butterfly and beyond. IEEE Transactions on Information Theory,
56(7):3478–3490, 2010. arXiv:quantph/0608223v5

Complex
networks: S.
Perseguers, M. Lewenstein, A. Acín, J. I. Cirac,
Quantum
complex networks, Nature Physics 6, 539  543 (2010).
arXiv:0907.3283v1
[quantph]

Graphs
as channels; T. S. Cubitt, D. Leung, W. Matthews, A. Winter,
Improving zeroerror classical communication with entanglement,
Phys. Rev. Lett., 104(23):230503, 2010. arXiv:0911.5300v2
[quantph]; D.
Leung, L. Mancinska, W. Matthews, M. Ozols, A. Roy,
Entanglement
can increase asymptotic rates of zeroerror classical communication
over classical channels, 2010. arXiv:1009.1195v2
[quantph]

Quantum
colouring: C.
Godsil, M. W. Newman, Coloring an Orthogonality Graph, SIAM J.
Discrete Math. 22(2): 683692 (2008). arXiv:math/0509151v1
[math.CO]; J.
Fukawa, Hi. Imai, F. Le Gall, Quantum
Coloring Games via Symmetric SAT Games.
Presented as a long talk at the 11th Asian Quantum Information
Science Conference (AQIS 2011).

Background
independent models of quantum gravity based on timedependent
graphs: A.
Hamma, F. Markopoulou, Background independent condensed matter
models for quantum gravity, New J. Phys. 13:095006, 2011.
arXiv:1011.5754v1
[grqc]; F.
Caravelli, F. Markopoulou, Properties of quantum graphity at low
temperature, Phys. Rev. D 84 024002, 2011. arXiv:1008.1340v3
[grqc]
And
here a list of references that I find useful:
 R.
Penrose, On
the nature of quantum geometry, in Magic
Without Magic,
ed. J. Klauder, Freeman, San Francisco, 1972, pp. 333354.

N.
Linial, Z. Luria, An
upper bound on the number of high dimensional permutations,
arXiv:1106.0649v1
[math.CO]

A.
Ashikhmin, A. Robert Calderbank, W. Kewlin, Multidimensional
Second Order ReedMuller Codes as Grassmannian Packings, ISIT
2006, Seattle, USA, July 9 14, 2006.

P.
Diaconis and J. Salzman, Projection
pursuit for discrete data. IMS Collections Probability and
Statistics: Essays in Honor of David A. Freedman, Vol. 2 (2008)
265–288. arXiv:0805.3043v1
[math.ST]

B.
J. Frey and D. Dueck, Clustering
by Passing Messages Between Data Points, Science
315, 972–976, February 2007. citeseerx.
Software.

D.
Jakobson, S. D.Miller, I. Rivin, Z. Rudnick,
Eigenvalue
spacings for regular graphs, IMA vol. 109 (Emerging applications of
number theory, Minneapolis, MN 1996). arXiv:hepth/0310002v1

S.
M. Pincus, Approximate
entropy as a measure of system complexity,
PNAS March 15, 1991 vol. 88 no. 6 22972301. (See our work
arXiv:1201.0045v1
[condmat.disnn].)

H.
R. Kleinberg, and A. Lehman, On
the capacity of information networks,
IEEE
Transactions on Information Theory, 52(6):2345–2364, 2006.

N.
Goldenfeld, L. P. Kadanoff, Simple
lessons from complexity,
Science
2 April 1999: Vol. 284 no. 5411 pp. 8789.

G.
Tkacik and A M. Walczak, Information transmission in gene regulatory
networks: a review, J. Phys.: Condens. Matter 23 (2011) 153102
(31pp). arXiv:1101.4240v1
[physics.bioph]

E.
Carlstein. Nonparametric
change point estimation, The Annals of Statistics, Vol. 16, No.
1. (1988), pp. 188197.

S.
Janson, D. E. Knuth, T. Łuczak, B. Pittel, The
birth of the giant component, Random Structures Algorithms 4 (1993),
no. 3, 231358. arXiv:math/9310236v1
[math.PR]

D.
Deutsch, Physics,
Philosophy and Quantum Technology
(talk
PDF),
The Sixth International Conference on Quantum Communication,
Measurement and Computing, in Proceedings
of the Sixth International Conference on Quantum Communication,
Measurement and Computing, Shapiro, J.H. and Hirota, O., Eds.
(Rinton Press, Princeton, NJ. 2003).

E.
A. Rietman, R. L. Karp, and J. A Tuszynski, Review
and application of group theory to molecular systems biology,
Theoretical Biology and Medical Modelling 2011, 8:21.

L.
A. Zager, G. C. Verghese, Graph
similarity scoring and matching, Applied Mathematics Letters,
21:1(2008), 8694.

M.
M. Wilde, From Classical to Quantum Shannon Theory, 2011.
arXiv:1106.1445v2
[quantph]

N.
Alon, C. Avin, M. Koucky, G. Kozma, Z. Lotker, M. R. Tuttle, Many
Random Walks Are Faster Than One, Combinatorics, Probability and
Computing (2011), 20 : pp 481502. arXiv:0705.0467v2
[math.PR]

P.
Expert, T. Evans, V. D. Blondel, R. Lambiotte, Beyond Space For
Spatial Networks, PNAS 2011 108 (19) 76637668.

Planar
Separator Theorem: D.
A. Spielman, S.H. Teng (1996), Disk packings and planar separators,
Proc. 12th ACM Symposium on Computational Geometry (SCG '96), pp.
349–358; D. A. Spielman, S.H. Teng (2007), Spectral
partitioning works: Planar graphs and finite element meshes, Linear
Algebra and its Applications 421 (2–3): 284–305,

J.
H. Conway, A. J. Jones, Trigonometric Diophantine equations (On
vanishing sums of roots of unity), Acta Arith. 30 (1976), no. 3,
229240.

B.
Poonen, M. Rubinstein, The Number of Intersection Points Made by the
Diagonals of a Regular Polygon, SIAM
Journal on Discrete Mathematics 11 (1998), no. 1, 135156.
arXiv:math/9508209v3
[math.MG]

P.
Bourgade, J. P. Keating, Quantum
chaos, random matrix theory, and the Riemann zetafunction,
Seminaire Poincare, XIV (2010) 115153.

C.
W. J. Granger, Investigating causal relations by econometric models
and crossspectral methods, Econometrica
37:3
(1969), 424–438.

Y.A.
Kim, S. Wuchty, T. M. Przytycka, Identifying
causal genes and dysregulated pathways in complex disease, PLoS
Comput Biol 7(3): e1001095.

T.
Ideker, N. J. Krogan, Differential
network biology, Molecular Systems Biology 8:565.

T.
Manke, L. Demetrius, and M. Vingron, An
entropic characterization of protein interaction networks and
cellular robustness, J. R. Soc. Interface. 2006 December 22;
3(11): 843–850.

A.
E. Motter, Cascade
control and defense in complex networks, Phys. Rev. Lett. 93,
098701 (2004).

T.
Schreiber, Meauring
information transfer, Phys. Rev. Lett. 85, 461 (2000).

H.
G. Tanner, On
the controllability of nearest neighbor interconnections,
Decision
and Control, 2004. CDC. 43rd IEEE Conference on.

D.
Ruelle, Is
our mathematics natural: The case of equilibrium statistical
mechanics, Bull. Amer. Math. Soc. (N.S.) Volume 19, Number 1
(1988).

J.
Paris, J. and L. Harrington,
A
Mathematical Incompleteness in Peano Arithmetic. In Handbook for
Mathematical Logic (Ed. J. Barwise).
Amsterdam,
Netherlands: NorthHolland, 1977.

M.
Warmuth, A
Bayes Rule
for Density Matrices, In Y. Weiss, B. Schölkopf, and J.
Platt, editors, Advances in Neural Information Processing Systems
18, pages 1457–1464. MIT Press, Cambridge, MA, 2005.

M.
K. Warmuth, D. Kuzmin, Bayesian
Generalized Probability Calculus for Density Matrices, In
Proceedings of the 22^{nd}
Annual
Conference on Uncertainty in Artificial Intelligence, 2006.

S.
Boyd, P. Diaconis, and L. Xiao, Fastest
Mixing Markov Chain on a Graph, SIAM Review, 46(4):667689,
2004.

K.
P. Murphy, An
introduction to graphical models, 2001.

J.
Gunawardena, Six
Lectures on System Biology (Cambridge 2011).

Hedetniemi
conjecture.

J.
Cooper, Graph
Theory Study Guide.

Rotor
Router Model by Jim Propp. The model involves a bug moving along
a directed graph.

Igraph
is
a free software package for creating and manipulating undirected and
directed graphs. Cytoscape
is an open source software platform for visualizing complex
networks. CFinder
is
a free software for finding and visualizing overlapping dense groups
of nodes in networks, based on the Clique Percolation Method (CPM)
of Palla
et. al., Nature
435,
814818
(2005).

S.
Severini, Mathoverflow: Rewiring
graphs.

KONECT
is the Koblenz Network Collection. KONECT is a project to collect
large network datasets of all types in order to perform research in
the area of network mining, collected by the Institute
of Web Science and Technologies of the University
of Koblenz–Landau. (7/2/12)

Mark
Newman Network
Data.

E.
D. Kolaczyk, (2009), Statistical Analysis of Network Data: Methods
and Models. Springer, New York.

Kappalanguage:
A rulebased language for modeling protein interaction networks.

Two
interesting topics in Markov chains analysis: P. Doyle, Kemeny
constant: C. D. Meyer, Stochastic
Complementation.

Smart
Cities: World Economic Forum, Urban
Sustainability. Companies in Smart
Cities.

Subhash
A. Khot, Nisheeth K. Vishnoi, The
Unique Games Conjecture, Integrality Gap for Cut
Problems and Embeddability of Negative Type Metrics into l_1,
2005.

A.
Kavruk, V. I. Paulsen, I. G. Todorov, M. Tomforde, Tensor
products of operator systems.
J.
Funct. Anal.
261
(2011),
no.
2,
267–299.

M.V.
Berry and J.P. Keating The
Riemann zeros and eigenvalue asymptotics, SIAM Review, 41, No. 2
(1999), 236266.

A.
Ferrante, M. Pavon, Matrix
completion à la Dempster by the principle of parsimony, IEEE
Trans. Inform. Theory
57
(2011),
no.
6, 39253931.

Information
System on Graph Classes and their Inclusions.

Yvo
Desmedt, Yongge Wang, Perfectly Secure Message Transmission
Revisited, IEEE Trans. Inform. Theory 54 (2008), 258202595.
arXiv:cs/0208041v1
[cs.CR]

Asu
Ozdaglar: Learning
and dynamics on networks, Acemoglu,
Daron, Munther Dahleh, Ilan Lobel, and Asuman Ozdaglar (2008),
Bayesian
learning in social networks, LIDS Working Paper 2780,
Massachusetts nstitute of Technology.

M.
Agrawal, Axiomatic
/ Postulatory Quantum Mechanics, in Fundamental Physics in
NanoStructured Materials
and Devices (Stanford University, 2008).

R.
Diestel, Graph
Theory, Electronic Edition 2010.

Measuring
Worth, historical data on important economic aggregates, with
particular emphasis on nominal measures.

Hà
Quang Minh, Reproducing
Kernel Hilbert Spaces and Learning Problems on the Hypercube ,
preprint, 2012.

Network
Workbench: A LargeScale Network Analysis, Modeling and
Visualization Toolkit for Biomedical, Social Science and Physics
Research.

Gephi
The Open Graph Viz Platform.

Measuring
complexity (by S. Lloyd): 1.
How hard is it to describe?
Entropy;
Algorithmic
Complexity or Algorithmic Information Content; Minimum Description
Length; Fisher Information; Renyi Entropy; Code Length (prefixfree,
Huffman, ShannonFano, errorcorrecting, Hamming); Chernoff
Information; Dimension; Fractal Dimension; LempelZiv Complexity. 2.
How hard is it to create? Time
Computational Complexity; Space
Computational Complexity; InformationBased Complexity; Logical
Depth; Thermodynamic Depth; Cost; Crypticity. 3.
What is its degree of organization? Metric
Entropy; Fractal Dimension; Excess Entropy; Stochastic
Complexity; Sophistication; Effective Measure Complexity; True
Measure Complexity; Topological epsilonmachine size; Conditional
Information; Conditional Algorithmic Information Content; Schema
length; Ideal Complexity; Hierarchical Complexity; Tree subgraph
diversity; Homogeneous Complexity; Grammatical Complexity.
Algorithmic Mutual Information; Channel Capacity; Correlation;
Stored Information; Organization.

S.
Bhamidi, R. Rajagopal, S. Roch, Network Delay Inference from
Additive Metrics. arXiv:math/0604367v2
[math.PR]

R.
Castro, M. Coates, G. Liang, R. Nowak and B. Yu, Network
Tomography: Recent Developments, Statistical Science, Vol. 19,
No. 3, 499–517, 2004.

GraphCrunch2
is a software tool for network analysis, modelling and alignment.

L.
Lovász, Very
large graphs, Current Developments in Mathematics 2008 (eds. D.
Jerison, B. Mazur, T. Mrowka, W. Schmid, R. Stanley, and S. T. Yau),
International Press, Somerville, MA (2009), 67128.

A.
Clauset, C. R. Shalizi, M. E. J. Newman, Power
law distribution of empirical data, SIAM Review 51, 661703
(2009).

Blonstein,
D. Fahmy, H., and Grbavec, A, (1996), Issues
in the practical use of graph rewriting.

Bioconductor
provides tools for the analysis and comprehension of highthroughput
genomic data.

NetworkX
is a Python language software package for the creation,
manipulation, and study of the structure, dynamics, and functions of
complex networks.

Pajek,
program for large networks analysis.

Guess,
the graph exploration system.

Pegasus,
opensource, graphmining system with massive scalability.

NetLogo
is a multiagent programmable modeling environment.

Massey
Tutorial
on Zeroerror Information Theory, Information Theory Winter
School, La Colle Sur Loup, March 2007.

D.
Zelazo and M. Mesbahi, Graphtheoretic
methods for networked dynamic systems: Heterogeneity and H_{2}
Performance,
in Efficient Modeling and Control of LargeScale Systems (J.
Mohammadpour and K.M. Grigoriadis, eds.), New York, New York:
Springer, pp. 219249.

B.
Chazelle, The
Convergence of Bird Flocking, arXiv:0905.4241v1
[cs.CG]

Arora,
S., Rao, S., and Vazirani, U. 2009., Expander
flows, geometric embeddings and graph partitioning, J. ACM 56,
2, Article 5 (April 2009).

G.
Szabo, G. Fath, Evolutionary
games on graphs, Physics Reports 446 (46), 97217 (2007).

L.
Vinet, A. Zhedanov, Dual 1 Hahn polynomials and perfect state
transfer, arXiv:1110.6477v3
[mathph]

Some
nice
conjectures in algebraic combinatorics by Tewodros Amdeberhan (8
August 2012).

T.
Bu, N. Duffield, F. Lo Presti, D. Towsley, Network
Tomography on General Topology, Proc. of ACM SIGMETRICS 2002.

NetEvo
is a computing framework and collection of enduser tools designed
to allow researchers to investigate evolutionary aspects of
dynamical complex networks.

P.
Malacaria, F. Smeraldi, The
Thermodynamics of Confidentiality, CSF 2012: 280290, 2011.

D.
Aharonov, A. TaShma, Adiabatic Quantum State Generation and
Statistical Zero Knowledge, arXiv:quantph/0301023v2.

B.
Sinaimeri, Structures
of Diversity, PhD Thesis, Sapienza University, Roma, 2009.

B.
D. McKay, Hadamard
equivalence via graph isomorphism, Discrete Math. 27 (1979), no.
2, 213–214.

P.
Schweitzer, Problems of Unknown Complexity, PhD Thesis, Universitat
des Saarlandes, Saarbrucken, 2009.

G.
Haggard, D. J. Pearce, and G. Royle, Computing
Tutte Polynomials, ACM Trans. Math. Softw. 37, 3, Article 24
(September 2010), 17 pages.

M.
Fürer, On
the power of combinatorial and spectral invariants, Linear
Algebra Appl. 432 (2010), no. 9, 2373–2380.

Network
Coding Bibliography

A.
C. Kalloniatis, From
incoherence to synchronicity in the network Kuramoto model,
Phys. Rev. E (3) 82 (2010), no. 6, 066202.

M.
P. Frank, Physical
Limits of Computing, IEEE Computing in Science & Engineering
magazine, May/June 2002.

K.
Tsuda, Machine
learning with quantum relative entropy, International Workshop
on StatisticalMechanical Informatics 2008 (IWSMI 2008).

L.
H. Kauffman, Biologic,
2002.

L.
G. Valiant, Evolvability, ECCC TR06120.

A
beautiful bibliography on the Physics
of Algorithms (Los Alamos National Laboratory).

Y.
Colin de Verdiere, Spectral
Graph Theory (Spectres de Graphes).

A.
Dutta, U. Divakaranb , D. Senc , B. K Chakrabartid , T. F.
Rosenbaume, and G. Aeppli, Quantum phase transitions in transverse
ﬁeld spin models: From Statistical Physics to Quantum
Information, arXiv:1012.0653
[condmat.statmech]

M.
Laurent, Semidefinite
Optimization (great lectures)

Some
of my favourite conjectures: Hadamard
conjecture; Hedetniemi
conjecture; Rosenfeld
conjecture: the Shannon capacity of the complement of the Clebsch
graph is 16^(1/3).

J.
C. Colburn, The
combinatorics of network reliability, Oxford Univ. Press, 1987.

DBPedia.

Writelatex
is good.

A
good lecture on the Ising
model
(Frank
Krauss).

S.
Kauffman, L. Smolin, Combinatorial dynamics in quantum gravity.
arXiv:hepth/9809161

Richard
Feynman's lectures (on enhanced video player platform).

Cook
D. J. and Holder L. B., Mining Graph Data, John Wiley & Sons,
2007.

Sperner
Capacities, 1993.

J.
P. Keating and N. C. Snaith (2003), Random
matrices and Lfunctions, J. Phys. A 36, pp. 28592881.

Lasse
Kiviluoto, Patric R. J. Östergård, and Vesa P.
Vaskelainen. 2009, Sperner
capacity of small digraphs. Advances in Mathematics of
Communications, volume 3, number 2, pages 125133.

Landau,
H.G. (1953), "On dominance relations and the structure of
animal societies. III. The condition for a score structure",
Bulletin of Mathematical Biophysics 15
(2):
143–148. (Landau's Theorem is beautiful)

The
Comprehensive LaTeX
Symbols List (useful)

British
Combinatorial
Bulletin
2013  University of Essex

L.
Lovasz, Information
and complexity (how to measure them?)

R.
L. Cilibrasi,
P. M. B. Vitanyi, Clustering
by compression, IEEE Trans. Information Theory, 51:4(2005),
1523–1545. And I like th

B.
Litow, N. Deo, Graph compression and the zeros of polynomials.
Inform. Process. Lett. 92 (2004), no. 1, 39–44.

P.
M. B. Vitanyi, Compressionbased
Similarity, arXiv:1110.4544
[cs.IT].

P.
M. B. Vitanyi, Meaningful
information, arXiv:cs/0111053
[cs.CC]

F.
Y. Wu, Potts
model and graph theory, J. Stat. Phys., 52, no. 1,2 (1988).

S.
Chen, S. S. Plotkin, Statistical
mechanics of graph models and their implications for emergent
manifolds, Physical Review D, vol. 87, Issue 8, id. 084011.

U.
Feige, M. Langberg ,G. Schechtman, Graphs
with Tiny Vector Chromatic Numbers and Huge Chromatic Numbers,
SIAM J. COMPUT. 2004 , Vol. 33, No. 6, pp. 1338–1368.

I
like Graph
Kernels.

R.
Kondor, N. Shervashidze and K. M. Borgwardt,
The graphlet spectrum (ICML 2009) [pdf]

M.
Arzano, T. W. Kephart, Y. J. Ng, From
spacetime foam to holographic foam cosmology, arXiv:grqc/0605117

Halava,
Vesa; Karhumäki, Juhani; Nowotka, Dirk; Rozenberg, Grzegorz
Words, graphs, automata, and languages: special issue honoring the
60th birthday of Professor Tero Harju. Fund. Inform. 116 (2012), no.
14, vii–viii. 6806.

F.
J. Brandenburg, K. Skodinis, Finite graph automata for linear and
boundary graph languages. Theoret. Comput. Sci. 332 (2005), no. 13,
199–232.

W.
H. Zurek, Decoherence,
einselection, and the quantum origins of the classical, Rev.
Modern Phys. 75 (2003), no. 3, 715–775.

C.
Rigetti, et al. Geometric Approach to Digital Quantum Information,
arXiv:quantph/0312196.
(This contains the same graphs of A.
Ashikhmin, A. Robert Calderbank, W. Kewlin, Multidimensional
Second Order ReedMuller Codes as Grassmannian Packings, ISIT
2006, Seattle, USA, July 9 14, 2006.)

Y.
Choi and W. Szpankowski, Compression of graphical structures, IEEE
Transaction on Information Theory, 58, 2012; also IEEE International
Symposium on Information Theory, Seoul, 364–368, 2009.

Nan
Hu, Leonidas Guibas, Spectral Descriptors for Graph Matching,
arXiv:1304.1572 [cs.CV]

I
like the problem of finding the length of the minimal
superpermutation:
N. Johnston, Nonuniqueness of minimal superpermutations. Discrete
Math. 313 (2013), no. 14, 1553–1557. arXiv:1303.4150
[math.CO]

Final
projects 201314 (COMP3091, COMPM091): 1) A
new measure of complexity for graphs: Perfect
graphs form an important family of graphs. In fact, many hard
problems can be solved efficiently for perfect graphs by using the
ellipsoid method for linear programming or ad hoc combinatorial
techniques. Trivially perfect graphs are a subfamily of perfect
graphs. The project consists on studying a technique to turn a
generic graph into a trivially perfect graph via a sequence of
operations. The minimum number of operations can be interpreted as a
new measure of graph complexity, with potential applications in the
analysis of big data. The project consists on (1) writing a computer
programme to implement the operations and (2) classify graphs
according to the new measure of complexity. 2) A
new measure of similarity for graph: Measures
of similarity for the vertices of a graph are important because they
can help to determine similarity in big data (e.g., members of a
social networks, companies in a large economy, biological data,
etc.). The project consists on (1) writing a computer programme to
implement a new measure of similarity based on a graph distance
introduced by Chartrand, Kubicki, and Schultz in late 90s, (2) apply
the measure to real world data, and (3) check the performance
against other known measures.

Timeseries
of matrices: G. Zumbach, The empirical properties of large
covariance matrices. arXiv:0903.1525
[qfin.ST]

H.
Wilf, Generatingfunctionology.

Map
of Combinatorics in
Korea.

Some
notes for the Fellowship of the Odd Ring (Karol, Michal,
Monika, Ravi, et al.):

F.
Arends, A
Lower Bound on the Size of the Smallest KochenSpecker Vector System
in Three Dimensions, Master Thesis, Oxford, 2009. (This contains
the gadget we are interested on and the proof of minimality.)

E.
R. Scheinerman, D. H. Ullman, Fractional
graph theory, 2008. (Very detailed overview including the
fractional chromatic number.)

V.
Lozin, Graph
Theory Notes, 2012(?). (Great basic intro to graphs.)

The
Network Coding Home Page

Hillary
S. W. Han, Thomas J. X. Li, Christian M. Reidys, Combinatorics
of $\ gamma
$structures.

This
a conjecture from: D. Emms, S. Severini, R. Wilson, E. Hancock,
A matrix representation of graphs and its spectrum as a graph
invariant, The Electronic Journal of Combinatorics, R34, Volume
13(1), 2006. arXiv:quantph/0505026v2
[See also K. J. Guo, Quantum Walks on Strongly Regular Graphs,
Master Dissertation, University of Waterloo, 2010.] But then there
is (at least) this paper by Jamie Smith
http://arxiv.org/pdf/1103.0262v1.pdf
“Cellular Algebras and Graph Invariants Based on Quantum
Walks” that kills the problem in the general case.

Lovasz
Conjecture: Every finite connected vertextransitive
graph contains a Hamiltonian path.

Hedetniemi
Conjecture: The chromatic number of the Kronecker product of two
graphs is the smallest between their chromatic numbers.

Positive
Semidefinite Minimum Rank (PSMR) Conjecture (for the complement):
The PSMR of a graph plus the PSMR of its complement are no larger
than the number of vertices plus 2.

The
independence number project (Craig Larson, Patrick Gaskill).

Index
Coding: Local graph
coloring and index coding; Linear
index coding via semidefinite programming; The
rate of index coding;
R.
M. Gray and A. D. Wyner, “Source coding for a simple network,”
Bell System Technical Journal, vol. 53, no. 9, pp. 1681–1721,
November 1974.

Perfect
sorting by reversals is interesting (Mathilde Bouvel, Cedric
Chauve, Marni Mishna and Dominique Rossin).

I
like this talk: The
giant component of a random subgraph of a given graph, Linyuan
Lu, 2011.

The
Quantum Pontiff and other blogs: Bits
of DNA, Schroedinger's
Rat, What's new
(the Prince of mathematical blogs), The
polymath blog, ShtetlOptimized.

The
CV
of Leonardo da Vinci.

Open
problem: Minimizing
the gate length in a logic circuit (5/2/14)

G.
Grimmett, The RandomCluster Model, 2003. arXiv:math/0205237v2
[math.PR]

O.
Weiss, M. A. JimenezMontano. H.
P. Herzel, Information
Content of Protein Sequences,
J. Theor. Biol. (2000) 206, 379—386.

Stringology:
A.
Apostolico and Z. Galil, editors, Pattern
Matching Algorithms,
Oxford University Press, New York, 1997, 377 pages. M. Crochemore,
C. Hancart et T. Lecroq, Algorithmique
du texte,
Vuibert, Paris, 2001, 347 pages. M. Crochemore and W. Rytter, Text
Algorithms,
Oxford University Press, New York, 1994, 412 pages. D. Gusfield,
Algorithms
on Strings, Trees, and Sequences,
Cambridge University Press, New York, 1997, 534 pages. W. F. Smyth,
Computing
Patterns in Strings,
AddisonWesley, 2002. G.A. Stephen, String
Searching Algorithms,
World Scientific Publishing Co., 1994, 243 pages.

J.
Spencer, Nine
Lectures on Random Graphs.

D.
Sculley and Carla E. Brodley, Compression
and Machine Learning: A New Perspective on Feature Space Vectors.

How
journals like Nature,
Cell and
Science
are
damaging science: The incentives offered by top journals distort
science, just as big bonuses distort banking

P.
Di Francesco, Integrable
combinatorics, ICMP2012.

Bioconductor,
Open Source Software for Bioinformatics.

"A
scientist should be judged not by his (papers) prizes or other
honours bestowed upon him, but by the quality of the people he has
helped to produce. Let these works speak for themselves."
(Brenner); “Mathematics is the art of giving the same name to
different things: Politics is the art of giving different names to
the same thing.” (Severi).
Mohammad
Bavarian, Peter W. Shor, Information Causality, SzemerédiTrotter
and Algebraic Variants of CHSH, arXiv:1311.5186
[quantph]
D.
Stahlke, Entanglement
and interference resources in quantum computation and communication,
PhD Thesis, Carnegie Mellon University, July 2014.
(Congratulations!)
I
like this book: Information,
physics, and computation (2008).
Miscellanea
 Computational
complexity: learning resources. Tim
Gowers – Computational
Complexity and Quantum Computation, 12 Graduate Levels Lectures,
Cambridge 2009 (video). Luca Trevisan, Lecture
notes on computational complexity, 2002. Computational
Complexity: A Modern Approach, by Arora and Barak. Moni Naor,
Complexity
theory, 2005. "The sprawling web of known relations among
complexity classes", link
to the zoo. Michael Garey and David Johnson: Computers and
Intractability  A Guide to the Theory of NPcompleteness; Freeman,
1979. Hopcroft, Ullman and Motwani,
Introduction to Automata Theory, Languages, and Computation (second
edition), AddisonWesley, 2001 website.
Christos
Papadimitriou, Elements of the theory of computation
(PrenticeHall 1982, with Harry Lewis, second edition September
1997). Lance Fortnow's Computational
Complexity Web Log. Chee
K. Yap: Introduction to Complexity Classes.

Zeroerror
(reprise): Xiaodong
Xu, Stanisław Radziszowski, Bounds
on Shannon capacity and Ramsey numbers for products of graphs,
IEEE Transactions on Information Theory, 59(8) (2013) 47674770. A.
Vesel, J. Zerovnik, Improved
lower bounds on the Shannon capacity of C_7,
Information
Processing Letters, Volume 81, Issue 5, 16 March 2002, Pages
277–282.

CFI
graphs: Descriptive complexity: Graceful labelings:

Graph
limits: Borgs,
Christian; Chayes, Jennifer; Lovász, László;
Sós, Vera T.; Vesztergombi, Katalin Counting graph
homomorphisms. Topics in discrete mathematics, 315–371,
Algorithms Combin., 26, Springer, Berlin, 2006. Borgs,
Christian; Chayes,
Jennifer; Lovász,
László; Sós,
Vera T.; Szegedy,
Balázs; Vesztergombi,
Katalin Graph limits and parameter testing. STOC'06:
Proceedings of the 38th Annual ACM Symposium on Theory of Computing,
261–270,
ACM,
New York, 2006.
Diaconis,
Persi; Holmes,
Susan; Janson,
Svante Threshold graph limits and random threshold graphs.
Internet
Math. 5
(2008),
no.
3, 267–320 (2009). Lovász,
László Large networks and graph limits. American
Mathematical Society Colloquium Publications, 60. American
Mathematical Society, Providence, RI, 2012.
Bollobás,
Béla; Janson,
Svante; Riordan,
Oliver Monotone graph limits and quasimonotone graphs. Internet
Math. 8
(2012),
no.
3, 187–231. Janson,
Svante Quasirandom graphs and graph limits. European
J. Combin. 32
(2011),
no.
7, 1054–1083. A talk
at IAS by Lovász.