A tournament is a complete directed graph. A source in a tournament is a vertex that has no in-neighbours (every other vertex is reachable from it via a path of length 1), and a king in a tournament is a vertex v such that every other vertex is reachable from v via a path of length at most 2. It is well known that every tournament has at least one king. In particular, a maximum out-degree vertex is a king. The tasks of finding a king and a maximum out-degree vertex in a tournament has been relatively well studied in the context of query complexity. We study the communication complexity of finding a king, of finding a maximum out-degree vertex, and of finding a source (if it exists) in a tournament, where the edges are partitioned between two players. The following are our main results for n-vertex tournaments: We show that the communication task of finding a source in a tournament is equivalent to the well-studied Clique vs. Independent Set (CIS) problem on undirected graphs. As a result, known bounds on the communication complexity of CIS [Yannakakis, JCSS’91, Göös, Pitassi, Watson, SICOMP’18] imply a bound of Θ(log e 2 n) for finding a source (if it exists, or outputting that there is no source) in a tournament. The deterministic and randomized communication complexities of finding a king are Θ(n). The quantum communication complexity of finding a king is Θ(e √n). The deterministic, randomized, and quantum communication complexities of finding a maximum out-degree vertex are Θ(n log n), Θ(e n) and Θ(e √n), respectively. Our upper bounds above hold for all partitions of edges, and the lower bounds for a specific partition of the edges. One of our lower bounds uses a fooling-set based argument, and all our other lower bounds follow from carefully-constructed reductions from Set-Disjointness. An interesting point to note here is that while the deterministic query complexity of finding a king has been open for over two decades [Shen, Sheng, Wu, SICOMP’03], we are able to essentially resolve the complexity of this problem in a model (communication complexity) that is usually harder to analyze than query complexity.

Given an Abelian group 𝒢, a Boolean-valued function f: 𝒢 → {-1,+1}, is said to be s-sparse, if it has at most s-many non-zero Fourier coefficients over the domain 𝒢. In a seminal paper, Gopalan et al. [Gopalan et al., 2011] proved "Granularity" for Fourier coefficients of Boolean valued functions over ℤ₂ⁿ, that have found many diverse applications in theoretical computer science and combinatorics. They also studied structural results for Boolean functions over ℤ₂ⁿ which are approximately Fourier-sparse. In this work, we obtain structural results for approximately Fourier-sparse Boolean valued functions over Abelian groups 𝒢 of the form, 𝒢: = ℤ_{p_1}^{n_1} × ⋯ × ℤ_{p_t}^{n_t}, for distinct primes p_i. We also obtain a lower bound of the form 1/(m²s)^⌈φ(m)/2⌉, on the absolute value of the smallest non-zero Fourier coefficient of an s-sparse function, where m = p_1 ⋯ p_t, and φ(m) = (p_1-1) ⋯ (p_t-1). We carefully apply probabilistic techniques from [Gopalan et al., 2011], to obtain our structural results, and use some non-trivial results from algebraic number theory to get the lower bound. We construct a family of at most s-sparse Boolean functions over ℤ_pⁿ, where p > 2, for arbitrarily large enough s, where the minimum non-zero Fourier coefficient is o(1/s). The "Granularity" result of Gopalan et al. implies that the absolute values of non-zero Fourier coefficients of any s-sparse Boolean valued function over ℤ₂ⁿ are Ω(1/s). So, our result shows that one cannot expect such a lower bound for general Abelian groups. Using our new structural results on the Fourier coefficients of sparse functions, we design an efficient sparsity testing algorithm for Boolean function, which tests whether the given function is s-sparse, or ε-far from any sparse Boolean function, and it requires poly((ms)^φ(m),1/ε)-many queries. Further, we generalize the notion of degree of a Boolean function over an Abelian group 𝒢. We use it to prove an Ω(√s) lower bound on the query complexity of any adaptive sparsity testing algorithm.

For any Boolean functions f and g, the question whether R(f∘g) = Θ̃(R(f) ⋅ R(g)), is known as the composition question for the randomized query complexity. Similarly, the composition question for the approximate degree asks whether deg̃(f∘g) = Θ̃(deg̃(f)⋅deg̃(g)). These questions are two of the most important and well-studied problems in the field of analysis of Boolean functions, and yet we are far from answering them satisfactorily. It is known that the measures compose if one assumes various properties of the outer function f (or inner function g). This paper extends the class of outer functions for which R and deg̃ compose. A recent landmark result (Ben-David and Blais, 2020) showed that R(f∘g) = Ω(noisyR(f)⋅ R(g)). This implies that composition holds whenever noisyR(f) = Θ̃(R(f)). We show two results: 1. When R(f) = Θ(n), then noisyR(f) = Θ(R(f)). In other words, composition holds whenever the randomized query complexity of the outer function is full. 2. If R composes with respect to an outer function, then noisyR also composes with respect to the same outer function. On the other hand, no result of the type deg̃(f∘g) = Ω(M(f) ⋅ deg̃(g)) (for some non-trivial complexity measure M(⋅)) was known to the best of our knowledge. We prove that deg̃(f∘g) = Ω̃(√{bs(f)} ⋅ deg̃(g)), where bs(f) is the block sensitivity of f. This implies that deg̃ composes when deg̃(f) is asymptotically equal to √{bs(f)}. It is already known that both R and deg̃ compose when the outer function is symmetric. We also extend these results to weaker notions of symmetry with respect to the outer function.

We show that the deterministic decision tree complexity of a (partial) function or relation f lifts to the deterministic parity decision tree (PDT) size complexity of the composed function/relation f∘g as long as the gadget g satisfies a property that we call stifling. We observe that several simple gadgets of constant size, like Indexing on 3 input bits, Inner Product on 4 input bits, Majority on 3 input bits and random functions, satisfy this property. It can be shown that existing randomized communication lifting theorems ([Göös, Pitassi, Watson. SICOMP'20], [Chattopadhyay et al. SICOMP'21]) imply PDT-size lifting. However there are two shortcomings of this approach: first they lift randomized decision tree complexity of f, which could be exponentially smaller than its deterministic counterpart when either f is a partial function or even a total search problem. Second, the size of the gadgets in such lifting theorems are as large as logarithmic in the size of the input to f. Reducing the gadget size to a constant is an important open problem at the frontier of current research. Our result shows that even a random constant-size gadget does enable lifting to PDT size. Further, it also yields the first systematic way of turning lower bounds on the width of tree-like resolution proofs of the unsatisfiability of constant-width CNF formulas to lower bounds on the size of tree-like proofs in the resolution with parity system, i.e., Res(⊕), of the unsatisfiability of closely related constant-width CNF formulas.

A classic result of Nisan [SICOMP ’91] states that the deterministic decision tree *depth* complexity of every total Boolean function is at most the cube of its randomized decision tree *depth* complexity. The question whether randomness helps in significantly reducing the *size* of decision trees appears not to have been addressed. We show that the logarithm of the deterministic decision tree size complexity of every total Boolean function on n input variables is at most the fourth power of the logarithm of its bounded-error randomized decision tree size complexity, ignoring a polylogarithmic factor in the input size.

We study the relationship between various one-way communication complexity measures of a composed function with the analogous decision tree complexity of the outer function. We consider two gadgets: the AND function on 2 inputs, and the Inner Product on a constant number of inputs. More generally, we show the following when the gadget is Inner Product on 2b input bits for all b ≥ 2, denoted IP. - If f is a total Boolean function that depends on all of its n input bits, then the bounded-error one-way quantum communication complexity of f∘IP equals Ω(n(b-1)). - If f is a partial Boolean function, then the deterministic one-way communication complexity of f∘IP is at least Ω(b ⋅ 𝖣_{dt}^ → (f)), where 𝖣_{dt}^ → (f) denotes non-adaptive decision tree complexity of f. To prove our quantum lower bound, we first show a lower bound on the VC-dimension of f∘IP. We then appeal to a result of Klauck [STOC'00], which immediately yields our quantum lower bound. Our deterministic lower bound relies on a combinatorial result independently proven by Ahlswede and Khachatrian [Adv. Appl. Math.'98], and Frankl and Tokushige [Comb.'99]. It is known due to a result of Montanaro and Osborne [arXiv'09] that the deterministic one-way communication complexity of f∘XOR equals the non-adaptive parity decision tree complexity of f. In contrast, we show the following when the inner gadget is the AND function on 2 input bits. - There exists a function for which even the quantum non-adaptive AND decision tree complexity of f is exponentially large in the deterministic one-way communication complexity of f∘AND. - However, for symmetric functions f, the non-adaptive AND decision tree complexity of f is at most quadratic in the (even two-way) communication complexity of f∘AND. In view of the first bullet, a lower bound on non-adaptive AND decision tree complexity of f does not lift to a lower bound on one-way communication complexity of f∘AND. The proof of the first bullet above uses the well-studied Odd-Max-Bit function. For the second bullet, we first observe a connection between the one-way communication complexity of f and the Möbius sparsity of f, and then give a lower bound on the Möbius sparsity of symmetric functions. An upper bound on the non-adaptive AND decision tree complexity of symmetric functions follows implicitly from prior work on combinatorial group testing; for the sake of completeness, we include a proof of this result. It is well known that the rank of the communication matrix of a function F is an upper bound on its deterministic one-way communication complexity. This bound is known to be tight for some F. However, in our final result we show that this is not the case when F = f∘AND. More precisely we show that for all f, the deterministic one-way communication complexity of F = f∘AND is at most (rank(M_{F}))(1 - Ω(1)), where M_{F} denotes the communication matrix of F.

Chang’s lemma (Duke Mathematical Journal, 2002) is a classical result in mathematics, with applications spanning across additive combinatorics, combinatorial number theory, analysis of Boolean functions, communication complexity and algorithm design. For a Boolean function f that takes values in {-1, 1} let r(f) denote its Fourier rank (i.e., the dimension of the span of its Fourier support). For each positive threshold t, Chang’s lemma provides a lower bound on δ(f):= Pr[f(x) = -1] in terms of the dimension of the span of its characters with Fourier coefficients of magnitude at least 1/t. In this work we examine the tightness of Chang’s lemma with respect to the following three natural settings of the threshold: the Fourier sparsity of f, denoted k(f), the Fourier max-supp-entropy of f, denoted k′(f), defined to be the maximum value of the reciprocal of the absolute value of a non-zero Fourier coefficient, the Fourier max-rank-entropy of f, denoted k′′(f), defined to be the minimum t such that characters whose coefficients are at least 1/t in magnitude span a r(f)-dimensional space. In this work we prove new lower bounds on δ(f) in terms of the above measures. One of our lower bounds, δ(f) = Ω (r(f)2/(k(f) log2 k(f))), subsumes and refines the previously best known upper bound r(f) = O(pk(f) log k(f)) on r(f) in terms of k(f) by Sanyal (Theory of Computing, 2019). We improve upon this bound and show r(f) = O(pk(f)δ(f) log k(f)). Another lower bound, δ(f) = Ω (r(f)/(k′′(f) log k(f))), is based on our improvement of a bound by Chattopadhyay, Hatami, Lovett and Tal (ITCS, 2019) on the sum of absolute values of level-1 Fourier coefficients in terms of F2-degree. We further show that Chang’s lemma for the above-mentioned choices of the threshold is asymptotically outperformed by our bounds for most settings of the parameters involved. Next, we show that our bounds are tight for a wide range of the parameters involved, by constructing functions witnessing their tightness. All the functions we construct are modifications of the Addressing function, where we replace certain input variables by suitable functions. Our final contribution is to construct Boolean functions f for which our lower bounds asymptotically match δ(f), and for any choice of the threshold t, the lower bound obtained from Chang’s lemma is asymptotically smaller than δ(f). Our results imply more refined deterministic one-way communication complexity upper bounds for XOR functions. Given the wide-ranging application of Chang’s lemma to areas like additive combinatorics, learning theory and communication complexity, we strongly feel that our refinements of Chang’s lemma will find many more applications.

We study parity decision trees for Boolean functions. The motivation of our study is the log-rank conjecture for XOR functions and its connection to Fourier analysis and parity decision tree complexity. Let f be a Boolean function with Fourier support S and Fourier sparsity k. 1) We prove via the probabilistic method that there exists a parity decision tree of depth O(sqrt k) that computes f. This matches the best known upper bound on the parity decision tree complexity of Boolean functions (Tsang, Wong, Xie, and Zhang, FOCS 2013). Moreover, while previous constructions (Tsang et al., FOCS 2013, Shpilka, Tal, and Volk, Comput. Complex. 2017) build the trees by carefully choosing the parities to be queried in each step, our proof shows that a naive sampling of the parities suffices. 2) We generalize the above result by showing that if the Fourier spectra of Boolean functions satisfy a natural "folding property", then the above proof can be adapted to establish existence of a tree of complexity polynomially smaller than O(sqrt k). We make a conjecture in this regard which, if true, implies that the communication complexity of an XOR function is bounded above by the fourth root of the rank of its communication matrix, improving upon the previously known upper bound of square root of rank (Tsang et al., FOCS 2013, Lovett, J. ACM. 2016). 3) It can be shown by elementary techniques that for any Boolean function f and all pairs (alpha, beta) of parities in S, there exists another pair (gamma, delta) of parities in S such that alpha + beta = gamma + delta. We show, among other results, that there must exist several gamma in F_2^n such that there are at least three pairs (alpha_1, alpha_2) of parities in S with alpha_1 + alpha_2 = gamma.

For any relation f subseteq {0,1}^n x S and any partial Boolean function g:{0,1}^m -> {0,1,*}, we show that R_{1/3}(f o g^n) in Omega(R_{4/9}(f) * sqrt{R_{1/3}(g)}) , where R_epsilon(*) stands for the bounded-error randomized query complexity with error at most epsilon, and f o g^n subseteq ({0,1}^m)^n x S denotes the composition of f with n instances of g. The new composition theorem is optimal, at least, for the general case of relational problems: A relation f_0 and a partial Boolean function g_0 are constructed, such that R_{4/9}(f_0) in Theta(sqrt n), R_{1/3}(g_0)in Theta(n) and R_{1/3}(f_0 o g_0^n) in Theta(n). The theorem is proved via introducing a new complexity measure, max-conflict complexity, denoted by bar{chi}(*). Its investigation shows that bar{chi}(g) in Omega(sqrt{R_{1/3}(g)}) for any partial Boolean function g and R_{1/3}(f o g^n) in Omega(R_{4/9}(f) * bar{chi}(g)) for any relation f, which readily implies the composition statement. It is further shown that bar{chi}(g) is always at least as large as the sabotage complexity of g.

Saks and Wigderson [in Proceedings of the $27$th FOCS, IEEE Computer Society, Los Alamitos, CA, 1986, pp. 29--38] conjectured that $R_0(f) = \Omega(D(f)^{0.753\ldots})$ for all Boolean functions $f$, where $R_0$ denotes the randomized zero-error query complexity and $D$ denotes the deterministic query complexity. We show that for the pointer function $\mathsf{GPW}^{r \times s}$ defined by Göös, Pitassi, and Watson [in Proceedings of the $56$th FOCS, IEEE, Piscataway, NJ, 2015, pp. 1077--1088], the following hold: (a) $R_1(\mathsf{GPW}^{r \times s}) = \widetilde{\Theta}({r+s})$ and (b) $R_1(\overline{\mathsf{GPW}^{r \times s}}) = \widetilde{\Theta}(r+\sqrt{r}s)$, where $R_1$ denotes the randomized one-sided error query complexity. These results imply that (i) $R_0(\mathsf{GPW}^{s^2 \times s}) = O(D(\mathsf{GPW}^{s^2 \times s})^{2/3})$, thereby refuting the conjecture of Saks and Wigderson, and (ii) $R_1(\mathsf{GPW}^{s \times s})=\widetilde{O}(R_0(\mathsf{GPW}^{s \times s})^{2/3})$, thereby providing a polynomial separation between the randomized zero-error and one-sided error query complexity measures.

Let the randomized query complexity of a relation for error probability epsilon be denoted by R_epsilon(). We prove that for any relation f contained in {0,1}^n times R and Boolean function g:{0,1}^m -> {0,1}, R_{1/3}(f o g^n) = Omega(R_{4/9}(f).R_{1/2-1/n^4}(g)), where f o g^n is the relation obtained by composing f and g. We also show using an XOR lemma that R_{1/3}(f o (g^{xor}_{O(log n)})^n) = Omega(log n . R_{4/9}(f) . R_{1/3}(g))$, where g^{xor}_{O(log n)} is the function obtained by composing the XOR function on O(log n) bits and g.

The pointer function of G{ö}{ö}s, Pitassi and Watson \cite{DBLP:journals/eccc/GoosP015a} and its variants have recently been used to prove separation results among various measures of complexity such as deterministic, randomized and quantum query complexities, exact and approximate polynomial degrees, etc. In particular, the widest possible (quadratic) separations between deterministic and zero-error randomized query complexity, as well as between bounded-error and zero-error randomized query complexity, have been obtained by considering {\em variants}~\cite{DBLP:journals/corr/AmbainisBBL15} of this pointer function. However, as was pointed out in \cite{DBLP:journals/corr/AmbainisBBL15}, the precise zero-error complexity of the original pointer function was not known. We show a lower bound of $\widetildeΩ(n^{3/4})$ on the zero-error randomized query complexity of the pointer function on $Θ(n \log n)$ bits; since an $\widetilde{O}(n^{3/4})$ upper bound is already known \cite{DBLP:conf/fsttcs/MukhopadhyayS15}, our lower bound is optimal up to a factor of $\polylog\, n$.

We show that there exists a Boolean function F which gives the following separations among deterministic query complexity (D(F)), randomized zero error query complexity (R_0(F)) and randomized one-sided error query complexity (R_1(F)): R_1(F) = ~O(sqrt{D(F)) and R_0(F)=~O(D(F))^3/4. This refutes the conjecture made by Saks and Wigderson that for any Boolean function f, R_0(f)=Omega(D(f))^0.753.. . This also shows widest separation between R_1(f) and D(f) for any Boolean function. The function F was defined by Göös, Pitassi and Watson who studied it for showing a separation between deterministic decision tree complexity and unambiguous non-deterministic decision tree complexity. Independently of us, Ambainis et al proved that different variants of the function F certify optimal (quadratic) separation between D(f) and R_0(f), and polynomial separation between R_0(f) and R_1(f). Viewed as separation results, our results are subsumed by those of Ambainis et al. However, while the functions considered in the work of Ambainis et al are different variants of F, in this work we show that the original function F itself is sufficient to refute the Saks-Wigderson conjecture and obtain widest possible separation between the deterministic and one-sided error randomized query complexity.

This paper focusses on the performance of the Metropolis algorithm when employed for solving combinatorial optimization problems. One finds in the literature two notions of success for the Metropolis algorithm in the context of such problems. First, we show that both these notions are equivalent. Next, we provide two characterizations, or in other words, necessary and sufficient conditions, for the success of the algorithm, both characterizations being conditions on the family of Markov chains which the Metropolis algorithm gives rise to when applied to an optimization problem. The first characterization is that the Metropolis algorithm is successful if in every chain, for every set A of states not containing the optimum, the ratio of the ergodic flow out of A to the capacity of A is high. The second characterization is that in every chain the stationary probability of the optimum is high and that the family of chains mixes rapidly. We illustrate the applicability of our results by giving alternative proofs of certain known results.