### Michael Whitmeyer

###
EECS Department

University of California, Berkeley

Technical Report No. UCB/EECS-2021-152

May 21, 2021

### http://www2.eecs.berkeley.edu/Pubs/TechRpts/2021/EECS-2021-152.pdf

This thesis focuses on the following question: if we have query access to some $f: \pmone^n \to \pmone$ (meaning we can query any of its $2^n$ outputs at will), how many queries do we need to discern whether $f$ is ``close'' or ``far'' from depending on only a subset of $k$ of its inputs? Such functions are known in the field as ``$k$-juntas''. The main results come from the recent work of \cite{ITW}, which gave an improved upper bound on the query complexity of this problem. Namely, it was shown that only $2^{\Tilde{O}(\sqrt{k})}$ queries to $f$ suffice to answer this question. Along the way, we will provide a more detailed and leisurely survey of the other results and progress in this area, examining other techniques and the strongest known upper and lower bounds for variants of this problem.

**Advisor:** Avishay Tal

BibTeX citation:

@mastersthesis{Whitmeyer:EECS-2021-152, Author = {Whitmeyer, Michael}, Title = {How Close is your Function to Depending on a Small Number of its Inputs?}, School = {EECS Department, University of California, Berkeley}, Year = {2021}, Month = {May}, URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2021/EECS-2021-152.html}, Number = {UCB/EECS-2021-152}, Abstract = {This thesis focuses on the following question: if we have query access to some $f: \pmone^n \to \pmone$ (meaning we can query any of its $2^n$ outputs at will), how many queries do we need to discern whether $f$ is ``close'' or ``far'' from depending on only a subset of $k$ of its inputs? Such functions are known in the field as ``$k$-juntas''. The main results come from the recent work of \cite{ITW}, which gave an improved upper bound on the query complexity of this problem. Namely, it was shown that only $2^{\Tilde{O}(\sqrt{k})}$ queries to $f$ suffice to answer this question. Along the way, we will provide a more detailed and leisurely survey of the other results and progress in this area, examining other techniques and the strongest known upper and lower bounds for variants of this problem.} }

EndNote citation:

%0 Thesis %A Whitmeyer, Michael %T How Close is your Function to Depending on a Small Number of its Inputs? %I EECS Department, University of California, Berkeley %D 2021 %8 May 21 %@ UCB/EECS-2021-152 %U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2021/EECS-2021-152.html %F Whitmeyer:EECS-2021-152