Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Fourier analysis of Boolean functions:
TR06-065 | 24th May 2006
Jan Arpe, RĂ¼diger Reischuk

When Does Greedy Learning of Relevant Features Succeed? --- A Fourier-based Characterization ---

Detecting the relevant attributes of an unknown target concept
is an important and well studied problem in algorithmic learning.
Simple greedy strategies have been proposed that seem to perform reasonably
well in practice if a sufficiently large random subset of examples of the target
concept is provided.

Introducing a ... more >>>

TR11-146 | 1st November 2011
Bireswar Das, Manjish Pal, Vijay Visavaliya

The Entropy Influence Conjecture Revisited

In this paper, we prove that most of the boolean functions, $f : \{-1,1\}^n \rightarrow \{-1,1\}$
satisfy the Fourier Entropy Influence (FEI) Conjecture due to Friedgut and Kalai (Proc. AMS'96)\cite{FG96}. The conjecture says that the Entropy of a boolean function is at most a constant times the Influence of ... more >>>

TR14-088 | 13th July 2014
Swagato Sanyal

Sub-linear Upper Bounds on Fourier dimension of Boolean Functions in terms of Fourier sparsity

Revisions: 1 , Comments: 1

We prove that the Fourier dimension of any Boolean function with
Fourier sparsity $s$ is at most $O\left(s^{2/3}\right)$. Our proof
method yields an improved bound of $\widetilde{O}(\sqrt{s})$
assuming a conjecture of Tsang~\etal~\cite{tsang}, that for every
Boolean function of sparsity $s$ there is an affine subspace of
more >>>

TR17-147 | 3rd October 2017
Venkatesan Guruswami, Rishi Saket

Hardness of Rainbow Coloring Hypergraphs

A hypergraph is $k$-rainbow colorable if there exists a vertex coloring using $k$ colors such that each hyperedge has all the $k$ colors. Unlike usual hypergraph coloring, rainbow coloring becomes harder as the number of colors increases. This work studies the rainbow colorability of hypergraphs which are guaranteed to be ... more >>>

TR20-058 | 24th April 2020
Shafi Goldwasser, Guy Rothblum, Jonathan Shafer, Amir Yehudayoff

Interactive Proofs for Verifying Machine Learning

We consider the following question: using a source of labeled data and interaction with an untrusted prover, what is the complexity of verifying that a given hypothesis is "approximately correct"? We study interactive proof systems for PAC verification, where a verifier that interacts with a prover is required to accept ... more >>>

ISSN 1433-8092 | Imprint