For any Boolean function f:{0,1}ⁿ → {0,1} with a complexity measure having value k ≪ n, is it possible to restrict the function f to Θ(k) variables while keeping the complexity preserved at Θ(k)? Instantiation of this question for the measure of circuit complexity of the Boolean function was shown to be related to circuit lower bounds (Buresh-Oppenheim and Santhanam, 2006). Variants of the above question were also shown to have connections to the log-rank conjecture in communication complexity (Hrubeš, 2024) and lower bounds in proof complexity (Razborov, 2016). In the context of communication and query complexity, this question was recently studied by Göös, Newman, Riazanov and Sokolov (2024). They showed, among other results, that query complexity cannot be condensed losslessly. In this work, we show that there exists a Boolean function f such that any restriction of f to O(ℳ(f)) variables has ℳ(⋅)-complexity at most Õ(ℳ(f)^{2/3}), where ℳ is one of block sensitivity (bs), fractional block sensitivity (fbs), certificate complexity (𝖢), deterministic query complexity (𝖣), zero-error randomized query complexity (𝖱₀), and AND (and OR)-decision tree query complexity. This improves upon the results of Göös, Newman, Riazanov, and Sokolov (2024) for 𝖣 and 𝖱₀, and in particular answers their open question about the condensation of block sensitivity. We complement the negative results on lossless condensation with positive results about lossy condensation. In particular, we show that for every Boolean function f there exists a restriction of f to O(ℳ(f)) variables such that its ℳ(⋅)-complexity is at least Ω(ℳ(f)^{1/2}), where ℳ ∈ {bs,fbs,𝖢,UC_{min},UC₁,UC,𝖣,deg̃,λ}. In addition, we show lossy condensation for randomized and quantum query complexity with a slightly smaller exponent.

Determining the approximate degree composition for Boolean functions remains a significant unsolved problem in Boolean function complexity. In recent decades, researchers have concentrated on proving that approximate degree composes for special types of inner and outer functions. An important and extensively studied class of functions are the recursive functions, i.e. functions obtained by composing a base function with itself a number of times. Let h^d denote the standard d-fold composition of the base function h. The main result of this work is to show that the approximate degree composes if either of the following conditions holds: - The outer function f:{0,1}ⁿ → {0,1} is a recursive function of the form h^d, with h being any base function and d = Ω(log log n). - The inner function is a recursive function of the form h^d, with h being any constant arity base function (other than AND and OR) and d = Ω(log log n), where n is the arity of the outer function. In terms of proof techniques, we first observe that the lower bound for composition can be obtained by introducing majority in between the inner and the outer functions. We then show that majority can be efficiently eliminated if the inner or outer function is a recursive function.

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 introduce and study Certificate Game complexity, a measure of complexity based on the probability of winning a game where two players are given inputs with different function values and are asked to output some index i such that x_i≠ y_i, in a zero-communication setting. We give upper and lower bounds for private coin, public coin, shared entanglement and non-signaling strategies, and give some separations. We show that complexity in the public coin model is upper bounded by Randomized query and Certificate complexity. On the other hand, it is lower bounded by fractional and randomized certificate complexity, making it a good candidate to prove strong lower bounds on randomized query complexity. Complexity in the private coin model is bounded from below by zero-error randomized query complexity. The quantum measure highlights an interesting and surprising difference between classical and quantum query models. Whereas the public coin certificate game complexity is bounded from above by randomized query complexity, the quantum certificate game complexity can be quadratically larger than quantum query complexity. We use non-signaling, a notion from quantum information, to give a lower bound of n on the quantum certificate game complexity of the OR function, whose quantum query complexity is Θ(√n), then go on to show that this "non-signaling bottleneck" applies to all functions with high sensitivity, block sensitivity or fractional block sensitivity. We also consider the single-bit version of certificate games, where the inputs of the two players are restricted to having Hamming distance 1. We prove that the single-bit version of certificate game complexity with shared randomness is equal to sensitivity up to constant factors, thus giving a new characterization of sensitivity. On the other hand, the single-bit version of certificate game complexity with private randomness is equal to λ², where λ is the spectral sensitivity.

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.

Polynomial factoring has famous practical algorithms over fields-- finite, rational and p-adic. However, modulo prime powers, factoring gets harder because there is non-unique factorization and a combinatorial blowup ensues. For example, x^2+p \bmod p^2 is irreducible, but x^2+px \bmod p^2 has exponentially many factors! We present the first randomized poly(\deg f, łog p) time algorithm to factor a given univariate integral f(x) modulo p^k, for a prime p and k łeq 4. Thus, we solve the open question of factoring modulo p^3 posed in (Sircana, ISSAC'17). Our method reduces the general problem of factoring f(x) mod p^k to that of \em root finding in a related polynomial E(y) \bmodłangle p^k, \varphi(x)^\ell \rangle for some irreducible \varphi \bmod p. We can efficiently solve the latter for kłe4, by incrementally transforming E(y). Moreover, we discover an efficient refinement of Hensel lifting to lift factors of f(x) \bmod p to those \bmod\ p^4 (if possible). This was previously unknown, as the case of repeated factors of f(x) \bmod p forbids classical Hensel lifting.

In this paper, we construct explicit families of quantum error correcting codes based on cyclic codes. But for a crucial theoretical idea that we introduce here, namely working with a modified symplectic form as the basis of Weyl commutation, these codes would not have been possible - under the standard symplectic form, there are Galois theoretic no-go theorems on cyclic codes [7], [Corollary IV.5, page 651], [6], [Corollary 5.16, page 51] of certain lengths. More importantly, we circumvent the above no-go theorems without disturbing the one crucial property that cyclic codes have - efficient decoding algorithms. Recall that for general codes, efficient decoding algorithms do not exist if some widely believed complexity theoretic assumptions are true hence this is a crucial property to have. Cyclicity is a basis dependent property and for codes that we construct, is only evident in the modified symplectic setting. If we were to recast this code using the standard symplectic form, there would be a basis change on the underlying vector space that disturbs cyclicity. Hence, this change of perspective that we have here is crucial not only in the construction, where we had to circumvent the no-go theorems that we mentioned above, but also in the design of efficient decoding algorithm. Theoretically our result is also tight: we have a complete characterization (Theorem 6) of the codes that we construct here.

Constructing r-th nonresidue over a finite field is a fundamental computational problem. A related problem is to construct an irreducible polynomial of degree re (where r is a prime) over a given finite field Fq of characteristic p (equivalently, constructing the bigger field Fqre). Both these problems have famous randomized algorithms but the derandomization is an open question. We give some new connections between these two problems and their variants.

State conversion generalizes query complexity to the problem of converting between two input-dependent quantum states by making queries to the input. We characterize the complexity of this problem by introducing a natural information-theoretic norm that extends the Schur product operator norm. The complexity of converting between two systems of states is given by the distance between them, as measured by this norm. In the special case of function evaluation, the norm is closely related to the general adversary bound, a semi-definite program that lower-bounds the number of input queries needed by a quantum algorithm to evaluate a function. We thus obtain that the general adversary bound characterizes the quantum query complexity of any function whatsoever. This generalizes and simplifies the proof of the same result in the case of boolean input and output. Also in the case of function evaluation, we show that our norm satisfies a remarkable composition property, implying that the quantum query complexity of the composition of two functions is at most the product of the query complexities of the functions, up to a constant. Finally, our result implies that discrete and continuous-time query models are equivalent in the bounded-error setting, even for the general state-conversion problem.