Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > RESILIENT FUNCTIONS:
Reports tagged with resilient functions:
TR15-119 | 23rd July 2015

#### Explicit Two-Source Extractors and Resilient Functions

Revisions: 5

We explicitly construct an extractor for two independent sources on $n$ bits, each with min-entropy at least $\log^C n$ for a large enough constant $C$. Our extractor outputs one bit and has error $n^{-\Omega(1)}$. The best previous extractor, by Bourgain [B2], required each source to have min-entropy $.499n$.

A key ... more >>>

TR15-144 | 1st September 2015
Raghu Meka

#### Explicit resilient functions matching Ajtai-Linial

Revisions: 1

A Boolean function on n variables is q-resilient if for any subset of at most q variables, the function is very likely to be determined by a uniformly random assignment to the remaining n-q variables; in other words, no coalition of at most q variables has significant influence on the ... more >>>

TR18-066 | 8th April 2018
Avraham Ben-Aroya, Gil Cohen, Dean Doron, Amnon Ta-Shma

In their seminal work, Chattopadhyay and Zuckerman (STOC'16) constructed a two-source extractor with error $\varepsilon$ for $n$-bit sources having min-entropy $poly\log(n/\varepsilon)$. Unfortunately, the construction running-time is $poly(n/\varepsilon)$, which means that with polynomial-time constructions, only polynomially-large errors are possible. Our main result is a $poly(n,\log(1/\varepsilon))$-time computable two-source condenser. For any $k ... more >>> TR19-145 | 31st October 2019 Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, Shachar Lovett, David Zuckerman #### XOR Lemmas for Resilient Functions Against Polynomials A major challenge in complexity theory is to explicitly construct functions that have small correlation with low-degree polynomials over$F_2$. We introduce a new technique to prove such correlation bounds with$F_2\$ polynomials. Using this technique, we bound the correlation of an XOR of Majorities with constant degree polynomials. In ... more >>>

TR21-111 | 19th July 2021
Aniruddha Biswas, Palash Sarkar

#### Influence of a Set of Variables on a Boolean Function

The influence of a set of variables on a Boolean function has three separate definitions in the literature, the first due to Ben-Or and Linial (1989), the second due to Fischer et al. (2002) and Blais (2009) and the third due to Tal (2017). The goal of the present work ... more >>>

ISSN 1433-8092 | Imprint