May 2013 - talks - lists.cs.princeton.edu

V Yao generals
by Melissa M. Lawson 16 May '13

16 May '13

Vicky Yao will present her research seminar/general exam on Monday May 20 at 10AM in Room 402. The members of her committee are: Olga Troyanskaya (advisor), Mona Singh, and John Storey (MOL). Everyone is invited to attend her talk, and those faculty wishing to remain for the oral exam following are welcome to do so. Her abstract and reading list follow below. ----- Original Message ----- Abstract: Integration of genomics data has already been shown to be helpful in improving our understanding of functional relationships between genes in a wide range of organisms, including yeast, worm, mouse, and human. As the quantity of these datasets increases, we are presented with the opportunity not only in improving functional predictions between genes, but also in attempting to attack this difficult problem of understanding functional relationships in tissue-specific contexts, with the eventual goal of developing a better understanding of alternative splicing and isoform expression in different tissues. We create tissue-specific functional networks in C. elegans by utilizing knowledge of already curated tissue-specific genes in our integration of available genomics data using Bayesian learning methods. By extending our tissue-specific functional predictions in genes to differentially spliced exons and leveraging known protein domain interaction data, we hope to be able to predict potential tissue-specific protein interactions. These predictions would be extremely useful for improving our understanding of tissue-specific processes. Reading list: Introduction to Machine Learning (second edition) by Ethem Alpaydin Ch 1 Introduction Ch 2 Supervised Learning Ch 3 Bayesian Decision Theory Ch 4 Parametric Methods Ch 5 Multivariate Methods Ch 8 Nonparametric Methods Ch 10 Linear Discrimination Ch 14 Bayesian Estimation Ch 17 Combining Multiple Learners Ch 19 Design and Analysis of Machine Learning Experiments Papers: Anders S, Huber W (2010) Differential expression analysis for sequence count data. Genome Biology 11:R106. Anders S, Reyes A, Huber W (2012) Detecting differential usage of exons from RNA-seq data. Genome Research 22: 2008-2017. Bossi A, Lehner B (2009) Tissue specificity and the human protein interaction network. Mol Syst Biol 5: 260. Buljan M, Chalancon G, Eustermann S, Wagner GP, Fuxreiter M, Bateman A, Babu MM (2012) Tissue-specific splicing of disordered segments that embed binding motifs rewires protein interaction networks. Mol Cell 46(6): 871-83. Chikina MD, Huttenhower C, Murphy CT, Troyanskaya OG (2009) Global Prediction of Tissue-Specific Gene Expression and Context-Dependent Gene Networks in Caenorhabditis elegans. PLoS Comput Biol 5(6): e1000417. Guan Y, Gorenshteyn D, Burmeister M, Wong AK, Schimenti JC, Handel MA, Bult CJ, Hibbs MA, Troyanskaya OG (2012) Tissue-specific functional networks for prioritizing phenotype and disease genes. PLoS Comput Biol 8(9): e1002694. Kim D, Pertea G, Trapnell C, Pimentel H, Kelley H, Salzberg SL (2013) TopHat2: accurate alignment of transcriptomes in the presence of insertions, deletions and gene fusions. Genome Biology 14:R36. Li Y, Breitling R, Snoek BL, van der Velde KJ, Swertz MA, Riksen J, Jansen RC, Kammenga JE (2010) Global Genetic Robustness of the Alternative Splicing Machinery in Caenorhabditis elegans . Genetics 186: 405-410. Merkin J, Russel C, Chen P, Burge CB (2012) Evolutionary Dynamics of Gene and Isoform Regulation in Mammalian Tissues. Science 338(6114): 1593-9. Wang ET, Sandberg R, Luo S, Khrebtukova I, Zhang L, Mayr C, Kingsmore SF, Schorth GP, Burge CB (2008) Alternative isoform regulation in human tissue transcriptomes. Nature 456: 470-476.

1 0

Prof. Radu Teodorescu, Seminar today at 12:30 in CS402.
by Margaret Martonosi 14 May '13

14 May '13

Reminder that Prof. Radu Teodorescu will be giving a seminar today at 12:30 in CS402. > Designing Energy-Efficient Microprocessors in the Era of Unpredictable Transistors > > ABSTRACT: > Energy efficiency is now a principal design constraint across all computing markets - from supercomputers to smartphones. Performance growth in these markets can only be sustained going forward through significant improvements in the energy efficiency of computation. A very effective approach to improving microprocessor energy efficiency is to lower supply voltage to very close to the transistor's threshold voltage, into the so-called near-threshold region. Near-threshold operation reduces energy consumption by an order of magnitude but comes at the cost of reduced frequency, degraded reliability and increased parameter variability. > > In this talk I will describe hardware and software co-design techniques that address and alleviate the challenges of low-voltage computing, bringing it closer to commercial feasibility. These include techniques for reducing the effects of process and voltage variability and a new approach for runtime reduction of voltage margins prototyped in a state-of-the-art server processor. > > BIO: > Radu Teodorescu is an Assistant Professor in the Department of Computer Science and Engineering at The Ohio State University where he leads the Computer Architecture Research Lab. He received his PhD from University of Illinois at Urbana-Champaign in 2008. His research interests include computer architecture with a focus on energy efficient microprocessor design and the impact of technology scaling on reliability and process variability. He received a CAREER award from the National Science Foundation in 2012, the W. J. Poppelbaum award from University of Illinois in 2008 and an Intel Fellowship in 2007. Margaret Martonosi Hugh Trumbull Adams '35 Professor of Computer Science Princeton University http://www.princeton.edu/~mrm mrm(a)princeton.edu

1 0

M Homilius general exam
by Melissa M. Lawson 10 May '13

10 May '13

Max Homilius will present his research seminar/general exam on Friday March 17 at 10AM in Room 302 (note room!). The members of his committee are: Olga Troyanskaya (advisor), Mona Singh, and Tom Funkhouser. Everyone is invited to attend his talk and those faculty wishing to remain for the oral exam following are welcome to do so. His abstract and reading list follow below. ---------------------- Abstract ======== Classical pharmacological approaches for the identification of new drug candidates often follow a one disease - one target - one drug paradigm. At the same time, there is little knowledge about the specific mode of action for many compounds and the principles underlying interactions between multiple drugs. I developed a machine learning approach for the prediction of synergistic drug pairs for fungicidal and anti-cancer compounds. This approach takes into account the effects of a compound on multiple target genes that are part of complex biological network, and combines experimental results from different large-scale studies to improve predictions. In addition, I constructed functional networks specific to non-steroidal anti-inflammatory drugs. Measures of differential expression and coexpression of genes after drug treatment were reconciled with these networks and are predictive of the mode of action of the administered drug. Reading list ========== [1] Ethem Alpaydin (2004). Introduction to Machine Learning. First edition. MIT Press. Ch 1 Introduction Ch 2 Supervised Learning Ch 3 Bayesian Decision Theory Ch 4 Parametric Methods Ch 5 Multivariate Methods Ch 8 Nonparametric Methods Ch 10 Linear Discrimination Ch 14 Assessing and Comparing Classification Algorithms Ch 15 Combining Multiple Learners [2] Aryee, M. J., Gutiérrez-Pabello, J. a, Kramnik, I., Maiti, T., & Quackenbush, J. (2009). An improved empirical bayes approach to estimating differential gene expression in microarray time-course data: BETR (Bayesian Estimation of Temporal Regulation). BMC bioinformatics, 10, 409. [3] Cokol, M., Chua, H. N., Tasan, M., Mutlu, B., Weinstein, Z. B., Suzuki, Y., Nergiz, M. E., et al. (2011). Systematic exploration of synergistic drug pairs. Molecular systems biology, 7(544), 544. [4] Dawson, J. a, & Kendziorski, C. (2012). An empirical Bayesian approach for identifying differential coexpression in high-throughput experiments. Biometrics, 68(2), 455–65. [5] Grosser, T., Fries, S., & FitzGerald, G. (2006). Biological basis for the cardiovascular consequences of COX-2 inhibition: therapeutic challenges and opportunities. Journal of Clinical Investigation, 116(1). [6] Jansen, G., Lee, A. Y., Epp, E., Fredette, A., Surprenant, J., Harcus, D., Scott, M., et al. (2009). Chemogenomic profiling predicts antifungal synergies. Molecular systems biology, 5(338), 338. [7] Laenen, G., Thorrez, L., Börnigen, D., & Moreau, Y. (2013). Finding the targets of a drug by integration of gene expression data with a protein interaction network. Molecular BioSystems. [8] Nitsch, D., Gonçalves, J. P., Ojeda, F., De Moor, B., & Moreau, Y. (2010). Candidate gene prioritization by network analysis of differential expression using machine learning approaches. BMC bioinformatics, 11(2007), 460. [9] Poirel, C. L., Rahman, A., Rodrigues, R. R., Krishnan, A., Addesa, J. R., & Murali, T. M. (2013). Reconciling differential gene expression data with molecular interaction networks. Bioinformatics, 29(5), 622–9. [10] Wong, A. K., Park, C. Y., Greene, C. S., Bongo, L. a, Guan, Y., & Troyanskaya, O. G. (2012). IMP: a multi-species functional genomics portal for integration, visualization and prediction of protein functions and networks. Nucleic acids research, 40, W484–90.

1 1

J Fix general exam
by Melissa M. Lawson 10 May '13

10 May '13

Jordan Fix will present his research seminar/general exam on Thursday May 16 at 10AM in Room 402. The members of his committee are: David August (advisor), David Wentzlaff (ELE), and Andrew Appel. Everyone is invited to attend his talk and those faculty wishing to remain for the oral exam following are welcome to do so. His abstract and reading list follow below. ----------------------------- Abstract: The emergence of multicore architectures necessitates new techniques such as transactional memory (TM) to gain performance without burdening programmers. This talk presents the first evaluation of a hardware multi-threaded transactional (MTX) memory system and improves upon prior proposed designs. MTX enables more diverse parallelization schemes than traditional TM systems which restrict transactions to a single thread, limiting their applicability. Prior software-based MTX memory systems require extra book keeping threads and instructions to manage speculative memory, imposing more overhead than a hardware-based implementation. The proposed hardware MTX memory system employs new transactional instructions, adds new cache state, and is implemented on top of a snoopy MOESI cache coherence protocol, allowing transactions spanning multiple threads to determine their state by snooping coherence messages. Reading List: Textbooks: • J. L. Hennessy and D. A. Patterson. Computer Architecture: A Quantitative Approach. Morgan Kaufmann, San Francisco, CA, 1996 • A. W. Appel. Modern Compiler Implementation in ML. Cambridge University Press, 1998 Papers: • Maurice Herlihy and J. Eliot B. Moss. 1993. Transactional memory: architectural support for lock-free data structures. In Proceedings of the 20th annual international symposium on computer architecture (ISCA '93) • S. Gopal, T. Vijaykumar, J. Smith, and G. Sohi. 1998. Speculative Versioning Cache. In Proceedings of the 4th International Symposium on High-Performance Computer Architecture (HPCA '98). • Lance Hammond, Vicky Wong, Mike Chen, Brian D. Carlstrom, John D. Davis, Ben Hertzberg, Manohar K. Prabhu, Honggo Wijaya, Christos Kozyrakis, and Kunle Olukotun. 2004. Transactional Memory Coherence and Consistency. In Proceedings of the 31st annual international symposium on Computer architecture (ISCA '04). • Nir Shavit and Dan Touitou. 1995. Software transactional memory. In Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing (PODC '95). • Arun Raman, Hanjun Kim, Thomas R. Mason, Thomas B. Jablin, and David I. August. 2010. Speculative parallelization using software multi-threaded transactions. In Proceedings of the fifteenth edition of ASPLOS on Architectural support for programming languages and operating systems (ASPLOS XV). • N. Vachharajani. Intelligent Speculation for Pipelined Multithreading. PhD thesis, Department of Computer Science, Princeton University, Princeton, New Jersey, United States, November 2008. • J. Greggory Steffan, Christopher B. Colohan, Antonia Zhai, and Todd C. Mowry. 2000. A scalable approach to thread-level speculation. In Proceedings of the 27th annual international symposium on Computer architecture (ISCA '00) • María Jesús Garzarán, Milos Prvulovic, José María Llabería, Víctor Viñals, Lawrence Rauchwerger, and Josep Torrellas. 2005. Tradeoffs in buffering speculative memory state for thread-level speculation in multiprocessors. ACM Transactions on Architecture and Code Optimization (TACO '05). • James R. Goodman. 1983. Using cache memory to reduce processor-memory traffic. In Proceedings of the 10th annual international symposium on Computer architecture (ISCA '83). • P. Sweazey and A. J. Smith. 1986. A class of compatible cache consistency protocols and their support by the IEEE futurebus. In Proceedings of the 13th annual international symposium on Computer architecture (ISCA '86).

1 0

P Prabhu FPO
by Melissa M. Lawson 09 May '13

09 May '13

Prakash Prabhu will present his FPO on Thursday May 16 at 2PM in Room 402. The members of his committee are: David August, advisor; David Walker and JP Singh, readers; Kai Li and Margaret Martonosi, nonreaders. A copy of his thesis, "Semantic Language Extensions for Implicit Parallel Programming", is on display in Room 310. Everyone is invited to attend his talk.

1 0

F Yu general exam
by Melissa M. Lawson 07 May '13

07 May '13

Fisher Yu will present his research seminar/general exam on Tuesday May 14 at 2PM in Room 402. The members of his committee are: Tom Funkhouser (advisor), Szymon Rusinkiewicz, and Adam Finkelstein. Everyone is invited to attend his talk and those faculty wishing to remain for the oral exam following are welcome to do so. His abstract and reading list follow below. --------------------- Abstract: City scale reconstruction is gaining more and more attention these years driven by its popularity in consumer market. It can help people get familiar with a new place without physically being there. Nowadays, people can view the 3D city models from aerial view or check the panorama images of the street. However, although the street level virtual scene can give the users an immersed experience in the virtual environment, the technology to build large scale detailed 3D textured models is still not mature enough for the customers. In this project, we make use of both laser range scanning and images from Google Street View project to recover the 3D shapes and their texture by combining the sparse shape information of the range scans and detailed texture information of the images. As we are working towards the goal, there are mainly three problems we need to solve, namely, adjusting pose estimation, increase the resolution of the scans, and fill the holes in the regions the scanners failed to reach. To adjust the pose estimation, we build a framework to optimize the laser and image poses together. Also, we can optimize the scan point positions and their subdivided mesh by considering both photo consistency and scan measurement. Our methods can now work on a number of sample environments. Reading List: Szeliski, R. (2010). Computer vision: Algorithms and applications. Springer-Verlag New York Inc. Musialski, P., Wonka, P., Aliaga, D. G., Wimmer, M., Van Gool, L., & Purgathofer, W. (2012). A Survey of Urban Reconstruction. Eurographics 2012 - State of the Art Reports. Triggs, B., McLauchlan, P. F., Hartley, R. I., & Fitzgibbon, A. W. (2000). Bundle Adjustment — A Modern Synthesis. Vision Algorithms: Theory and Practice Furukawa, Y., & Ponce, J. (2010). Accurate, Dense, and Robust Multiview Stereopsis. Pattern Analysis and Machine Intelligence Furukawa, Y., Curless, B., Seitz, S. M., & Szeliski, R. (2010). Towards Internet-scale multi-view stereo. Computer Vision and Pattern Recognition Snavely, N., Seitz, S. M., & Szeliski, R. (2007). Modeling the World from Internet Photo Collections. International Journal of Computer Vision Kazhdan, M., & Hoppe, H. (2013). Screened Poisson Surface Reconstruction. ACM Transactions on Graphics . Lowe, D. G. (2004). Distinctive Image Features from Scale-Invariant Keypoints. International Journal of Computer Vision Pollefeys, M., Nistér, D., Frahm, J., Akbarzadeh, A., Mordohai, P., Clipp, B., Engels, C., et al. (2007). Detailed Real-Time Urban 3D Reconstruction from Video. International Journal of Computer Vision Seitz, S. M., Curless, B., Diebel, J., Scharstein, D., & Szeliski, R. (2006). A Comparison and Evaluation of Multi-View Stereo Reconstruction Algorithms. Computer Vision and Pattern Recognition Hernández, C., & Vogiatzis, G. (2010). Shape from photographs : a multi-view stereo pipeline. Computer Vision Studies in Computational Intelligence Sorkine, O. (2005). Laplacian mesh processing. Eurographics 2005 - State of the Art Reports

1 0

Talk: Implications of Non Volatile Memory on Software Architectures- Tues. May 7, 12pm
by Nicole E. Wagenblast 07 May '13

07 May '13

Implications of Non Volatile Memory on Software Architectures Nisha Talagala , Fusion-io Tuesday, May 7, 2013, 12:00pm Computer Science 402 Flash based non volatile memory is revolutionizing data center architectures, improving application performance by bridging the gap between DRAM and disk. Future non volatile memories promise performance even closer to DRAM. While flash adoption in industry started as disk replacement, the past several years have seen data center architectures change to take advantage of flash as a new memory tier in both servers and storage. This talk covers the implications of nonvolatile memory on software. We describe the stresses that non volatile memory places on existing application and OS designs, and illustrate optimizations to exploit flash as a new memory tier. Until the introduction of flash, there has been no compelling reason to change the existing operating system storage stack. We will describe the technologies contained in the upcoming Fusion-io Software Developer Kit (ioMemory SDK) that allow applications to leverage the native capabilities of non-volatile memory as both an I/O device and a memory device. The technologies described will include new I/O based APIs and libraries to leverage the ioMemory Virtual Storage Layer, as well as features for extending DRAM into flash for cost and power reduction. Finally, we describe Auto-Commit-Memory, a new persistent memory type that will allow applications to combine the benefits of persistence with programming semantics and performance levels normally associated with DRAM. Nisha Talagala is Lead Architect at Fusion-io, where she works on innovation in non volatile memory technologies and applications. Nisha has more than 10 years of expertise in software development, distributed systems, storage, I/O solutions, and non-volatile memory. She has worked as technology lead for server flash at Intel - where she led server platform non volatile memory technology development and partnerships. Prior to Intel, Nisha was the CTO of Gear6, where she developed clustered computing caches for high performance I/O environments. Nisha also served at Sun Microsystems, where she developed storage and I/O solutions and worked on file systems. Nisha earned her PhD at UC Berkeley where she did research on clusters and distributed storage. Nisha hold more than 30 patents in distributed systems, networking, storage, performance and non-volatile memory

2 1

Prof. Radu Teodorescu, Seminar on May 14
by Margaret Martonosi 07 May '13

07 May '13

Hello--- Prof. Radu Teodorescu from Ohio State will be visiting on Tuesday May 14 and giving a lunchtime seminar in CS402. (Noon lunch, followed by 12:30 seminar). The title and abstract are below. If you are interested in a one-on-one meeting with Radu, please either sign up on the google doc visitors spreadsheet: https://docs.google.com/spreadsheet/ccc?key=0AgeypYYNTzO8dEhneUxHV0Q3eEJQUj… Or let me know your scheduling constraints between 11am and 6pm, and I will grab a one-on-one slot for you. Thanks, Margaret > Designing Energy-Efficient Microprocessors in the Era of Unpredictable Transistors > > ABSTRACT: > Energy efficiency is now a principal design constraint across all computing markets - from supercomputers to smartphones. Performance growth in these markets can only be sustained going forward through significant improvements in the energy efficiency of computation. A very effective approach to improving microprocessor energy efficiency is to lower supply voltage to very close to the transistor's threshold voltage, into the so-called near-threshold region. Near-threshold operation reduces energy consumption by an order of magnitude but comes at the cost of reduced frequency, degraded reliability and increased parameter variability. > > In this talk I will describe hardware and software co-design techniques that address and alleviate the challenges of low-voltage computing, bringing it closer to commercial feasibility. These include techniques for reducing the effects of process and voltage variability and a new approach for runtime reduction of voltage margins prototyped in a state-of-the-art server processor. > > BIO: > Radu Teodorescu is an Assistant Professor in the Department of Computer Science and Engineering at The Ohio State University where he leads the Computer Architecture Research Lab. He received his PhD from University of Illinois at Urbana-Champaign in 2008. His research interests include computer architecture with a focus on energy efficient microprocessor design and the impact of technology scaling on reliability and process variability. He received a CAREER award from the National Science Foundation in 2012, the W. J. Poppelbaum award from University of Illinois in 2008 and an Intel Fellowship in 2007. Margaret Martonosi Hugh Trumbull Adams '35 Professor of Computer Science Princeton University http://www.princeton.edu/~mrm mrm(a)princeton.edu

1 0

H Luo general exam
by Melissa M. Lawson 06 May '13

06 May '13

Haipeng Luo will present his research seminar/general exam on Monday May 13 at 2PM in Room 402. The members of his committee are: Rob Schapire, Sebastien Bubeck (ORFE), and Moses Charikar. Everyone is invited to attend his talk and those faculty wishing to remain for the oral exam following are welcome to do so. His abstract and reading list follow below. ----- Original Message ----- Title : Online Learning with Unknown Time Horizon Abstract : We consider online learning when the time horizon T is unknown. We apply a minimax analysis, beginning with the fixed horizon case, and then moving on to two unknown-horizon settings, one that assumes the horizon is chosen randomly according to some known distribution, and the other which allows the adversary full control over the horizon. For the random horizon setting with restricted losses, we derive a fully optimal minimax algorithm. And for the adversarial horizon setting, we prove a nontrivial lower bound which shows that the adversary obtains strictly more power than when the horizon is fixed and known. Based on the minimax solution of the random horizon setting, we then propose a new adaptive algorithm which “pretends” that the horizon is drawn from a distribution from a special family, but no matter how the actual horizon is chosen, the worst-case regret is bounded by O(sqrt(T*lnN)), where N is the number of actions. Furthermore, the constant in our regret bound approaches 1, which is better than the best previously known bound for this setting (as far as we know). Moreover, our algorithm can be generalized to other games, such as predicting with expert advice. Reading List : Textbooks: 1. Mehryar Mohri, Afshin Rostamizadeh and Ameet Talwalkar. Foundations of Machine Learning. MIT Press, 2012. 2. Nicolo Cesa-Bianchi and Gabor Lugosi. Prediction, Learning, and Games (Chapter 2,4,6,7). Cambridge University Press, 2006. Papers: 3. Jacob Abernethy and Manfred K. Warmuth. Repeated games against budgeted adversaries. In Advances in Neural Information Processing Systems 24, 2010. 4. Jacob Abernethy, Manfred K. Warmuth, and Joel Yellin. Optimal strategies from random walks. In Proceedings of the 21st Annual Conference on Learning Theory, 2008. 5. Jacob Abernethy, Alekh Agarwal, Peter L. Bartlett, Alexander Rakhlin. A Stochastic View of Optimal Regret through Minimax Duality. arXiv:0903.5328, 2009. 6. Peter Auer, Nicolo Cesa-Bianchi, and Claudio Gentile. Adaptive and self-conﬁdent on-line learning algorithms. Journal of Computer and System Sciences, 64(1):48–75, 2002. 7. Nicolo Cesa-Bianchi, Yoav Freund, David P. Helmbold, David Haussler, Robert E. Schapire, and Manfred K. Warmuth. How to use expert advice. Journal of the ACM, 44(3):427–485, May 1997. 8. Kamalika Chaudhuri, Yoav Freund, and Daniel Hsu. A parameter-free hedging algorithm. arXiv:0903.2851, 2009. 9. Yoav Freund and Robert E. Schapire. Adaptive game playing using multiplicative weights. Games and Economic Behavior, 29:79–103, 1999. 10. David Haussler, Jyrki Kivinen, and Manfred K. Warmuth. Sequential prediction of individual sequences under general loss functions. IEEE Transactions on Neural Networks, 10(6):1291–1304, 1999. 11. Nick Littlestone and Manfred Warmuth. The weighted majority algorithm. In 30th Annual Symposium on Foundations of Computer Science, pages 256–261, 1989. 12. Alexander Rakhlin, Ohad Shamir, Karthik Sridharan. Relax and Randomize: From Value to Algorithms. arXiv:1204.0870, 2012. 13. V. G. Vovk. A game of prediction with expert advice. Journal of Computer and System Sciences, 56(2):153–173, April 1998.

1 0

K Edwards general exam
by Melissa M. Lawson 06 May '13

06 May '13

Katherine Edwards will present her research seminar/general exam on Friday May 10 at 2PM in room 302. The members of her committee are: Paul Seymour (Math) advisor, Moses Charikar, and Mark Braverman. Everyone is invited to attend her talk and those faculty wishing to remain for the oral exam following are welcome to do so. Her abstract and reading list follow below. ----------------------------- Edge-coloring 7- and 8-regular planar graphs In 1974, Seymour conjectured the following: Let G be a k-regular planar (multi)graph, such that for every odd set X of vertices of G, at least k edges of G have one end in X and the other in V (G) nX. Then G is k-edge-colorable. For k = 3 this is equivalent to the four-color theorem. The cases k = 4; 5 were solved by Guenin, the case k = 6 by Dvorak, Kawarabayashi and Kral, and the case k = 7 by Edwards and Kawarabayashi. In joint work with Chudnovsky and Seymour, we now have a proof for the case k = 8, and that is the topic of this talk. Reading list [1] Paolo Codato, Michele Conforti, and Claudia Sera ni. Packing t-joins. Journal of Graph Theory, 22(4):293{296, 1996. [2] WJ Cook, WH Cunningham, WR Pulleyblank, and A Schrijver. Combinatorial Opti- mization. 1998. New York, NY: Wiley-Interscience. [3] Bertrand Guenin. Packing t-joins and edge colouring in planar graphs. 2003. [4] Penny Haxell and Jessica McDonald. On characterizing vizing's edge colouring bound. Journal of Graph Theory, 69(2):160-168, 2012. [5] Takao Nishizeki and Kenichi Kashiwagi. On the 1.1 edge-coloring of multigraphs. SIAM Journal on Discrete Mathematics, 3(3):391-410, 1990. [6] Neil Robertson, Daniel Sanders, Paul Seymour, and Robin Thomas. The four-colour theorem. Journal of Combinatorial Theory, Series B, 70(1):2 -44, 1997. [7] P.D. Seymour. The matroids with the max-flow min-cut property. Journal of Combina- torial Theory, Series B, 23(2-3):189-222, 1977. [8] P.D. Seymour. On multi-colourings of cubic graphs, and conjectures of fulkerson and tutte. Proc. London Math. Soc, 38(3):423-460, 1979. [9] P.D. Seymour. On odd cuts and plane multicommodity flows. Proceedings of the London Mathematical Society, 3(1):178-192, 1981.

1 0