Next

__
TR21-111
| 19th July 2021
__

Aniruddha Biswas, Palash Sarkar#### Influence of a Set of Variables on a Boolean Function

__
TR21-110
| 22nd July 2021
__

Jaroslaw Blasiok, Peter Ivanov, Yaonan Jin, Chin Ho Lee, Rocco Servedio, Emanuele Viola#### Fourier growth of structured $\mathbb{F}_2$-polynomials and applications

__
TR21-109
| 20th July 2021
__

Sravanthi Chede, Anil Shukla#### QRAT Polynomially Simulates Merge Resolution.

Next

Aniruddha Biswas, Palash Sarkar

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

Jaroslaw Blasiok, Peter Ivanov, Yaonan Jin, Chin Ho Lee, Rocco Servedio, Emanuele Viola

We analyze the Fourier growth, i.e. the $L_1$ Fourier weight at level $k$ (denoted $L_{1,k}$), of various well-studied classes of "structured" $\mathbb{F}_2$-polynomials. This study is motivated by applications in pseudorandomness, in particular recent results and conjectures due to [CHHL19,CHLT19,CGLSS20] which show that upper bounds on Fourier growth (even at ... more >>>

Sravanthi Chede, Anil Shukla

Merge Resolution (MRes [Beyersdorff et al. J. Autom. Reason.'2021] ) is a refutational proof system for quantified Boolean formulas (QBF). Each line of MRes consists of clauses with only existential literals, together with information of countermodels stored as merge maps. As a result, MRes has strategy extraction by design. The ... more >>>

Next