Simone Severini's Homepage

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, Measurement-based quantum computation with cluster states, Phys. Rev. A 68, 022312 (2003). arXiv:quant-ph/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:quant-ph/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:quant-ph/0411020v2; C. Godsil, State Transfer on Graphs, 2011. arXiv:1102.4898v2 [math.CO]. Quantum expanders: A. Ben-Aroya, A. Ta-Shma, Quantum expanders and the quantum entropy difference problem, 2007. arXiv:quant-ph/0702129v3; A. W. Harrow, R. A. Low, Efficient Quantum Tensor Product Expanders and k-designs, Proceedings of RANDOM 2009, LNCS, 5687:548-561, 2009. arXiv:0811.2597v3 [quant-ph]. 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. 50-59; A. Ambainis, Quantum walks and their algorithmic applications, International Journal of Quantum Information, 1:507-518, 2003. arXiv:quant-ph/0403120v3; M. Mohseni, P. Rebentrost, S. Lloyd, A. Aspuru-Guzik. Environment-assisted quantum walks in photosynthetic energy transfer, Journal of Chemical Physics 129, 174106 (2008). arXiv:0805.2741v2 [quant-ph]; A. M. Childs, Universal computation by quantum walk, Phys. Rev. Lett. 102, 180501 (2009). arXiv:0806.1972v1 [quant-ph]. Quantum graphs: T. Kottos and U. Smilansky, Quantum Chaos on Graphs, Phys. Rev. Lett. 79, 4794-797, (1997); U. Smilansky, Quantum chaos on discrete graphs, 2007. arXiv:0704.3525v1 [math-ph]. Graphs of unitary matrices: L. Deaett, The minimum semidefinite rank of a triangle-free graph, Linear Algebra and its Applications 434 (2011), 1945-1955; T. J. Osborne, Approximate Locality for Quantum Systems on Graphs, Phys. Rev. Lett. 101, 140503 (2008). arXiv:quant-ph/0611231v2. Complexity metrics: R. Jozsa, On the simulation of quantum circuits, 2006. arXiv:quant-ph/0603163v1; I. L. Markov, Y. Shi, Simulating quantum computation by contracting tensor networks, SIAM Journal on Computing, 38(3):963-981, 2008. arXiv:quant-ph/0511069v7; D. Aharonov, Z. Landau, J. Makowsky, The quantum FFT can be classically simulated, 2006, arXiv:quant-ph/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): 74-90 (2007). arXiv:math/0507251v1 [math.CO]; J. K. Gamble, M. Friesen, D. Zhou, R. Joynt, S. N. Coppersmith, Two-particle quantum walks applied to the graph isomorphism problem. Phys. Rev. A, 81(5):052313, 2010. arXiv:1002.3003v1 [quant-ph]. 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:quant-ph/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:quant-ph/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 [quant-ph]. Graphs as channels; T. S. Cubitt, D. Leung, W. Matthews, A. Winter, Improving zero-error classical communication with entanglement, Phys. Rev. Lett., 104(23):230503, 2010. arXiv:0911.5300v2 [quant-ph]; D. Leung, L. Mancinska, W. Matthews, M. Ozols, A. Roy, Entanglement can increase asymptotic rates of zero-error classical communication over classical channels, 2010. arXiv:1009.1195v2 [quant-ph]. Quantum colouring: C. Godsil, M. W. Newman, Coloring an Orthogonality Graph, SIAM J. Discrete Math. 22(2): 683-692 (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 time-dependent graphs: A. Hamma, F. Markopoulou, Background independent condensed matter models for quantum gravity, New J. Phys. 13:095006, 2011. arXiv:1011.5754v1 [gr-qc]; F. Caravelli, F. Markopoulou, Properties of quantum graphity at low temperature, Phys. Rev. D 84 024002, 2011. arXiv:1008.1340v3 [gr-qc] R. Penrose, On the nature of quantum geometry, in Magic Without Magic, ed. J. Klauder, Freeman, San Francisco, 1972, pp. 333-354. 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 Reed-Muller 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:hep-th/0310002v1. S. M. Pincus, Approximate entropy as a measure of system comple xity, PNAS March 15, 1991 vol. 88 no. 6 2297-2301. (See our work arXiv:1201.0045v1 [cond-mat.dis-nn].). 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. 87-89. 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.bio-ph]. E. Carlstein. Non-parametric change point estimation, The Annals of Statistics, Vol. 16, No. 1. (1988), pp. 188-197. S. Janson, D. E. Knuth, T. Łuczak, B. Pittel, The birth of the giant component, Random Structures Algorithms 4 (1993), no. 3, 231-358. 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), 86-94. M. M. Wilde, From Classical to Quantum Shannon Theory, 2011. arXiv:1106.1445v2 [quant-ph] 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 481-502. arXiv:0705.0467v2 [math.PR]. P. Expert, T. Evans, V. D. Blondel, R. Lambiotte, Beyond Space For Spatial Networks, PNAS 2011 108 (19) 7663-7668. 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, 229--240. 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, 135-156. arXiv:math/9508209v3 [math.MG]. P. Bourgade, J. P. Keating, Quantum chaos, random matrix theory, and the Riemann zeta-function, Seminaire Poincare, XIV (2010) 115-153. 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, Springer-Verlag, New York, 1986, pp. 1-17. C. W. J. Granger, Investigating causal relations by econometric models and cross-spectral 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: North-Holland, 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):667-689, 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, 814-818 (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 rule-based 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), 236-266. A. Ferrante, M. Pavon, Matrix completion à la Dempster by the principle of parsimony, IEEE Trans. Inform. Theory 57 (2011), no. 6, 3925-3931. Information System on Graph Classes and their Inclusions. Yvo Desmedt, Yongge Wang, Perfectly Secure Message Transmission Revisited, IEEE Trans. Inform. Theory 54 (2008), 25820-2595. 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 Nano-Structured 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 Large-Scale 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 (prefix-free, Huffman, Shannon-Fano, error-correcting, Hamming); Chernoff Information; Dimension; Fractal Dimension; Lempel-Ziv Complexity. 2. How hard is it to create? Time Computational Complexity; Space Computational Complexity; Information-Based 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 epsilon-machine 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), 67-128. A. Clauset, C. R. Shalizi, M. E. J. Newman, Power law distribution of empirical data, SIAM Review 51, 661-703 (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 high-throughput 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, open-source, graph-mining system with massive scalability. NetLogo is a multi-agent programmable modeling environment. Massey Tutorial on Zero-error Information Theory, Information Theory Winter School, La Colle Sur Loup, March 2007. D. Zelazo and M. Mesbahi, Graph-theoretic methods for networked dynamic systems: Heterogeneity and H₂ Performance, in Efficient Modeling and Control of Large-Scale Systems (J. Mohammadpour and K.M. Grigoriadis, eds.), New York, New York: Springer, pp. 219-249. 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 (4-6), 97-217 (2007). L. Vinet, A. Zhedanov, Dual -1 Hahn polynomials and perfect state transfer, arXiv:1110.6477v3 [math-ph]. 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 end-user tools designed to allow researchers to investigate evolutionary aspects of dynamical complex networks. P. Malacaria, F. Smeraldi, The Thermodynamics of Confidentiality, CSF 2012: 280-290, 2011. D. Aharonov, A. Ta-Shma, Adiabatic Quantum State Generation and Statistical Zero Knowledge, arXiv:quant-ph/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 Statistical-Mechanical Informatics 2008 (IW-SMI 2008). L. H. Kauffman, Biologic, 2002. L. G. Valiant, Evolvability, ECCC TR06-120. 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 [cond-mat.stat-mech]. 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:hep-th/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 L-functions, J. Phys. A 36, pp. 2859-2881. 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 125-133. 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, Compression-based 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:gr-qc/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. 1-4, vii–viii. 68-06. F. J. Brandenburg, K. Skodinis, Finite graph automata for linear and boundary graph languages. Theoret. Comput. Sci. 332 (2005), no. 1-3, 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:quant-ph/0312196. (This contains the same graphs of A. Ashikhmin, A. Robert Calderbank, W. Kewlin, Multidimensional Second Order Reed-Muller 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, Non-uniqueness of minimal superpermutations. Discrete Math. 313 (2013), no. 14, 1553–1557. arXiv:1303.4150 [math.CO] Final projects 2013-14 (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. Time-series of matrices: G. Zumbach, The empirical properties of large covariance matrices. arXiv:0903.1525 [q-fin.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 Kochen-Specker 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:quant-ph/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 vertex-transitive 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, Shtetl-Optimized. The CV of Leonardo da Vinci. Open problem: Minimizing the gate length in a logic circuit (5/2/14). G. Grimmett, The Random-Cluster Model, 2003. arXiv:math/0205237v2 [math.PR]. O. Weiss, M. A. Jimenez-Montano. 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, Addison-Wesley, 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édi-Trotter and Algebraic Variants of CHSH, arXiv:1311.5186 [quant-ph]. 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 full-text 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, QMA-complete 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:cond-mat/0312028v2 [cond-mat.stat-mech] 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 NP-completeness; Freeman, 1979. Hopcroft, Ullman and Motwani, Introduction to Automata Theory, Languages, and Computation (second edition), Addison-Wesley, 2001 website. Christos Papadimitriou, Elements of the theory of computation (Prentice-Hall 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. Zero-error (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) 4767-4770. 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 Quasi-random 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), 311-314. hog.grinvin.org. Other references: A. M. Childs, D. Gosset, Z. Webb, The Bose-Hubbard model is QMA-complete, 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 Weisfeiler-Lehman refinements, Journal of Combinatorial Theory, Series B 100 (2010), 671-682. http://arxiv.org/abs/0801.2322v1. Course on combinatorial games in finite model theory by Phokion Kolaitis. P. Wocjan, S. Zhang, Several natural BQP-complete problems, arXiv:quant-ph/0606179 [It shows that QWGT is BQP-complete]. E. Knill and R. Laflamme,”Quantum Computing and Quadratically Signed Weight Enumerators”, Information Processing Letters 79 (4) pp. 173-1 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 spin-glass partition function] M. Grohe, The quest for a logic capturing PTIME, 2008. [Fixed points logic with non-deterministic 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 EF-games to prove inexpressibility results]. This is an interesting logic: http://www.joshuasack.info/papers/qpdsol.pdf. Y.-K. Liu, M. Christandl, F. Verstraete, N-representability is QMA-complete, Phys. Rev. Lett. 98, 110503 (2007) [an interesting QMA-complete problem]. M. Grohe, Equivalence in finite-variable logics is complete for polynomial time, Combinatorica 19:507-532, 1999. [great result about P-completeness of testing equivalence]. N. Immerman, E. Lander, Describing graphs: A first-order approach to graph canonization, In Complexity Theory Retrospective, pages 59--81. Springer-Verlag, 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 k-locality, 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 Weisfeiler-Leman Algorithm, 1997. A. Dawar, On tractable approximations of graph isomorphism, 2014. M. Furer, Weisfeiler-Lehman 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. 1-3, 117–126. Three problems: color refinement; coarsest equitable partition; floyd algorithm for collisions; VC dimension; graceful labelings; Ulam's reconctruction conjecture: http://www.automata.rwth-aachen.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/matrices-2.pdf http://www-lp.fmf.uni-lj.si/plestenjak/papers/nicegr.pdf http://www.sciencedirect.com/science/article/pii/S0304397501003036 http://www.jmlr.org/papers/volume12/shervashidze11a/shervashidze11a.pdf. k-e.c. property: Bonato's review. GI (nice). Xiao-Dong Zhang, A survey of laplacian eigenvalues. Crossing numbers of the complete graph: history. Richter-Salazar, 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 non-locality course by Vern Paulsen: http://www.math.uwaterloo.ca/~vpaulsen/EntanglementAndNonlocality_LectureNotes_7.pdf (very useful to learn about games/graphs/non-locality). 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., Reading-London-Amsterdam, 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 PAC-Bayes bounds through distribution-dependent priors. Provable Bounds for Learning Some Deep Representations, Going deeper with convolutions, PAC-Bayesian 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 Finite-State 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 two-qubit 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 49-Qubit Barrier in the Simulation of Quantum Circuits, Simulation of quantum random walks using interference of classical field