Exact and point-wise approximating representations of Boolean functions by real polynomials have been of great interest in the theory of computing. We focus on the study of sparsity of such representations. Our results include the following: First, we show that for every total Boolean function, its exact and approximate sparsity in the De Morgan basis are polynomially related to each other in the log scale, ignoring poly-log(n) factors. This answers an open question posed by Knop, Lovett, McGuire and Yuan (STOC 2021). It builds on and is analogous to the seminal result of Nisan and Szegedy (Computational Complexity 1994) who proved the same for degree and approximate degree. Second, we consider more powerful representations using generalized monomials, where each monomial is an indicator of a sub-cube. There are 3n such monomials, where n is the number of variables. We prove that even for these representations, the sparsity and approximate sparsity of total Boolean functions remain polynomially related to each other in the log scale, ignoring poly-log(n) factors. Third, we show that for every total Boolean function f, the log of its De Morgan sparsity characterizes up to polynomial loss and ignoring poly-log(n) factors, the quantum and classical 2-party bounded-error communication complexity of f ∘ EQ4, where EQ4 is Equality of two 2-bit strings, one held by Alice and the other by Bob. As a consequence, we show that bounded-error quantum protocols cannot exhibit super-polynomial cost advantage over their classical counterparts, for computing such functions.

We relate various complexity measures like sensitivity, block sensitivity, certificate complexity for multi-output functions to the query complexities of such functions. Using these relations, we show that the deterministic query complexity of total search problems is at most the third power of its pseudo-deterministic query complexity. Previously, a fourth-power relation was shown by Goldreich, Goldwasser and Ron (ITCS'13). Using our proof along with a decision-tree manipulation technique, we give a simple and self-contained proof that the $$\text{SearchCNF}$$ problem on random $$\text{k}$$ -CNF has pseudo-deterministic query complexity $$\Omega(n^{1/3})$$ ; a lower bound of $$\Omega(\sqrt{n})$$ is known, due to Goldwasser, Impagliazzo, Pitassi, and Santhanam (CCC'21), but via a significantly more complex proof. We improve the known separation between pseudo-deterministic and randomized decision tree size for total search problems in two ways: (1) We exhibit an $$\text{exp}(\widetilde{\Omega}(n^{1/4}))$$ separation for the $$\text{SearchCNF}$$ relation for random $$k$$ -CNFs. This seems to be the first exponential lower bound on the pseudo-deterministic size complexity of $$\text{SearchCNF}$$ associated with random $$k$$ -CNFs. (2) We exhibit an $${\text{exp}(\Omega(n))}$$ separation for the $$\text{ApproxHW}$$ relation. The previous best known separation for any relation was $${\text{exp}(\Omega(n^{1/2}))}$$ . We also separate pseudo-determinism from randomness in $$\text{AND}$$ and $$\text{CONJ}$$ decision trees, and determinism from pseudo-determinism in $$\text{Parity}$$ decision trees. Finally, for a hypercube colouring problem, that was introduced by Goldwasswer et al. to analyze the pseudo-deterministic complexity of a complete problem in $$\text{TFNPdt}$$ , we prove that either the monotone block-sensitivity or the anti-monotone block sensitivity is $${\Omega(n^{1/3})}$$ ; Goldwasser et al. showed an $${\Omega(n^{1/2})}$$ bound for general block-sensitivity.

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.

In the decision tree computation model for Boolean functions , the depth corresponds to query complexity, and the size corresponds to storage space. The depth measure is the most well-studied one, and is known to be polynomially related to several non-computational complexity measures of functions such as certificate complexity. The size measure is also studied, but to a lesser extent. Another decision tree measure that has received very little attention is the minimal rank of the decision tree , first introduced by Ehrenfeucht and Haussler in 1989. This measure is closely related to the logarithm of the size, but is not polynomially related to depth, and hence it can reveal additional information about the complexity of a function. It is characterised by the value of a Prover-Delayer game first proposed by Pudlák and Impagliazzo in the context of tree-like resolution proofs. In this paper we study this measure further. We obtain an upper bound on depth in terms of rank and Fourier sparsity . We obtain upper and lower bounds on rank in terms of (variants of) certificate complexity. We also obtain upper and lower bounds on the rank for composed functions in terms of the depth of the outer function and the rank of the inner function. This allows us to easily recover known asympotical lower bounds on logarithm of the size for Iterated AND-OR and Iterated 3-bit Majority. We compute the rank exactly for several natural functions and use them to show that all the bounds we have obtained are tight. We also show that rank in the simple decision tree model can be used to bound query complexity, or depth, in the more general conjunctive decision tree model. Finally, we improve upon the known size lower bound for the Tribes function and conclude that in the size-rank relationship for decision trees, obtained by Ehrenfeucht and Haussler, the upper bound for Tribes is asymptotically tight.

PCA with Outliers is the fundamental problem of identifying an underlying low-dimensional subspace in a data set corrupted with outliers. A large body of work is devoted to the information-theoretic aspects of this problem. However, from the computational perspective, its complexity is still not well-understood. We study this problem from the perspective of parameterized complexity by investigating how parameters like the dimension of the data, the subspace dimension, the number of outliers and their structure, and approximation error, influence the computational complexity of the problem. Our algorithmic methods are based on techniques of randomized linear algebra and algebraic geometry.

Over the last ten years, tremendous speedups for problems in randomized numerical linear algebra such as low rank approximation and regression have been made possible via the technique of randomized data dimensionality reduction, also known as sketching. In theory, such algorithms have led to optimal input sparsity time algorithms for a wide array of problems. While several scattered implementations of such methods exist, the goal of this work is to provide a comprehensive comparison of such methods to alternative approaches. We investigate least squares regression, iteratively reweighted least squares, logistic regression, robust regression with Huber and Bisquare loss functions, leverage score computation, Frobenius norm low rank approximation, and entrywise $\ell_1$-low rank approximation. We give various implementation techniques to speed up several of these algorithms, and the resulting implementations demonstrate the tradeoffs of such techniques in practice.