Seminar • Algorithms and Complexity • A Tale of Two ReconstructionsExport this event to calendar

Thursday, February 24, 2022 12:00 PM EST

Please note: This seminar will be given online.

Vishwas Bhargava
Department of Computer Science, Rutgers University

Host: Professor Rafael Oliveira

Arithmetic circuits are a natural model for computing polynomials using basic arithmetic operations like addition and multiplication. The problem of learning arithmetic circuits, a.k.a. reconstruction, is an important and well-studied problem. Here we are given a polynomial (either explicitly as a list of coefficients or using black-box access) and the goal is to find the smallest (or approximately smallest) arithmetic circuit computing it.

In this talk, we will discuss two vastly different paradigms in learning arithmetic circuits, which are worst-case learning and average-case (non-degenerate) learning. We will elaborate on various techniques involved in these paradigms, their similarity, and their differences. Along the way, we will see a worst-case as well as a non-degenerate algorithm for decomposing tensors. Time permitting, we will also discuss some recent progress in non-degenerate learning of “generalized” depth 3 arithmetic circuits.


Bio: Vishwas Bhargava is a final-year Ph.D. student at Rutgers, advised by Shubhangi Saraf. He is broadly interested in the theoretical aspects of computer science; specifically, problems in Computational Complexity theory, Pseudorandomness/derandomization, and problems having Algebraic or Number Theoretic flavor.


To join this seminar on Zoom, please go to https://uwaterloo.zoom.us/j/94328913686?pwd=SWdrMEdXZUJla3pTM1FlcGZIYy9IQT09.

Location 
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 (96)
    1. April (19)
    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)