Nisan and Szegedy (CC 1994) showed that any Boolean function f:\{0,1\}^n\to\{0,1\} that depends on all its input variables, when represented as a real-valued multivariate polynomial P(x_1,\ldots,x_n), has degree at least \log n - O(\log \log n). This was improved to a tight (\log n - O(1)) bound by Chiarelli, Hatami ... more >>>

The probabilistic degree of a Boolean function f:\{0,1\}^n\rightarrow \{0,1\} is defined to be the smallest d such that there is a random polynomial \mathbf{P} of degree at most d that agrees with f at each point with high probability. Introduced by Razborov (1987), upper and lower bounds on probabilistic degrees ... more >>>

In a recent paper, Kim and Kopparty (Theory of Computing, 2017) gave a deterministic algorithm for the unique decoding problem for polynomials of bounded total degree over a general grid S_1\times\cdots \times S_m. We show that their algorithm can be adapted to solve the unique decoding problem for the general ... more >>>

The \delta-Coin Problem is the computational problem of distinguishing between coins that are heads with probability (1+\delta)/2 or (1-\delta)/2, where \delta is a parameter that is going to 0. We study the complexity of this problem in the model of constant-depth Boolean circuits and prove the following results.

1. Upper ... more >>>