
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] 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. And the seminal paper:
M.V.Berry, Riemann's
zeta function: A model for quantum chaos,
in Quantum Chaos and Statistical Nuclear Physics, T.H. Seligman and
H. Nishioka, eds., Lecture Notes in Phys. 263, SpringerVerlag, New
York, 1986, pp. 117. 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. 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). Hadwiger–Nelson
problem; The Crossing Number of the Complete Graph; Adam's
conjecture. 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. 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. 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!). CP projects at CoMPLEX should be written in
LaTeX. A good introduction to LaTeX is "Essential
LaTeX" . I like this book: Information,
physics, and computation (2008). Compressed
fulltext indexes. D. Kovach, The computational theory of
intelligence, Dec 2014. arXiv:1412.7978
[cs.AI] (interesting philosophical perspective). M. Laurent,
Networks
and semidefinite programming, Lecture notes, 2013. A. Bookatz,
QMAcomplete
problems, 2012. M. Otto, Finite
model theory, Lecture notes 2005. R. Milo, N. Kashtan, S.
Itzkovitz, M. E. J. Newman, U. Alon, On the uniform generation of
random graphs with prescribed degree sequences,
arXiv:condmat/0312028v2
[condmat.statmech] 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. Antonina
Kolokolova lecture
notes. 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. Graceful
labelings: Kernels: Cubelike graphs: Graph representations: (A
fundamental problem of computer science is to determine the relative
efficiencies of different data structures for representing a given
problem (Rivest & Vuillemin, 1976). Homomorphisms:
Graph
drawing: 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. Ramsey
numbers:
H. Haanpaa, Computational
Methods for Ramsey Numbers, Helsinki University of Technology
Report, 65, 2000. M. Lauria ,P. Pudlak, V. Rodl, N. Thapen, The
complexity of proving that a graph is Ramsey, ICALP2013. Very
nice: G. Brinkmann, K. Coolsaet, J. Goedgebeur, and H. Melot, House
of graphs, a database of interesting graphs, Discrete Applied
Mathematics, 161 (2013), 311314. hog.grinvin.org.
Other
references: A. M. Childs, D. Gosset, Z. Webb, The
BoseHubbard model is QMAcomplete, ICALP14. [It also contains a
result about the XY Hamiltonian; recall that QMP is a plausible
quantum analogue of NP; Arnoldi]. D. Murfet, Logic
and linear algebra: an introduction, Jul 2014. A. Alzaga, R.
Iglesias, R. Pignol, Spectra
of symmetric powers of graphs and the WeisfeilerLehman refinements,
Journal of Combinatorial Theory, Series B 100 (2010), 671682.
http://arxiv.org/abs/0801.2322v1.
Course
on combinatorial games in finite model theory by Phokion Kolaitis.
P. Wocjan, S. Zhang, Several natural BQPcomplete problems,
arXiv:quantph/0606179
[It shows that QWGT is BQPcomplete]. E.
Knill and R. Laflamme,”Quantum
Computing and Quadratically Signed Weight Enumerators”,
Information Processing Letters 79 (4) pp. 1731 79, 2001 [It
introduces the QWGT – also it contains a beautiful link
between probabilistic and quantum computation. M. Muzychuk and I.
Ponomarenko, Association
schemes, Schur rings and the isomorphism problem for circulant
graphs. Part 1. D. Lidar, On
the quantum computational complexity of the Ising spin glass
partition function and of knot invariants, 2004 New J. Phys. 6
167. [Link between the QWGT and the spinglass partition function]
M. Grohe, The
quest for a logic capturing PTIME, 2008. [Fixed points logic
with nondeterministic choice operators?]. Quantum
computing and polynomial equations over Z_2. Maybe looking at
the logic there...K. Eickmeyer, M. Grohe, Ramdomization
and derandomization in descriptive complexity, LMCS (2011). [An
attempt to capture BPP; inexpressibility result for other classes?].
R. Fagin, Easier
ways to win logical games, 1997. [Use of EFgames to prove
inexpressibility results]. This is an interesting logic:
http://www.joshuasack.info/papers/qpdsol.pdf.
Y.K. Liu, M. Christandl, F. Verstraete, Nrepresentability
is QMAcomplete, Phys. Rev. Lett. 98, 110503 (2007) [an
interesting QMAcomplete problem]. M. Grohe, Equivalence
in finitevariable logics is complete for polynomial time,
Combinatorica 19:507532, 1999. [great result about Pcompleteness
of testing equivalence]. N.
Immerman, E. Lander, Describing
graphs: A firstorder approach to graph canonization, In
Complexity Theory Retrospective, pages 5981. SpringerVerlag,
1990. [fundamental result about C_k]. M.
Grohe, M. Otto, Pebble games and linear equations, arXiv:1204.1990
[cs.LO]. R.
O’Donnell, J. Wright, C. Wu, and Y.
Zhou. Hardness of
Robust Graph Isomorphism, Lasserre Gaps, and Asymmetry of Random
Graphs, chapter 120, pages 1659–1677. 201. Fagin's
Theorem: Anuj
Dawar lecture notes and more
general notes.
http://www.csc.kth.se/~lauria/sos14/lecturenotes/lecture9.pdf.
L. Hella. Logical hierarchies in PTIME. In Proceedings
of the 6th IEEE Symposium on Logic in Computer Science pages
360–368, 1992. M.
Mladenov, K. Kirsting, Lifted
inference via klocality, 2013. [Good description of the links
between WL and SA]. M. Fürer, On
the power of combinatorial and spectral invariants, Linear
Algebra Appl. 432 (2010), no. 9, 2373–2380. Luitpold
Babel, Irina V. Chuvaeva, Mikhail Klin, Dmitrii V. Pasechnik,
Algebraic
Combinatorics in Mathematical Chemistry. Methods and Algorithms. II.
Program Implementation of the WeisfeilerLeman Algorithm, 1997.
A. Dawar, On
tractable approximations of graph isomorphism, 2014. M. Furer,
WeisfeilerLehman
Renement Requires at Least a Linear Number of Iterations, ICALP
2001. C.
Berkholz, P. Bonsma, M. Grohe, Tight
Lower and Upper Bounds for the Complexity
of Canonical Colour Refinement, ESA 2013. Coarsest
partition problem. Quantum
spin glasses. Lovely
notes on graph theory by Vadim Lozin. P. Hell, Pavol; J.
Nešetřil, The core of a graph. Algebraic graph theory
(Leibnitz, 1989). Discrete Math. 109 (1992), no. 13, 117–126.
Three problems: color refinement; coarsest equitable partition;
floyd algorithm for collisions; VC dimension; graceful labelings;
Ulam's reconctruction conjecture:
http://www.automata.rwthaachen.de/~grohe/cap/all.pdf
http://en.wikipedia.org/wiki/Reconstruction_conjecture
http://folk.uio.no/taralgs/artikler/hovedfag.pdf
http://www.cs.yale.edu/homes/spielman/PAPERS/SGTChapter.pdf
http://pefmath2.etf.rs/files/117/860.pdf
http://vcp.med.harvard.edu/papers/matrices2.pdf
http://wwwlp.fmf.unilj.si/plestenjak/papers/nicegr.pdf
http://www.sciencedirect.com/science/article/pii/S0304397501003036
http://www.jmlr.org/papers/volume12/shervashidze11a/shervashidze11a.pdf.
ke.c. property: Bonato's
review. GI
(nice). XiaoDong Zhang, A
survey of laplacian eigenvalues. Crossing
numbers of the complete graph: history. RichterSalazar,
Crossing
numbers (2008). Parking
functions, by Richard Stanley. Tree
bijections, by Igor Pak. SVM,
by Tristan Fletcher. Spectacular notes on “Quantum Proofs”
by Vidick and Watrous: https://arxiv.org/pdf/1610.01664v1.pdf.
Entanglement and nonlocality course by Vern Paulsen:
http://www.math.uwaterloo.ca/~vpaulsen/EntanglementAndNonlocality_LectureNotes_7.pdf
(very useful to learn about games/graphs/nonlocality). Good review
on the Clique
Problems. 2016: T. Gartner, A
survey of kernels for structured data. R. Hamming, You
and your research. Two beautiful paper: . R. Caianiello,
Combinatorics and renormalization in quantum field theory, Frontiers
in Physics, W. A. Benjamin, Inc., ReadingLondonAmsterdam, 1973. L.
Faddeev, Yu. Reshetikhin, Tacktajan, Quantization of Lie groups and
Lie algebras, Algebraic analysis, Vol. I, pp. 129–139,
Academic Press, Boston, MA, 1988. X.D. Zhang, The
Laplacian eigenvalues of graphs: a survey, 2011. S. Bravyi, D.
Gosset, Improved
classical simulation of quantum circuits dominated by Clifford
gates, 2016. M. Y. Vardi, Database
Queries – Logic and Complexity. B. Rosgen, Hard
quantum problems. Very nice review: Quantum
Hamiltonian Complexity. Nov 2017. General
purpose computation with neural networks, Optimal
simulation of automata by neural nets, Efficient
Sampling for Bipartite Matching Problems, Invariant
scattering convolutional networks, Mathematical
Foundations of Supervised Learning, Differential
Privacy: a short tutorial, Tighter
PACBayes bounds through distributiondependent priors. Provable
Bounds for Learning Some Deep Representations, Going
deeper with convolutions, PACBayesian
Supervised Classification: The Thermodynamics of Statistical
Learning, Generalization
of Quantum Fourier Transformation, Determinant
versus permanent, Learning
in linear neural networks: a survey, Solutions
of the Two Dimensional Hubbard Model: Benchmarks and Results from a
Wide Range of Numerical Algorithms, On
the learnability of discrete distributions, On
Learning FiniteState Quantum Sources, The
probabilistic method in combinatorics (nice lecture notes),
Universal
semantic communication I, A
global geometric framework for nonlinear dimensionality reduction
Jan
2018. Physical
limits of inference, Semantics
and Thermodynamics, Unitary
Evolution Recurrent Neural Networks, An
Introduction to Matrix Concentration Inequalities,
Multiresolution
Matrix Compression, Effective
Tensor Sketching via Sparsification, Faster
Algorithms via Approximation Theory, Analyzing
the Approximation Error of the Fast Graph Fourier Transform,
Complexity
classification of twoqubit commuting hamiltonians, Quantum
Simulation of Electronic Structure with Linear Depth and
Connectivity, A
quantum algorithm providing exponential speed increase for finding
eigenvalues and eigenvectors, Towards
quantum simulation with circular Rydberg atoms, Matrix
Exponential, A
compressed classical description of quantum states, Learning
rotations with little regret, A
Metric Between Probability Distributions on Finite Sets of Different
Cardinalities and Applications to Order Reduction, Breaking
the 49Qubit Barrier in the Simulation of Quantum Circuits,
Simulation of
quantum random walks using interference of classical field