Falk Unger: Better gates can make fault-tolerant computation impossible Export this event to calendar

Tuesday, November 2, 2010 — 12:00 PM to 1:00 PM EDT

Falk Unger, University of California, Berkeley

We consider fault-tolerant computation with formulas composed of noisy
Boolean gates with two input wires.   It is known that  if all gates
fail independently with probability at least beta (roughly equal to
8.856%), fault-tolerant computation is not possible. On the other
hand, if all gates fail with the same probability e and e<beta, then
fault-tolerant computation is possible. The assumption that all gates
fail with "exactly" the same probability is pretty strong and
unrealistic in real-world scenarios. Furthermore, one might be tempted
to think that it can be removed easily, since making gates "better"
should not hurt. Surprisingly, this is not the case, as we show in
this work: there is a constant alpha<beta such that almost all
functions cannot be computed by formulas, if the noise rate of each
individual gate is  selected adversarially in the range [0,alpha].
Hence, while a hardware manufacturer who produces consistently bad
gates with noise rate alpha can always achieve reliable computation, a
manufacturer who can only ensure that all gates have noise rates at
most alpha cannot.

Click here to see Falk's website.

Location 
RAC - Research Advancement Centre
2009
475 Wes Graham Way

Waterloo, ON N2L 6R2
Canada

S M T W T F S
29
30
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
31
1
2
  1. 2020 (2)
    1. August (1)
    2. June (1)
    3. May (1)
  2. 2019 (126)
    1. December (1)
    2. November (2)
    3. October (6)
    4. September (5)
    5. August (10)
    6. July (17)
    7. June (14)
    8. May (15)
    9. April (15)
    10. March (11)
    11. February (20)
    12. January (12)
  3. 2018 (148)
    1. December (8)
    2. November (20)
    3. October (10)
    4. September (10)
    5. August (10)
    6. July (11)
    7. June (9)
    8. May (13)
    9. April (16)
    10. March (17)
    11. February (14)
    12. January (13)
  4. 2017 (135)
  5. 2016 (94)
  6. 2015 (85)
  7. 2014 (97)
  8. 2013 (92)
  9. 2012 (125)
  10. 2011 (117)
  11. 2010 (41)
  12. 2009 (4)
  13. 2008 (1)
  14. 2007 (1)
  15. 2005 (1)
  16. 2004 (3)