Jan Arpe, RĂ¼diger Reischuk

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

Bireswar Das, Manjish Pal, Vijay Visavaliya

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

Swagato Sanyal

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

Venkatesan Guruswami, Rishi Saket

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

Shafi Goldwasser, Guy Rothblum, Jonathan Shafer, Amir Yehudayoff

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

Nikhil Mande, Swagato Sanyal

We study parity decision trees for Boolean functions. The motivation of our study is the log-rank conjecture for XOR functions and its connection to Fourier analysis and parity decision tree complexity. Our contributions are as follows. Let $f : \mathbb{F}_2^n \to \{-1, 1\}$ be a Boolean function with Fourier support ... more >>>

Eshan Chattopadhyay, Jason Gaitonde, Abhishek Shetty

In recent work by Chattopadhyay et al.[CHHL19,CHLT19], the authors exhibit a simple and flexible construction of pseudorandom generators for classes of Boolean functions that satisfy $L_1$ Fourier bounds. [CHHL19] show that if a class satisfies such tail bounds at all levels, this implies a PRG whose seed length depends on ... more >>>

Alexander A. Sherstov, Andrey Storozhenko, Pei Wu

We prove that for every decision tree, the absolute values of the Fourier coefficients of given order $\ell\geq1$ sum to at most $c^{\ell}\sqrt{{d\choose\ell}(1+\log n)^{\ell-1}},$ where $n$ is the number of variables, $d$ is the tree depth, and $c>0$ is an absolute constant. This bound is essentially tight and settles a ... more >>>

Gil Cohen, Noam Peri, Amnon Ta-Shma

In this work we ask the following basic question: assume the vertices of an expander graph are labelled by $0,1$. What "test" functions $f : \{ 0,1\}^t \to \{0,1\}$ cannot distinguish $t$ independent samples from those obtained by a random walk? The expander hitting property due to Ajtai, Komlos and ... more >>>

Uma Girish, Avishay Tal, Kewen Wu

We prove that for every parity decision tree of depth $d$ on $n$ variables, the sum of absolute values of Fourier coefficients at level $\ell$ is at most $d^{\ell/2} \cdot O(\ell \cdot \log(n))^\ell$.

Our result is nearly tight for small values of $\ell$ and extends a previous Fourier bound ...
more >>>