## University of Waterloo COVID-19 update

Please see the University of Waterloo’s frequently asked questions for information about COVID-19 and how it has affected university operations.

Please visit the list of modified services if you have questions about university services.

Although the University of Waterloo is closed for in-person events until further notice, many virtual events and presentations of interest to computer scientists are taking place each week at the Cheriton School of Computer Science. Please check out what our students and faculty are doing.

# PhD Defence • Algorithms and Complexity — On Tolerant Testing and Tolerant Junta Testing

Wednesday, June 17, 2020 — 10:00 AM EDT

## Please note: This PhD defence will be given online.

Amit Levi, PhD candidate
David R. Cheriton School of Computer Science

During the past few decades property testing became an active field of study in theoretical computer science. The algorithmic task is to determine, given access to an unknown large object (e.g. functions, graphs, probability distributions), whether it has some fixed property, or it is far from any object having the property. The approximate nature of those algorithms allows in many cases to achieve a significant saving in running time, and obtain \emph{sublinear} running time. Nevertheless, in various settings and applications, accepting only inputs that exactly have a certain property is too restrictive, and it is more beneficial to distinguish between inputs that are close to having the property, and those that are far from it. The framework of \emph{tolerant} testing tackles this exact problem. In this thesis, we will focus on one of the most fundamental properties of Boolean functions: the property of being a \emph{$k$-junta} (i.e., being dependent on at most $k$ variables).

The first chapter focuses on algorithms for tolerant junta testing. In particular, we show that there exists $\poly(k)$ query algorithm distinguishing functions close to $k$-juntas and functions that are far from $2k$-juntas. We also show how to obtain a trade-off between the “tolerance” of the algorithm and its query complexity.

The second chapter considers lower bounds for tolerant junta testing. In particular, we show that for any non-adaptive tolerant junta tester, required to make at least $\Omega(k^2/\polylog k)$. In addition, we show that using a weaker access model, under a certain hardness assumption, there is no algorithm that can distinguish between functions close to $k$-juntas and functions which are far from it in $\poly(k)$ time.

The third chapter considers tolerant testing in a more general context, and asks whether tolerant testing is strictly harder than standard testing. In particular, we show that for any constant $\ell\in \N$, there exists a property $\calP_\ell$ such that $\calP_\ell$ can be tested in $O(1)$ queries, but any tolerant tester for $\calP_\ell$ is required to make at least $\Omega(n/\log^{(\ell)}n)$ queries (where $\log^{(\ell)}$ denote the $\ell$ times iterated log function).

The final chapter focuses on applications. We show how to leverage the techniques developed in previous chapters to obtain results on tolerant isomorphism testing, unateness testing, and erasure resilient testing.

Location
Online PhD defence
200 University Avenue West

Waterloo, ON N2L 3G1

### May 2020

S M T W T F S
26
27
28
29
30
2
3
4
9
10
11
13
15
16
17
18
21
23
24
25
28
30
31
1
2
3
4
5
6
1. 2020 (104)
1. June (3)
2. May (17)
3. April (20)
4. March (17)
5. February (25)
6. January (22)
2. 2019 (255)
1. December (21)
2. November (25)
3. October (16)
4. September (20)
5. August (18)
6. July (12)
7. June (23)
8. May (23)
9. April (32)
10. March (25)
11. February (16)
12. January (24)
3. 2018 (220)
4. 2017 (36)
5. 2016 (21)
6. 2015 (36)
7. 2014 (33)
8. 2013 (23)
9. 2012 (4)
10. 2011 (1)
11. 2010 (1)
12. 2009 (1)
13. 2008 (1)