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.

Advisors: 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