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.

Algebraic Graph Theory Seminar - Nathan LindzeyExport this event to calendar

Monday, November 23, 2020 — 11:30 AM EST

Title: Complexity Measures on the Symmetric Group and Beyond

Speaker: Nathan Lindzey
Affiliation: CU Boulder
Zoom: Contact Soffia Arnadottir

Abstract:

A classical result in complexity theory states that a degree-d Boolean function on the hypercube can be computed using a decision tree of depth poly(d). Conversely, a Boolean function computed by a decision tree of depth d has degree at most d. Thus degree and decision tree complexity are polynomially related. Many other complexity measures of Boolean functions on the hypercube are polynomially related to the degree (e.g., approximate degree, certificate complexity, block sensitivity), and last year Huang famously added sensitivity to the list. Can we prove similar results for Boolean functions on other combinatorial domains?

We give natural extensions of many complexity measures (e.g., degree, approximate degree, decision tree complexity, sensitivity, block sensitivity) to domains such as the symmetric group, perfect matchings, k-sets, and a few others. We show that these complexity measures are polynomially related by generalizing classical arguments of Nisan (and others) and reducing to Huang's sensitivity theorem using so-called "pseudo-characters", which witness the degree of a function. As an application, we give a characterization of the degree-1 Boolean functions of the perfect matching scheme and we simplify the characterization of maximum-size t-intersecting families in the symmetric group and the perfect matching scheme.

arXiv: https://arxiv.org/abs/2010.07405

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