Logo

Mathematical Sciences Research Institute

Home » Workshop on Topological Methods in Combinatorics, Computational Geometry, and the Study of Algorithms

Workshop

Workshop on Topological Methods in Combinatorics, Computational Geometry, and the Study of Algorithms October 02, 2006 - October 06, 2006
Registration Deadline: September 25, 2006 about 8 years ago
To apply for Funding you must register by: July 02, 2006 over 8 years ago
Parent Program: Computational Applications of Algebraic Topology
Organizers G. Carlsson, P. Diaconis, R. Jardine, and G. M. Ziegler
Speaker(s)

Show List of Speakers

Description

In the twenty-seven years since Lovász solved the Kneser conjecture by an ingenious application of the Borsuk-Ulam theorem, the general area of topological methods in combinatorial, discrete-geometric and algorithmic problems has developed into a strikingly effective body of technique. The range of problems treated, and the variety of tools brought into play are still expanding: equivariant obstruction theory, homology theory, configuration spaces and fixed-point theorems and a great variety of other topics are utilized in applications, for example, to graph coloring problems, partition problems, and in data compression for meshes. Modern homotopy theory is also starting to appear in language design and the development of models for concurrent behaviour of systems. In this workshop, we will discuss recent successes in the application of topological methods in combinatorics, discrete and computational geometry, and algorithms. We also expect to learn more about the tools that can lead to further, future successes. Making the important developments in this area understandable will be a fundamental goal of the meeting. Schedule with Abstracts

Program

Monday, October 2 9:00 am: Herbert Edelsbrunner (Duke University): An introduction to topological persistence 10:30 am: Alex Suciu (Northeastern University): Fundamental group computations in the theory of arrangements and related spaces 2:00 pm: Dmitry Feichtner-Kozlov (ETH Zurich/University of Bremen): Chromatic numbers, morphism complexes, and Stiefel-Whitney characteristic classes 3:30 pm: Contributed 30 minute talks - Raghavan Dhandapani: Greedy drawings of planar triangulations - Matthew Kahle: The neighborhood complex of a random graph Tuesday, October 3 9:30 am: Sinisa Vrecica (University of Belgrade): Equivariant methods 11:00 am: Michael Joswig (Technische Universität, Darmstadt): Explicit computations in algebraic topology 2:00 pm: Carsten Schultz (Technische Universität Berlin): Homomorphism complexes of graphs: constructions and computations 3:30 pm: Persi Diaconis (Stanford University): Graph homomorphisms and the birthday problem 4:30 pm: Reception Wednesday, October 4 9:30 am: Joel Hass (University of California, Davis): Unknotting algorithms and their computational complexity 11:00 am: Nikolaus Witte (MSRI/Technische Universität, Berlin): Branched covers: A combinatorial model and applications 2:00 pm: Kevin Knudson (Mississippi State University): Algorithms in discrete Morse theory 3:30 pm: Graham Denham (University of Western Ontario): Generalized moment-angle complexes Thursday, October 5 9:30 am: Gunnar Carlsson (Stanford University): Sparseness and matrix algorithms 11:00 am - 12:00 noon: Martin Raussen (University of Aalborg): Invariance of directed spaces and persistence 2:00 pm: Michael Joswig (Technische Universität, Darmstadt): Bounds for the f-vectors of tight spans 4:10 pm at UC Berkeley - Math Department Colloquium: Herbert Edelsbrunner (Duke): Global methods for high-dimensional data sets Friday, October 6 9:30 am: Bernd Sturmfels (University of California, Berkeley): Convex Rank Tests 11:00 am: Raman Sanyal (Technische Universität, Berlin): Topological obstructions to polytope projection 12:00 pm: Lunch 1:30 pm: Contributed talks:     Anton Dochtermann (U Washington): Universality of Hom-complexes     Shripad Thite (Eindhoven): Pants decomposition of the punctured plane     Javier Arsuaga (SFSU): Using computational knot theory to understand DNA packing in viruses     Abhishek Bhattacharya (Arizona): Statistics on the planar shape space A block of rooms has been reserved at the Hotel Durant. Please mention the workshop name and reference the following code when making reservations via phone, fax or e-mail: K20000. The cut-off date for reservations is September 1, 2006.


Funding & Logistics Show All Collapse

Show Funding

To apply for funding, you must register by the funding application deadline displayed above.

Students, recent Ph.D.'s, women, and members of underrepresented minorities are particularly encouraged to apply. Funding awards are typically made 6 weeks before the workshop begins. Requests received after the funding deadline are considered only if additional funds become available.

Show Lodging

MSRI has preferred rates at the Rose Garden Inn, depending on room availability. Reservations may be made by calling 1-800-992-9005 OR directly on their website. Click on Corporate at the bottom of the screen and when prompted enter code MATH (this code is not case sensitive). By using this code a new calendar will appear and will show the MSRI rate on all room types available.

MSRI has preferred rates at the Hotel Durant. Reservations may be made by calling 1-800-238-7268. When making reservations, guests must request the MSRI preferred rate. If you are making your reservations on line, please go to this link and enter the promo/corporate code 123MSRI. Our preferred rate is $139 per night for a Deluxe Queen/King, based on availability.

MSRI has preferred rates of $149 - $189 plus tax at the Hotel Shattuck Plaza, depending on room availability. Guests can either call the hotel's main line at 510-845-7300 and ask for the MSRI- Mathematical Science Research Inst. discount; or go to www.hotelshattuckplaza.com and click Book Now. Once on the reservation page, click “Promo/Corporate Code“ and input the code: msri.

MSRI has preferred rates of $110 - $140 at the Berkeley Lab Guest House, depending on room availability. Reservations may be made by calling 510-495-8000 or directly on their website. Select “I am an individual traveler affiliated with MSRI”.

Additional lodging options may be found on our short term housing page.

Show Directions to Venue

Show Visa/Immigration

Schedule
Show All Collapse
Oct 02, 2006
Monday
09:00 AM - 10:00 AM
  An introduction to topological persistence
Herbert Edelsbrunner (Duke University)
10:30 AM - 11:30 AM
  Fundamental group computations in the theory of arrangements and related spaces
Alexandru Suciu (Northeastern University)
02:00 PM - 03:00 PM
  Chromatic numbers, morphism complexes, and Stiefel-Whitney characteristic classes
Dmitry Feichtner-Kozlov
03:30 PM - 04:00 PM
  Greedy drawings of planar triangulations
Raghavan Dhandapani
04:00 PM - 04:30 PM
  The neighborhood complex of a random graph
Matthew Kahle
Oct 03, 2006
Tuesday
09:30 AM - 10:30 AM
  Equivariant methods
Sinisa Vrecica
10:30 AM - 11:30 AM
  Explicit computations in algebraic topology
Michael Joswig
02:00 PM - 03:00 PM
  Homomorphism complexes of graphs: constructions and computations
Carsten Schultz
03:30 PM - 04:30 PM
  Graph homomorphisms and the birthday problem
Persi Diaconis (Stanford University)
Oct 04, 2006
Wednesday
09:30 AM - 10:30 AM
  Unknotting algorithms and their computational complexity
Joel Hass (University of California, Davis)
10:30 AM - 11:30 AM
  Branched covers: A combinatorial model and applications
Nikolaus Witte
02:00 PM - 03:00 PM
  Algorithms in discrete Morse theory
Kevin Knudson
Oct 05, 2006
Thursday
09:30 AM - 10:30 AM
  Sparseness and matrix algorithms
Gunnar Carlsson (Stanford University)
10:30 AM - 12:00 PM
  Invariance of directed spaces and persistence
Martin Raussen
02:00 PM - 03:00 PM
  Bounds for the f-vectors of tight spans
Michael Joswig
Oct 06, 2006
Friday
09:30 AM - 10:30 AM
  Convex Rank Tests
Bernd Sturmfels (UC Berkeley Math Faculty)
10:30 AM - 12:00 PM
  Topological obstructions to polytope projection
Raman Sanyal (Freie Universität Berlin)
01:30 PM - 02:00 PM
  Statistics on the planar shape space
Abhishek Bhattacharya
02:00 PM - 02:30 PM
  Universality of Hom-complexes
Anton Dochtermann
02:30 PM - 03:00 PM
  Pants decomposition of the punctured plane
Shripad Thite
03:00 PM - 03:30 PM
  Using computational knot theory to understand DNA packing in viruses
Javier Arsuaga