Seminar • Algorithms and Complexity • On Matrix Multiplication and Polynomial Identity TestingExport this event to calendar

Tuesday, December 6, 2022 — 1:00 PM to 2:00 PM EST

Please note: This seminar will take place in DC 1302 and online.

Robert Andrews, PhD candidate
Department of Computer Science, University of Illinois Urbana-Champaign

Determining the complexity of matrix multiplication is a fundamental problem of theoretical computer science. It is popularly conjectured that ω, the matrix multiplication exponent, equals 2. If true, this conjecture would yield fast algorithms for a wide array of problems in linear algebra and beyond. If instead ω > 2, can we leverage the hardness of matrix multiplication to design algorithms for other problems? In this talk, I will describe how lower bounds on ω can be used to make progress on derandomizing polynomial identity testing.


To join this PhD seminar on Zoom, please go to https://uwaterloo.zoom.us/j/92482486309. You can also attend in person in DC 1302.

Location 
DC - William G. Davis Computer Research Centre
Hybrid: DC 1302 | Online seminar
200 University Avenue West

Waterloo, ON N2L 3G1
Canada
Event tags 

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
1
2
3
4
  1. 2023 (33)
    1. March (1)
    2. February (10)
    3. January (22)
  2. 2022 (245)
    1. December (20)
    2. November (28)
    3. October (15)
    4. September (12)
    5. August (29)
    6. July (23)
    7. June (17)
    8. May (20)
    9. April (24)
    10. March (22)
    11. February (16)
    12. January (19)
  3. 2021 (210)
  4. 2020 (217)
  5. 2019 (255)
  6. 2018 (217)
  7. 2017 (36)
  8. 2016 (21)
  9. 2015 (36)
  10. 2014 (33)
  11. 2013 (23)
  12. 2012 (4)
  13. 2011 (1)
  14. 2010 (1)
  15. 2009 (1)
  16. 2008 (1)