CanaDAM 2011 Université de Victoria, 31 mai - 3 juin 2011 www.smc.math.ca//2011f

# Horaire - Minisymposiums invités

Veuillez noter que l'horaire peut être modifié sans préavis, surtout s'il s'agit de modifications à l'intérieur d'une session.

 Algebraic Combinatorics (IM6) Org: Mike Zabrocki (York University) This minisymposia will have speakers who research areas of algebra and combinatorics. Topics might include representation theory, algebra and symmetric functions and the use of combinatorial tools to solve problems in these areas. vendredi 3 juin 10:10 - 10:35 Kurt Luoto (University of British Columbia), Quasisymmetric and noncommutative Schur functions, Cornett A121 10:40 - 11:05 Sara Faridi (Dalhousie University), Resolutions of monomial ideals, Cornett A121 11:10 - 11:35 Adriano Garsia (University of California San Diego), Combinatorial properties of Parking Functions and Diagonal Harmonics, Cornett A121 11:40 - 12:05 Angela Hicks (University of California San Diego), Parking Function Properties Suggested by the Haglund-Morse-Zabrocki Conjecture, Cornett A121 12:10 - 12:35 Nantel Bergeron (York University), An Hopf Monoid of supercharacter, Cornett A121 Bioinformatics (IM3) Org: Miklos Csuros (University of Montreal) The mini-symposium addresses current problems in the mathematics of molecular sequence analysis. Advanced technologies for sequencing DNA and proteins drive increasingly more comprehensive studies about the diversity of molecular sequences across living organisms. Talks in this mini-symposium touch on fundamental mathematical and algorithmic issues arising at different stages along the analysis pipeline between sequence data production and their biological applications. mercredi 1er juin 15:15 - 15:40 Cedric Chauve (Simon Fraser University), Mapping ancestral genomes with massive gene loss: a matrix sandwich problem, Cornett A121 15:45 - 16:10 Lucian Ilie (University of Western Ontario), Fast combinatorial computation of good seeds for genome alignment, Cornett A121 16:15 - 16:40 Bin Ma (University of Waterloo), Algorithms for Protein/Peptide Sequencing with Mass Spectrometry, Cornett A121 16:45 - 17:10 Paul Medvedev (University of California San Diego / University of Toronto), Paired de Bruijn Graphs: a Novel Approach for Incorporating Mate Pair Information into Genome Assemblers, Cornett A121 17:15 - 17:40 Juraj Stacho (Caesarea Rothschild Institute, University of Haifa), Unique perfect phylogeny is NP-hard, Cornett A121 Combinatorial Optimization (IM1) Org: Mohit Singh (McGill University) Combinatorial optimization problems usually come in two flavours, ones that can be solved in polynomial time and others that are NP-hard. This session will feature recent developments on problems from both classes. For the former, the talks will present fast algorithms for some fundamental combinatorial optimization problems. For the problems that are NP-hard, the talks will present approximation algorithms that are efficient and solve the problem approximately with a good guarantee on the solution. mardi 31 mai 10:10 - 10:35 Bruce Shepherd (McGill University), Maximum Edge Disjoint Paths, Cornett A121 10:40 - 11:05 Dan Golovin (California Institute of Technology), Adaptive Submodularity: A New Approach to Active Learning and Stochastic Optimization, Cornett A121 11:10 - 11:35 Tom McCormick (University of British Columbia), A Combinatorial Polynomial Algorithm for Weighted Abstract Cut, Cornett A121 11:40 - 12:05 Glencora Borradaile (Oregon State University), Finding all min st-cuts in planar graphs, Cornett A121 12:10 - 12:35 Guyslain Naves (McGill University, Montreal), Mader-Mengerian graphs (joint work with Vincent Jost, École Polytechnique, France)., Cornett A121 Computational Complexity (IM7) Org: Venkatesh Srinivasan (University of Victoria) Computational complexity is a central field of research in theoretical computer science that focuses on classifying computational problems based on the amount of resources they require. Examples of such resources include time, space, communication, amount of randomness and so on. This field has introduced many interesting computational models to study such problems and has been the source of amazing results in the recent years leading to a deeper understanding of the power and limitations of efficient computation. vendredi 3 juin 10:10 - 10:35 Paul Beame (University of Washington), Making Branching Programs Oblivious Requires Superlogarithmic Overhead, Cornett A120 10:40 - 11:05 Valerie King (University of Victoria), Scalable Distributed Computing Using Averaging Samplers and Bit-fixing Random Sources, Cornett A120 11:10 - 11:35 David Kirkpatrick (University of British Columbia), Finding treasure in trees, Cornett A120 11:40 - 12:05 Anup Rao (University of Washington), Towards Coding for Maximum Errors in Interactive Communication, Cornett A120 12:10 - 12:35 Venkatesh Srinivasan (University of Victoria), Rewriting of Visibly Pushdown Languages for XML Data Integration, Cornett A120 Cryptography (IM2) Org: Bruce Kapron (University of Victoria) There are a now a variety of well-founded mathematical approaches to understanding security in cryptographic systems. Techniques from algorithms and computational complexity, formal logic, and information theory have all been successfully used in providing a more rigorous foundation for the study of cryptography. This minisymposium will explore cryptographic security from these varied perspectives. mardi 31 mai 15:15 - 15:40 Bruce Kapron (University of Victoria), Co-induction and Computational Semantics for Public-key Encryption with Key Cycles, Cornett A121 15:45 - 16:10 Yassine Lakhnech (Université Joseph Fourier (Grenoble 1)), Computational Indistinguishability Logic, Cornett A121 16:15 - 16:40 Rei Safavi-Naini (University of Calgary), cryptographic keys from noisy channels, Cornett A121 16:45 - 17:10 Andre Scedrov (University of Pennsylvania), Bounded memory Dolev-Yao adversaries, Cornett A121 Discrete and Computational Geometry (IM8) Org: Binay Bhattacharya (Simon Fraser University) vendredi 3 juin 15:15 - 15:40 Caoan Wang (Memorial University of Newfoundland), A note on Hamiltonian tetrahedralizations, Cornett A121 15:45 - 16:10 Ladislav Stacho (Simon Fraser University), Problems on Geometric Graphs, Cornett A121 16:15 - 16:40 David Kirkpatrick (University of British Columbia), Polygonal paths of bounded curvature, Cornett A121 16:45 - 17:10 Sue Whitesides (University of Victoria), Approaches to Hard (and Potentially Deep and Wet) Problems in Computational Geometry, Cornett A121 17:15 - 17:40 Binay Bhattacharya (Simon Fraser University), Application of computational geometry to network location problems, Cornett A121 Extremal Graph Theory (IM4) Org: Penny Haxell (University of Waterloo) Extremal graph theory can be described as the study of how global properties of a graph can guarantee the existence of local substructures. A classical example is the theorem of Turán, which tells us the maximum number of edges that a graph with $n$ vertices can have, if it does not contain a complete subgraph with $r$ vertices. Many natural questions can be formulated as extremal graph problems, and the subject has developed into a rich theory. Applications abound in many fields, including number theory, optimization, theoretical computer science, economics, hardware design, and optical networks. jeudi 2 juin 10:10 - 10:35 M. DeVos (Simon Fraser University), Edge Expansion, Cornett A121 10:40 - 11:05 A. Kostochka (University of Illinois at Urbana-Champaign), Packing hypergraphs with few edges, Cornett A121 11:10 - 11:35 D. Mubayi (University of Illinois at Chicago), Lower bounds for the independence number of hypergraphs, Cornett A121 11:40 - 12:05 O. Pikhurko (Carnegie Mellon University), Turan function of even cycles, Cornett A121 12:10 - 12:35 J. Verstraete (University of California at San Diego), Recent progress on bipartite Turan numbers, Cornett A121 Probabilistic Combinatorics (IM5) Org: Tom Bohman et Po-Shen Loh (Carnegie Mellon University) Probabilistic Combinatorics stands at the intersection of several thriving areas of Mathematics and Computer Science. It focuses on the combinatorial properties of random discrete objects (e.g., random graphs), and their potential applications to other branches of Mathematics. This mini-symposium will highlight a variety of recent advances in the field. We also intend to use this forum to make state of the art probabilistic techniques available to a broader audience. jeudi 2 juin 15:15 - 15:40 Louigi Addario-Berry (McGill University), The second eigenvalue of random lifts, Cornett A121 15:45 - 16:10 Kevin Costello (Georgia Institute of Technology), On Randomizing Derandomized Greedy Algorithms, Cornett A121 16:15 - 16:40 Po-Shen Loh (Carnegie Mellon University), Rainbow Hamilton cycles in random graphs, Cornett A121 16:45 - 17:10 Bruce Reed (McGill University), Bounding $\chi$ as a convex combination of $\omega$ and $\Delta +1$, Cornett A121 17:15 - 17:40 Jacob Fox (MIT), Graph regularity and removal lemmas, Cornett A121