University COVID-19 update

The University of Waterloo is constantly updating our most Frequently Asked Questions.

Questions about buildings and services? Visit the list of Modified Services.

Please note: The University of Waterloo is closed for all events until further notice.

Tutte seminar - Daniel GottesmanExport this event to calendar

Friday, June 19, 2009 — 3:30 PM to 4:30 PM EDT

Computational Complexity of Translationally-Invariant Systems

Speaker: Daniel Gottesman
Affiliation: Perimeter Institute
Room: Mathematics & Computer Building (MC) 5158

Abstract:

In general, it is a computationally hard problem to determine whether a two-dimensional grid can be tiled using some set of rules on what kinds of tiles can be adjacent. A related problem, hard for a quantum complexity class, is to determine the lowest energy state of a system with interactions only for particles adjacent along a line. Of course, there are also specific systems of this type which are easy to solve. What are the key distinguishing properties between the hard systems and the easy systems? One might expect that symmetry should play a role, with very symmetric systems being easy. However, we show that even with a great deal of symmetry - translational invariance - tiling problems and spin systems remain hard to solve in general. 

This is joint work with Sandy Irani.

Location 
MC - Mathematics & Computer Building
5158
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
29
30
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
1
2
  1. 2020 (33)
    1. March (11)
    2. February (11)
    3. January (11)
  2. 2019 (167)
    1. December (5)
    2. November (15)
    3. October (18)
    4. September (15)
    5. August (9)
    6. July (17)
    7. June (18)
    8. May (16)
    9. April (9)
    10. March (24)
    11. February (13)
    12. January (8)
  3. 2018 (138)
  4. 2017 (103)
  5. 2016 (137)
  6. 2015 (136)
  7. 2014 (88)
  8. 2013 (48)
  9. 2012 (39)
  10. 2011 (36)
  11. 2010 (40)
  12. 2009 (40)
  13. 2008 (39)
  14. 2007 (15)