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 - Ashwin NayakExport this event to calendar

Friday, November 2, 2007 — 3:30 PM to 4:30 PM EDT

The Direct-Product Property, Subdistribution Bounds, and Applications

Speaker: Ashwin Nayak
Affiliation: University of Waterloo
Room: Mathematics & Computer Building (MC) 5158

Abstract:

A basic question in complexity theory is whether the computational resources required for solving k independent instances of the same problem scale as k times the resources required for one instance. In this talk, we revisit a few instances where this kind of "direct product'' property occurs in quantum communication. We then define a new notion of complexity for boolean functions, a "subdistribution bound'', and explain how this enables us to prove the direct product property in some instances. This way we recover and generalize, in a unified manner, several recent results on the direct product question.

Joint work with Rahul Jain (U. Waterloo) and Hartmut Klauck (Goethe-U., Frankfurt).

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

Waterloo, ON N2L 3G1
Canada

S M T W T F S
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
3
  1. 2020 (89)
    1. September (11)
    2. August (11)
    3. July (17)
    4. June (11)
    5. May (6)
    6. March (11)
    7. February (11)
    8. 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)