Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Analysis of Boolean Functions:
TR09-144 | 24th December 2009
Prahladh Harsha, Adam Klivans, Raghu Meka

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
Adam Klivans, Pravesh Kothari

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

Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy

Revisions: 1

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
Irit Dinur, Yotam Dikstein, Yuval Filmus, Prahladh Harsha

Boolean function analysis on high-dimensional expanders

Revisions: 1

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 >>>

ISSN 1433-8092 | Imprint