Seminar • Algorithms and Complexity • New Lower Bounds for Set Multilinear FormulasExport this event to calendar

Friday, October 28, 2022 — 1:00 PM to 2:00 PM EDT

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

Shubhangi Saraf, Associate Professor
Department of Mathematics, Department of Computer Science, University of Toronto

The recent exciting breakthrough by Limaye, Srinivasan, and Tavenas showing superpolynomial lower bounds for constant-depth algebraic circuits has underscored the importance of studying the complexity of set multilinear formulas.

In this talk, along with discussing the impact of this work and several others in the literature, I will discuss some new results in this area, namely strong (and “sharp”) lower bounds for set-multilinear circuits/formulas in the constant (or low) depth setting.

This is based on joint work with Deepanshu Kush.


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

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

Waterloo, ON N2L 3G1
Canada
Event tags 

S M T W T F S
25
26
27
28
29
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
3
4
5
6
  1. 2024 (100)
    1. April (23)
    2. March (27)
    3. February (25)
    4. January (25)
  2. 2023 (296)
    1. December (20)
    2. November (28)
    3. October (15)
    4. September (25)
    5. August (30)
    6. July (30)
    7. June (22)
    8. May (23)
    9. April (32)
    10. March (31)
    11. February (18)
    12. January (22)
  3. 2022 (245)
  4. 2021 (210)
  5. 2020 (217)
  6. 2019 (255)
  7. 2018 (217)
  8. 2017 (36)
  9. 2016 (21)
  10. 2015 (36)
  11. 2014 (33)
  12. 2013 (23)
  13. 2012 (4)
  14. 2011 (1)
  15. 2010 (1)
  16. 2009 (1)
  17. 2008 (1)