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.

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.

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.

A tournament is a complete directed graph. It is well known that every tournament contains at least one vertex v such that every other vertex is reachable from v by a path of length at most 2. All such vertices v are called kings of the underlying tournament. Despite active recent research in the area, the best-known upper and lower bounds on the deterministic query complexity (with query access to directions of edges) of finding a king in a tournament on n vertices are from over 20 years ago, and the bounds do not match: the best-known lower bound is Ω(n^{4/3}) and the best-known upper bound is O(n^{3/2}) [Shen, Sheng, Wu, SICOMP'03]. Our contribution is to show tight bounds (up to logarithmic factors) of Θ̃(n) and Θ̃(√n) in the randomized and quantum query models, respectively. We also study the randomized and quantum query complexities of finding a maximum out-degree vertex in a tournament.

We present a Karchmer-Wigderson game to study the complexity of hazard-free formulas. This new game is both a generalization of the monotone Karchmer-Wigderson game and an analog of the classical Boolean Karchmer-Wigderson game. Therefore, it acts as a bridge between the existing monotone and general games. Using this game, we prove hazard-free formula size and depth lower bounds that are provably stronger than those possible by the standard technique of transferring results from monotone complexity in a black-box fashion. For the multiplexer function we give (1) a hazard-free formula of optimal size and (2) an improved low-depth hazard-free formula of almost optimal size and (3) a hazard-free formula with alternation depth 2 that has optimal depth. We then use our optimal constructions to obtain an improved universal worst-case hazard-free formula size upper bound. We see our results as a step towards establishing hazard-free computation as an independent missing link between Boolean complexity and monotone complexity.

In the discrete $k$-center problem, we are given a metric space $(P,\texttt{dist})$ where $|P|=n$ and the goal is to select a set $C\subseteq P$ of $k$ centers which minimizes the maximum distance of a point in $P$ from its nearest center. For any $ε>0$, Agarwal and Procopiuc [SODA '98, Algorithmica '02] designed an $(1+ε)$-approximation algorithm for this problem in $d$-dimensional Euclidean space which runs in $O(dn\log k) + \left(\dfrac{k}ε\right)^{O\left(k^{1-1/d}\right)}\cdot n^{O(1)}$ time. In this paper we show that their algorithm is essentially optimal: if for some $d\geq 2$ and some computable function $f$, there is an $f(k)\cdot \left(\dfrac{1}ε\right)^{o\left(k^{1-1/d}\right)} \cdot n^{o\left(k^{1-1/d}\right)}$ time algorithm for $(1+ε)$-approximating the discrete $k$-center on $n$ points in $d$-dimensional Euclidean space then the Exponential Time Hypothesis (ETH) fails. We obtain our lower bound by designing a gap reduction from a $d$-dimensional constraint satisfaction problem (CSP) defined by Marx and Sidiropoulos [SoCG '14] to discrete $d$-dimensional $k$-center. As a byproduct of our reduction, we also obtain that the exact algorithm of Agarwal and Procopiuc [SODA '98, Algorithmica '02] which runs in $n^{O\left(d\cdot k^{1-1/d}\right)}$ time for discrete $k$-center on $n$ points in $d$-dimensional Euclidean space is asymptotically optimal. Formally, we show that if for some $d\geq 2$ and some computable function $f$, there is an $f(k)\cdot n^{o\left(k^{1-1/d}\right)}$ time exact algorithm for the discrete $k$-center problem on $n$ points in $d$-dimensional Euclidean space then the Exponential Time Hypothesis (ETH) fails. Previously, such a lower bound was only known for $d=2$ and was implicit in the work of Marx [IWPEC '06]. [see paper for full abstract]

For a function g∶{0,1}m→{0,1}, a function f∶ {0,1}n→{0,1} is called a g-polymorphism if their actions commute: f(g(row1(Z)),…,g(rown(Z))) = g(f(col1(Z)),…,f(colm(Z))) for all Z∈{0,1}n× m. The function f is called an approximate g-polymorphism if this equality holds with probability close to 1, when Z is sampled uniformly. A pair of functions f0,f1∶ {0,1}n → {0,1} are called a skew g-polymorphism if f0(g(row1(Z)),…,g(rown(Z))) = g(f1(col1(Z)),…,f1(colm(Z))) for all Z∈{0,1}n× m.

Nisan showed in 1991 that the width of a smallest noncommutative single-(source,sink) algebraic branching program (ABP) to compute a noncommutative polynomial is given by the ranks of specific matrices. This means that the set of noncommutative polynomials with ABP width complexity at most k is Zariski-closed, an important property in geometric complexity theory. It follows that approximations cannot help to reduce the required ABP width. It was mentioned by Forbes that this result would probably break when going from single-(source,sink) ABPs to trace ABPs. We prove that this is correct. Moreover, we study the commutative monotone setting and prove a result similar to Nisan, but concerning the analytic closure. We observe the same behavior here: The set of polynomials with ABP width complexity at most k is closed for single-(source,sink) ABPs and not closed for trace ABPs. The proofs reveal an intriguing connection between tangent spaces and the vector space of flows on the ABP. We close with additional observations on VQP and the closure of VNP which allows us to establish a separation between the two classes.

Given a Boolean function $f:\{-1,1\}^n\to \{-1,1\}$, the Fourier distribution assigns probability $\widehat{f}(S)^2$ to $S\subseteq [n]$. The Fourier Entropy-Influence (FEI) conjecture of Friedgut and Kalai asks if there exist a universal constant C>0 such that $H(\hat{f}^2)\leq C Inf(f)$, where $H(\hat{f}^2)$ is the Shannon entropy of the Fourier distribution of $f$ and $Inf(f)$ is the total influence of $f$. 1) We consider the weaker Fourier Min-entropy-Influence (FMEI) conjecture. This asks if $H_{\infty}(\hat{f}^2)\leq C Inf(f)$, where $H_{\infty}(\hat{f}^2)$ is the min-entropy of the Fourier distribution. We show $H_{\infty}(\hat{f}^2)\leq 2C_{\min}^\oplus(f)$, where $C_{\min}^\oplus(f)$ is the minimum parity certificate complexity of $f$. We also show that for every $ε\geq 0$, we have $H_{\infty}(\hat{f}^2)\leq 2\log (\|\hat{f}\|_{1,ε}/(1-ε))$, where $\|\hat{f}\|_{1,ε}$ is the approximate spectral norm of $f$. As a corollary, we verify the FMEI conjecture for the class of read-$k$ $DNF$s (for constant $k$). 2) We show that $H(\hat{f}^2)\leq 2 aUC^\oplus(f)$, where $aUC^\oplus(f)$ is the average unambiguous parity certificate complexity of $f$. This improves upon Chakraborty et al. An important consequence of the FEI conjecture is the long-standing Mansour's conjecture. We show that a weaker version of FEI already implies Mansour's conjecture: is $H(\hat{f}^2)\leq C \min\{C^0(f),C^1(f)\}$?, where $C^0(f), C^1(f)$ are the 0- and 1-certificate complexities of $f$, respectively. 3) We study what FEI implies about the structure of polynomials that 1/3-approximate a Boolean function. We pose a conjecture (which is implied by FEI): no "flat" degree-$d$ polynomial of sparsity $2^{ω(d)}$ can 1/3-approximate a Boolean function. We prove this conjecture unconditionally for a particular class of polynomials.

A quasi-Gray code of dimension n and length l over an alphabet Sigma is a sequence of distinct words w_1,w_2,...,w_l from Sigma^n such that any two consecutive words differ in at most c coordinates, for some fixed constant c>0. In this paper we are interested in the read and write complexity of quasi-Gray codes in the bit-probe model, where we measure the number of symbols read and written in order to transform any word w_i into its successor w_{i+1}. We present construction of quasi-Gray codes of dimension n and length 3^n over the ternary alphabet {0,1,2} with worst-case read complexity O(log n) and write complexity 2. This generalizes to arbitrary odd-size alphabets. For the binary alphabet, we present quasi-Gray codes of dimension n and length at least 2^n - 20n with worst-case read complexity 6+log n and write complexity 2. This complements a recent result by Raskin [Raskin '17] who shows that any quasi-Gray code over binary alphabet of length 2^n has read complexity Omega(n). Our results significantly improve on previously known constructions and for the odd-size alphabets we break the Omega(n) worst-case barrier for space-optimal (non-redundant) quasi-Gray codes with constant number of writes. We obtain our results via a novel application of algebraic tools together with the principles of catalytic computation [Buhrman et al. '14, Ben-Or and Cleve '92, Barrington '89, Coppersmith and Grossman '75].

The VP versus VNP question, introduced by Valiant, is probably the most important open question in algebraic complexity theory. Thanks to completeness results, a variant of this question, VBP versus VNP, can be succinctly restated as asking whether the permanent of a generic matrix can be written as a determinant of a matrix of polynomially bounded size. Strikingly, this restatement does not mention any notion of computational model. To get a similar restatement for the original and more fundamental question, and also to better understand the class itself, we need a complete polynomial for VP. Ad hoc constructions yielding complete polynomials were known, but not natural examples in the vein of the determinant. We give here several variants of natural complete polynomials for VP, based on the notion of graph homomorphism polynomials.