Meera Sitharam

We develop an analytic framework based on

linear approximation and point out how a number of complexity

related questions --

on circuit and communication

complexity lower bounds, as well as

pseudorandomness, learnability, and general combinatorics

of Boolean functions --

fit neatly into this framework. ...
more >>>

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

tatsuie tsukiji

This paper aims to derandomize the following problems in the smoothed analysis of Spielman and Teng. Learn Disjunctive Normal Form (DNF), invert Fourier Transforms (FT), and verify small circuits' unsatisfiability. Learning algorithms must predict a future observation from the only $m$ i.i.d. samples of a fixed but unknown joint-distribution $P(G(x),y)$ ... more >>>

Aniruddha Biswas, Palash Sarkar

We describe a new construction of Boolean functions. A specific instance of our construction provides a 30-variable Boolean function having min-entropy/influence ratio to be 128/45 ? 2.8444 which is presently the highest known value of this ratio that is achieved by any Boolean function. Correspondingly, 128/45 is also presently the ... more >>>