Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > ANALYSIS OF BOOLEAN FUNCTIONS:
Reports tagged with Analysis of Boolean Functions:
TR09-144 | 24th December 2009

#### An Invariance Principle for Polytopes

Let $X$ be randomly chosen from $\{-1,1\}^n$, and let $Y$ be randomly
chosen from the standard spherical Gaussian on $\R^n$. For any (possibly unbounded) polytope $P$
formed by the intersection of $k$ halfspaces, we prove that
\left|\Pr\left[X \in P\right] - \Pr\left[Y \in P\right]\right| \leq \log^{8/5}k ... more >>>

TR13-049 | 1st April 2013
Amir Shpilka, Ben Lee Volk, Avishay Tal

#### On the Structure of Boolean Functions with Small Spectral Norm

Revisions: 1

In this paper we prove results regarding Boolean functions with small spectral norm (the spectral norm of $f$ is $\|\hat{f}\|_1=\sum_{\alpha}|\hat{f}(\alpha)|$). Specifically, we prove the following results for functions $f:\{0,1\}^n\to \{0,1\}$ with $\|\hat{f}\|_1=A$.

1. There is a subspace $V$ of co-dimension at most $A^2$ such that $f|_V$ is constant.

2. ... more >>>

TR14-063 | 23rd April 2014

#### Embedding Hard Learning Problems into Gaussian Space

We give the first representation-independent hardness result for agnostically learning halfspaces with respect to the Gaussian distribution. We reduce from the problem of learning sparse parities with noise with respect to the uniform distribution on the hypercube (sparse LPN), a notoriously hard problem in computer science and show that ... more >>>

TR16-029 | 7th March 2016
Joshua Brakensiek, Venkatesan Guruswami

#### New hardness results for graph and hypergraph colorings

Finding a proper coloring of a $t$-colorable graph $G$ with $t$ colors is a classic NP-hard problem when $t\ge 3$. In this work, we investigate the approximate coloring problem in which the objective is to find a proper $c$-coloring of $G$ where $c \ge t$. We show that for all ... more >>>

TR16-183 | 16th November 2016
Joshua Brakensiek, Venkatesan Guruswami

Revisions: 2

A classic result due to Schaefer (1978) classifies all constraint satisfaction problems (CSPs) over the Boolean domain as being either in $\mathsf{P}$ or NP-hard. This paper considers a promise-problem variant of CSPs called PCSPs. A PCSP over a finite set of pairs of constraints $\Gamma$ consists of a pair $(\Psi_P, ... more >>> TR17-180 | 26th November 2017 Irit Dinur, Yuval Filmus, Prahladh Harsha #### Low degree almost Boolean functions are sparse juntas Nisan and Szegedy showed that low degree Boolean functions are juntas. Kindler and Safra showed that low degree functions which are *almost* Boolean are close to juntas. Their result holds with respect to$\mu_p$for every *constant*$p$. When$p$is allowed to be very small, new phenomena emerge. ... more >>> TR18-075 | 23rd April 2018 Yotam Dikstein, Irit Dinur, Yuval Filmus, Prahladh Harsha #### Boolean function analysis on high-dimensional expanders Revisions: 2 We initiate the study of Boolean function analysis on high-dimensional expanders. We describe an analog of the Fourier expansion and of the Fourier levels on simplicial complexes, and generalize the FKN theorem to high-dimensional expanders. Our results demonstrate that a high-dimensional expanding complex X can sometimes serve as a sparse ... more >>> TR18-167 | 25th September 2018 Srinivasan Arunachalam, Sourav Chakraborty, Michal Koucky, Nitin Saurabh, Ronald de Wolf #### Improved bounds on Fourier entropy and Min-entropy Given a Boolean function$f: \{-1,1\}^n\rightarrow \{-1,1\}$, define the Fourier distribution to be the distribution on subsets of$[n]$, where each$S\subseteq [n]$is sampled with probability$\widehat{f}(S)^2$. The Fourier Entropy-Influence (FEI) conjecture of Friedgut and Kalai [FK96] seeks to relate two fundamental measures associated with the Fourier distribution: does ... more >>> TR18-176 | 26th October 2018 Arkadev Chattopadhyay, Nikhil Mande, Suhail Sherif #### The Log-Approximate-Rank Conjecture is False We construct a simple and total XOR function$F$on$2n$variables that has only$O(\sqrt{n})$spectral norm,$O(n^2)$approximate rank and$n^{O(\log n)}$approximate nonnegative rank. We show it has polynomially large randomized bounded-error communication complexity of$\Omega(\sqrt{n})$. This yields the first exponential gap between the logarithm of the ... more >>> TR19-029 | 20th February 2019 Yuval Filmus, Lianna Hambardzumyan, Hamed Hatami, Pooya Hatami, David Zuckerman #### Biasing Boolean Functions and Collective Coin-Flipping Protocols over Arbitrary Product Distributions The seminal result of Kahn, Kalai and Linial shows that a coalition of$O(\frac{n}{\log n})$players can bias the outcome of *any* Boolean function$\{0,1\}^n \to \{0,1\}$with respect to the uniform measure. We extend their result to arbitrary product measures on$\{0,1\}^n\$, by combining their argument with a completely ... more >>>

ISSN 1433-8092 | Imprint